論文の概要: Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches

• arxiv url: http://arxiv.org/abs/2206.02702v1
• Date: Mon, 6 Jun 2022 16:00:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 19:24:53.170841
• Title: Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
• Title（参考訳）: 確率分散還元ニュートン:大きなバッチで有限サム最小化を加速する
• Authors: Micha{\l} Derezi\'nski
• Abstract要約: 本稿では,二階法の利点をすべて享受する有限サム最小化アルゴリズムを提案する。 本稿では,SVRNが最小二乗解法(Subsampled Newtonなど)や反復最小二乗解法を高速化できることを示す。
• 参考スコア（独自算出の注目度）: 22.925108493465363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic variance reduction has proven effective at accelerating first-order algorithms for solving convex finite-sum optimization tasks such as empirical risk minimization. Incorporating additional second-order information has proven helpful in further improving the performance of these first-order methods. However, comparatively little is known about the benefits of using variance reduction to accelerate popular stochastic second-order methods such as Subsampled Newton. To address this, we propose Stochastic Variance-Reduced Newton (SVRN), a finite-sum minimization algorithm which enjoys all the benefits of second-order methods: simple unit step size, easily parallelizable large-batch operations, and fast local convergence, while at the same time taking advantage of variance reduction to achieve improved convergence rates (per data pass) for smooth and strongly convex problems. We show that SVRN can accelerate many stochastic second-order methods (such as Subsampled Newton) as well as iterative least squares solvers (such as Iterative Hessian Sketch), and it compares favorably to popular first-order methods with variance reduction.
• Abstract（参考訳）: 確率分散還元は、経験的リスク最小化のような凸有限サム最適化タスクを解くための一階アルゴリズムの高速化に有効であることが証明されている。 追加の第2次情報の導入は、これらの第1次メソッドのパフォーマンスをさらに向上させる上で有用であることが証明されている。 しかし、Subsampled Newtonのような確率的二階法を高速化するために分散還元を利用する利点についてはあまり知られていない。 そこで本研究では,単純な単位ステップサイズ,並列化が容易な大バッチ演算,高速局所収束といった2次手法の利点を享受する有限サム最小化アルゴリズムであるStochastic Variance-Reduced Newton (SVRN)を提案する。 その結果,svrn は逐次最小二乗解法 (反復ヘッシアンスケッチなど) と同様に,多くの確率的二階法 (ニュートンの副サンプリングなど) を高速化できることを示し,分散還元を伴う一般的な一階法と比較した。

関連論文リスト

• Improving Stochastic Cubic Newton with Momentum [37.1630298053787]
  モーメントが推定値の分散を確実に安定化させることを示す。 グローバリゼーション手法を用いて収束点を証明した。 また、運動量を持つ凸ニュートン法を示す。
  論文  参考訳（メタデータ） (2024-10-25T15:49:16Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
  非強凸設定における最小二乗回帰問題の近似を考察する。 本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-03T14:39:33Z)
• SCORE: Approximating Curvature Information under Self-Concordant Regularization [0.0]
  本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。 提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
  論文  参考訳（メタデータ） (2021-12-14T13:03:04Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• SPAN: A Stochastic Projected Approximate Newton Method [17.94221425332409]
  ヘッセン行列の逆数を計算するために,新しい近似的かつ高速なニュートン法であるSPANを提案する。 SPANは、コンバージェンスウォールクロック時間の観点から、既存の1次および2次最適化手法より優れている。
  論文  参考訳（メタデータ） (2020-02-10T12:42:42Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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