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

• arxiv url: http://arxiv.org/abs/2206.02702v2
• Date: Tue, 29 Apr 2025 13:47:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:51.425007
• Title: Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
• Title（参考訳）: 確率可変生成ニュートン:大型バッチによる有限サム最小化の高速化
• Authors: Michał Dereziński,
• Abstract要約: 既存のニュートン法を確実に高速化する有限サム最小化アルゴリズムを提案する。 驚くべきことに、このアクセラレーションはデータサイズが大きくなるほど大きくなります。 我々のアルゴリズムは、容易に並列な大バッチ演算や単純な単位ステップサイズなど、ニュートン型手法の重要な利点を保っている。
• 参考スコア（独自算出の注目度）: 0.0
• 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 second-order information has proven helpful in further improving the performance of these first-order methods. Yet, 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 that provably accelerates existing stochastic Newton methods from $O(\alpha\log(1/\epsilon))$ to $O\big(\frac{\log(1/\epsilon)}{\log(n)}\big)$ passes over the data, i.e., by a factor of $O(\alpha\log(n))$, where $n$ is the number of sum components and $\alpha$ is the approximation factor in the Hessian estimate. Surprisingly, this acceleration gets more significant the larger the data size $n$, which is a unique property of SVRN. Our algorithm retains the key advantages of Newton-type methods, such as easily parallelizable large-batch operations and a simple unit step size. We use SVRN to accelerate Subsampled Newton and Iterative Hessian Sketch algorithms, and show that it compares favorably to popular first-order methods with variance~reduction.
• Abstract（参考訳）: 確率的分散還元は、経験的リスク最小化のような凸有限サム最適化タスクを解くための一階アルゴリズムの高速化に有効であることが証明されている。 二次情報を組み込むことは、これらの一階法の性能向上に有効であることが証明されている。 しかし、Subsampled Newtonのような確率的二階法を加速するために分散還元を用いることの利点についてはあまり知られていない。 これを解決するために、Stochastic Variance-Reduced Newton (SVRN) という、既存の確率ニュートン法を$O(\alpha\log(1/\epsilon))$から$O\big(\frac{\log(1/\epsilon)}{\log(n)}\big)$から$O(\alpha\log(n))$へ渡る、すなわち$O(\alpha\log(n))$、$n$は和成分の数であり、$\alpha$はヘッセン推定の近似因子である。 驚くべきことに、このアクセラレーションは、SVRNのユニークな特性であるデータサイズが$n$ほど大きくなる。 我々のアルゴリズムは、容易に並列化可能な大バッチ演算や単純な単位ステップサイズなど、ニュートン型手法の重要な利点を保っている。 我々は、SVRNを用いてSubsampled Newton と Iterative Hessian Sketch アルゴリズムを高速化し、人気のある一階法と分散-還元法を比較した。

関連論文リスト

• Improving Stochastic Cubic Newton with Momentum [37.1630298053787]
  モーメントが推定値の分散を確実に安定化させることを示す。 グローバリゼーション手法を用いて収束点を証明した。 また、運動量を持つ凸ニュートン法を示す。
  論文  参考訳（メタデータ） (2024-10-25T15:49:16Z)
• Alternating Iteratively Reweighted $\ell_1$ and Subspace Newton Algorithms for Nonconvex Sparse Optimization [11.56128809794923]
  本稿では,可微分損失関数と非滑らか正規化関数の和を最小化する新しいハイブリッドアルゴリズムを提案する。 臨界点へのグローバル収束を証明し、適切な条件下では、アルゴリズムが既存の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:15:59Z)
• Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients [0.196629787330046]
  目的関数の部分的な2次情報を組み込むことで、分散還元勾配法のミニバッチサイズに対するロバスト性を劇的に向上させることができることを示す。 本稿では,この現象をプロトタイプNewton(textttMb-SVRN$)アルゴリズムで示す。
  論文  参考訳（メタデータ） (2024-04-23T05:45:52Z)
• 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)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• 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)
• 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)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Stochastic Subspace Cubic Newton Method [14.624340432672172]
  本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。 ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。 注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
  論文  参考訳（メタデータ） (2020-02-21T19:42:18Z)
• 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)

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

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