論文の概要: Stochastic Subspace Cubic Newton Method
- arxiv url: http://arxiv.org/abs/2002.09526v1
- Date: Fri, 21 Feb 2020 19:42:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 01:56:45.590343
- Title: Stochastic Subspace Cubic Newton Method
- Title（参考訳）: 確率的部分空間立方体ニュートン法
- Authors: Filip Hanzely, Nikita Doikov, Peter Richt\'arik, Yurii Nesterov
- Abstract要約: 本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。
ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。
注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
- 参考スコア（独自算出の注目度）: 14.624340432672172
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a new randomized second-order optimization
algorithm---Stochastic Subspace Cubic Newton (SSCN)---for minimizing a high
dimensional convex function $f$. Our method can be seen both as a {\em
stochastic} extension of the cubically-regularized Newton method of Nesterov
and Polyak (2006), and a {\em second-order} enhancement of stochastic subspace
descent of Kozak et al. (2019). We prove that as we vary the minibatch size,
the global convergence rate of SSCN interpolates between the rate of stochastic
coordinate descent (CD) and the rate of cubic regularized Newton, thus giving
new insights into the connection between first and second-order methods.
Remarkably, the local convergence rate of SSCN matches the rate of stochastic
subspace descent applied to the problem of minimizing the quadratic function
$\frac12 (x-x^*)^\top \nabla^2f(x^*)(x-x^*)$, where $x^*$ is the minimizer of
$f$, and hence depends on the properties of $f$ at the optimum only. Our
numerical experiments show that SSCN outperforms non-accelerated first-order CD
algorithms while being competitive to their accelerated variants.
- Abstract（参考訳）: 本稿では,高次元凸関数を最小化するために,ランダム化二階最適化アルゴリズム--SSCN(Stochastic Subspace Cubic Newton)を提案する。
我々の手法は、Nesterov と Polyak (2006) の立方正則化ニュートン法の {\em stochastic} 拡張と、Kozak et al. (2019) の確率的部分空間降下の {\em second-order} 拡張である。
ミニバッチサイズが変化するにつれて,sscnのグローバル収束率は,確率座標降下率 (cd) と立方体正規化ニュートン率の間に補間され,一階法と二階法の間に新たな知見を与える。
注目すべきことに、SSCN の局所収束速度は二次函数 $\frac12 (x-x^*)^\top \nabla^2f(x^*)(x-x^*)$ の最小化問題に適用される確率的部分空間降下率と一致する。
数値実験により,SSCNは高速な変種と競合しながら,非加速的な1次CDアルゴリズムよりも優れていた。
関連論文リスト
- 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) - Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate [83.3933097134767]
次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。
提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
論文 参考訳（メタデータ） (2024-01-05T20:24:18Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - 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) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization [20.189732632410024]
準ニュートン法は, セカント方程式を用いてヘッセンを近似することにより曲率情報を提供する。
線形収束率を持つ凸関数の大規模な経験的リスクに対するニュートンステップに基づくDP最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-16T14:04:51Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。