論文の概要: Faster Perturbed Stochastic Gradient Methods for Finding Local Minima

• arxiv url: http://arxiv.org/abs/2110.13144v1
• Date: Mon, 25 Oct 2021 07:20:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-27 14:17:53.975280
• Title: Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Title（参考訳）: 局所最小値探索のための高速摂動確率勾配法
• Authors: Zixiang Chen and Dongruo Zhou and Quanquan Gu
• Abstract要約: 局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。 SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。 我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
• 参考スコア（独自算出の注目度）: 92.99933928528797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Escaping from saddle points and finding local minima is a central problem in nonconvex optimization. Perturbed gradient methods are perhaps the simplest approach for this problem. However, to find $(\epsilon, \sqrt{\epsilon})$-approximate local minima, the existing best stochastic gradient complexity for this type of algorithms is $\tilde O(\epsilon^{-3.5})$, which is not optimal. In this paper, we propose \texttt{Pullback}, a faster perturbed stochastic gradient framework for finding local minima. We show that Pullback with stochastic gradient estimators such as SARAH/SPIDER and STORM can find $(\epsilon, \epsilon_{H})$-approximate local minima within $\tilde O(\epsilon^{-3} + \epsilon_{H}^{-6})$ stochastic gradient evaluations (or $\tilde O(\epsilon^{-3})$ when $\epsilon_H = \sqrt{\epsilon}$). The core idea of our framework is a step-size ``pullback'' scheme to control the average movement of the iterates, which leads to faster convergence to the local minima. Experiments on matrix factorization problems corroborate our theory.
• Abstract（参考訳）: サドルポイントから逃れて局所ミニマを見つけることは、非凸最適化における中心的な問題である。 摂動勾配法はおそらくこの問題の最も単純な方法である。 しかし、(\epsilon, \sqrt{\epsilon})$-approximate local minimaを見つけるには、このタイプのアルゴリズムの既存の最良の確率的勾配複雑性は$\tilde o(\epsilon^{-3.5})$であり、最適ではない。 本稿では,局所極小を見つけるためのより高速な摂動確率勾配フレームワークである \texttt{pullback} を提案する。 SARAH/SPIDER や STORM のような確率勾配推定器を用いたプルバックは$(\epsilon, \epsilon_{H})$-approximate local minima in $\tilde O(\epsilon^{-3} + \epsilon_{H}^{-6})$ stochastic gradient evaluations (または $\tilde O(\epsilon^{-3})$ if $\epsilon_H = \sqrt{\epsilon}$) で得られることを示す。 我々のフレームワークの中核となる考え方は、反復体の平均運動を制御するステップサイズ ``pullback'' スキームであり、局所ミニマへのより高速な収束をもたらす。 行列分解問題の実験は我々の理論を裏付ける。

関連論文リスト

• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
  論文  参考訳（メタデータ） (2022-11-29T18:38:40Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
  サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
  論文  参考訳（メタデータ） (2021-03-29T23:03:24Z)
• 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)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
  本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。 この方法はこの問題でよく知られている。
  論文  参考訳（メタデータ） (2020-01-11T09:05:03Z)

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

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