論文の概要: Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate

• arxiv url: http://arxiv.org/abs/2306.15444v1
• Date: Tue, 27 Jun 2023 12:59:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-28 13:21:12.239826
• Title: Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate
• Title（参考訳）: 非漸近的超線形収束率を持つリミテッドメモリグリーディ準ニュートン法
• Authors: Zhan Gao and Aryan Mokhtari and Alec Koppel
• Abstract要約: 本稿では, 暗黙的な非漸近性超線形速度を実現する限定記憶型BFGS(LG-BFGS)法を提案する。 我々の確立した非漸近超線形収束速度は、収束速度とメモリ要求とのトレードオフを示す。
• 参考スコア（独自算出の注目度）: 34.23260882135828
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-asymptotic convergence analysis of quasi-Newton methods has gained attention with a landmark result establishing an explicit superlinear rate of O$((1/\sqrt{t})^t)$. The methods that obtain this rate, however, exhibit a well-known drawback: they require the storage of the previous Hessian approximation matrix or instead storing all past curvature information to form the current Hessian inverse approximation. Limited-memory variants of quasi-Newton methods such as the celebrated L-BFGS alleviate this issue by leveraging a limited window of past curvature information to construct the Hessian inverse approximation. As a result, their per iteration complexity and storage requirement is O$(\tau d)$ where $\tau \le d$ is the size of the window and $d$ is the problem dimension reducing the O$(d^2)$ computational cost and memory requirement of standard quasi-Newton methods. However, to the best of our knowledge, there is no result showing a non-asymptotic superlinear convergence rate for any limited-memory quasi-Newton method. In this work, we close this gap by presenting a limited-memory greedy BFGS (LG-BFGS) method that achieves an explicit non-asymptotic superlinear rate. We incorporate displacement aggregation, i.e., decorrelating projection, in post-processing gradient variations, together with a basis vector selection scheme on variable variations, which greedily maximizes a progress measure of the Hessian estimate to the true Hessian. Their combination allows past curvature information to remain in a sparse subspace while yielding a valid representation of the full history. Interestingly, our established non-asymptotic superlinear convergence rate demonstrates a trade-off between the convergence speed and memory requirement, which to our knowledge, is the first of its kind. Numerical results corroborate our theoretical findings and demonstrate the effectiveness of our method.
• Abstract（参考訳）: 準ニュートン法の非漸近収束解析は、o$((1/\sqrt{t})^t)$という明示的な超線形率を確立して注目されている。 しかし、この速度を得る方法にはよく知られた欠点があり、それらは以前のヘッセン近似行列の保存を必要とするか、現在のヘッセン逆近似を形成するために過去の曲率情報を全て保存する必要がある。 有名なL-BFGSのような準ニュートン法は、過去の曲率情報の限られた窓を利用してヘッセン逆近似を構築することでこの問題を緩和する。 結果として、イテレーション毎の複雑性とストレージ要件は O$(\tau d)$ であり、$\tau \le d$ はウィンドウのサイズであり、$d$ は O$(d^2)$ の計算コストと標準準ニュートン法のメモリ要件を減らす問題次元である。 しかしながら、我々の知る限り、任意の限定メモリ準ニュートン法に対して非漸近超線形収束率を示す結果は存在しない。 本研究では,非漸近的スーパーリニアレートを達成するための限定メモリの bfgs (lg-bfgs) 法を提案することで,このギャップを解消する。 本研究では, 変形後の勾配変動に, 変位分布, すなわちデコリレーション射影を組み込むとともに, ヘシアン推定の進捗測度を真のヘッシアンにグレッシィに最大化する可変変動に対する基底ベクトル選択スキームを組み込んだ。 それらの組み合わせにより、過去の曲率情報はスパース部分空間に留まり、完全な歴史の有効な表現が得られる。 興味深いことに、確立された非漸近超線形収束率は、我々の知る限りでは最初の収束速度とメモリ要求のトレードオフを示している。 数値実験の結果から,本手法の有効性が示唆された。

関連論文リスト

• 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)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
  非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-02-16T20:58:09Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck [14.309243378538012]
  本稿では,現在の後方中心のHellingerメトリックに対して,エラー近傍を修正可能なオンライン圧縮方式を提案する。 一定の誤差半径の場合、POG は集団後部の近傍 (Theorem 1(ii)) に収束するが、特徴空間の計量エントロピーによって決定される有限メモリのオン・ウォーストに収束する。
  論文  参考訳（メタデータ） (2020-04-23T11:52:06Z)
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
  準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
  論文  参考訳（メタデータ） (2020-03-30T16:42:41Z)

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

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