論文の概要: Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence

• arxiv url: http://arxiv.org/abs/2302.08580v2
• Date: Tue, 25 Jul 2023 04:48:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 21:10:22.298063
• Title: Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence
• Title（参考訳）: オンライン学習ガイド曲率近似:大域的非漸近超線形収束を伴う準ニュートン法
• Authors: Ruichen Jiang, Qiujiang Jin, Aryan Mokhtari
• Abstract要約: 非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
• 参考スコア（独自算出の注目度）: 22.286753988825048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quasi-Newton algorithms are among the most popular iterative methods for solving unconstrained minimization problems, largely due to their favorable superlinear convergence property. However, existing results for these algorithms are limited as they provide either (i) a global convergence guarantee with an asymptotic superlinear convergence rate, or (ii) a local non-asymptotic superlinear rate for the case that the initial point and the initial Hessian approximation are chosen properly. In particular, no current analysis for quasi-Newton methods guarantees global convergence with an explicit superlinear convergence rate. In this paper, we close this gap and present the first globally convergent quasi-Newton method with an explicit non-asymptotic superlinear convergence rate. Unlike classical quasi-Newton methods, we build our algorithm upon the hybrid proximal extragradient method and propose a novel online learning framework for updating the Hessian approximation matrices. Specifically, guided by the convergence analysis, we formulate the Hessian approximation update as an online convex optimization problem in the space of matrices, and we relate the bounded regret of the online problem to the superlinear convergence of our method.
• Abstract（参考訳）: 準ニュートンアルゴリズムは、制約のない最小化問題を解くための最も一般的な反復法の一つである。 しかし、これらのアルゴリズムの既存の結果は、どちらかを提供するため限られている。 (i)漸近的な超線形収束率を持つ大域収束保証、又は 2)初期点と初期ヘッセン近似が適切に選択された場合の局所的非漸近性超線形速度。 特に、準ニュートン法の電流解析は、明示的な超線形収束率で大域収束を保証する。 本稿では,このギャップを埋め,非漸近性超線形収束率を明示した最初のグローバル収束準ニュートン法を示す。 古典的準ニュートン法とは異なり, ハイブリッドな近位勾配法に基づくアルゴリズムを構築し, ヘッセン近似行列を更新するための新しいオンライン学習フレームワークを提案する。 具体的には、収束解析により、行列空間におけるオンライン凸最適化問題としてヘッセン近似更新を定式化し、オンライン問題における無関係な後悔と我々の方法の超線形収束を関連づける。

関連論文リスト

• 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)
• Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate [37.49160762239869]
  本稿では,非漸近性超線形速度を明示的に達成できるリミテッドメモリGreedy BFGS(LG-BFGS)法を提案する。 我々の確立した非漸近超線形収束速度は、収束速度とメモリ要求との明確なトレードオフを示す。
  論文  参考訳（メタデータ） (2023-06-27T12:59:56Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
  本研究では,Threshold Learned Iterative Shrinkage Algorithming (NLISTA)を導入することでギャップを埋める。 合成データを用いた実験は理論結果と相関し,その手法が最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-26T11:31:08Z)
• 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)

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

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