論文の概要: Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

• arxiv url: http://arxiv.org/abs/2610.01546v1
• Date: Thu, 01 Oct 2026 12:15:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.107423
• Title: Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
• Title（参考訳）: リニアプログラミングのための強化学習によるPrimal-Dual Hybrid Gradientの高速化
• Abstract要約: 我々は、強化学習を用いて連続アルゴリズムパラメータを共同学習し、再起動決定を個別に行うGALLOPを紹介した。 GALLOPは、$1.9$-$5.6$の要素でカウントを減らし、MPAXよりもアルゴリズムウォールタイムで最大$16.0timesのスピードアップを実現している。
• 参考スコア（独自算出の注目度）: 17.042522687595937
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of $1.9$-$5.6$ and achieves up to a $16.0\times$ speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs $3\times$-$400\times$ larger than the largest training instances, including Transport LPs with $10.24$ million variables.
• Abstract（参考訳）: プリマル・デュアルハイブリッド勾配法 (PDHG) は、GPUフレンドリーな行列ベクトル積とプロジェクションを用いて大規模な線形プログラム(LP)を解くが、実際の性能はアルゴリズムパラメータ、加速度、再起動の調整に依存する。 我々は,強化学習を用いて連続アルゴリズムパラメータを共同学習し,解法を介さずに再起動決定を個別に行うGALLOPを紹介した。 その一般化された加速PDHG更新は、個別の原始外挿と二重外挿、履歴補正、再起動アンカーと独立に調整可能な係数を組み合わせたものである。 我々は、異なる制御群に対して確率比を別々にクリップし、再起動遷移において不活性な加速度制御を除外するグループワイズ近似ポリシー最適化目標を用いて、次元に依存しないフィードバックポリシーを訓練する。 GALLOPを6つのLPファミリーとパブリックアイテム配置ベンチマークで評価した。 6つのファミリーにおける主要な評価設定では、GALLOPは反復回数を1.9$-5.6$で減らし、最大16.0\times$MPAXよりもアルゴリズムウォールタイムの高速化を実現している。 家族1人1人1人1つの政策で、学習されたポリシーは、家族内のLPを3ドル(約3,300円)から400ドル(約4,800円)に減らさずに一般化される。

関連論文リスト

• Rate-Optimal Algorithm for Adversarial Linear CMDPs [8.015940996821541]
  本研究では,Slater の条件を仮定することなく,後悔と累積的制約違反を$widetildemathcalO(sqrtK)$で実現する原始双対アルゴリズムを提案する。 適応二元正則化器は、原始後悔境界における双対重みへの依存をオフセットし、政策混合の必要性を除去する。
  論文  参考訳（メタデータ） (2026-10-01T02:03:07Z)
• Learned Preconditioning for a Primal-Dual Interior-Point Method [1.7694768544626636]
  内部点法(IPM)は、制約付き最適化において最も広く使われているアルゴリズムの一つである。 pdProjLIP に学習前条件を組み込むスムーズな非線形プログラムのための IPM である pd を導入する。 学習されたイテレーションはHessianの評価を避け、Newton-systemはGPU並列化のために一階演算と座標演算のみを使用する。
  論文  参考訳（メタデータ） (2026-09-28T17:24:54Z)
• WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled $LDL^\top$ Factorization [19.701591585846014]
  本稿では、逐次2次プログラミング(SQP)の繰り返しの大規模なバッチを解く際に、GPU上でのスループットを最大化する数値最適化を提案する。 この最適化は、JAX と Warp のモデル予測制御 (MPC) のためのツールボックス WarpMPC で実装されている。 非線形カートポール,四極子,ヒューマノイドロボットベンチマークを用いて,毎秒8,000～25万SQPのスループットを実現した。
  論文  参考訳（メタデータ） (2026-07-13T14:27:47Z)
• Scalable Deep Unfolding of Conic Optimizers [16.022960827366067]
  Deep Openfolding (DU)は、学習可能なコンポーネントを導入し、未学習のイテレーションを通じてそれらをトレーニングすることで、反復を加速します。 COSMOのような完全更新された円錐解法をアンロールすると、学習した円錐解法に先立つ2つの障害が露呈する。 行列のない暗黙差分法で最初の障害に対処し、メモリを$O(n2)$から$O(n)$に減らし、直接分解がメモリを使い果たしたスケールでのバックプロパゲーションを可能にする。
  論文  参考訳（メタデータ） (2026-06-11T18:58:09Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Not All Rollouts are Useful: Down-Sampling Rollouts in LLM Reinforcement Learning [55.15106182268834]
  検証可能な報奨付き強化学習(RLVR)が,大規模言語モデルにおける推論能力向上のための主要なアプローチとして登場した。 ロールアウト生成は恥ずかしく並列であり、メモリライトであるのに対して、ポリシー更新は通信量が多く、メモリ集約的である。 PODS(Policy Optimization with Down-Sampling)を導入し、戦略的に選択されたロールアウトサブセットでのみトレーニングすることで、ポリシー更新からロールアウト生成を分離する。
  論文  参考訳（メタデータ） (2025-04-18T17:49:55Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• DiffPD: Differentiable Projective Dynamics with Contact [65.88720481593118]
  DiffPDは、暗黙の時間積分を持つ効率的な微分可能なソフトボディシミュレータである。 我々はDiffPDの性能を評価し,様々な応用における標準ニュートン法と比較して4～19倍のスピードアップを観測した。
  論文  参考訳（メタデータ） (2021-01-15T00:13:33Z)

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

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