論文の概要: Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate
- arxiv url: http://arxiv.org/abs/2401.03058v1
- Date: Fri, 5 Jan 2024 20:24:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 20:47:54.493239
- Title: Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate
- Title（参考訳）: クリロフキュービック正規化ニュートン:次元自由収束率を持つ部分空間2次法
- Authors: Ruichen Jiang, Parameswaran Raman, Shoham Sabach, Aryan Mokhtari,
Mingyi Hong, Volkan Cevher
- Abstract要約: 次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。
提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
- 参考スコア（独自算出の注目度）: 83.3933097134767
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Second-order optimization methods, such as cubic regularized Newton methods,
are known for their rapid convergence rates; nevertheless, they become
impractical in high-dimensional problems due to their substantial memory
requirements and computational costs. One promising approach is to execute
second-order updates within a lower-dimensional subspace, giving rise to
subspace second-order methods. However, the majority of existing subspace
second-order methods randomly select subspaces, consequently resulting in
slower convergence rates depending on the problem's dimension $d$. In this
paper, we introduce a novel subspace cubic regularized Newton method that
achieves a dimension-independent global convergence rate of
${O}\left(\frac{1}{mk}+\frac{1}{k^2}\right)$ for solving convex optimization
problems. Here, $m$ represents the subspace dimension, which can be
significantly smaller than $d$. Instead of adopting a random subspace, our
primary innovation involves performing the cubic regularized Newton update
within the Krylov subspace associated with the Hessian and the gradient of the
objective function. This result marks the first instance of a
dimension-independent convergence rate for a subspace second-order method.
Furthermore, when specific spectral conditions of the Hessian are met, our
method recovers the convergence rate of a full-dimensional cubic regularized
Newton method. Numerical experiments show our method converges faster than
existing random subspace methods, especially for high-dimensional problems.
- Abstract（参考訳）: 立方体正規化ニュートン法のような二階最適化法は、その急速な収束速度で知られているが、しかしながら、十分なメモリ要求と計算コストのために高次元の問題では実用的でない。
1つの有望なアプローチは、低次元のサブ空間内で2階更新を実行することである。
しかし、既存の部分空間二階法の大部分はランダムに部分空間を選択し、その結果、問題の次元 $d$ に依存する収束率が遅くなる。
本稿では,凸最適化問題の解法として,次元独立な大域収束率を${O}\left(\frac{1}{mk}+\frac{1}{k^2}\right)$とする,新しい部分空間正規化ニュートン法を提案する。
ここで、$m$は部分空間次元を表し、$d$よりもかなり小さい。
ランダムな部分空間を採用する代わりに、我々の主要な革新は、ヘシアンと目的関数の勾配に付随するクリロフ部分空間内で立方正則ニュートン更新を行うことである。
この結果は、部分空間の2階法に対する次元独立収束率の最初の例を示す。
さらに,Hessianのスペクトル条件が一致した場合,本手法は実次元立方正則ニュートン法の収束率を回復する。
数値実験により,本手法は既存のランダム部分空間法,特に高次元問題よりも高速に収束することを示す。
関連論文リスト
- Improving Stochastic Cubic Newton with Momentum [37.1630298053787]
モーメントが推定値の分散を確実に安定化させることを示す。
グローバリゼーション手法を用いて収束点を証明した。
また、運動量を持つ凸ニュートン法を示す。
論文 参考訳（メタデータ） (2024-10-25T15:49:16Z) - Cubic regularized subspace Newton for non-convex optimization [3.481985817302898]
我々は、ランダムな部分空間に定常正規化を適用すると解釈できる座標二階SSCNを解析する。
従来の一階法と比較して,大幅な高速化を示した。
論文 参考訳（メタデータ） (2024-06-24T14:20:02Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Second-order optimization with lazy Hessians [55.51077907483634]
一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。
我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:26Z) - 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) - DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。
理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
論文 参考訳（メタデータ） (2022-07-30T13:05:01Z) - Stochastic Subspace Cubic Newton Method [14.624340432672172]
本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。
ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。
注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
論文 参考訳（メタデータ） (2020-02-21T19:42:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。