通过算法对齐提升组合优化中的知识蒸馏成功率
Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization
- 用图神经网络匹配动态规划算法结构，实现任务对齐
- 在源模型足够强大时，蒸馏问题可在多项式时间内求解
- 为算法对齐型蒸馏提供理论保证，适合优化部署场景
知识蒸馏将大型模型的知识转移至更小、高效的模型，适用于实际部署。在结构化预测任务中，若目标模型架构与底层问题的算法对齐，则可提升蒸馏效果。本文基于近期关于决策树蒸馏的学习理论分析（Boix-Adsera, 2024），研究组合优化任务下蒸馏成功的条件。聚焦目标模型为图神经网络且其架构与动态规划（DP）算法对齐的情形。假设源模型足够丰富，以线性表示假设（LRH）形式刻画（Elhage et al., 2022; Park et al., 2024），我们证明蒸馏问题可在动态规划转移函数复杂度参数范围内高效求解，该转移函数以决策树形式表示。结果提供了算法对齐范式下的蒸馏成功严格充分条件。
原文摘要 · Abstract (English)
Distillation transfers knowledge from a large model trained on broad data to a smaller, more efficient model suitable for deployment. In structured prediction settings, prior knowledge about the task can guide the choice of a target architecture that is algorithmically aligned with the underlying problem. Building on recent learning-theoretic analyses of decision-tree (DT) distillation (Boix-Adsera, 2024), we study when distillation succeeds for combinatorial optimization tasks. We focus on the case where the target model is a graph neural network whose architecture is aligned with a dynamic programming (DP) algorithm for the task. Assuming that the source model is sufficiently rich, formalized through the linear representation hypothesis (LRH) (Elhage et al., 2022; Park et al., 2024), we show that the distillation problem can be solved efficiently in the complexity parameters of the DP transition function, represented as a DT. Our results provide a rigorous sufficient condition for successful distillation in the flavour of algorithmic alignment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。