論文の概要: Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

• arxiv url: http://arxiv.org/abs/2002.00057v2
• Date: Tue, 7 Jul 2020 03:20:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 06:02:02.910563
• Title: Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Title（参考訳）: Smooth Convex-Concave Saddle問題における最終イテレーションは平均イテレーションよりも遅い
• Authors: Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar
• Abstract要約: 最後の段階(EG)の繰り返しは、$O (1/sqrtT)$で収束することを示す。 本論文は,円凸凹型サドル点問題に対するEGの最終繰り返しに対する収束率保証を行う最初の論文である。
• 参考スコア（独自算出の注目度）: 28.12079055746505
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last iterate of EG converges at a rate of $O(1/\sqrt{T})$. To the best of our knowledge, this is the first paper to provide a convergence rate guarantee for the last iterate of EG for the smooth convex-concave saddle point problem. Moreover, we show that this rate is tight by proving a lower bound of $\Omega(1/\sqrt{T})$ for the last iterate. This lower bound therefore shows a quadratic separation of the convergence rates of ergodic and last iterates in smooth convex-concave saddle point problems.
• Abstract（参考訳）: 本稿では,滑らかな凸凹サドル点問題について検討する。 具体的には,Extragradient (EG)アルゴリズムの最後の反復収束特性を解析する。 EG のエルゴード的(平均化された)反復が$O(1/T)$ (Nemirovski, 2004) の速度で収束することが知られている。 本稿では、EG の最後の反復が$O(1/\sqrt{T})$で収束することを示す。 我々の知る限りでは、この論文は滑らかな凸凸対鞍点問題に対するegの最終反復に対する収束率保証を提供する最初の論文である。 さらに、この値は、最後の反復に対して$\Omega(1/\sqrt{T})$の低い境界を証明することによって、厳密であることを示す。 したがって、この下限は滑らかな凸凸対鞍点問題におけるエルゴードと最後のイテレートの収束率の二次分離を示す。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
  論文  参考訳（メタデータ） (2021-12-30T20:31:46Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms [125.99533416395765]
  本稿では,サドル点問題の分散最適化に着目する。 本論文は,本研究における分散手法の有効性を実験的に示すものである。
  論文  参考訳（メタデータ） (2020-10-25T13:13:44Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
  論文  参考訳（メタデータ） (2020-06-14T11:12:05Z)

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

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