論文の概要: 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}})$の係数で既存の最良の結果を改善する。 ブラックボックス深層ニューラルネットワークの構造逆攻撃に関する広範囲な実験結果から,新しいアルゴリズムの有効性が示された。

関連論文リスト

• 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)
• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。 本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
  論文  参考訳（メタデータ） (2024-05-20T02:24:58Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。