論文の概要: Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization
- arxiv url: http://arxiv.org/abs/2008.08170v7
- Date: Mon, 17 Jan 2022 01:35:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 21:21:09.288091
- Title: Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization
- Title（参考訳）: ミニからミニマックス最適化へのゼロ階乗法と1階乗法
- Authors: Feihu Huang, Shangqian Gao, Jian Pei, Heng Huang
- Abstract要約: そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。
一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。
特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
- 参考スコア（独自算出の注目度）: 133.53164856723782
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In the paper, we propose a class of accelerated zeroth-order and first-order
momentum methods for both nonconvex mini-optimization and minimax-optimization.
Specifically, we propose a new accelerated zeroth-order momentum (Acc-ZOM)
method for black-box mini-optimization where only function values can be
obtained. Moreover, we prove that our Acc-ZOM method achieves a lower query
complexity of $\tilde{O}(d^{3/4}\epsilon^{-3})$ for finding an
$\epsilon$-stationary point, which improves the best known result by a factor
of $O(d^{1/4})$ where $d$ denotes the variable dimension. In particular, our
Acc-ZOM does not need large batches required in the existing zeroth-order
stochastic algorithms. Meanwhile, we propose an accelerated zeroth-order
momentum descent ascent (Acc-ZOMDA) method for black-box minimax optimization,
where only function values can be obtained. Our Acc-ZOMDA obtains a low query
complexity of $\tilde{O}((d_1+d_2)^{3/4}\kappa_y^{4.5}\epsilon^{-3})$ without
requiring large batches for finding an $\epsilon$-stationary point, where $d_1$
and $d_2$ denote variable dimensions and $\kappa_y$ is condition number.
Moreover, we propose an accelerated first-order momentum descent ascent
(Acc-MDA) method for minimax optimization, whose explicit gradients are
accessible. Our Acc-MDA achieves a low gradient complexity of
$\tilde{O}(\kappa_y^{4.5}\epsilon^{-3})$ without requiring large batches for
finding an $\epsilon$-stationary point. In particular, our Acc-MDA can obtain a
lower gradient complexity of $\tilde{O}(\kappa_y^{2.5}\epsilon^{-3})$ with a
batch size $O(\kappa_y^4)$, which improves the best known result by a factor of
$O(\kappa_y^{1/2})$. Extensive experimental results on black-box adversarial
attack to deep neural networks and poisoning attack to logistic regression
demonstrate efficiency of our algorithms.
- Abstract（参考訳）: 本稿では,非凸極小最適化と最小極小最適化の双方に対して,加速ゼロ階法と一階運動量法を提案する。
具体的には、関数値のみが得られるブラックボックス最小最適化のための新しい加速零次運動量(acc-zom)法を提案する。
さらに、このacc-zom法は、$\epsilon$-stationary pointを見つけるために$\tilde{o}(d^{3/4}\epsilon^{-3})$という低いクエリ複雑さを達成することを証明します。
特に、Acc-ZOMは、既存のゼロ階確率アルゴリズムに必要な大きなバッチを必要としない。
一方,関数値のみが得られるブラックボックスミニマックス最適化のための高速化されたゼロ次運動量降下上昇法(acc-zomda)を提案する。
acc-zomda は $\tilde{o}((d_1+d_2)^{3/4}\kappa_y^{4.5}\epsilon^{-3})$ という低いクエリ複雑さを得ることができ、ここで $d_1$ と $d_2$ は変数次元を表し、$\kappa_y$ は条件数である。
また,Acc-MDA法を極小最適化のための高速化した1次運動量降下法を提案する。
我々のAcc-MDAは、$\epsilon$-stationary点を見つけるために大きなバッチを必要とすることなく、$\tilde{O}(\kappa_y^{4.5}\epsilon^{-3})$の低勾配の複雑性を達成する。
特に、我々のacc-mdaは、バッチサイズ$o(\kappa_y^4)$で$\tilde{o}(\kappa_y^{2.5}\epsilon^{-3})$という低い勾配複雑性を得ることができる。
ディープニューラルネットワークに対するブラックボックス逆攻撃とロジスティック回帰に対する中毒攻撃の広範な実験結果から,アルゴリズムの効率性が証明された。
関連論文リスト
- An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - 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) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
ミニマックス問題を解くためのリーマン的手法のクラスを提案する。
我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。
また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
論文 参考訳（メタデータ） (2020-10-13T00:54:00Z) - Accelerated Stochastic Gradient-free and Projection-free Methods [37.15461647823691]
本稿では,STORMの新たな分散化手法に基づいて,ゼロオーダーのFrank-Wolfe (Acc-SZOFW) を提案する。
Acc-SZOFWで必要とされる大きなバッチを緩和するために、新しいSTORMの分散化技術に基づいて、ゼロ階のフランク・ウルフ(Acc-SZOFW*)を高速化する手法を提案する。
論文 参考訳（メタデータ） (2020-07-16T20:50:15Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。