Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

2020/05/21 by Eduard Gorbunov, М. А. Данилова, Gorbunov, Eduard +4 · 11 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/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.

Cited by

• Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Mean
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences
• Federated Stochastic Minimax Optimization under Heavy-Tailed Noises
• Online Distributed Zeroth-Order Optimization With Non-Zero-Mean Adverse Noises
• Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
• Gradient Shaping Beyond Clipping: A Functional Perspective on Update Magnitude Control
• Improved High-probability Convergence Guarantees of Decentralized SGD
• The Convergence Behavior of Adam under Heavy-Tailed Noise
• Stochastic Bilevel Optimization with Heavy-Tailed Noise
• Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds

Related

• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems
• High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise