論文の概要: Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence
- arxiv url: http://arxiv.org/abs/2204.09266v1
- Date: Wed, 20 Apr 2022 07:14:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-21 22:35:00.049830
- Title: Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence
- Title(参考訳): 確率的ニュートン法による超線形収束のヘシアン平均化
- Authors: Sen Na, Micha{\l} Derezi\'nski, Michael W. Mahoney
- Abstract要約: ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
- 参考スコア(独自算出の注目度): 69.65563161962245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider minimizing a smooth and strongly convex objective function using
a stochastic Newton method. At each iteration, the algorithm is given an oracle
access to a stochastic estimate of the Hessian matrix. The oracle model
includes popular algorithms such as the Subsampled Newton and Newton Sketch,
which can efficiently construct stochastic Hessian estimates for many tasks.
Despite using second-order information, these existing methods do not exhibit
superlinear convergence, unless the stochastic noise is gradually reduced to
zero during the iteration, which would lead to a computational blow-up in the
per-iteration cost. We address this limitation with Hessian averaging: instead
of using the most recent Hessian estimate, our algorithm maintains an average
of all past estimates. This reduces the stochastic noise while avoiding the
computational blow-up. We show that this scheme enjoys local $Q$-superlinear
convergence with a non-asymptotic rate of $(\Upsilon\sqrt{\log (t)/t}\,)^{t}$,
where $\Upsilon$ is proportional to the level of stochastic noise in the
Hessian oracle. A potential drawback of this (uniform averaging) approach is
that the averaged estimates contain Hessian information from the global phase
of the iteration, i.e., before the iterates converge to a local neighborhood.
This leads to a distortion that may substantially delay the superlinear
convergence until long after the local neighborhood is reached. To address this
drawback, we study a number of weighted averaging schemes that assign larger
weights to recent Hessians, so that the superlinear convergence arises sooner,
albeit with a slightly slower rate. Remarkably, we show that there exists a
universal weighted averaging scheme that transitions to local convergence at an
optimal stage, and still enjoys a superlinear convergence~rate nearly (up to a
logarithmic factor) matching that of uniform Hessian averaging.
- Abstract(参考訳): 確率ニュートン法による滑らかで強い対流対象関数の最小化を検討する。
各反復において、アルゴリズムはヘッセン行列の確率的推定へのオラクルアクセスを与える。
oracle のモデルには,newton や newton sketch といった,多くのタスクに対して確率的ヘッセン推定を効率的に構築可能な一般的なアルゴリズムが含まれている。
第二次情報を用いるにもかかわらず、これらの既存の手法は、反復の間に確率的ノイズが徐々にゼロに減少しない限り、超線形収束を示しない。
この制限をヘッセン平均化(Hessian averaging)によって解決する: 最新のヘッセン推定を使用する代わりに、我々のアルゴリズムは過去のすべての推定値の平均を維持する。
これにより、計算の爆発を避けながら確率ノイズを低減できる。
このスキームは、非漸近的なレートである$(\upsilon\sqrt{\log (t)/t}\,)^{t}$(ただし、$\upsilon$ はヘッセン神託における確率的雑音のレベルに比例する)で局所的な$q$-超線形収束を享受する。
この(一様平均化)アプローチの潜在的な欠点は、平均推定値が反復のグローバル位相、すなわち反復が局所近傍に収束する前にヘッセン情報を含むことである。
これにより、局所近傍が到達するまでの時間に、超線形収束を実質的に遅らせる歪みが生じる。
この欠点に対処するために、最近のヘッセン語により大きな重みを割り当てる重み付き平均化スキームについて検討し、超線型収束はより早く起こるが、わずかに遅くなる。
驚くべきことに、最適段階において局所収束に移行し、一様ヘッセン平均化とほぼ(対数係数まで)一致する超線形収束率を享受する普遍的な重み付き平均化スキームが存在する。
関連論文リスト
- Stochastic Newton Proximal Extragradient Method [18.47705532817026]
そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。
我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
論文 参考訳(メタデータ) (2024-06-03T16:06:23Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳(メタデータ) (2024-02-04T05:54:51Z) - Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。
私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。
これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
論文 参考訳(メタデータ) (2024-01-23T13:44:15Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-03-03T14:39:33Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳(メタデータ) (2022-02-07T21:23:17Z) - Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization [20.189732632410024]
準ニュートン法は, セカント方程式を用いてヘッセンを近似することにより曲率情報を提供する。
線形収束率を持つ凸関数の大規模な経験的リスクに対するニュートンステップに基づくDP最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-16T14:04:51Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。