論文の概要: Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates

• arxiv url: http://arxiv.org/abs/2402.02359v1
• Date: Sun, 4 Feb 2024 05:54:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-06 20:12:08.603340
• Title: Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
• Title（参考訳）: より高速な超線形収束速度をもつインクリメンタル準ニュートン法
• Authors: Zhuanghua Liu and Luo Luo and Bryan Kian Hsiang Low
• Abstract要約: 各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
• 参考スコア（独自算出の注目度）: 50.36933471975506
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate that is dependent on the condition number of the problem. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework, which results in the condition-number-free local superlinear convergence rate. Furthermore, we can boost our method by applying the block update on the Hessian approximation, which leads to an even faster local convergence rate. The numerical experiments show the proposed methods significantly outperform the baseline methods.
• Abstract（参考訳）: 各成分関数は強凸であり、リプシッツ連続勾配とヘッシアンを持つ有限サム最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法はBFGSの更新に基づいて,問題の条件数に依存する局所超線形収束率を達成する。 本稿では,対称 rank-1 更新をインクリメンタル・フレームワークに組み込むことにより,より効率的な準ニュートン法を提案する。 さらに,Hessian近似のブロック更新を適用し,より高速な局所収束率を実現することにより,本手法を向上することができる。 数値実験により,提案手法はベースライン法よりも有意に優れていた。

関連論文リスト

• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。 これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-10-03T16:08:16Z)
• Incremental Gauss--Newton Methods with Superlinear Convergence Rates [16.92437325972209]
  Incrmental Gauss--Newton(IGN)法を明示的な超線形収束速度で導入する。 特に、有限サム構造を持つ非線形最小二乗で問題を定式化する。 また、より高速な超線形収束率を得るIGN法に対するミニバッチ拡張も提供する。
  論文  参考訳（メタデータ） (2024-07-03T15:26:34Z)
• Stochastic Newton Proximal Extragradient Method [18.47705532817026]
  そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。 我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
  論文  参考訳（メタデータ） (2024-06-03T16:06:23Z)
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
  非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-02-16T20:58:09Z)
• 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)
• Acceleration Methods [57.202881673406324]
  まず2次最適化問題を用いて加速法を2つ導入する。 我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。 我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
  論文  参考訳（メタデータ） (2021-01-23T17:58:25Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
  準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
  論文  参考訳（メタデータ） (2020-03-30T16:42:41Z)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  そこでは,この知識を最適な値である$f_*$で置き換える。 まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
  論文  参考訳（メタデータ） (2020-02-03T17:50:28Z)

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

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