論文の概要: On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games

• arxiv url: http://arxiv.org/abs/2503.02825v1
• Date: Tue, 04 Mar 2025 17:49:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:13:06.049850
• Title: On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
• Title（参考訳）: ゲームにおける学習のベストイテレート,ランダムイテレート,最終イテレート収束の分離について
• Authors: Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng,
• Abstract要約: ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
• 参考スコア（独自算出の注目度）: 71.73971094342349
• License:
• Abstract: Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest.
• Abstract（参考訳）: ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、近年広く研究されている。 最近の研究 (Cai et al , 2024) は、楽観的乗算重み更新 (OMWU) を含む幅広い学習力学系が、単純な2ドルの2$マトリクスゲームにおいても任意に遅い最終点収束を示すことを示した。 しかし、これらのアルゴリズムが最良点収束のようなより弱い基準の下で高速な非エルゴード収束を達成するかどうかは不明である。 2 ドルの行列ゲームの場合、OMWU は O(T^{-1/6})$$ best-iterate convergence rate を達成する。 さらに,OMWUが任意の多項式ランダム点収束率を達成できないことを示す下界を確立する。 この結果は、ランダム・イテレート収束が本質的にベスト・イテレート収束と等価であるという従来の知恵に挑戦し、前者は後者を確立するためのプロキシとしてしばしば使用される。 我々の分析により、動的後悔への新たなつながりが明らかとなり、独立性のある最良の収束に対する新しい2相アプローチが提示される。

関連論文リスト

• Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games [31.989723099872638]
  2人プレイのゼロサムゲームにおける学習アルゴリズムの終局的動作について、広範囲に研究されている。 既存の結果の多くは、ゲームが時間に依存しないという仮定の下でこれらの特性を確立する。 本稿では,制約付き周期ゲームにおける楽観的および外段階的手法の終局的挙動について検討する。
  論文  参考訳（メタデータ） (2024-06-15T11:50:36Z)
• The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
  本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。 特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。 また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• 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)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)

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

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