論文の概要: Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems
- arxiv url: http://arxiv.org/abs/2108.00473v5
- Date: Thu, 25 Jan 2024 15:15:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-26 19:11:42.134473
- Title: Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems
- Title（参考訳）: 一般非凸凸ミニマックス問題に対する微分自由交互射影アルゴリズム
- Authors: Zi Xu, Ziqi Wang, Jingjing Shen, Yuhong Dai
- Abstract要約: 本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
- 参考スコア（独自算出の注目度）: 9.173866646584031
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study zeroth-order algorithms for nonconvex-concave minimax
problems, which have attracted widely attention in machine learning, signal
processing and many other fields in recent years. We propose a zeroth-order
alternating randomized gradient projection (ZO-AGP) algorithm for smooth
nonconvex-concave minimax problems, and its iteration complexity to obtain an
$\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$,
and the number of function value estimation is bounded by
$\mathcal{O}(d_{x}+d_{y})$ per iteration. Moreover, we propose a zeroth-order
block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving
block-wise nonsmooth nonconvex-concave minimax optimization problems, and the
iteration complexity to obtain an $\varepsilon$-stationary point is bounded by
$\mathcal{O}(\varepsilon^{-4})$ and the number of function value estimation per
iteration is bounded by $\mathcal{O}(K d_{x}+d_{y})$. To the best of our
knowledge, this is the first time that zeroth-order algorithms with iteration
complexity gurantee are developed for solving both general smooth and
block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on
data poisoning attack problem and distributed nonconvex sparse principal
component analysis problem validate the efficiency of the proposed algorithms.
- Abstract（参考訳）: 本稿では,近年,機械学習,信号処理,その他多くの分野で注目されている非凸凹ミニマックス問題に対するゼロ次アルゴリズムについて検討する。
我々は,滑らかな非凸凸凸ミニマックス問題に対するゼロ次交互ランダム勾配投影(zo-agp)アルゴリズムを提案し,その反復複雑性から$\varepsilon$-stationary point を得るには$\mathcal{o}(\varepsilon^{-4})$ を条件とし,関数値推定の回数を$\mathcal{o}(d_{x}+d_{y})$ とする。
さらに,ブロック方向非滑らかな非凸凸凸型ミニマックス最適化問題を解くために,ゼロ次ブロック交互なランダムな近位勾配アルゴリズム (zo-bapg) を提案し,$\varepsilon$-stationary point を得るための反復複雑性を$\mathcal{o}(\varepsilon^{-4})$ で制限し,各イテレーション当たりの関数値推定数は$\mathcal{o}(k d_{x}+d_{y})$で制限する。
我々の知る限りでは、一般にスムーズかつブロックワイズ非滑らかな非凸凹極小問題を解くため、反復複雑性を保証したゼロ階アルゴリズムが開発されたのはこれが初めてである。
データ中毒攻撃問題と分散非凸スパース主成分分析問題に関する数値結果は,提案アルゴリズムの有効性を検証する。
関連論文リスト
- Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
提案手法は,非強弱畳み込みミニマックス問題の解法である。
本稿では,提案アルゴリズムが$mathcalを達成することを示す。
スティロン
2階ノルムは上向きであることが証明されている。
tk
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
$k
論文 参考訳（メタデータ） (2024-11-24T09:46:36Z) - 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) - 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。