論文の概要: Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity
- arxiv url: http://arxiv.org/abs/1907.13463v4
- Date: Mon, 11 Dec 2023 06:13:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-13 03:53:50.115520
- Title: Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity
- Title(参考訳): 非凸ゼロ階確率ADMM法
- Authors: Feihu Huang, Shangqian Gao, Jian Pei and Heng Huang
- Abstract要約: ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
- 参考スコア(独自算出の注目度): 109.54166127479093
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Zeroth-order (a.k.a, derivative-free) methods are a class of effective
optimization methods for solving complex machine learning problems, where
gradients of the objective functions are not available or computationally
prohibitive. Recently, although many zeroth-order methods have been developed,
these approaches still have two main drawbacks: 1) high function query
complexity; 2) not being well suitable for solving the problems with complex
penalties and constraints. To address these challenging drawbacks, in this
paper, we propose a class of faster zeroth-order stochastic alternating
direction method of multipliers (ADMM) methods (ZO-SPIDER-ADMM) to solve the
nonconvex finite-sum problems with multiple nonsmooth penalties. Moreover, we
prove that the ZO-SPIDER-ADMM methods can achieve a lower function query
complexity of $O(nd+dn^{\frac{1}{2}}\epsilon^{-1})$ for finding an
$\epsilon$-stationary point, which improves the existing best nonconvex
zeroth-order ADMM methods by a factor of $O(d^{\frac{1}{3}}n^{\frac{1}{6}})$,
where $n$ and $d$ denote the sample size and data dimension, respectively. At
the same time, we propose a class of faster zeroth-order online ADMM methods
(ZOO-ADMM+) to solve the nonconvex online problems with multiple nonsmooth
penalties. We also prove that the proposed ZOO-ADMM+ methods achieve a lower
function query complexity of $O(d\epsilon^{-\frac{3}{2}})$, which improves the
existing best result by a factor of $O(\epsilon^{-\frac{1}{2}})$. Extensive
experimental results on the structure adversarial attack on black-box deep
neural networks demonstrate the efficiency of our new algorithms.
- Abstract(参考訳): ゼロ階数法(英: Zeroth-order method、つまり微分自由法)は、複雑な機械学習問題を解決するための効果的な最適化手法のクラスである。
近年,ゼロ次法が多数開発されているが,その欠点は2つある。
1) 高機能クエリの複雑さ
2)複雑な罰則や制約で問題を解決するには適していない。
本稿では,これらの難解な欠点に対処するため,マルチプライヤ法(zo-spider-admm)のゼロ次確率的交互方向法を高速化し,非スムースペナルティの非凸有限サム問題を解く手法を提案する。
さらに、zo-spider-admm メソッドは $o(nd+dn^{\frac{1}{2}}\epsilon^{-1})$ という関数クエリの複雑さを低下させることを証明し、ここでは $n$ と $d$ はそれぞれサンプルサイズとデータ次元を表す$o(d^{\frac{1}{3}}n^{\frac{1}{6}}) という係数で、既存の最良の非凸零次 admm メソッドを改善する$\epsilon$-stationary point を求める。
同時に,複数の非スムースペナルティを伴う非凸オンライン問題を解くために,より高速なゼロ次オンラインadmm法(zoo-admm+)を提案する。
また、提案したZOO-ADMM+メソッドは、$O(d\epsilon^{-\frac{3}{2}})$の低い関数クエリ複雑性を実現し、$O(\epsilon^{-\frac{1}{2}})$の係数で既存の最良の結果を改善する。
ブラックボックス深層ニューラルネットワークの構造逆攻撃に関する広範囲な実験結果から,新しいアルゴリズムの有効性が示された。
関連論文リスト
- Certified Multi-Fidelity Zeroth-Order Optimization [0.0]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
我々は、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundを証明した。
論文 参考訳(メタデータ) (2023-08-02T07:20:37Z) - Stochastic Distributed Optimization under Average Second-order
Similarity: Algorithms and Analysis [36.646876613637325]
マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。
本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T08:18:47Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳(メタデータ) (2021-06-21T20:16:40Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - Faster Stochastic Alternating Direction Method of Multipliers for
Nonconvex Optimization [110.52708815647613]
本稿では、SPADMMと呼ばれる新しい経路を用いて、非積分最適化のための乗算器の高速な交互方向(ADMM)を提案する。
我々は,SPADMMが1次微分オラクル推定器 (IFO) を達成し,IFOの記録を求める。
我々は,オンラインSPIDER-ADMMがIFOFO(epsilon)を$mathcalO(n1)$の係数で持つことを示した。
論文 参考訳(メタデータ) (2020-08-04T02:59:42Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。