論文の概要: Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

• arxiv url: http://arxiv.org/abs/2307.07030v2
• Date: Sat, 25 Oct 2025 20:04:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 22:08:13.672746
• Title: Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
• Title（参考訳）: 非凸最適化のための加速勾配法:厳密なサドル点からの軌跡と局所ミニマへの収束
• Authors: Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa,
• Abstract要約: 本稿では、スムーズな非同相関数に対する一般加速勾配法の挙動を理解することの問題点について考察する。 最近のアルゴリズムによって動機付けられ、NesterAcceleredメソッドのクラスの解析を提供する。 加速されたメソッドのサブクラスを提供し、同じサブクラスにおける局所レートにほぼ最適な時間で近傍の非函数に収束することができる。
• 参考スコア（独自算出の注目度）: 5.403677859218301
• 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 both an 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 rates 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 non-asymptotic 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 minimum and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG.
• Abstract（参考訳）: 本稿では,滑らかな非凸関数上の加速度勾配法の一般クラスの挙動を理解することの問題点について考察する。 ポリアックの重ボール法とネステロフ加速勾配法に基づいて、局所最小の非凸関数への収束を実現するためのアルゴリズムを提案する最近の研究により、この研究は、ネステロフ型加速関数の幅広いクラスを提案し、これらの手法がサドル点からの脱出と局所ミニマへの収束を漸近的および非漸近的解析によって包含する厳密な研究を行った。 本稿では,Nesterov の運動量パラメータを持つ加速勾配法 (NAG) が,厳密なサドル点をほぼ確実に回避するかどうかというオープンな疑問に答える。 この研究は、収束と発散の漸近速度の2つの指標も開発し、これらの指標をNAGやネステロフの加速勾配など、厳密なサドル点付近で一定の運動量(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)

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

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