論文の概要: Linear Convergence in Games with Delayed Feedback via Extra Prediction
- arxiv url: http://arxiv.org/abs/2602.17486v1
- Date: Thu, 19 Feb 2026 15:56:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-20 15:21:29.194249
- Title: Linear Convergence in Games with Delayed Feedback via Extra Prediction
- Title（参考訳）: 余剰予測による遅延フィードバックを持つゲームにおける線形収束
- Authors: Yuma Fujimoto, Kenshi Abe, Kaito Ariu,
- Abstract要約: 本稿では, 重み付き最適勾配Descence-Ascent(WOGDA)の線形収束率を導出する。
我々はそれを古典的近点(PP)よりも遠い将来報酬に基づいて更新されるEPP(Extra Proximal Point)の近似として分析する。
- 参考スコア（独自算出の注目度）: 26.93300099029726
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate $\exp(-Θ(t/m^{5}))$ after $t$ iterations for delay $m$. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to $\exp(-Θ(t/(m^{2}\log m)))$. Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.
- Abstract（参考訳）: 実世界のマルチエージェント学習では、フィードバックの遅延は避けられない。
これらは性能を著しく低下させることが知られており、双線形ゲームにおいても遅延フィードバックによる収束率はまだ不明である。
本稿では、制約のない双線型ゲームにおいて、余分な楽観性を伴って将来の報奨を予測できる重み付き最適勾配Descent-Ascent(WOGDA)の線形収束率を導出する。
アルゴリズムを解析するために,従来の近似点 (PP) よりも遠い将来的な報酬に基づいて更新されるEPP (Extra Proximal Point) の近似として解釈する。
我々の定理は、標準楽観主義(次のステップの報酬を予測する)が、遅延$m$に対する$t$反復の後に$\exp(-t/m^{5})$で平衡への線形収束を達成することを示している。
さらに、余分な楽観主義(将来の報奨を予測する)を用いることで、より大きなステップサイズを許容し、$\exp(-\exp(-t/(m^{2}\log m)))$に大幅に加速する。
我々の実験はまた、余分な楽観主義によって引き起こされる加速収束を示し、我々の定理と質的に一致している。
本稿では,フィードバック遅延による性能劣化対策として,余剰最適化が有望な対策であることを示す。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Min-Max Optimization under Delays [26.830212508878162]
大規模な機械学習問題では遅延と非同期は避けられない。
min-max最適化に類似した理論は存在しない。
たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
論文 参考訳（メタデータ） (2023-07-13T16:39:01Z) - Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
一般化線形包帯における遅延報酬の現象を理論的に研究する。
遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-07-21T23:35:01Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳（メタデータ） (2021-03-21T10:16:15Z) - Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。
平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。
任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
論文 参考訳（メタデータ） (2020-06-16T20:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。