論文の概要: Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2008.01296v3
• Date: Mon, 10 Aug 2020 03:20:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-02 23:22:44.985250
• Title: Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
• Title（参考訳）: 非凸最適化のための乗算器の高速確率交互方向法
• Authors: Feihu Huang, Songcan Chen, Heng Huang
• Abstract要約: 本稿では、SPADMMと呼ばれる新しい経路を用いて、非積分最適化のための乗算器の高速な交互方向(ADMM)を提案する。 我々は,SPADMMが1次微分オラクル推定器 (IFO) を達成し,IFOの記録を求める。 我々は,オンラインSPIDER-ADMMがIFOFO(epsilon)を$mathcalO(n1)$の係数で持つことを示した。
• 参考スコア（独自算出の注目度）: 110.52708815647613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a faster stochastic alternating direction method of multipliers (ADMM) for nonconvex optimization by using a new stochastic path-integrated differential estimator (SPIDER), called as SPIDER-ADMM. Moreover, we prove that the SPIDER-ADMM achieves a record-breaking incremental first-order oracle (IFO) complexity of $\mathcal{O}(n+n^{1/2}\epsilon^{-1})$ for finding an $\epsilon$-approximate stationary point, which improves the deterministic ADMM by a factor $\mathcal{O}(n^{1/2})$, where $n$ denotes the sample size. As one of major contribution of this paper, we provide a new theoretical analysis framework for nonconvex stochastic ADMM methods with providing the optimal IFO complexity. Based on this new analysis framework, we study the unsolved optimal IFO complexity of the existing non-convex SVRG-ADMM and SAGA-ADMM methods, and prove they have the optimal IFO complexity of $\mathcal{O}(n+n^{2/3}\epsilon^{-1})$. Thus, the SPIDER-ADMM improves the existing stochastic ADMM methods by a factor of $\mathcal{O}(n^{1/6})$. Moreover, we extend SPIDER-ADMM to the online setting, and propose a faster online SPIDER-ADMM. Our theoretical analysis shows that the online SPIDER-ADMM has the IFO complexity of $\mathcal{O}(\epsilon^{-\frac{3}{2}})$, which improves the existing best results by a factor of $\mathcal{O}(\epsilon^{-\frac{1}{2}})$. Finally, the experimental results on benchmark datasets validate that the proposed algorithms have faster convergence rate than the existing ADMM algorithms for nonconvex optimization.
• Abstract（参考訳）: 本稿では,SPIDER-ADMMと呼ばれる新しい確率パス積分微分推定器(SPIDER)を用いて,非凸最適化のための高速な確率交互方向法を提案する。 さらに、SPIDER-ADMMは、$\mathcal{O}(n+n^{1/2}\epsilon^{-1})$を$\epsilon$-approximate固定点を求めるために、記録破りのインクリメンタルな1次オラクル(IFO)複雑性を達成し、$n$はサンプルサイズを表す$\mathcal{O}(n^{1/2})$によって決定論的ADMMを改善することを証明している。 本稿では,非凸確率ADMM法に対する新たな理論的解析フレームワークを提案する。 この新しい解析枠組みに基づき,既存の非凸svrg-admm法とsaga-admm法の未解決の最適ifo複雑性を調べ,$\mathcal{o}(n+n^{2/3}\epsilon^{-1}) の最適ifo複雑性を証明した。 したがって、SPIDER-ADMMは既存の確率ADMM法を$\mathcal{O}(n^{1/6})$で改善する。 さらに,SPIDER-ADMMをオンライン環境に拡張し,より高速なオンラインSPIDER-ADMMを提案する。 我々の理論分析によると、オンラインSPIDER-ADMMは、$\mathcal{O}(\epsilon^{-\frac{3}{2}})$のIFO複雑性を持ち、$\mathcal{O}(\epsilon^{-\frac{1}{2}})$の係数で既存の最良の結果を改善する。 最後に,提案アルゴリズムは非凸最適化のための既存のADMMアルゴリズムよりも収束速度が速いことを示す。

関連論文リスト

• 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)
• A Convergent ADMM Framework for Efficient Neural Network Training [17.764095204676973]
  乗算器の交互方向法(ADMM)は多くの分類と回帰の応用において大きな成功を収めた。 本稿では,ADMM (dlADMM) を用いてニューラルネットワークの一般的なトレーニング問題を同時に解くための新しい枠組みを提案する。 提案したdlADMMアルゴリズムの収束, 効率, 有効性を示す7つのベンチマークデータセットの実験を行った。
  論文  参考訳（メタデータ） (2021-12-22T01:55:24Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization [21.81837334970773]
  本稿では,予測最大化(EM)アルゴリズムへのパス付き微分エスティマの拡張を提案する。 SPIDER-EM-IDERと同じ状態アート境界をサポートし,その結果を得た。
  論文  参考訳（メタデータ） (2020-11-24T21:20:53Z)
• Differentially Private ADMM Algorithms for Machine Learning [38.648113004535155]
  勾配摂動による乗算器(ADMM)の高効率な個人交互方向法について検討した。 差分型ADMM(DP-ADMM)アルゴリズムを提案し,性能保証を$(epsilon,delta)$-differential privacy とする。
  論文  参考訳（メタデータ） (2020-10-31T01:37:24Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)
• 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)

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

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