論文の概要: 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つの異なる設定の下で、提案アルゴリズムの勾配複雑性も同様に確立することができる。
関連論文リスト
- 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 [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 [5.142024994067472]
近年,機械学習や信号処理の分野では,非数学的ミニマックス問題に注目が集まっている。
線形制約を用いた非ミニマックス点数問題の解法として,複雑性保証付き2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (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) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳(メタデータ) (2021-03-29T18:53:57Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。