論文の概要: Doubly Smoothed GDA: Global Convergent Algorithm for Constrained
Nonconvex-Nonconcave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.12978v3
- Date: Mon, 29 May 2023 14:46:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 02:26:50.246442
- Title: Doubly Smoothed GDA: Global Convergent Algorithm for Constrained
Nonconvex-Nonconcave Minimax Optimization
- Title（参考訳）: 2重平滑化gda:制約付き非凸非凸ミニマックス最適化のための大域収束アルゴリズム
- Authors: Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, Jose Blanchet,
Jiajin Li
- Abstract要約: 非コンケーブなミニマックス最適化は、機械学習に広く応用されているため、この10年で大きな注目を集めている。
ほとんどの既存のアルゴリズムは、グローバルに収束することを保証できない。
一つの指数を持つ一方のクルディ・ロジャシエヴィチ条件の下では、原始凸/凸双対関数を持つゲームを見つけることができる。
- 参考スコア（独自算出の注目度）: 24.324099234430715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonconvex-nonconcave minimax optimization has received intense attention over
the last decade due to its broad applications in machine learning.
Unfortunately, most existing algorithms cannot be guaranteed to converge
globally and even suffer from limit cycles. To address this issue, we propose a
novel single-loop algorithm called doubly smoothed gradient descent ascent
method (DSGDA), which naturally balances the primal and dual updates. The
proposed DSGDA can get rid of limit cycles in various challenging
nonconvex-nonconcave examples in the literature, including Forsaken,
Bilinearly-coupled minimax, Sixth-order polynomial, and PolarGame. We further
show that under an one-sided Kurdyka-\L{}ojasiewicz condition with exponent
$\theta\in(0,1)$ (resp. convex primal/concave dual function), DSGDA can find a
game-stationary point with an iteration complexity of
$\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$ (resp.
$\mathcal{O}(\epsilon^{-4})$). These match the best results for single-loop
algorithms that solve nonconvex-concave or convex-nonconcave minimax problems,
or problems satisfying the rather restrictive one-sided Polyak-\L{}ojasiewicz
condition. Our work demonstrates, for the first time, the possibility of having
a simple and unified single-loop algorithm for solving nonconvex-nonconcave,
nonconvex-concave, and convex-nonconcave minimax problems.
- Abstract（参考訳）: nonconvex-nonconcave minimaxの最適化は、機械学習の幅広い応用により、過去10年間、大きな注目を集めてきた。
残念なことに、ほとんどの既存のアルゴリズムはグローバル収束を保証できず、制限サイクルに苦しむことさえできない。
この問題に対処するために,2重平滑化勾配降下昇降法(dsgda)と呼ばれる,プライマルとデュアルの更新を自然にバランスさせる新しい単一ループアルゴリズムを提案する。
提案したDSGDAは、Forsaken、Bilinearly-coupled minimax、Sixth-order polynomial、PolarGameなど、様々な難解な非凸非凸例の極限サイクルを除去することができる。
さらに、指数 $\theta\in(0,1)$ (resp.convex primal/concave dual function) を持つ一方のKurtyka-\L{}ojasiewicz条件の下で、DSGDA は $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$ (resp.convex primal/concave dual function) の反復複雑性を持つゲーム定常点を見つけることができる。
o (\epsilon^{-4})$) である。
これらは、非凸凹や非凸凹のミニマックス問題を解くシングルループアルゴリズムや、より限定的な一方的なポリアック-\L{}ojasiewicz条件を満たす問題に対する最良の結果と一致する。
本研究は,非凸非凸,非凸凸および凸非凸ミニマックス問題を解決するための単純で統一された単一ループアルゴリズムを初めて持つことを実証する。
関連論文リスト
- 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) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文 参考訳（メタデータ） (2024-01-26T11:22:13Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。
そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-09T05:32:30Z) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳（メタデータ） (2021-03-29T18:53:57Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。