論文の概要: 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$-超線形収束を享受する。 この(一様平均化)アプローチの潜在的な欠点は、平均推定値が反復のグローバル位相、すなわち反復が局所近傍に収束する前にヘッセン情報を含むことである。 これにより、局所近傍が到達するまでの時間に、超線形収束を実質的に遅らせる歪みが生じる。 この欠点に対処するために、最近のヘッセン語により大きな重みを割り当てる重み付き平均化スキームについて検討し、超線型収束はより早く起こるが、わずかに遅くなる。 驚くべきことに、最適段階において局所収束に移行し、一様ヘッセン平均化とほぼ(対数係数まで)一致する超線形収束率を享受する普遍的な重み付き平均化スキームが存在する。

関連論文リスト

• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。 これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
  論文  参考訳（メタデータ） (2024-09-28T02:30:44Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• 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)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• 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)
• 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)

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

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