論文の概要: Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization

• arxiv url: http://arxiv.org/abs/2408.11974v2
• Date: Thu, 26 Sep 2024 16:48:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-08 06:00:03.928372
• Title: Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization
• Title（参考訳）: 非凸ミニマックス最適化のための2時間勾配勾配昇華アルゴリズム
• Authors: Tianyi Lin, Chi Jin, Michael. I. Jordan,
• Abstract要約: 我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
• 参考スコア（独自算出の注目度）: 77.3396841985172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a unified analysis of two-timescale gradient descent ascent (TTGDA) for solving structured nonconvex minimax optimization problems in the form of $\min_\textbf{x} \max_{\textbf{y} \in Y} f(\textbf{x}, \textbf{y})$, where the objective function $f(\textbf{x}, \textbf{y})$ is nonconvex in $\textbf{x}$ and concave in $\textbf{y}$, and the constraint set $Y \subseteq \mathbb{R}^n$ is convex and bounded. In the convex-concave setting, the single-timescale gradient descent ascent (GDA) algorithm is widely used in applications and has been shown to have strong convergence guarantees. In more general settings, however, it can fail to converge. Our contribution is to design TTGDA algorithms that are effective beyond the convex-concave setting, efficiently finding a stationary point of the function $\Phi(\cdot) := \max_{\textbf{y} \in Y} f(\cdot, \textbf{y})$. We also establish theoretical bounds on the complexity of solving both smooth and nonsmooth nonconvex-concave minimax optimization problems. To the best of our knowledge, this is the first systematic analysis of TTGDA for nonconvex minimax optimization, shedding light on its superior performance in training generative adversarial networks (GANs) and in other real-world application problems.
• Abstract（参考訳）: 目的関数 $f(\textbf{x}, \textbf{y})$ は $\textbf{x}$ の非凸であり、$\textbf{y}$ の凹凸であり、$\textbf{y}$ の制約セット $Y \subseteq \mathbb{R}^n}$ は凸で有界である。 コベックス・コンケーブでは、GDAアルゴリズムがアプリケーションで広く使われており、強い収束保証があることが示されている。 しかし、より一般的な設定では、収束に失敗する可能性がある。 我々の貢献は、凸凹設定を超えて有効であるTTGDAアルゴリズムを設計し、関数 $\Phi(\cdot) := \max_{\textbf{y} \in Y} f(\cdot, \textbf{y})$ の定常点を効率的に見つけることである。 また、スムーズかつ非滑らかな非凸凹極小最適化問題の解法に関する理論的境界を確立する。 我々の知る限り、これは非凸極小最適化のためのTTGDAの最初の体系的解析であり、GAN(Generative Adversarial Network)のトレーニングや、その他の現実世界のアプリケーション問題における優れた性能に光を当てている。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
  非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。 本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
  論文  参考訳（メタデータ） (2024-05-28T20:52:46Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis [28.575516056239575]
  PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。 PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
  論文  参考訳（メタデータ） (2022-09-22T07:12:48Z)
• A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
  提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。 提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
  論文  参考訳（メタデータ） (2020-06-03T04:00:52Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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