論文の概要: Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods

• arxiv url: http://arxiv.org/abs/2003.13607v4
• Date: Tue, 30 Nov 2021 22:41:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-18 08:39:37.184973
• Title: Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
• Title（参考訳）: 標準準ニュートン法の非漸近超線形収束
• Authors: Qiujiang Jin and Aryan Mokhtari
• Abstract要約: 準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
• 参考スコア（独自算出の注目度）: 26.328847475942894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon--Fletcher--Powell (DFP) method and the Broyden--Fletcher--Goldfarb--Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of $(1/k)^{k/2}$, where $k$ is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.
• Abstract（参考訳）: 本稿では,ダビドン-フレッチャー-パウエル (DFP) 法とブロイデン-フレッチャー-ゴルドファーブ-シャンノ (BFGS) 法を含む準ニュートンアルゴリズムのブロイデン類における非漸近超線形収束速度について検討し,その証明を行う。 これらの準ニュートン法の漸近的超線形収束速度は文献で広く研究されているが、その明示的な有限時間局所収束速度は十分に研究されていない。 本稿では,対象関数が強凸であること,勾配がリプシッツ連続であること,ヘシアンが最適解においてリプシッツ連続であることを仮定して,ブロイデン準ニュートンアルゴリズムの有限時間(非漸近的)収束解析を行う。 最適解の局所的な近傍では、DFP と BFGS の双方が生成したイテレートが 1/k)^{k/2}$ の超線型速度で最適解に収束し、$k$ は反復数である。 また、同様の局所超線形収束結果が、目的関数が自己一致である場合にも証明する。 いくつかのデータセットに関する数値実験により、明示的な収束速度境界が確認できる。 我々の理論的保証は準ニュートン法に対する非漸近超線型収束率を与える最初の結果の1つである。

関連論文リスト

• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。 これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-10-03T16:08:16Z)
• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate [37.49160762239869]
  本稿では,非漸近性超線形速度を明示的に達成できるリミテッドメモリGreedy BFGS(LG-BFGS)法を提案する。 我々の確立した非漸近超線形収束速度は、収束速度とメモリ要求との明確なトレードオフを示す。
  論文  参考訳（メタデータ） (2023-06-27T12:59:56Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
  非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-02-16T20:58:09Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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