論文の概要: Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints
- arxiv url: http://arxiv.org/abs/2402.03352v1
- Date: Fri, 26 Jan 2024 11:22:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-11 15:40:38.488415
- Title: Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints
- Title（参考訳）: 線形制約を持つ非凸ミニマックス問題に対するゼロ次原始双対射影勾配アルゴリズム
- Authors: Huiling Zhang, Zi Xu, Yuhong Dai
- Abstract要約: 線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
- 参考スコア（独自算出の注目度）: 3.898056433020865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study zeroth-order algorithms for nonconvex minimax
problems with coupled linear constraints under the deterministic and stochastic
settings, which have attracted wide attention in machine learning, signal
processing and many other fields in recent years, e.g., adversarial attacks in
resource allocation problems and network flow problems etc. We propose two
single-loop algorithms, namely the zero-order primal-dual alternating projected
gradient (ZO-PDAPG) algorithm and the zero-order regularized momentum
primal-dual projected gradient algorithm (ZO-RMPDPG), for solving deterministic
and stochastic nonconvex-(strongly) concave minimax problems with coupled
linear constraints. The iteration complexity of the two proposed algorithms to
obtain an $\varepsilon$-stationary point are proved to be
$\mathcal{O}(\varepsilon ^{-2})$ (resp. $\mathcal{O}(\varepsilon ^{-4})$) for
solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems
with coupled linear constraints under deterministic settings and
$\tilde{\mathcal{O}}(\varepsilon ^{-3})$ (resp.
$\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$) under stochastic settings
respectively. To the best of our knowledge, they are the first two zeroth-order
algorithms with iterative complexity guarantees for solving
nonconvex-(strongly) concave minimax problems with coupled linear constraints
under the deterministic and stochastic settings.
- Abstract（参考訳）: 本稿では,近年,機械学習や信号処理,その他多くの分野,例えば資源割当問題やネットワークフロー問題などにおいて広く注目されている,決定論的・確率的設定の下で線形制約を結合した非凸ミニマックス問題に対するゼロ次アルゴリズムについて検討する。
線形制約を結合したミニマックス問題を決定論的・確率的非凸(強)に解くために,ゼロ次原始二乗交互射影勾配アルゴリズム (ZO-PDAPG) とゼロ次正規化運動量原始二乗射影勾配アルゴリズム (ZO-RMPDPG) の2つの単一ループアルゴリズムを提案する。
提案した2つのアルゴリズムの反復複雑性を$\varepsilon$-stationary point とし、$\mathcal{O}(\varepsilon ^{-2})$ (resp) とする。
非凸強凸(非凸凸凸)のミニマックス問題を解くための$\mathcal{o}(\varepsilon ^{-4})$ (resp. nonconvex-concave) 決定論的設定と$\tilde{\mathcal{o}}(\varepsilon ^{-3})$ (resp.nonconvex-concave) である。
確率的な設定でそれぞれ$\tilde{\mathcal{o}}(\varepsilon ^{-6.5})$) となる。
我々の知る限り、これらのアルゴリズムは、決定論的および確率的設定の下で線形制約を結合したミニマックス問題を解くための反復的な複雑性保証を持つ最初の2つのゼロ階アルゴリズムである。
関連論文リスト
- An accelerated first-order regularized momentum descent ascent algorithm
for stochastic nonconvex-concave minimax problems [0.5801621787540265]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(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 [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 [4.70696854954921]
非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。
そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-09T05:32:30Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。