論文の概要: Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence
- arxiv url: http://arxiv.org/abs/2410.02626v1
- Date: Thu, 3 Oct 2024 16:08:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 02:02:21.115056
- Title: Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence
- Title（参考訳）: 大域的非漸近的収束を考慮したオンライン学習指導準ニュートン法
- Authors: Ruichen Jiang, Aryan Mokhtari,
- Abstract要約: 双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
- 参考スコア（独自算出の注目度）: 20.766358513158206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a quasi-Newton method for solving smooth and monotone nonlinear equations, including unconstrained minimization and minimax optimization as special cases. For the strongly monotone setting, we establish two global convergence bounds: (i) a linear convergence rate that matches the rate of the celebrated extragradient method, and (ii) an explicit global superlinear convergence rate that provably surpasses the linear convergence rate after at most ${O}(d)$ iterations, where $d$ is the problem's dimension. In addition, for the case where the operator is only monotone, we prove a global convergence rate of ${O}(\min\{{1}/{k},{\sqrt{d}}/{k^{1.25}}\})$ in terms of the duality gap. This matches the rate of the extragradient method when $k = {O}(d^2)$ and is faster when $k = \Omega(d^2)$. These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method, without querying the Jacobian of the operator. Unlike classical quasi-Newton methods, we achieve this by using the hybrid proximal extragradient framework and a novel online learning approach for updating the Jacobian approximation matrices. Specifically, guided by the convergence analysis, we formulate the Jacobian approximation update as an online convex optimization problem over non-symmetric matrices, relating the regret of the online problem to the convergence rate of our method. To facilitate efficient implementation, we further develop a tailored online learning algorithm based on an approximate separation oracle, which preserves structures such as symmetry and sparsity in the Jacobian matrices.
- Abstract（参考訳）: 本稿では,制約のない最小化や極小最適化など,滑らかで単調な非線形方程式を解くための準ニュートン法を提案する。
強い単調な設定では、2つの大域収束境界を確立する。
一 卓越した過度な方法の率と一致する直線収束率、及び
(ii)少なくとも${O}(d)$反復の後に、線形収束率を確実に上回る明示的な大域的超線型収束率(d$は問題の次元である)。
さらに、作用素が単調である場合、双対性ギャップの観点で${O}(\min\{{1}/{k},{\sqrt{d}}/{k^{1.25}}\})$の大域収束率を証明する。
これは $k = {O}(d^2)$ で、$k = \Omega(d^2)$ のときよりも高速である。
これらの結果は、作用素のヤコビアンを問うことなく、半ニュートン法が次数次法よりも優れていることを示す最初の大域収束結果である。
古典的準ニュートン法と異なり, ハイブリッド近位次フレームワークと, ヤコビ近似行列を更新するための新しいオンライン学習手法を用いてこれを実現している。
具体的には, 収束解析により, 非対称行列上でのオンライン凸最適化問題としてヤコビ近似更新を定式化し, オンライン問題の後悔と手法の収束率を関連づける。
効率的な実装を容易にするため,ヤコビ行列の対称性や空間性などの構造を保存する近似的な分離オラクルに基づくオンライン学習アルゴリズムをさらに開発する。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic
Superlinear Convergence Rate [37.49160762239869]
本稿では,非漸近性超線形速度を明示的に達成できるリミテッドメモリGreedy BFGS(LG-BFGS)法を提案する。
我々の確立した非漸近超線形収束速度は、収束速度とメモリ要求との明確なトレードオフを示す。
論文 参考訳（メタデータ） (2023-06-27T12:59:56Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Online Learning Guided Curvature Approximation: A Quasi-Newton Method
with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。
古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
論文 参考訳（メタデータ） (2023-02-16T20:58:09Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。
この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
論文 参考訳（メタデータ） (2020-03-30T16:42:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。