論文の概要: Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees

• arxiv url: http://arxiv.org/abs/2508.19712v1
• Date: Wed, 27 Aug 2025 09:18:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-28 19:07:41.574073
• Title: Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• Title（参考訳）: 大域収束保証付き準ニュートン法の簡易ステップサイズ
• Authors: Artem Agafonov, Vladislav Ryspayev, Samuel Horváth, Alexander Gasnikov, Martin Takáč, Slavomir Hanzely,
• Abstract要約: 我々は、凸関数に対して大域収束率$O (1/k) を保証できる単純なステップサイズスケジュールを導入することで、準ニュートン法の理論的理解を拡大する。 ヘッセン近似の不完全性が所定の相対的精度で制御された場合、ネステロフの加速勾配法と3次正規化ニュートン法の両方の最もよく知られた速度に一致する1O (1/k)$の加速収束率が得られることを示す。
• 参考スコア（独自算出の注目度）: 46.16377198030688
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quasi-Newton methods are widely used for solving convex optimization problems due to their ease of implementation, practical efficiency, and strong local convergence guarantees. However, their global convergence is typically established only under specific line search strategies and the assumption of strong convexity. In this work, we extend the theoretical understanding of Quasi-Newton methods by introducing a simple stepsize schedule that guarantees a global convergence rate of ${O}(1/k)$ for the convex functions. Furthermore, we show that when the inexactness of the Hessian approximation is controlled within a prescribed relative accuracy, the method attains an accelerated convergence rate of ${O}(1/k^2)$ -- matching the best-known rates of both Nesterov's accelerated gradient method and cubically regularized Newton methods. We validate our theoretical findings through empirical comparisons, demonstrating clear improvements over standard Quasi-Newton baselines. To further enhance robustness, we develop an adaptive variant that adjusts to the function's curvature while retaining the global convergence guarantees of the non-adaptive algorithm.
• Abstract（参考訳）: 準ニュートン法は、実装の容易さ、実用効率、強い局所収束保証のために凸最適化問題を解くために広く用いられている。 しかしながら、それらのグローバル収束は通常、特定の線探索戦略と強い凸性の仮定の下でのみ確立される。 本研究では、凸関数に対する大域収束率${O}(1/k)$を保証した単純なステップサイズスケジュールを導入することにより、準ニュートン法の理論的理解を拡大する。 さらに, ヘッセン近似の不等式が所定の相対的精度で制御された場合, ネステロフの加速勾配法と3次正規化ニュートン法の両方の既知値に一致する${O}(1/k^2)$の加速収束率が得られることを示す。 実験的な比較によって理論的な知見を検証し,標準準ニュートンベースラインに対する明確な改善を実証した。 さらにロバスト性を高めるために,非適応アルゴリズムのグローバル収束保証を維持しつつ関数の曲率に適応的な変種を開発する。

関連論文リスト

• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness [50.78508362183774]
  シャッフル型勾配法はその単純さと迅速な経験的性能のために実践的に好まれる。 リプシッツ条件は一般的な機械学習スキームでは満たされないことが多い。
  論文  参考訳（メタデータ） (2025-07-11T15:36:48Z)
• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods [37.1630298053787]
  我々はヘルパーフレームワークと呼ばれる新しいフレームワークを提案する。 グローバルな複雑性保証を備えた分散アルゴリズムと二階アルゴリズムの統一的なビューを提供する。
  論文  参考訳（メタデータ） (2023-02-23T12:18:28Z)
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
  非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-02-16T20:58:09Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
  準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
  論文  参考訳（メタデータ） (2020-03-30T16:42:41Z)

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

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