Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
arXiv:2005.10785
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.
arXiv commentNeurIPS 2020; 60 pages, 15 figures
References in corpus (17)
- On the difficulty of training Recurrent Neural Networks
- Convolutional Sequence to Sequence Learning
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Regularizing and Optimizing LSTM Language Models
- Train faster, generalize better: Stability of stochastic gradient descent
- Loss minimization and parameter estimation with heavy tails
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Parametric estimation. Finite sample theory
- Why gradient clipping accelerates training: A theoretical justification for adaptivity
- The Power of Normalization: Faster Evasion of Saddle Points
- Better Theory for SGD in the Nonconvex World
- A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
- A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
- A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
- Stochastic gradient methods with inexact oracle
- Universal fast gradient method for stochastic composit optimization problems
- From low probability to high confidence in stochastic convex optimization
Cited by in corpus (5)
- Review: Deep Learning in Electron Microscopy
- Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness
- Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
- Improved Analysis of Clipping Algorithms for Non-convex Optimization
- Heavy-tailed Streaming Statistical Estimation