論文の概要: Noise-adaptive (Accelerated) Stochastic Heavy-Ball Momentum
- arxiv url: http://arxiv.org/abs/2401.06738v1
- Date: Fri, 12 Jan 2024 18:17:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-15 18:47:49.614254
- Title: Noise-adaptive (Accelerated) Stochastic Heavy-Ball Momentum
- Title(参考訳): 騒音適応型(加速型)確率重ボールモーメント
- Authors: Anh Dang, Reza Babanezhad, Sharan Vaswani
- Abstract要約: SHB (小さなミニバッチを持つ) は二次群においても加速的な収束速度を達成できないことを示す。
本稿では,収束に対する雑音適応的アプローチを実現するための多段階アプローチを提案する。
- 参考スコア(独自算出の注目度): 7.974134340935598
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the convergence of stochastic heavy ball (SHB) momentum in the
smooth, strongly-convex setting. Kidambi et al. (2018) show that SHB (with
small mini-batches) cannot attain an accelerated rate of convergence even for
quadratics, and conjecture that the practical gain of SHB is a by-product of
mini-batching. We substantiate this claim by showing that SHB can obtain an
accelerated rate when the mini-batch size is larger than some threshold. In
particular, for strongly-convex quadratics with condition number $\kappa$, we
prove that SHB with the standard step-size and momentum parameters results in
an $O\left(\exp(-\frac{T}{\sqrt{\kappa}}) + \sigma \right)$ convergence rate,
where $T$ is the number of iterations and $\sigma^2$ is the variance in the
stochastic gradients. To ensure convergence to the minimizer, we propose a
multi-stage approach that results in a noise-adaptive
$O\left(\exp\left(-\frac{T}{\sqrt{\kappa}} \right) + \frac{\sigma}{T}\right)$
rate. For general strongly-convex functions, we use the averaging
interpretation of SHB along with exponential step-sizes to prove an
$O\left(\exp\left(-\frac{T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$
convergence to the minimizer in a noise-adaptive manner. Finally, we
empirically demonstrate the effectiveness of the proposed algorithms.
- Abstract(参考訳): 我々は,滑らかで強い凸条件下での確率重球(SHB)運動量の収束を解析した。
Kidambi et al. (2018) は、SHB (小さなミニバッチを持つ) が二次数に対してさえ収束速度が加速できないことを示し、SHB の実用的ゲインがミニバッチの副産物であるという予想を示した。
ミニバッチサイズがしきい値より大きい場合、shbは加速速度を得ることができることを示すことで、この主張を裏付ける。
特に、条件数$\kappa$の強い凸二次数に対して、標準のステップサイズと運動量パラメータを持つSHBが$O\left(\exp(-\frac{T}{\sqrt{\kappa}}) + \sigma \right)$収束率、$T$は反復数、$\sigma^2$は確率勾配の分散であることを示す。
最小化器への収束を確保するために、雑音適応型 $O\left(-\frac{T}{\sqrt{\kappa}} \right) + \frac{\sigma}{T}\right)$ rate をもたらす多段階アプローチを提案する。
一般の強凸函数に対しては、SHB の平均解釈と指数的なステップサイズを使い、$O\left(\exp\left(-\frac{T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$ を雑音適応的に最小値に収束させる。
最後に,提案アルゴリズムの有効性を実証的に示す。
関連論文リスト
- Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Sharper Analysis for Minibatch Stochastic Proximal Point Methods:
Stability, Smoothness, and Deviation [41.082982732100696]
我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。
ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。
小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
論文 参考訳(メタデータ) (2023-01-09T00:13:34Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳(メタデータ) (2021-10-21T19:22:14Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳(メタデータ) (2021-01-31T16:17:56Z) - Inference on the change point in high dimensional time series models via
plug in least squares [2.7718973516070684]
本研究では,変化が高次元ランダムベクトルの平均となる点パラメータの最小2乗推定器について検討する。
この推定器が平均パラメータの推定におけるプラグに対する十分な適応性を持つ十分な条件を得る。
論文 参考訳(メタデータ) (2020-07-03T18:08:12Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳(メタデータ) (2020-06-14T11:12:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。