論文の概要: Learning Warm Starts for the Simplex Method from Measured Solver Cost

• arxiv url: http://arxiv.org/abs/2610.20892v1
• Date: Wed, 14 Oct 2026 20:19:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.059397
• Title: Learning Warm Starts for the Simplex Method from Measured Solver Cost
• Title（参考訳）: 測定したソルバーコストから単純解法を学習する
• Abstract要約: 強い教師付き基底予測器は、二重単純体の反復の3分の2を除去するが、その時間の3分の1しか除去しない。 良いスタートによって取り除かれたイテレーションは安価になりがちで、最適なベースへの近さはコストによってランク付けされません。 そこで,CostStartを紹介した。これは教師付き予測をベースとして,測定した命令数に基づいて小さなポリシーを訓練する。
• 参考スコア（独自算出の注目度）: 0.06363400715351394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learned warm starts for the simplex method build starting bases using predictions of which variables will be basic at optimality. Prior work has shown that starting bases predicted by graph neural networks can sharply reduce iteration counts, but the time saved may fall well short of the iterations saved. On 25 classes of linear programs (LPs), we find that a strong supervised basis predictor removes two thirds of the dual simplex's iterations but only a third of its time. Two effects explain the gap: the iterations removed by a good start tend to be cheap, and closeness to an optimal basis does not rank starts by cost. We prove that two starts with equal overlap with an optimal basis and equal pivot counts can differ in linear-algebra work by a factor that grows with the square root of the number of rows. Empirically, across the starts of one LP, the pivot count explains 71% of the variance of log solve time, while the CPU instruction count explains 98.5%. We introduce CostStart, which uses supervised prediction for the basis and trains a small policy on measured instruction counts to choose, per LP, how many predicted columns to use, which algorithm and pricing rule to run, and whether to warm-start at all. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time relative to the solver's default start and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.
• Abstract（参考訳）: 学習されたウォームスタートは、最適な変数が基本となる予測を使って、Simplexメソッドの開始ベースを構築するためのものである。 従来の研究によると、グラフニューラルネットワークによって予測されるスタートベースは、イテレーション数を大幅に削減できるが、保存された時間は、保存されたイテレーションのかなり不足する可能性がある。 線形プログラム(LP)の25のクラスでは、強い教師付き基底予測器が2つの単純な反復の3分の2を除去するが、その時間の3分の1しか除去しないことがわかった。 良いスタートによって取り除かれたイテレーションは安価になりがちで、最適なベースへの近さはコストによってランク付けされません。 最適基底と等しいピボット数を持つ2つの始点が、行数の平方根で成長する因子によって線形代数的作業において異なることを証明する。 実証的に、1つのLPの開始時において、ピボットカウントはログ解決時間のばらつきの71%を、CPU命令カウントは98.5%を説明している。 提案するCostStartは,教師付き予測をベースとして,LP毎に測定した命令数に対する小さなポリシ,予測列数,実行すべきアルゴリズムと価格ルール,ウォームスタートの可否を判断する。 LPの4倍のトレーニングサイズを含む未確認のLPでは、CostStartはソルバのデフォルトスタートに対する解決時間をほぼ半減し、同じデータで再トレーニングされた2つのメソッドの1.4倍から2.2倍の速度である。

関連論文リスト

• 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)
• Learned Preconditioning for a Primal-Dual Interior-Point Method [1.7694768544626636]
  内部点法(IPM)は、制約付き最適化において最も広く使われているアルゴリズムの一つである。 pdProjLIP に学習前条件を組み込むスムーズな非線形プログラムのための IPM である pd を導入する。 学習されたイテレーションはHessianの評価を避け、Newton-systemはGPU並列化のために一階演算と座標演算のみを使用する。
  論文  参考訳（メタデータ） (2026-09-28T17:24:54Z)
• WARP: A Benchmark for Primal-Dual Warm-Starting of Interior-Point Solvers [0.3058685580689604]
  成長する仕事の体は、機械学習を使って原始的なウォームスタートのイテレーションを予測し、30-46%の減少を報告している。 これらの報告は不適切な評価基準に当てはまることを示す。 実験により、完全原始二重バリア状態 $(x*, *, z*, *)$ はIPOPTイテレーションを 23 から 3 に減少させる。
  論文  参考訳（メタデータ） (2026-05-07T06:19:16Z)
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。 私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
  論文  参考訳（メタデータ） (2024-02-06T01:29:35Z)
• Optimal Linear Decay Learning Rate Schedules and Further Refinements [46.79573408189601]
  実際に使用される学習率のスケジュールは、理論によって推奨されるものとはほとんど似ていない。 我々はこの理論と実践的ギャップの多くを閉じ、その結果、新しい問題適応型学習率スケジュールを導き出すことができる。
  論文  参考訳（メタデータ） (2023-10-11T19:16:35Z)
• Revisiting a Design Choice in Gradient Temporal Difference Learning [18.326126953667842]
  オフ・ポリシー・ラーニングは、強化学習エージェントが実行されていないポリシーについて反実的に推論することを可能にする。 関数近似とブートストラップを組み合わせると不安定になる可能性がある。 本稿では、$Atop$TDの変種である$A_ttop$TDが、致命的なトライアドの効果的な解であることを示す。
  論文  参考訳（メタデータ） (2023-08-02T14:16:22Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。 この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
  論文  参考訳（メタデータ） (2021-07-27T08:48:01Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)

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

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