論文の概要: Accelerated Stochastic Gradient-free and Projection-free Methods
- arxiv url: http://arxiv.org/abs/2007.12625v2
- Date: Mon, 10 Aug 2020 15:45:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 23:09:45.130390
- Title: Accelerated Stochastic Gradient-free and Projection-free Methods
- Title（参考訳）: 確率勾配フリーおよび射影フリーの高速化
- Authors: Feihu Huang, Lue Tao, Songcan Chen
- Abstract要約: 本稿では,STORMの新たな分散化手法に基づいて,ゼロオーダーのFrank-Wolfe (Acc-SZOFW) を提案する。
Acc-SZOFWで必要とされる大きなバッチを緩和するために、新しいSTORMの分散化技術に基づいて、ゼロ階のフランク・ウルフ(Acc-SZOFW*)を高速化する手法を提案する。
- 参考スコア（独自算出の注目度）: 37.15461647823691
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the paper, we propose a class of accelerated stochastic gradient-free and
projection-free (a.k.a., zeroth-order Frank-Wolfe) methods to solve the
constrained stochastic and finite-sum nonconvex optimization. Specifically, we
propose an accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW) method
based on the variance reduced technique of SPIDER/SpiderBoost and a novel
momentum accelerated technique. Moreover, under some mild conditions, we prove
that the Acc-SZOFW has the function query complexity of
$O(d\sqrt{n}\epsilon^{-2})$ for finding an $\epsilon$-stationary point in the
finite-sum problem, which improves the exiting best result by a factor of
$O(\sqrt{n}\epsilon^{-2})$, and has the function query complexity of
$O(d\epsilon^{-3})$ in the stochastic problem, which improves the exiting best
result by a factor of $O(\epsilon^{-1})$. To relax the large batches required
in the Acc-SZOFW, we further propose a novel accelerated stochastic
zeroth-order Frank-Wolfe (Acc-SZOFW*) based on a new variance reduced technique
of STORM, which still reaches the function query complexity of
$O(d\epsilon^{-3})$ in the stochastic problem without relying on any large
batches. In particular, we present an accelerated framework of the Frank-Wolfe
methods based on the proposed momentum accelerated technique. The extensive
experimental results on black-box adversarial attack and robust black-box
classification demonstrate the efficiency of our algorithms.
- Abstract（参考訳）: 本稿では,制約付き確率的・有限和非凸最適化を解くために,確率的勾配なし・投影不要(すなわちゼロ次フランクウルフ)法のクラスを提案する。
具体的には、SPIDER/SpiderBoostの分散低減技術と新しい運動量加速技術に基づいて、確率ゼロ階Frank-Wolfe(Acc-SZOFW)法を提案する。
さらに,いくつかの穏やかな条件下では, acc-szofw の関数クエリの複雑性が $o(d\sqrt{n}\epsilon^{-2})$ であることが証明され, 有限サム問題において $\epsilon$-stationary point を見つけるために,$o(\sqrt{n}\epsilon^{-2})$ の係数で最良値が向上し, 確率問題において $o(d\epsilon^{-3})$ の関数クエリの複雑さが証明され,$o(\epsilon^{-1})$ の係数によって最良値が向上する。
acc-szofwで必要とされる大きなバッチを緩和するために、我々はさらに、大きなバッチに頼らずに確率問題において、関数クエリの複雑性が$o(d\epsilon^{-3})$に達する、stormの新しい分散削減技術に基づいて、新しい加速確率確率確率的ゼロ次frank-wolfe (acc-szofw*)を提案する。
特に,提案手法に基づくFrank-Wolfe手法の高速化フレームワークを提案する。
ブラックボックス攻撃とロバストブラックボックス分類の広範な実験結果から,アルゴリズムの有効性が示された。
関連論文リスト
- A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization [3.8919212824749296]
提案したSFOMは,目的関数の高次滑らか度を$f$とすることで,最適化を高速化できることを示す。
我々の知る限りでは、これは対象関数の任意の次スムーズネスを加速度に利用した最初のSFOMである。
論文 参考訳（メタデータ） (2024-12-19T03:22:47Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization [133.53164856723782]
そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。
一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。
特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
論文 参考訳（メタデータ） (2020-08-18T22:19:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。