論文の概要: Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity

• arxiv url: http://arxiv.org/abs/2201.11411v4
• Date: Wed, 26 Apr 2023 02:17:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-27 18:44:11.441899
• Title: Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity
• Title（参考訳）: 再開された非凸型加速勾配降下:$o(\epsilon^{-7/4})$複雑性の多対数因子
• Authors: Huan Li and Zhouchen Lin
• Abstract要約: 本稿では,2つの単純な加速勾配法,再発進勾配降下法(AGD)と再発進球法(HB)を提案する。 我々は、我々の手法が$frac1epsilon)$の勾配反復数を達成することを確証する。 我々のアルゴリズムは、ネストフの古典的なAGDオークのHBと再起動機構のみからなるという意味では単純である。
• 参考スコア（独自算出の注目度）: 70.65867695317633
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies accelerated gradient methods for nonconvex optimization with Lipschitz continuous gradient and Hessian. We propose two simple accelerated gradient methods, restarted accelerated gradient descent (AGD) and restarted heavy ball (HB) method, and establish that our methods achieve an $\epsilon$-approximate first-order stationary point within $O(\epsilon^{-7/4})$ number of gradient evaluations by elementary proofs. Theoretically, our complexity does not hide any polylogarithmic factors, and thus it improves over the best known one by the $O(\log\frac{1}{\epsilon})$ factor. Our algorithms are simple in the sense that they only consist of Nesterov's classical AGD or Polyak's HB iterations, as well as a restart mechanism. They do not invoke negative curvature exploitation or minimization of regularized surrogate functions as the subroutines. In contrast with existing analysis, our elementary proofs use less advanced techniques and do not invoke the analysis of strongly convex AGD or HB. Code is avaliable at https://github.com/lihuanML/RestartAGD.
• Abstract（参考訳）: 本稿では,リプシッツ連続勾配とヘシアンを用いた非凸最適化のための勾配法を高速化する。 本稿では,2つの簡単な加速勾配法,再加速勾配降下法(AGD)と再始動重球法(HB)を提案し,初等証明による勾配評価の回数を$O(\epsilon^{-7/4})で$\epsilon$-approximate 1次定常点とすることを確認した。 理論的には、我々の複雑性はいかなる多相因子も隠さないので、$O(\log\frac{1}{\epsilon})$ factorによって最もよく知られた因子よりも改善される。 我々のアルゴリズムは、Nesterovの古典的なAGDまたはPolyakのHBイテレーションと再起動メカニズムのみで構成されているという意味では単純である。 彼らは負の曲率利用や正規化された代理関数の最小化をサブルーチンとして起こさない。 既存の解析とは対照的に,我々の初等証明はより高度な手法を用いており,強い凸 AGD や HB の分析は行わない。 コードはhttps://github.com/lihuanml/restartagdで評価できる。

関連論文リスト

• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。 また、あるSGDの変種に対する新しい境界を得ることもできる。
  論文  参考訳（メタデータ） (2022-05-27T07:23:01Z)
• ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally! [6.170898159041277]
  ProxSkipは、スムーズな(f$)関数と高価な非滑らかな(psi$)関数の和を最小化する驚くほどシンプルで、証明可能な効率のよい方法である。 我々の主な動機は、勾配演算子の評価が、すべてのデバイスで独立して局所的なGDステップを取ることに対応する、連合学習にある。
  論文  参考訳（メタデータ） (2022-02-18T18:56:05Z)
• Escape saddle points by a simple gradient-descent based algorithm [6.7298812735467095]
  非最適化において、サドルポイントのエスケープは中心的な研究トピックである。 滑らかな関数 $fcolonmathbbRntomathbbR$ に対して、$epsilonO(log n)2/epsilon4)$ を出力する。 技術的に、我々の主な貢献は勾配のみを用いたロバストなヘッセンパワー手法の実装である。
  論文  参考訳（メタデータ） (2021-11-28T07:32:54Z)
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
  局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。 SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。 我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
  論文  参考訳（メタデータ） (2021-10-25T07:20:05Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond [25.845034951660544]
  我々は,一階述語法では改善できないことを示した。 我々は、$$quasar のアログ関数を計算する変種加速降下を開発する。 ファーストオーダーの方法では改善できません。
  論文  参考訳（メタデータ） (2019-06-27T22:39:35Z)

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

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