論文の概要: Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex
Optimization
- arxiv url: http://arxiv.org/abs/2010.01449v2
- Date: Sun, 14 Feb 2021 20:06:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 03:04:21.215274
- Title: Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex
Optimization
- Title(参考訳): 非凸最適化における重球運動量による良性領域の探索
- Authors: Jun-Kun Wang and Jacob Abernethy
- Abstract要約: 重球法は連続関数を最適化する一階法である。
重球運動量は,大域的最適点を高速に含む良性相に入るのに役立つことを示す。
- 参考スコア(独自算出の注目度): 8.452237741722724
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Heavy Ball Method, proposed by Polyak over five decades ago, is a
first-order method for optimizing continuous functions. While its stochastic
counterpart has proven extremely popular in training deep networks, there are
almost no known functions where deterministic Heavy Ball is provably faster
than the simple and classical gradient descent algorithm in non-convex
optimization. The success of Heavy Ball has thus far eluded theoretical
understanding. Our goal is to address this gap, and in the present work we
identify two non-convex problems where we provably show that the Heavy Ball
momentum helps the iterate to enter a benign region that contains a global
optimal point faster. We show that Heavy Ball exhibits simple dynamics that
clearly reveal the benefit of using a larger value of momentum parameter for
the problems. The first of these optimization problems is the phase retrieval
problem, which has useful applications in physical science. The second of these
optimization problems is the cubic-regularized minimization, a critical
subroutine required by Nesterov-Polyak cubic-regularized method to find
second-order stationary points in general smooth non-convex problems.
- Abstract(参考訳): 5年以上前にPolyakによって提案されたヘビーボール法は、連続関数を最適化するための一階法である。
その確率論的対向はディープネットワークのトレーニングで非常に人気があるが、非凸最適化における単純で古典的な勾配降下アルゴリズムよりも決定論的に高速な関数はほとんど知られていない。
ヘビーボールの成功は、これまで理論的な理解を解き明かしてきた。
我々の目標は、このギャップに対処することであり、本研究では、重いボールの運動量が、地球的最適点を含む良性領域に入るのに役立つことを示す2つの非凸問題を特定する。
ヘビーボールは,問題に対する運動量パラメータの値が大きいことの利点を明らかにする,単純なダイナミクスを示す。
これらの最適化問題の第一は位相検索問題であり、物理科学に有用な応用がある。
これらの最適化問題の2つ目は立方正則化最小化であり、これは一般に滑らかな非凸問題において二階定常点を見つけるためにネステロフ・ポリアク立方正則化法が要求する臨界部分ルーチンである。
関連論文リスト
- Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
過度にパラメータ化された状態における深度最適化のための最近の線探索手法と運動量方向との関係について検討する。
モーメントパラメータの定義にデータ持続性、共役型ルールの混合を利用するアルゴリズムを導入する。
結果のアルゴリズムは、他の一般的な手法よりも優れていることを実証的に示している。
論文 参考訳(メタデータ) (2024-11-11T16:26:33Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳(メタデータ) (2023-04-23T20:05:09Z) - Provable Acceleration of Heavy Ball beyond Quadratics for a Class of
Polyak-\L{}ojasiewicz Functions when the Non-Convexity is Averaged-Out [27.885807991400377]
現在、ヘビーボール(HB)は非動的最適化において最も一般的な運動量法の一つである。
本研究では,2次数を超える加速度を示す新しい手法を開発した。
二次数を超える HB の加速結果に対して、追加条件を満たす必要がある。
論文 参考訳(メタデータ) (2022-06-22T17:47:41Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - The Role of Momentum Parameters in the Optimal Convergence of Adaptive
Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。
新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文 参考訳(メタデータ) (2021-02-15T02:57:14Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳(メタデータ) (2020-12-11T08:28:51Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。