論文の概要: On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

• arxiv url: http://arxiv.org/abs/1906.00331v9
• Date: Thu, 14 Sep 2023 04:59:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-15 20:08:54.719980
• Title: On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Title（参考訳）: 非凸凹ミニマックス問題に対するグラディエントDescent Ascentについて
• Authors: Tianyi Lin, Chi Jin, Michael I. Jordan
• Abstract要約: 非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
• 参考スコア（独自算出の注目度）: 86.92205445270427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider nonconvex-concave minimax problems, $\min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y})$, where $f$ is nonconvex in $\mathbf{x}$ but concave in $\mathbf{y}$ and $\mathcal{Y}$ is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function $\Phi(\cdot) := \max_{\mathbf{y} \in \mathcal{Y}} f(\cdot, \mathbf{y})$ efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.
• Abstract（参考訳）: 我々は、非凸凸ミニマックス問題を考える: $\min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{y}} f(\mathbf{x}, \mathbf{y})$ ここで、$f$ は $\mathbf{x}$ で非凸であるが、$\mathbf{y}$ と $\mathcal{y}$ は凸かつ有界な集合である。 この問題を解決するための最も一般的なアルゴリズムの1つは、機械学習、制御理論、経済学で広く用いられてきたGDAアルゴリズムである。 凸凹集合の広範な収束結果にもかかわらず、階段化が等しいgdaは極限サイクルに収束するか、一般の設定で分岐する。 本稿では,非凸・凹極小問題の解法として,2時間スケールのGDAを用いて,関数 $\Phi(\cdot) := \max_{\mathbf{y} \in \mathcal{Y}} f(\cdot, \mathbf{y}) の定常点を効率的に求めることができることを示す。 我々の知る限り、これは2段階のGDAにおける最初の漸近解析であり、GAN(Generative Adversarial Network)やその他の実応用のトレーニングにおいて、その優れた実用性能に光を当てている。

関連論文リスト

• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [8.0153031008486]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• On Convergence of Gradient Descent Ascent: A Tight Local Analysis [30.206431787797776]
  GDA(Gradient Descent Ascent)法は、GAN(Generative Adversarial Network)における最小最適化のためのアルゴリズムである。 段差比eta_mathbfx$/eta_mathbfx=Theta(kappa2)によるGDAの収束を証明する。 我々はさらに収束保証を GDA および Extra-gradient Method (EG) に拡張する。
  論文  参考訳（メタデータ） (2022-07-03T05:04:46Z)
• 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)
• Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
  本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。 また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
  論文  参考訳（メタデータ） (2020-02-05T16:49:09Z)
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
  本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。 この方法はこの問題でよく知られている。
  論文  参考訳（メタデータ） (2020-01-11T09:05:03Z)

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

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