論文の概要: On Convergence of Gradient Descent Ascent: A Tight Local Analysis
- arxiv url: http://arxiv.org/abs/2207.00957v1
- Date: Sun, 3 Jul 2022 05:04:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-05 14:02:06.903005
- Title: On Convergence of Gradient Descent Ascent: A Tight Local Analysis
- Title（参考訳）: 勾配降下上昇の収束について--強固な局所解析
- Authors: Haochuan Li, Farzan Farnia, Subhro Das, Ali Jadbabaie
- Abstract要約: GDA(Gradient Descent Ascent)法は、GAN(Generative Adversarial Network)における最小最適化のためのアルゴリズムである。
段差比eta_mathbfx$/eta_mathbfx=Theta(kappa2)によるGDAの収束を証明する。
我々はさらに収束保証を GDA および Extra-gradient Method (EG) に拡張する。
- 参考スコア（独自算出の注目度）: 30.206431787797776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient Descent Ascent (GDA) methods are the mainstream algorithms for
minimax optimization in generative adversarial networks (GANs). Convergence
properties of GDA have drawn significant interest in the recent literature.
Specifically, for $\min_{\mathbf{x}} \max_{\mathbf{y}}
f(\mathbf{x};\mathbf{y})$ where $f$ is strongly-concave in $\mathbf{y}$ and
possibly nonconvex in $\mathbf{x}$, (Lin et al., 2020) proved the convergence
of GDA with a stepsize ratio
$\eta_{\mathbf{y}}/\eta_{\mathbf{x}}=\Theta(\kappa^2)$ where
$\eta_{\mathbf{x}}$ and $\eta_{\mathbf{y}}$ are the stepsizes for $\mathbf{x}$
and $\mathbf{y}$ and $\kappa$ is the condition number for $\mathbf{y}$. While
this stepsize ratio suggests a slow training of the min player, practical GAN
algorithms typically adopt similar stepsizes for both variables, indicating a
wide gap between theoretical and empirical results. In this paper, we aim to
bridge this gap by analyzing the \emph{local convergence} of general
\emph{nonconvex-nonconcave} minimax problems. We demonstrate that a stepsize
ratio of $\Theta(\kappa)$ is necessary and sufficient for local convergence of
GDA to a Stackelberg Equilibrium, where $\kappa$ is the local condition number
for $\mathbf{y}$. We prove a nearly tight convergence rate with a matching
lower bound. We further extend the convergence guarantees to stochastic GDA and
extra-gradient methods (EG). Finally, we conduct several numerical experiments
to support our theoretical findings.
- Abstract（参考訳）: GDA(Gradient Descent Ascent)法は、GAN(Generative Adversarial Network)における最小最適化のアルゴリズムである。
GDAの収束特性は近年の文献に多大な関心を寄せている。
具体的には、$\min_{\mathbf{x}} \max_{\mathbf{y}} f(\mathbf{x};\mathbf{y})$ ここで$f$は$\mathbf{y}$で強凹であり、おそらく非凸で$\mathbf{x}$, (lin et al., 2020) は、$\eta_{\mathbf{y}}/\eta_{\mathbf{x}}=\theta(\kappa^2)$ ここで$\eta_{\mathbf{x}}$と$\eta_{\mathbf{y}}$は$\mathbf{x}$と$\mathbf{y}$のステイズであり、$\kappa$は$\mathbf{x}$と$\mathbf{y}$のステイズである。
このステップ化比はminプレイヤーの遅いトレーニングを示唆するが、実用的なganアルゴリズムは通常、両方の変数に対して同様のステップ化を採用する。
本稿では、このギャップを、一般のemph{nonconvex-nonconcave}ミニマックス問題のemph{local convergence}を解析することで橋渡しすることを目的とする。
我々は、gda のスタックルベルク平衡への局所収束には、ステップ化比 $\theta(\kappa)$ が必要で十分であることを示し、ここで$\kappa$ は$\mathbf{y}$ の局所条件数である。
我々は、ほぼタイトな収束率を、一致する下界で証明する。
我々はさらに収束保証を確率的GDAとextra-gradient method(EG)に拡張する。
最後に, 理論的知見を裏付ける数値実験を複数実施する。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
論文 参考訳（メタデータ） (2023-06-25T16:32:00Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。