論文の概要: Faster Single-loop Algorithms for Minimax Optimization without Strong
Concavity
- arxiv url: http://arxiv.org/abs/2112.05604v1
- Date: Fri, 10 Dec 2021 15:35:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-13 14:03:56.161056
- Title: Faster Single-loop Algorithms for Minimax Optimization without Strong
Concavity
- Title（参考訳）: 強い凹凸のないミニマックス最適化のための高速単一ループアルゴリズム
- Authors: Junchi Yang, Antonio Orvieto, Aurelien Lucchi and Niao He
- Abstract要約: GDA(Gradient descent Ascent)は、GAN(Generative Adversarial Network)やGAN(Adversarial Network)といった実用用途で広く利用されている。
最近の研究は、一方のトレーニング結果に対する反復の理論において、GDAの収束率が劣っていることを示している。
本稿では, 1変数のpolyak-Lojasiewicz(PL)条件を満たすという軽微な仮定の下で, GDAと滑らかなGDAの交互化という2つの代替シングルループアルゴリズムを確立する。
- 参考スコア（独自算出の注目度）: 30.97847679999505
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient descent ascent (GDA), the simplest single-loop algorithm for
nonconvex minimax optimization, is widely used in practical applications such
as generative adversarial networks (GANs) and adversarial training. Albeit its
desirable simplicity, recent work shows inferior convergence rates of GDA in
theory even assuming strong concavity of the objective on one side. This paper
establishes new convergence results for two alternative single-loop algorithms
-- alternating GDA and smoothed GDA -- under the mild assumption that the
objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable.
We prove that, to find an $\epsilon$-stationary point, (i) alternating GDA and
its stochastic variant (without mini batch) respectively require $O(\kappa^{2}
\epsilon^{-2})$ and $O(\kappa^{4} \epsilon^{-4})$ iterations, while (ii)
smoothed GDA and its stochastic variant (without mini batch) respectively
require $O(\kappa \epsilon^{-2})$ and $O(\kappa^{2} \epsilon^{-4})$ iterations.
The latter greatly improves over the vanilla GDA and gives the hitherto best
known complexity results among single-loop algorithms under similar settings.
We further showcase the empirical efficiency of these algorithms in training
GANs and robust nonlinear regression.
- Abstract（参考訳）: 非凸極小最適化のための最も単純な単一ループアルゴリズムである勾配降下昇降法 (GDA) は、GAN(generative adversarial network) や対向訓練などの実践的応用に広く用いられている。
その望ましい単純さにもかかわらず、最近の研究は理論上gdaの収束率が低いことを示している。
本稿では, 1変数のpolyak-Lojasiewicz (PL) 条件を満たすという軽微な仮定の下で, GDA と滑らかな GDA を交互に組み合わせた2つの代替シングルループアルゴリズムの新たな収束結果を確立する。
私たちは、$\epsilon$-stationary 点を見つけるために、それを証明します。
i) GDA とその確率的変種(ミニバッチなしで)を交互に交換するには、それぞれ$O(\kappa^{2} \epsilon^{-2})$と$O(\kappa^{4} \epsilon^{-4})$反復が必要である。
(ii)滑らかなGDAとその確率多様体(ミニバッチなし)はそれぞれ$O(\kappa \epsilon^{-2})$と$O(\kappa^{2} \epsilon^{-4})$反復を必要とする。
後者はバニラGDAを大幅に改善し、同様の設定下でシングルループアルゴリズムで最もよく知られた複雑性結果を提供する。
さらに,ganの学習とロバスト非線形回帰における経験的効率を示す。
関連論文リスト
- MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - Stochastic Policy Gradient Methods: Improved Sample Complexity for
Fisher-non-degenerate Policies [19.779044926914704]
我々は、フィッシャー非退化パラメタライズドポリシーの一般クラスに対する改善されたグローバルコンバージェンス保証を開発する。
本研究では,Implicit Gradient Transport (N-PG-IGT) を用いた正規化政策勾配法を提案し,この手法のサンプル複雑性を$tildemathcalO(varepsilon-2.5)$とする。
我々はこの複雑さをさらに改善し、ヘッセン支援再帰政策勾配を考慮し、$tilde MathcalmathcalO (varepsilon-2)$に改善する。
論文 参考訳（メタデータ） (2023-02-03T13:50:23Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Solve Minimax Optimization by Anderson Acceleration [5.900781483345349]
勾配降下上昇(GDA)は、その単純さから最もよく使われるアルゴリズムである。
本稿では,GDA力学を固定点反復とみなす新しいミニマックス最適化フレームワークGDA-AMを提案する。
理論上,このアルゴリズムは温和条件下での双線形問題に対する大域収束を実現することができることを示す。
論文 参考訳（メタデータ） (2021-10-06T02:08:54Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for
Nonconvex-Concave Min-Max Problems [33.83671897619922]
非con-max問題は、このロバストな問題を解決するために、ポイントワイズな非函数の集合を最小化するなど、多くのアプリケーションで発生する。
A.A.アルゴリズムは、有限個の非函数の集合に対して$(/A-O-)の$(/A-O-)を達成できる。
論文 参考訳（メタデータ） (2020-10-29T17:13:46Z) - On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
ミニマックス問題を解くためのリーマン的手法のクラスを提案する。
我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。
また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
論文 参考訳（メタデータ） (2020-10-13T00:54:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。