論文の概要: 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)$ を雑音適応的に最小値に収束させる。
最後に,提案アルゴリズムの有効性を実証的に示す。
関連論文リスト
- Edge of Stochastic Stability: Revisiting the Edge of Stability for SGD [0.0]
我々は,ミニバッチ勾配降下(SGD)列車が異なる体制で「エッジ・オブ・安定性(EoSS)」と呼ばれることを示す。
2/eta$で安定化されるのは *Batch Sharpness* である。
さらに,SGD軌道の数学的モデリングについて考察する。
論文 参考訳(メタデータ) (2024-12-29T18:59:01Z) - Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD [16.019880089338383]
Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsff
論文 参考訳(メタデータ) (2024-10-26T10:14:17Z) - Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients [0.196629787330046]
目的関数の部分的な2次情報を組み込むことで、分散還元勾配法のミニバッチサイズに対するロバスト性を劇的に向上させることができることを示す。
本稿では,この現象をプロトタイプNewton(textttMb-SVRN$)アルゴリズムで示す。
論文 参考訳(メタデータ) (2024-04-23T05:45:52Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳(メタデータ) (2023-03-30T02:51:00Z) - 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) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳(メタデータ) (2021-10-21T19:22:14Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳(メタデータ) (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。