論文の概要: Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization

• arxiv url: http://arxiv.org/abs/1807.04252v5
• Date: Sat, 27 Sep 2025 08:38:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:18.59945
• Title: Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• Title（参考訳）: ラストイテレート収束:ゼロサムゲームと制約されたMin-Max最適化
• Authors: Constantinos Daskalakis, Ioannis Panageas,
• Abstract要約: 広く使われているグラディエント・ディキセント/アセンセント法は凸問題におけるサドル点への最終点収束を示す。 我々は、非回帰乗算重み更新法の変則の下で、エム制約最小値最適化のより一般的な問題において、同じことが成り立つことを示す。
• 参考スコア（独自算出の注目度）: 31.185065331321734
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Ascent (OGDA)", exhibits last-iterate convergence to saddle points in {\em unconstrained} convex-concave min-max optimization problems. We show that the same holds true in the more general problem of {\em constrained} min-max optimization under a variant of the no-regret Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights Update (OMWU)". This answers an open question of Syrgkanis et al \cite{SALS15}. The proof of our result requires fundamentally different techniques from those that exist in no-regret learning literature and the aforementioned papers. We show that OMWU monotonically improves the Kullback-Leibler divergence of the current iterate to the (appropriately normalized) min-max solution until it enters a neighborhood of the solution. Inside that neighborhood we show that OMWU is locally (asymptotically) stable converging to the exact solution. We believe that our techniques will be useful in the analysis of the last iterate of other learning algorithms.
• Abstract（参考訳）: ゲーム理論、最適化、生成共役ネットワークの応用により、近年のDaskalakis et al \cite{DISZ17} の業績と、Liang と Stokes \cite{LiangS18} のフォローアップ作業により、広く使われているグラディエント・ディクセント/アセンセント法("Optimistic Gradient Descent/Ascent (OGDA)")の変種が、凸凸・凹凸・最小-マックス最適化問題におけるサドル点への最終点収束を示すことが証明された。 ここでは,非回帰乗算重み更新法(Optimistic Multiplicative-Weights Update (OMWU)) の変種の下で, より一般的な min-max 最適化問題において, 同様のことが成り立つことを示す。 これは Syrgkanis et al \cite{SALS15} の開問題に答える。 この結果の証明には, 未学習の文献や前述の論文と根本的に異なる技術が必要である。 我々は,OMWUが解の近傍に入るまで,電流のKulback-Leibler分散を(適切に正規化された)min-max解に単調に改善することを示す。 その近傍では、OMWUが(漸近的に)局所的に正確な解に収束していることが示される。 我々は,我々の手法が,他の学習アルゴリズムの最後の繰り返しの分析に有用であると信じている。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。 本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。 私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
  論文  参考訳（メタデータ） (2022-10-06T17:50:42Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  我々は、滑らかな凸関数の標準設定において、AdaGradとその変種についてより深く理解する。 まず、制約のない問題に対して、バニラ AdaGrad の収束率を明示的に拘束する新しい手法を示す。 第二に、平均的な反復ではなく、最後の反復の収束を示すことのできる AdaGrad の変種を提案する。
  論文  参考訳（メタデータ） (2022-09-29T14:44:40Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes [33.2931644228746]
  オンライン学習フレームワーク「OMWU(Optimistic Multiplicative-Weights Update)」は,凸凹型ゲームにおいて,最後の反復収束を示す。 提案手法の高速収束を示す実験により,実験結果を補完する。
  論文  参考訳（メタデータ） (2020-02-17T04:40:38Z)

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

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