論文の概要: Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

• arxiv url: http://arxiv.org/abs/2002.05309v2
• Date: Wed, 17 Jun 2020 09:02:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-01 10:09:59.595716
• Title: Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Title（参考訳）: 最小値最適化のための最適エポッチ確率勾配勾配法
• Authors: Yan Yan and Yi Xu and Qihang Lin and Wei Liu and Tianbao Yang
• Abstract要約: エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。 Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
• 参考スコア（独自算出の注目度）: 61.66927778694731
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal convergence rate of $O(1/T)$ with $T$ iterative updates for the {\it objective gap}. However, its extension to solving stochastic min-max problems with strong convexity and strong concavity still remains open, and it is still unclear whether a fast rate of $O(1/T)$ for the {\it duality gap} is achievable for stochastic min-max optimization under strong convexity and strong concavity. Although some recent studies have proposed stochastic algorithms with fast convergence rates for min-max problems, they require additional assumptions about the problem, e.g., smoothness, bi-linear structure, etc. In this paper, we bridge this gap by providing a sharp analysis of epoch-wise stochastic gradient descent ascent method (referred to as Epoch-GDA) for solving strongly convex strongly concave (SCSC) min-max problems, without imposing any additional assumption about smoothness or the function's structure. To the best of our knowledge, our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O(1/T)$ for the duality gap of general SCSC min-max problems. We emphasize that such generalization of Epoch-GD for strongly convex minimization problems to Epoch-GDA for SCSC min-max problems is non-trivial and requires novel technical analysis. Moreover, we notice that the key lemma can also be used for proving the convergence of Epoch-GDA for weakly-convex strongly-concave min-max problems, leading to a nearly optimal complexity without resorting to smoothness or other structural conditions.
• Abstract（参考訳）: Hazan and Kale (2011) が提唱したエポッチ勾配降下法 (Epoch gradient descent method, Epoch-GD) は確率論的凸最小化のブレークスルーであり、O(1/T)$の最適収束率とT$の反復更新を達成している。 しかし、強い凸性と強い凹凸を持つ確率的min-max問題の解への拡張は依然として開かれておらず、強い凸性と強い凹凸の下での確率的min-max最適化のためにo(1/t)$が達成可能かどうかはまだ不明である。 近年の研究では、min-max問題に対する高速収束率を持つ確率的アルゴリズムが提案されているが、滑らか性、双線形構造など、問題に関する追加の仮定が必要である。 本稿では,強凸強凹(scscsc)min-max問題を解くためのエポックワイズ確率勾配降下上昇法(epoch-gda)の鋭利な解析を行い,滑らか性や関数の構造について追加の仮定を加えることなく,このギャップを解消する。 我々の知る限りでは、一般的なSCSC min-max問題の双対性ギャップに対して、Epoch-GDAが$O(1/T)$の最適レートを達成できることを示す最初の結果である。 我々は, SCSC min-max問題に対するEpoch-GDAに対して, 凸最小化問題に対するEpoch-GDのそのような一般化は非自明であり, 新たな技術的解析を必要とすることを強調する。 さらに,弱凸強凸min-max問題に対するepoch-gdaの収束性を証明するためにもキー補題を用いることができ,滑らか性や他の構造条件に頼らずにほぼ最適に複雑化できることを示した。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property [19.988762532185884]
  非滑らかな最適化問題は、学習にとって重要かつ困難である。 本稿では,PSGDの高速収束を示す新しい解析法について述べる。
  論文  参考訳（メタデータ） (2023-04-20T17:39:24Z)
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
  重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。 本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
  論文  参考訳（メタデータ） (2023-03-22T03:05:28Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。 Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
  論文  参考訳（メタデータ） (2022-08-11T16:55:26Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• 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)

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

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