論文の概要: Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class
of Nonconvex-Nonconcave Minimax Problems
- arxiv url: http://arxiv.org/abs/2211.13668v1
- Date: Thu, 24 Nov 2022 15:34:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 15:41:28.394531
- Title: Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class
of Nonconvex-Nonconcave Minimax Problems
- Title（参考訳）: 非凸非凸ミニマックス問題の零次交互勾配降下上昇アルゴリズム
- Authors: Zi Xu, Zi-Qi Wang, Jun-Lin Wang, Yu-Hong Dai
- Abstract要約: 内部変数に関して、ポリアック-$L$ojasiewicz (PL) 条件を満たす非コンケーブミニマックス問題のクラスを考える。
NC-PLミニマックス問題の解法としてゼロ階交互降下法(ZO-AGDA)を提案する。
NC-PLミニマックス問題の解法としてZO-AGDAとZO-VRAGDAの$epsilon$stationary pointを求める反復数は$mathcalO-2)$mathcalOで上界される
- 参考スコア（独自算出の注目度）: 9.792800635198935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a class of nonconvex-nonconcave minimax problems,
i.e., NC-PL minimax problems, whose objective functions satisfy the
Polyak-$\L$ojasiewicz (PL) condition with respect to the inner variable. We
propose a zeroth-order alternating gradient descent ascent (ZO-AGDA) algorithm
and a zeroth-order variance reduced alternating gradient descent ascent
(ZO-VRAGDA) algorithm for solving NC-PL minimax problem under the deterministic
and the stochastic setting, respectively. The number of iterations to obtain an
$\epsilon$-stationary point of ZO-AGDA and ZO-VRAGDA algorithm for solving
NC-PL minimax problem is upper bounded by $\mathcal{O}(\varepsilon^{-2})$ and
$\mathcal{O}(\varepsilon^{-3})$, respectively. To the best of our knowledge,
they are the first two zeroth-order algorithms with the iteration complexity
gurantee for solving NC-PL minimax problems.
- Abstract（参考訳）: 本稿では,非凸非凸ミニマックス問題(nc-plミニマックス問題)のクラスを考察し,その対象関数が内部変数に対して polyak-$\l$ojasiewicz (pl) 条件を満たすことを考察する。
本稿では, NC-PL極小問題を決定論的および確率論的条件下で解くため, ゼロ次交互勾配勾配勾配上昇(ZO-AGDA)アルゴリズムとゼロ次分散低減勾配勾配上昇(ZO-VRAGDA)アルゴリズムを提案する。
ZO-AGDA と ZO-VRAGDA の NC-PL minimax 問題を解くための$\epsilon$-stationary point を得るための反復数は、それぞれ $\mathcal{O}(\varepsilon^{-2})$ と $\mathcal{O}(\varepsilon^{-3})$ で上限づけられる。
我々の知る限りでは、NC-PLミニマックス問題を解くための反復複雑性を保証した最初の2つのゼロ階アルゴリズムである。
関連論文リスト
- 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) - Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。
本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。
我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
論文 参考訳（メタデータ） (2023-10-05T15:48:41Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。
そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-09T05:32:30Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。