論文の概要: 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つのゼロ階アルゴリズムである。
関連論文リスト
- 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.5801621787540265]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(FORMDA)を高速化する。
有界アルゴリズムの最大の複雑さは、客観性関数の停止下での非可逆ミニマックス問題の解法である。
論文 参考訳(メタデータ) (2023-10-24T01:45:11Z) - 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) - 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) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth
Nonconvex Minimax Problems with Coupled Linear Constraints [5.142024994067472]
近年,機械学習や信号処理の分野では,非数学的ミニマックス問題に注目が集まっている。
線形制約を用いた非ミニマックス点数問題の解法として,複雑性保証付き2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。