論文の概要: Doubly Smoothed GDA: Global Convergent Algorithm for Constrained
Nonconvex-Nonconcave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.12978v1
- Date: Mon, 26 Dec 2022 00:28:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 14:05:34.075518
- 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要約: このアルゴリズムはゲームポイントを見つけるための$calO()$を持ち、最適な静止点と一致することを示す。
ここで提示されたアルゴリズムは、証明可能な複雑性チェックアルゴリズムを設計するための新しい道を開く。
- 参考スコア（独自算出の注目度）: 24.324099234430715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonconvex-nonconcave minimax optimization has been the focus of intense
research over the last decade due to its broad applications in machine learning
and operation research. Unfortunately, most existing algorithms cannot be
guaranteed to converge and always suffer from limit cycles. Their global
convergence relies on certain conditions that are difficult to check, including
but not limited to the global Polyak-\L{}ojasiewicz condition, the existence of
a solution satisfying the weak Minty variational inequality and
$\alpha$-interaction dominant condition. In this paper, we develop the first
provably convergent algorithm called doubly smoothed gradient descent ascent
method, which gets rid of the limit cycle without requiring any additional
conditions. We further show that the algorithm has an iteration complexity of
$\mathcal{O}(\epsilon^{-4})$ for finding a game stationary point, which matches
the best iteration complexity of single-loop algorithms under
nonconcave-concave settings. The algorithm presented here opens up a new path
for designing provable algorithms for nonconvex-nonconcave minimax optimization
problems.
- Abstract（参考訳）: nonconvex-nonconcave minimax optimizationは、機械学習と運用研究に広く応用されているため、過去10年間にわたって激しい研究の焦点となっている。
残念ながら、既存のアルゴリズムの多くは収束を保証できず、常に制限サイクルに苦しむ。
それらの大域収束は、チェックが難しい特定の条件に依存しており、大域的ポリアック-\L{}ojasiewicz条件、弱ミンティ変量不等式を満たす解の存在、および$\alpha$-相互作用支配条件に限らない。
本稿では,2次スムーズな勾配勾配上昇法という,新たな条件を伴わずに限界周期を除去するアルゴリズムを開発した。
さらに,本アルゴリズムは,非凹凸条件下での単一ループアルゴリズムの最適反復複雑性と一致するゲーム定常点を求めるために,$\mathcal{O}(\epsilon^{-4})$の反復複雑性を持つことを示した。
ここで提示されるアルゴリズムは、非凸非凸ミニマックス最適化問題の証明可能なアルゴリズムを設計するための新しい経路を開く。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。