論文の概要: When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

• arxiv url: http://arxiv.org/abs/2605.13242v1
• Date: Wed, 13 May 2026 09:27:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:27.942621
• Title: When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
• Title（参考訳）: 最適乗算重量はいつ,なぜ遅いのか : エネルギー散逸の幾何学
• Authors: John Lazarsfeld, Anas Barakat, Georgios Piliouras, Antonios Varvitsiotis, Andre Wibisono,
• Abstract要約: 本稿では,OMWU (Optimistic Multiplicative Weights Update Algorithm) の2つのプレイヤーゼロサムゲームにおける収束性について検討する。 近年の研究では、OMWUの最終定位が任意に緩やかに収束できる事例が特定されているが、この緩やかな収束がいつ、なぜかは未解明のままである。
• 参考スコア（独自算出の注目度）: 32.14523629861835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the $2\times 2$ setting a new ${\widetilde O}(T^{-1/2})$ best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.
• Abstract（参考訳）: 本稿では,OMWU (Optimistic Multiplicative Weights Update Algorithm) の2つのプレイヤーゼロサムゲームにおける収束性について検討する。 近年の研究では、OMWUの最終定位が任意に緩やかに収束できる事例が特定されているが、この緩やかな収束がいつ、なぜかは未解明のままである。 本研究では,この行動について,鋭く定量的に説明できる新しい分析フレームワークを開発する。 我々の分析は、アルゴリズムの双対イテレートをエネルギー関数に対する楽観的なスキュー勾配の降下と見なすことに基づいている。 我々は、エネルギーが散逸性であることを双対反復で証明し、散逸の程度に厳密な境界を確立することにより、対応する原始反復が単純境界に近いときに生じる幾何学的ボトルネックを定量化する。 これはさらに、一意かつ内部的なナッシュ平衡を持つゲーム上でのKLの発散における新しい線形最終点収束率に変換される。 以前の研究と比較すると、この新しい速度はゲーム固有の定数へのよりシャープな依存を含んでおり、この依存が最適であることを証明している。 さらに、これらの幾何学的洞察は、OMWUの均一収束率に関する新たな分離へと変換される。 一方、KLのばらつきとナッシュからの全変動距離において、一様最良点収束率に対して一定の下界を証明した。 一方、新たな${\widetilde O}(T^{-1/2})$ best-iterate rate in duality gap を設定し、前処理よりも大幅に改善する。 このようにして、一様収束率の保証は、異なる距離の測度を越えてナッシュに移動しないことが一般に示される。

関連論文リスト

• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  NLHFにおける最適乗算重み更新(mathtOMWU$)に対する最初の収束保証を提供する。 本分析では, 稀に発生する行動の確率が指数関数的に小さい値から指数関数的に増大する新たな限界収束挙動を同定する。
  論文  参考訳（メタデータ） (2025-12-31T12:08:29Z)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• Last Iterate Convergence in Monotone Mean Field Games [24.486052525745574]
  平均場ゲーム(MFG)は、無限個のエージェント間の相互作用をモデル化する。 既存のアルゴリズムは厳密な単調性を必要とするか、平均的な反復の収束を保証するだけである。 本稿では,少数のMDステップによるPP更新を概ね実装した近似プロキシ・ポイント(mathtAPP$)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-07T15:28:18Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Forward Looking Best-Response Multiplicative Weights Update Methods [14.519198115835966]
  エンフェルティプリケートウェイト更新法の新しい変種は、独自のエンフェルティプリケート平衡を持つエンフェルティプリケートサムゲームに対する最終点収束を保証する 以上の結果から,本アルゴリズムは従来手法と比較して,収束率と収縮領域の両方において有意な利得が得られることが明らかとなった。
  論文  参考訳（メタデータ） (2021-06-07T13:03:33Z)
• 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)
• The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
  我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。 この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
  論文  参考訳（メタデータ） (2020-06-06T19:08:05Z)

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

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