論文の概要: Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth
Nonconvex Minimax Problems with Coupled Linear Constraints
- arxiv url: http://arxiv.org/abs/2212.04672v3
- Date: Sun, 3 Mar 2024 02:53:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 04:07:32.761485
- Title: Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth
Nonconvex Minimax Problems with Coupled Linear Constraints
- Title（参考訳）: 結合線形制約を持つ非滑らかな非凸ミニマックス問題に対する原始双対交互近勾配アルゴリズム
- Authors: Huiling Zhang, Junlin Wang, Zi Xu, Yu-Hong Dai
- Abstract要約: 近年,機械学習や信号処理の分野では,非数学的ミニマックス問題に注目が集まっている。
線形制約を用いた非ミニマックス点数問題の解法として,複雑性保証付き2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.142024994067472
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonconvex minimax problems have attracted wide attention in machine learning,
signal processing and many other fields in recent years. In this paper, we
propose a primal-dual alternating proximal gradient (PDAPG) algorithm and a
primal-dual proximal gradient (PDPG-L) algorithm for solving nonsmooth
nonconvex-(strongly) concave and nonconvex-linear minimax problems with coupled
linear constraints, respectively. The iteration complexity of the two
algorithms are proved to be $\mathcal{O}\left( \varepsilon ^{-2} \right)$
(resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under nonconvex-strongly
concave (resp. nonconvex-concave) setting and $\mathcal{O}\left( \varepsilon
^{-3} \right)$ under nonconvex-linear setting to reach an
$\varepsilon$-stationary point, respectively. To our knowledge, they are the
first two algorithms with iteration complexity guarantees for solving the
nonconvex minimax problems with coupled linear constraints.
- Abstract（参考訳）: 非凸ミニマックス問題は近年、機械学習、信号処理など多くの分野で注目されている。
本稿では,線形制約を結合した非凸-(強い)凹凸問題と非凸-線形極小問題をそれぞれ解くために,原始二重交互近位勾配(PDAPG)アルゴリズムと原始二重近位勾配(PDPG-L)アルゴリズムを提案する。
2つのアルゴリズムの反復複雑性は$\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp)であることが証明される。
unconvex-strongly concave (resp. nonconvex-concave) set と $\mathcal{o}\left( \varepsilon ^{-3} \right)$ それぞれ $\varepsilon$-stationary point となるように非凸線形条件下では$\mathcal{o}\left( \varepsilon ^{-4} \right)$ となる。
我々の知る限り、これらは線形制約を結合した非凸ミニマックス問題を解くために、反復複雑性を保証する最初の2つのアルゴリズムである。
関連論文リスト
- 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) - An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems [0.4910937238451484]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(FORMDA)を高速化する。
有界アルゴリズムの最大の複雑さは、客観性関数の停止下での非可逆ミニマックス問題の解法である。
論文 参考訳（メタデータ） (2023-10-24T01:45:11Z) - 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) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。