論文の概要: Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

• arxiv url: http://arxiv.org/abs/2605.09382v1
• Date: Sun, 10 May 2026 07:15:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.221332
• Title: Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
• Title（参考訳）: ニューラルデュアルワームスターを用いた学習拡張スケーラブル線形割当て問題最適化
• Authors: Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed, Jose Yallouz, Nir Weinberger,
• Abstract要約: 最適性と最悪の保証を維持しつつ、正確な代入解決を高速化する学習強化フレームワークを提案する。 グラフベースのモデルのメモリボトルネックを$mathcalO(N2)$で回避する軽量な行独立アーキテクチャであるRowDualNetを紹介します。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 線形割当問題 (LAP) は、コンピュータビジョンからロジスティクスに至るまでのアプリケーションに対する基本的な組合せ最適化課題である。 ハンガリーやJonker-Volgenant (LAPJV)アルゴリズムのような古典的な正確な解法は最適性を保証するが、その立方体時間複雑性$\mathcal{O}(N^{3})$は大規模インスタンスのボトルネックとなる。 最近の学習ベースのアプローチは、これらのソルバをニューラルネットワークに置き換えることを目的としている。 最適性と最悪の保証を維持しつつ、正確な代入解決を高速化する学習強化フレームワークを提案する。 本手法は,古典的解法を温めるために2変数を予測し,学習したアドバイスが信頼できない場合の漸近的実行時劣化を防止するフォールバックを提案する。 グラフベースモデルのメモリボトルネックを$\mathcal{O}(N^{2})$で回避し,大規模(N=16{,}384$)でニューラルウォームスタートを可能にする軽量な行独立アーキテクチャであるRowDualNetを紹介した。 実用性は、LP双対性(すなわちMin-Trick)に基づく建設的なメカニズムによって確保され、コストのかかる反復射影を排除できる。 実世界追跡(MOT)と輸送(LPT)のデータセットでそれぞれ1.25{\times}$と1.5{\times}$の改善に加えて、LAPJVの探索の労力を削減し、難易度の高い合成分布のスピードアップを2ドル以上達成しています。

関連論文リスト

• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasonerは、トークンログに対する差別化可能な最適化をデコードループに統合する反復生成フレームワークである。 $nabla$-Reasonerは、挑戦的な数学的推論ベンチマークで20%以上の精度の向上を実現している。
  論文  参考訳（メタデータ） (2026-03-05T08:42:54Z)
• Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers [5.227723778971733]
  凸制約の満足度を確保するために,ネットワークの出力層を導入する。 我々のアプローチである$Pi$netは、フォワードパスの高速かつ信頼性の高い投影に演算子分割を利用する。
  論文  参考訳（メタデータ） (2025-08-14T09:32:09Z)
• VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence [6.574641780732972]
  大規模非問題はディープラーニングでは一般的である。 ファーストオーダー(FO)は今日のベースラインとして機能する。 ZOアルゴリズムは計算量とメモリコストを減らす。 VAMOは、より少ない動的メモリ要求でこれらのゲインを達成する。
  論文  参考訳（メタデータ） (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]
  本稿では,2層最大化ネットワークとReLUネットワークの実証的リスク問題に対する,世界初となる最適アルゴリズムを提案する。 提案アルゴリズムは、小規模データセットに対して、証明可能な正確な解を提供する。 より大きなデータセットを扱うために,データサイズを管理可能なスケールに縮小する新しいコアセット選択手法を提案する。
  論文  参考訳（メタデータ） (2025-05-09T02:34:54Z)
• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization [6.896308995955336]
  グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。 本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
  論文  参考訳（メタデータ） (2023-12-06T01:16:10Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [67.66904892192794]
  我々は、強化学習のための新しいアルゴリズム、MQL-UCBを用いたモノトニックQ-Learningを提案する。 MQL-UCBは、$tildeO(dsqrtHK)$の最小限の後悔を実現する。 本研究は,非線形関数近似を用いたサンプル効率およびデプロイメント効率のよいQ-ラーニングの設計に重点を置いている。
  論文  参考訳（メタデータ） (2023-11-26T08:31:57Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  0-1整数線形プログラムの緩和を解くために,高速でスケーラブルなデータ駆動型手法を提案する。 グラフニューラルネットワーク(GNN)とラグランジュ分解に基づくアルゴリズムであるFastDOGを用いる。
  論文  参考訳（メタデータ） (2022-05-23T21:09:41Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。