Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization

• URL: http://arxiv.org/abs/2605.20074v1
• Date: Tue, 19 May 2026 16:28:18 GMT
• Title: Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization
• Abstract summary: Distillation transfers knowledge from a large model trained on broad data to a smaller, more efficient model suitable for deployment.<n>We show that the distillation problem can be solved efficiently in the complexity parameters of the DP transition function, represented as a DT.
• Score: 11.645059926678082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Model Specific Task Similarity for Vision Language Model Selection via Layer Conductance [92.72779885657373]
  We propose a framework that grounds model selection in the internal functional dynamics of the visual encoder.<n>Our approach represents each task via layer wise conductance and derives a target-conditioned block importance distribution through entropy regularized alignment.<n>Building on this, we introduce Directional Conductance Divergence (DCD), an asymmetric metric that quantifies how effectively a source task covers the target's salient functional blocks.
  arXiv  Detail & Related papers  (2026-02-01T17:29:43Z)
• Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning [51.20606796019663]
  We propose ALVGL, a novel and general enhancement to the differentiable causal discovery pipeline.<n>ALVGL employs a sparse and low-rank decomposition to learn the precision matrix of the data.<n>We show that ALVGL not only achieves state-of-the-art accuracy but also significantly improves optimization efficiency.
  arXiv  Detail & Related papers  (2026-01-09T02:18:59Z)
• Fast AI Model Splitting over Edge Networks [20.38061058476494]
  Complex AI model architectures pose high computational complexity to obtain the optimal model splitting.<n>We propose a fast DAG-based model splitting algorithm, which restructures the DAG to enable the optimal model splitting identification.<n>Considering AI models with block structures, we propose a block-wise model splitting algorithm to reduce computational complexity.
  arXiv  Detail & Related papers  (2025-06-23T07:14:04Z)
• Dataset Distillation as Pushforward Optimal Quantization [2.5892916589735457]
  We propose a synthetic training set that achieves similar performance to training on real data, with orders of magnitude less computational requirements.<n>In particular, we link existing disentangled dataset distillation methods to the classical optimal quantization and Wasserstein barycenter problems.<n>We achieve better performance and inter-model generalization on the ImageNet-1K dataset with trivial additional computation, and SOTA performance in higher image-per-class settings.
  arXiv  Detail & Related papers  (2025-01-13T20:41:52Z)
• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  We propose a novel problem of distilling an unlabeled dataset into a set of small synthetic samples for efficient self-supervised learning (SSL) We first prove that a gradient of synthetic samples with respect to a SSL objective in naive bilevel optimization is textitbiased due to randomness originating from data augmentations or masking. We empirically validate the effectiveness of our method on various applications involving transfer learning.
  arXiv  Detail & Related papers  (2023-10-10T10:48:52Z)
• Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm [0.9999629695552196]
  We introduce a two-phase algorithm to estimate the hub graphical models.<n>The proposed algorithm first generates a good initial point via a dual alternating direction method of multipliers (ADMM), and then warm starts a semismooth Newton (SSN) based augmented Lagrangian method (ALM)<n> Comprehensive experiments on both synthetic data and real data show that it obviously outperforms the existing state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-08-17T08:24:28Z)
• Understanding the Distillation Process from Deep Generative Models to Tractable Probabilistic Circuits [30.663322946413285]
  We theoretically and empirically discover that the performance of a PC can exceed that of its teacher model. In particular, on ImageNet32, PCs achieve 4.06 bits-per-dimension, which is only 0.34 behind variational diffusion models.
  arXiv  Detail & Related papers  (2023-02-16T04:52:46Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• A Hybrid Framework for Sequential Data Prediction with End-to-End Optimization [0.0]
  We investigate nonlinear prediction in an online setting and introduce a hybrid model that effectively mitigates hand-designed features and manual model selection issues. We employ a recurrent neural network (LSTM) for adaptive feature extraction from sequential data and a gradient boosting machinery (soft GBDT) for effective supervised regression. We demonstrate the learning behavior of our algorithm on synthetic data and the significant performance improvements over the conventional methods over various real life datasets.
  arXiv  Detail & Related papers  (2022-03-25T17:13:08Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Scalable Approximate Inference and Some Applications [2.6541211006790983]
  In this thesis, we propose a new framework for approximate inference. Our proposed four algorithms are motivated by the recent computational progress of Stein's method. Results on simulated and real datasets indicate the statistical efficiency and wide applicability of our algorithm.
  arXiv  Detail & Related papers  (2020-03-07T04:33:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.