論文の概要: Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient
Clipping
- arxiv url: http://arxiv.org/abs/2005.10785v2
- Date: Fri, 23 Oct 2020 11:00:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 00:04:36.439115
- Title: Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient
Clipping
- Title(参考訳): 加速度勾配クリッピングによる重音の確率最適化
- Authors: Eduard Gorbunov, Marina Danilova, Alexander Gasnikov
- Abstract要約: そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。
この場合、最先端の結果を上回る新たな複雑さが証明される。
本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
- 参考スコア(独自算出の注目度): 69.9674326582747
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a new accelerated stochastic first-order method
called clipped-SSTM for smooth convex stochastic optimization with heavy-tailed
distributed noise in stochastic gradients and derive the first high-probability
complexity bounds for this method closing the gap in the theory of stochastic
optimization with heavy-tailed noise. Our method is based on a special variant
of accelerated Stochastic Gradient Descent (SGD) and clipping of stochastic
gradients. We extend our method to the strongly convex case and prove new
complexity bounds that outperform state-of-the-art results in this case.
Finally, we extend our proof technique and derive the first non-trivial
high-probability complexity bounds for SGD with clipping without light-tails
assumption on the noise.
- Abstract(参考訳): 本稿では,確率勾配の重み付き分散雑音を用いた滑らかな凸確率最適化のためのクリップドsstmと呼ばれる新しい加速確率的一階法を提案し,重み付き雑音を用いた確率最適化理論のギャップを閉じる最初の高確率複雑性境界を導出する。
本手法は,加速度的確率勾配降下 (sgd) の特殊変種と確率勾配のクリップングに基づいている。
我々は,本手法を強凸の場合まで拡張し,この場合の最先端結果を上回る新しい複雑性境界を証明した。
最後に,本手法を拡張し,ノイズの微妙な仮定を伴わないクリッピングによるSGDの非自明な高確率複雑性境界を導出する。
関連論文リスト
- Variance Reduction and Low Sample Complexity in Stochastic Optimization
via Proximal Point Method [5.025654873456757]
本論文は,提案手法の収束性に関する高い確率保証を得るために,低サンプリング複雑性を確立する。
近位サブプロブレムを解くためにサブルーチンが開発され、分散還元のための新しい技術としても機能する。
論文 参考訳(メタデータ) (2024-02-14T07:34:22Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - High-Probability Convergence for Composite and Distributed Stochastic
Minimization and Variational Inequalities with Heavy-Tailed Noise [60.92108236919524]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳(メタデータ) (2023-10-03T07:49:17Z) - First Order Methods with Markovian Noise: from Acceleration to
Variational Inequalities [114.69800889030142]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳(メタデータ) (2023-05-25T11:11:31Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳(メタデータ) (2022-06-08T10:17:40Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳(メタデータ) (2022-06-02T15:21:55Z) - Computing the Variance of Shuffling Stochastic Gradient Algorithms via
Power Spectral Density Analysis [6.497816402045099]
理論上の利点を持つ勾配降下(SGD)の2つの一般的な選択肢は、ランダムリシャッフル(SGDRR)とシャッフルオンス(SGD-SO)である。
本研究では,SGD,SGDRR,SGD-SOの定常変動について検討した。
論文 参考訳(メタデータ) (2022-06-01T17:08:04Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。