論文の概要: Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients
- arxiv url: http://arxiv.org/abs/2404.14758v1
- Date: Tue, 23 Apr 2024 05:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 15:10:30.538201
- Title: Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients
- Title（参考訳）: 2次情報を用いた分散誘導勾配におけるミニバッチロバストネスの促進
- Authors: Sachin Garg, Albert S. Berahas, Michał Dereziński,
- Abstract要約: 目的関数の部分的な2次情報を組み込むことで、分散還元勾配法のミニバッチサイズに対するロバスト性を劇的に向上させることができることを示す。
本稿では,この現象をプロトタイプNewton(textttMb-SVRN$)アルゴリズムで示す。
- 参考スコア（独自算出の注目度）: 0.196629787330046
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that, for finite-sum minimization problems, incorporating partial second-order information of the objective function can dramatically improve the robustness to mini-batch size of variance-reduced stochastic gradient methods, making them more scalable while retaining their benefits over traditional Newton-type approaches. We demonstrate this phenomenon on a prototypical stochastic second-order algorithm, called Mini-Batch Stochastic Variance-Reduced Newton ($\texttt{Mb-SVRN}$), which combines variance-reduced gradient estimates with access to an approximate Hessian oracle. In particular, we show that when the data size $n$ is sufficiently large, i.e., $n\gg \alpha^2\kappa$, where $\kappa$ is the condition number and $\alpha$ is the Hessian approximation factor, then $\texttt{Mb-SVRN}$ achieves a fast linear convergence rate that is independent of the gradient mini-batch size $b$, as long $b$ is in the range between $1$ and $b_{\max}=O(n/(\alpha \log n))$. Only after increasing the mini-batch size past this critical point $b_{\max}$, the method begins to transition into a standard Newton-type algorithm which is much more sensitive to the Hessian approximation quality. We demonstrate this phenomenon empirically on benchmark optimization tasks showing that, after tuning the step size, the convergence rate of $\texttt{Mb-SVRN}$ remains fast for a wide range of mini-batch sizes, and the dependence of the phase transition point $b_{\max}$ on the Hessian approximation factor $\alpha$ aligns with our theoretical predictions.
- Abstract（参考訳）: 有限サム最小化問題に対して、目的関数の部分的な2次情報を組み込むことで、分散還元確率勾配法(英語版)のミニバッチサイズへのロバスト性を大幅に向上し、従来のニュートン型手法よりもその利点を保ちながら、よりスケーラブルであることを示す。
この現象は,確率的二階法であるMini-Batch Stochastic Variance-Reduced Newton ("\texttt{Mb-SVRN}$") で示される。
特に、データサイズ$n$が十分大きい場合、例えば$n\gg \alpha^2\kappa$, where $\kappa$ is the condition number and $\alpha$ is the Hessian approximation factor, $\texttt{Mb-SVRN}$は勾配のミニバッチサイズ$b$とは独立な高速な線形収束率を達成する。
この臨界点$b_{\max}$を超えるミニバッチサイズを拡大した後のみ、この手法はヘッセン近似の品質にはるかに敏感な標準ニュートン型アルゴリズムに遷移し始める。
ステップサイズを調整した後、$\texttt{Mb-SVRN}$の収束速度は、幅広いミニバッチサイズで高速であり、相転移点$b_{\max}$のヘッセン近似係数$\alpha$への依存性は、我々の理論的予測と一致していることを示す。
関連論文リスト
- (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
ヘビーボール運動量(SHB)は、機械学習モデルのトレーニングに一般的に用いられ、勾配降下の反復よりも経験的な改善を提供することが多い。
SHB は小サイズが $kappa の閾値 $b* よりも大きい場合に加速できることを示す。
論文 参考訳（メタデータ） (2024-01-12T18:17:28Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳（メタデータ） (2023-09-03T19:21:59Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳（メタデータ） (2022-11-29T18:38:40Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。
高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。
提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
論文 参考訳（メタデータ） (2022-02-19T22:12:30Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2021-02-09T02:44:24Z) - Fast decentralized non-convex finite-sum optimization with recursive
variance reduction [19.540926205375857]
本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
論文 参考訳（メタデータ） (2020-08-17T15:51:32Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。