論文の概要: Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave
Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.12978v5
- Date: Mon, 30 Oct 2023 08:56:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 04:06:00.574729
- Title: Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave
Minimax Optimization
- Title（参考訳）: 非凸非凹ミニマックス最適化のためのユニバーサル勾配降下上昇法
- Authors: Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, Jose Blanchet,
Jiajin Li
- Abstract要約: 非コンケーブなミニマックス最適化は、機械学習に広く応用されているため、この10年で大きな注目を集めている。
本稿では,一様かつ二重に勾配のバランスをとることができる新しい単一ループ二元アルゴリズムを提案する。
具体的には、指数$thetain(0,1)$の片側KL条件の下で、DS-GDAは$mathcalO(eps-2$2$1)の結果と収束する。
- 参考スコア（独自算出の注目度）: 22.392563619845212
- 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. Most
existing algorithms rely on one-sided information, such as the convexity (resp.
concavity) of the primal (resp. dual) functions, or other specific structures,
such as the Polyak-\L{}ojasiewicz (P\L{}) and Kurdyka-\L{}ojasiewicz (K\L{})
conditions. However, verifying these regularity conditions is challenging in
practice. To meet this challenge, we propose a novel universally applicable
single-loop algorithm, the doubly smoothed gradient descent ascent method
(DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA
with the same hyperparameters is able to uniformly solve nonconvex-concave,
convex-nonconcave, and nonconvex-nonconcave problems with one-sided K\L{}
properties, achieving convergence with $\mathcal{O}(\epsilon^{-4})$ complexity.
Sharper (even optimal) iteration complexity can be obtained when the K\L{}
exponent is known. Specifically, under the one-sided K\L{} condition with
exponent $\theta\in(0,1)$, DS-GDA converges with an iteration complexity of
$\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$. They all match the corresponding
best results in the literature. Moreover, we show that DS-GDA is practically
applicable to general nonconvex-nonconcave problems even without any regularity
conditions, such as the P\L{} condition, K\L{} condition, or weak Minty
variational inequalities condition. For various challenging
nonconvex-nonconcave examples in the literature, including ``Forsaken'',
``Bilinearly-coupled minimax'', ``Sixth-order polynomial'', and ``PolarGame'',
the proposed DS-GDA can all get rid of limit cycles. To the best of our
knowledge, this is the first first-order algorithm to achieve convergence on
all of these formidable problems.
- Abstract（参考訳）: nonconvex-nonconcave minimaxの最適化は、機械学習の幅広い応用により、過去10年間、大きな注目を集めてきた。
既存のアルゴリズムの多くは、原始(双対)函数の凸性 (resp. concavity) や、Polyak-\L{}ojasiewicz (P\L{}) や Kurdyka-\L{}ojasiewicz (K\L{}) のような特定の構造のような一方的な情報に依存している。
しかし、これらの規則性条件の検証は実際は困難である。
この課題を克服するために,2重平滑化勾配降下昇降法 (ds-gda) という,プライマルとデュアルの更新を自然にバランスさせる新しい単一ループアルゴリズムを提案する。
すなわち、同じハイパーパラメータを持つds-gdaは、一方のk\l{}特性を持つ非凸凸、凸非凸、非凸非凸問題を一様解くことができ、$\mathcal{o}(\epsilon^{-4})$ で収束する。
k\l{}指数が知られている場合、よりシャープな(最適な)反復複雑性が得られる。
具体的には、指数 $\theta\in(0,1)$ の片側 k\l{} 条件の下で、ds-gda は $\mathcal{o}(\epsilon^{-2\max\{2\theta,1\}})$ の反復複雑性で収束する。
いずれも文学における最良の結果と一致している。
さらに, ds-gda は p\l{} 条件, k\l{} 条件, 弱いミント変分不等式条件などの正規性条件がなくても, 一般の非凸非凸問題に適用可能であることを示した。
例えば ``Forsaken'' 、 ``Bilinearly-coupled minimax'' 、 ``Sixth-order polynomial'' 、 ``PolarGame' などである。
我々の知る限りでは、このアルゴリズムはこれらすべての恐ろしい問題に収束する最初の一階法である。
関連論文リスト
- 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 [77.8485863487028]
本稿では、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) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳（メタデータ） (2022-02-02T20:10:40Z) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。