論文の概要: AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
- arxiv url: http://arxiv.org/abs/2610.36321v1
- Date: Mon, 26 Oct 2026 21:49:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-29 04:15:49.202843
- Title: AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
- Title(参考訳): AHEAD: 大規模線形プログラミングのための適応型ニューラルアクセラレーション
- Abstract要約: AHEADは、一階線形プログラミング解決器のステップサイズを予測するアクセラレータである。
その重み付き予測器は、コンパクトなソルバ統計を読み出し、原始と二重のステップサイズを再スケールする。
AHEADは、グロビのファーストオーダーソルバをコールドスタートからエンド・ツー・エンドのスピードアップで6.5ドル-11.6タイムで達成した。
- 参考スコア(独自算出の注目度): 24.32992753372339
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Large-scale linear programs with millions of variables and constraints strain time and memory budgets. First-order methods such as the primal-dual hybrid gradient scale to this regime because they avoid matrix factorizations, but they require many iterations. Learned accelerators can reduce these iterations, yet fewer iterations do not guarantee a shorter solve. Learning inference also takes time, and running the accelerator longer trades solver time for inference time. Existing unrolled accelerators handle this trade-off poorly: each layer processes every variable and constraint, the predicted iterates still need solver refinement, and every instance runs the same layers. We therefore ask: What neural accelerator design achieves end-to-end speedups on large-scale linear programs across sizes and target accuracies? We introduce AHEAD, an accelerator that predicts step sizes for first-order linear programming solvers while keeping their update rules. Its weight-shared predictor reads compact solver statistics and rescales the primal and dual step sizes, so each warm-start iteration stays inexpensive and a short warm-start phase hands the solver a warm start. A learned handoff policy sets the number of warm-start iterations for each instance and target accuracy, after which the solver finishes under its own termination criterion. On packing linear programs with up to $10^7$ variables, AHEAD achieves $6.5$--$11.6\times$ end-to-end speedups over Gurobi's first-order solver from a cold start, including on instances of unseen sizes and distributions. The gains extend to PageRank linear programs and hold across difficulty levels and target accuracies.
- Abstract(参考訳): 数百万の変数と制約を持つ大規模線形プログラムは、時間とメモリの予算を歪ませる。
原始-双対ハイブリッド勾配のような一階法は、行列分解を避けるため、この状態にスケールするが、多くの反復を必要とする。
学習したアクセラレーターはこれらのイテレーションを減らすことができるが、短い解決が保証されないイテレーションは少ない。
推論の学習にも時間がかかり、加速器の実行時間は推論時間よりも長い。
各レイヤはすべての変数と制約を処理し、予測されたイテレーションは依然として解決器の洗練を必要とし、すべてのインスタンスは同じレイヤを実行します。
そこで我々は, 大規模リニアプログラムの大規模化と目標精度におけるエンドツーエンドのスピードアップを実現する,ニューラルアクセラレータ設計とは何か,と問う。
AHEADは、更新ルールを維持しながら、一階線形プログラミングソルバのステップサイズを予測するアクセラレータである。
ウェイトシェアの予測器は、コンパクトなソルバ統計を読み出し、原始と二重のステップサイズを再スケールするので、各ウォームスタートイテレーションは安価で、短いウォームスタートフェーズはソルバにウォームスタートを与える。
学習されたハンドオフポリシは、各インスタンスに対するウォームスタートイテレーションの数と目標精度を設定し、その後、ソルバは独自の終了基準の下で終了する。
最大$10^7$の変数を持つ線形プログラムのパッケージングにおいて、AHEADはGurobiの1次解法よりも6.5$-$11.6\times$エンドツーエンドのスピードアップを達成した。
ゲインはPageRankリニアプログラムに拡張され、難易度と目標精度を越えて保持される。
関連論文リスト
- Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming [17.042522687595937]
我々は、強化学習を用いて連続アルゴリズムパラメータを共同学習し、再起動決定を個別に行うGALLOPを紹介した。
GALLOPは、$1.9$-$5.6$の要素でカウントを減らし、MPAXよりもアルゴリズムウォールタイムで最大$16.0timesのスピードアップを実現している。
論文 参考訳(メタデータ) (2026-10-01T12:15:39Z) - HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation [56.14416807766864]
同型暗号化により、サーバは暗号化されたユーザープロンプト上で言語モデルを直接実行することができる。
既存のアプローチでは、各サイトのエラー許容度を調整するのではなく、モデル全体のイテレーションカウントを均一に修正する。
非線形反復回数を学習可能にする微調整法であるHAT(Hymomorphic Encryption-Aware Training)を導入する。
論文 参考訳(メタデータ) (2026-09-01T18:02:02Z) - INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
本稿では,学習した補正を支配方程式に統合する間接ニューラルコレクタ(mathrmINC$)を提案する。
$mathrmINC$は、$t-1 + L$の順番でエラー増幅を減らし、$t$はタイムステップ、$L$はリプシッツ定数である。
大規模なベンチマークで$mathrmINC$をテストし、1Dカオスシステムから3D乱流まで、多くの異なる解法、神経バックボーン、テストケースをカバーした。
論文 参考訳(メタデータ) (2025-11-16T20:14:28Z) - Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes [31.305425519412758]
本稿では,線形系解法を用いる反復法に着目し,限界次数勾配を推定する。
本稿では,解決者間で適用可能な3つの重要な改善点について論じる。
これらのテクニックは、トレランスの解決時に最大7,2倍のスピードアップを提供し、停止時に平均残留ノルムを最大7,7倍まで下げる。
論文 参考訳(メタデータ) (2024-05-28T16:58:37Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳(メタデータ) (2023-12-19T02:27:22Z) - Optimal Linear Decay Learning Rate Schedules and Further Refinements [46.79573408189601]
実際に使用される学習率のスケジュールは、理論によって推奨されるものとはほとんど似ていない。
我々はこの理論と実践的ギャップの多くを閉じ、その結果、新しい問題適応型学習率スケジュールを導き出すことができる。
論文 参考訳(メタデータ) (2023-10-11T19:16:35Z) - Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。
本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。
本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。
第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
論文 参考訳(メタデータ) (2022-09-15T21:32:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。