論文の概要: Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

• arxiv url: http://arxiv.org/abs/2609.28263v1
• Date: Wed, 23 Sep 2026 15:23:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:18.086669
• Title: Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
• Title（参考訳）: オンライン線形計画法における資源適応確率勾配
• Abstract要約: 我々は、オンライン線形プログラミングを動機付けるためのリソース適応型プログラミング降下法(RASGD)を開発した。 このアルゴリズムは1つのリクエストと現在のインベントリを使用してリソース価格を更新し、mリソースのO(m)操作と到着時のメモリを必要とする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.
• Abstract（参考訳）: 大規模言語モデル(LLM)の推論とサーチサービスの増大は、オンライン線形プログラミング問題の規模を増大させ、計算効率のよいアルゴリズムを動機付けている。 我々は、確率オンライン線形プログラミングのためのリソース適応確率勾配勾配(RASGD)を開発する。 このアルゴリズムは、リソース価格の更新に1つのリクエストと現在のインベントリを使用し、到着時のmリソースとメモリに対するO(m)操作が必要であり、LPやサンプル平均最適化は不要である。 中心となる考え方は、一階のSGD更新によって解決される現在のリソース価格の論理を表現することであり、それぞれの到着によって2つの目標における残りの発明的許容度が更新される一方、ステップサイズは早期学習のために減少し、その後、在庫調整の速度に一致するように増大する。 標準の非退化条件下では,本アルゴリズムはすべてのサンプルパスで実現可能であり,分布を知っており,制約のない計算を行うポリシであっても,下位境界に一致する実効的な分数的近視最適値に対して,O(\log T)期待の後悔を達成できる。 この分析は、資源水準の変化時に最適な価格を追跡することなく、固定基準価格の周りの曲率を在庫安定に変換する。 数値実験により、RASGDは1次法の計算効率を保ちながら、配列ごとのLP再解法と競合し、試験された1次ベースラインを改善した。 これらの結果から,RASGD は大規模 OLP において高いアロケーション品質を実現するための計算効率の高い手法として確立された。

関連論文リスト

• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  テストタイムの計算スケーリングは、大規模言語モデルのパフォーマンスを向上させるための強力なレバーとなっている。 しかし、これらのテクニックを有限の推論予算の下で展開するには、現在のシステムがほとんど無視する決定が必要である。 我々はこれを制約付き最適化問題(平均計算予算の予測精度を最大化する)として定式化し、2段階のソルベ・テン・ラーンパイプラインで解いた。
  論文  参考訳（メタデータ） (2026-04-16T10:39:22Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expertは、原則化されたリソース割り当てによる精度と効率のトレードオフを最適化する適応的なルーティングフレームワークである。 我々は、MATHの98.2%の精度、HumanityのLast Examの54.8%を含む、強く一貫した利得を示している。
  論文  参考訳（メタデータ） (2026-02-27T05:22:01Z)
• Flow-GRPO: Training Flow Matching Models via Online RL [80.62659379624867]
  本稿では,オンライン政策強化学習をフローマッチングモデルに統合する最初の方法であるFlow-GRPOを提案する。 提案手法では,(1)決定論的正規微分方程式を同値な微分方程式に変換するODE-to-SDE変換と,(2)推論ステップの数を維持しながらトレーニングの段階を短縮するDenoising Reduction戦略の2つの主要な戦略を用いる。
  論文  参考訳（メタデータ） (2025-05-08T17:58:45Z)
• Wait-Less Offline Tuning and Re-solving for Online Decision Making [14.444631755720073]
  LP法と1次LP法の長所を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは、$mathscrO(log (T/f) + sqrtf)$ regretを達成し、「待機なし」オンライン意思決定プロセスを提供する。
  論文  参考訳（メタデータ） (2024-12-12T18:58:14Z)
• Stochastic Direct Search Method for Blind Resource Allocation [6.574808513848414]
  線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。 直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。 そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
  論文  参考訳（メタデータ） (2022-10-11T07:40:45Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。 実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。 LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
  論文  参考訳（メタデータ） (2021-10-07T02:36:14Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。 本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-27T17:38:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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