論文の概要: Accelerated gradient methods for nonconvex optimization: Escape
trajectories from strict saddle points and convergence to local minima
- arxiv url: http://arxiv.org/abs/2307.07030v1
- Date: Thu, 13 Jul 2023 19:11:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-17 15:39:58.532501
- Title: Accelerated gradient methods for nonconvex optimization: Escape
trajectories from strict saddle points and convergence to local minima
- Title（参考訳）: 非凸最適化のための加速勾配法:厳密な鞍点からの脱出軌道と局所ミニマへの収束
- Authors: Rishabh Dixit, Mert Gurbuzbalaban, and Waheed U. Bajwa
- Abstract要約: 本稿ではその問題を考察する。
加速勾配法の一般一般の凸挙動を理解すること。
非アプティック関数。
これは、運動量可変ネステロフの加速法(NAG)が、厳密なサドル点をほぼ確実に避けていることを示している。
- 参考スコア（独自算出の注目度）: 9.66353475649122
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the problem of understanding the behavior of a general
class of accelerated gradient methods on smooth nonconvex functions. Motivated
by some recent works that have proposed effective algorithms, based on Polyak's
heavy ball method and the Nesterov accelerated gradient method, to achieve
convergence to a local minimum of nonconvex functions, this work proposes a
broad class of Nesterov-type accelerated methods and puts forth a rigorous
study of these methods encompassing the escape from saddle-points and
convergence to local minima through a both asymptotic and a non-asymptotic
analysis. In the asymptotic regime, this paper answers an open question of
whether Nesterov's accelerated gradient method (NAG) with variable momentum
parameter avoids strict saddle points almost surely. This work also develops
two metrics of asymptotic rate of convergence and divergence, and evaluates
these two metrics for several popular standard accelerated methods such as the
NAG, and Nesterov's accelerated gradient with constant momentum (NCM) near
strict saddle points. In the local regime, this work provides an analysis that
leads to the "linear" exit time estimates from strict saddle neighborhoods for
trajectories of these accelerated methods as well the necessary conditions for
the existence of such trajectories. Finally, this work studies a sub-class of
accelerated methods that can converge in convex neighborhoods of nonconvex
functions with a near optimal rate to a local minima and at the same time this
sub-class offers superior saddle-escape behavior compared to that of NAG.
- Abstract（参考訳）: 本稿では,滑らかな非凸関数に対する加速度勾配法の一般クラスの挙動を理解する問題を考える。
ポリアックの重ボール法とネステロフ加速勾配法に基づいて、局所最小の非凸関数への収束を実現するためのアルゴリズムを提案する最近の研究により、この研究は、ネステロフ型加速関数の幅広いクラスを提案し、これらの手法について、サドルポイントからの脱出と局所ミニマへの収束を漸近的および非漸近的解析によって包含する厳密な研究を行った。
漸近的手法では,可変運動量パラメータを持つネステロフ加速度勾配法(nag)が厳密な鞍点をほぼ確実に回避できるかどうかという疑問に答える。
この研究は、漸近的な収束率と発散率の2つの指標も開発し、これらの指標をNAGやNesterovの一定の運動量(NCM)を厳密なサドル点付近で加速するいくつかの一般的な加速法に対して評価する。
地域体制において、本研究は、これらの加速された手法の軌跡およびそのような軌跡が存在するために必要な条件のために厳密なサドル地区からの「線形」出口時間推定を導く分析を提供する。
最後に,非凸関数の凸近傍に局所最小値に最も近い速度で収束できる加速的手法のサブクラスについて検討し,同時に,このサブクラスはNAGよりも優れたサドル・エスケープ挙動を提供する。
関連論文リスト
- Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。
本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
論文 参考訳（メタデータ） (2024-04-03T00:41:19Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Acceleration and Implicit Regularization in Gaussian Phase Retrieval [5.484345596034159]
この設定では、Polyak や Nesterov の運動量の暗黙的な正規化による手法が、よい凸降下を保証することを証明している。
実験的な証拠は、これらの手法が実際には勾配降下よりも早く収束していることを示している。
論文 参考訳（メタデータ） (2023-11-21T04:10:03Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the
Bounded Gradient Assumption [11.367487348673793]
勾配勾配降下法(SGD)、重ボール法(SHB)、ネステロフ加速勾配法(SNAG)など、様々な勾配勾配降下法が、厳密なサドル多様体をほぼ確実に避けていることを示す。
SHB法とSNAG法でこのような結果が得られたのはこれが初めてである。
論文 参考訳（メタデータ） (2023-02-15T18:53:41Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - Boundary Conditions for Linear Exit Time Gradient Trajectories Around
Saddle Points: Analysis and Algorithm [9.69596041242667]
厳密なサドル点の景観における多目的関数の理解について述べる。
厳密なサドル点の最大値を持つ局所的な景観に収束する近傍の解析についても述べる。
論文 参考訳（メタデータ） (2021-01-07T16:59:15Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳（メタデータ） (2020-09-23T20:02:00Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z) - Exit Time Analysis for Approximations of Gradient Descent Trajectories
Around Saddle Points [9.66353475649122]
本稿では, 厳密なサドル地区周辺における勾配日射法について, 厳密な幾何学的解析を行った。
これは任意の初期条件に対して近似的な勾配軌道を生成するのに使用できる重要な結果を与える。
この解析により, 一定の初期条件下での勾配差分法に対する線形出口時間解が導かれる。
論文 参考訳（メタデータ） (2020-06-01T17:47:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。