Fugu-MT 論文翻訳(概要): Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization

論文の概要: 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' などである。我々の知る限りでは、このアルゴリズムはこれらすべての恐ろしい問題に収束する最初の一階法である。

関連論文リスト

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)

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

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