Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

• URL: http://arxiv.org/abs/2605.09382v1
• Date: Sun, 10 May 2026 07:15:49 GMT
• Title: Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
• Abstract summary: We propose a learning-augmented framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees.<n>We introduce RowDualNet, a lightweight row-independent architecture that avoids the $mathcalO(N2)$ memory bottleneck of graph-based models.
• Score: 19.540758462427878
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Linear Assignment Problem (LAP) is a fundamental combinatorial optimization task with applications ranging from computer vision to logistics. Classical exact solvers such as the Hungarian and Jonker-Volgenant (LAPJV) algorithms guarantee optimality, but their cubic time complexity $\mathcal{O}(N^{3})$ becomes a bottleneck for large-scale instances. Recent learning-based approaches aim to replace these solvers with neural models, often sacrificing exactness or failing to scale due to memory constraints. We propose a learning-augmented framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees. Our method predicts dual variables to warm-start a classical solver, with a fallback that prevents asymptotic runtime degradation when the learned advice is unreliable. We introduce RowDualNet, a lightweight row-independent architecture that avoids the $\mathcal{O}(N^{2})$ memory bottleneck of graph-based models, enabling neural warm-starting at large scale ($N=16{,}384$). Feasibility is ensured via a constructive mechanism based on LP duality (namely, the Min-Trick), eliminating costly iterative projection. Empirically, our approach reduces the search effort of LAPJV and achieves over $2{\times}$ speedups on challenging synthetic distributions, in addition to improving over $1.25{\times}$ and $1.5{\times}$ on real-world tracking (MOT) and transportation (LPT) datasets, respectively, while strictly maintaining full optimality, effectively yielding a robust zero-shot generalization to real-world tasks.

Related papers

• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) pruning methods operate layer-wise, minimizing the per-layer pruning error on a small dataset to avoid full retraining.<n>Existing methods hence rely on greedy convexs that ignore the weight interactions in the pruning objective.<n>Our method drastically reduces the per-layer pruning error, outperforms strong baselines on state-of-the-art GPT architectures, and remains memory-efficient.
  arXiv  Detail & Related papers  (2025-10-15T16:13:44Z)
• Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers [5.227723778971733]
  We introduce an output layer for networks that ensures satisfaction of convex constraints.<n>Our approach, $Pi$net, leverages operator splitting for rapid and reliable projections in the forward pass.
  arXiv  Detail & Related papers  (2025-08-14T09:32:09Z)
• VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence [6.574641780732972]
  Large-scale non problems are common in deep learning.<n>First-order (FO)s serve as today's baselines.<n>ZO algorithms reduce the size of computation and memory costs.<n>VAMO achieves these gains with smaller dynamic memory requirements.
  arXiv  Detail & Related papers  (2025-05-20T05:31:15Z)
• Deep-ICE: The first globally optimal algorithm for empirical risk minimization of two-layer maxout and ReLU networks [1.7266553199919665]
  This paper introduces the first globally optimal algorithm for the empirical risk problem of two-layer maxout and ReLU networks.<n>The proposed algorithm provides provably exact solutions for small-scale datasets.<n>To handle larger datasets, we introduce a novel coreset selection method that reduces the data size to a manageable scale.
  arXiv  Detail & Related papers  (2025-05-09T02:34:54Z)
• An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem [21.948190231334088]
  We propose DEITSP, a diffusion model with efficient iterations tailored for Traveling Salesman Problems.<n>We introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement.<n>We also design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities.
  arXiv  Detail & Related papers  (2025-01-23T15:47:04Z)
• Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach [32.36073823372713]
  In machine-learning models, the algorithm has to communicate to the data center and sample data for its gradient. This gives rise to the need for a decentralized optimization algorithm that is communication-efficient and minimizes the number of gradient computations. We propose a primal-dual sliding with conditional gradient sliding framework, which is communication-efficient and achieves an $varepsilon$-approximate solution.
  arXiv  Detail & Related papers  (2024-04-03T06:55:59Z)
• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization [6.896308995955336]
  Gradient-based minimax optimal algorithms have promoted the development of continuous optimization and machine learning. In this paper, we open up a new way to design and analyze gradient-based algorithms with direct applications in machine learning.
  arXiv  Detail & Related papers  (2023-12-06T01:16:10Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [67.66904892192794]
  We propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for reinforcement learning.<n>MQL-UCB achieves minimax optimal regret of $tildeO(dsqrtHK)$ when $K$ is sufficiently large and near-optimal policy switching cost.<n>Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.
  arXiv  Detail & Related papers  (2023-11-26T08:31:57Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  We present efficient methods for optimizing dynamic regret and adaptive regret.<n>The proposed algorithms require only one gradient query and one function evaluation at each round.<n>We also study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from $O(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG.
  arXiv  Detail & Related papers  (2022-05-23T21:09:41Z)
• Joint inference and input optimization in equilibrium networks [68.63726855991052]
  deep equilibrium model is a class of models that foregoes traditional network depth and instead computes the output of a network by finding the fixed point of a single nonlinear layer. We show that there is a natural synergy between these two settings. We demonstrate this strategy on various tasks such as training generative models while optimizing over latent codes, training models for inverse problems like denoising and inpainting, adversarial training and gradient based meta-learning.
  arXiv  Detail & Related papers  (2021-11-25T19:59:33Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.