論文の概要: A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems
- arxiv url: http://arxiv.org/abs/2006.02032v3
- Date: Tue, 19 Jul 2022 16:22:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 18:39:44.044536
- Title: A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems
- Title(参考訳): 非凸凸および凸非凸ミニマックス問題に対する単一ループ交流勾配投影アルゴリズム
- Authors: Zi Xu, Huiling Zhang, Yang Xu and Guanghui Lan
- Abstract要約: 提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
- 参考スコア(独自算出の注目度): 8.797831153231664
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Much recent research effort has been directed to the development of efficient
algorithms for solving minimax problems with theoretical convergence guarantees
due to the relevance of these problems to a few emergent applications. In this
paper, we propose a unified single-loop alternating gradient projection (AGP)
algorithm for solving smooth nonconvex-(strongly) concave and (strongly)
convex-nonconcave minimax problems. AGP employs simple gradient projection
steps for updating the primal and dual variables alternatively at each
iteration. We show that it can find an $\varepsilon$-stationary point of the
objective function in $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp.
$\mathcal{O}\left( \varepsilon ^{-4} \right)$) iterations under
nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its
gradient complexity to obtain an $\varepsilon$-stationary point of the
objective function is bounded by $\mathcal{O}\left( \varepsilon ^{-2} \right)$
(resp., $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under the strongly
convex-nonconcave (resp., convex-nonconcave) setting. To the best of our
knowledge, this is the first time that a simple and unified single-loop
algorithm is developed for solving both nonconvex-(strongly) concave and
(strongly) convex-nonconcave minimax problems. Moreover, the complexity results
for solving the latter (strongly) convex-nonconcave minimax problems have never
been obtained before in the literature. Numerical results show the efficiency
of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by
presenting a block alternating proximal gradient (BAPG) algorithm for solving
more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly)
convex-nonconcave minimax problems. We can similarly establish the gradient
complexity of the proposed algorithm under these four different settings.
- Abstract(参考訳): 最近の研究は、いくつかの創発的応用にこれらの問題の関連性があるため、理論的収束保証付きミニマックス問題を解くための効率的なアルゴリズムの開発に向けられている。
本稿では,滑らかな非凸(強い)凸および(強い)凸-非凸ミニマックス問題を解くための単一ループ交流勾配投影(agp)アルゴリズムを提案する。
AGPは単純な勾配プロジェクションステップを用いて、各イテレーションで代わりに原始変数と双対変数を更新する。
目的関数の $\varepsilon$-stationary point が $\mathcal{o}\left( \varepsilon ^{-2} \right)$ (resp.0) にあることを示す。
$\mathcal{O}\left( \varepsilon ^{-4} \right)$) 非凸-強凸 (resp. nonconvex-concave) 条件下での反復。
さらに、目的関数の$\varepsilon$-定常点を得るための勾配複雑性は、$\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp) で制限される。
, $\mathcal{O}\left( \varepsilon ^{-4} \right)$) を強凸非凸(resp., convex-nonconcave)設定で表す。
我々の知る限りでは、非凸凸(強)と(強)凸非凸極小問題を解くための単純で統一された単一ループアルゴリズムが開発されたのは今回が初めてである。
さらに、後者の(強く)凸非凹のミニマックス問題を解く複雑さは、文献ではこれまで得られなかった。
数値計算の結果,提案アルゴリズムの効率性を示した。
さらに,より一般的なマルチブロック非滑らかな凹凸問題と(強く)凸非凹極小問題を解くためのブロック交互近似勾配(BAPG)アルゴリズムを提示することにより,AGPアルゴリズムを拡張した。
これら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) - 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) - 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) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - 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) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳(メタデータ) (2021-08-01T15:23:49Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。