Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

In this paper, we propose a new accelerated stochastic first-order method\ncalled clipped-SSTM for smooth convex stochastic optimization with heavy-tailed\ndistributed noise in stochastic gradients and derive the first high-probability\ncomplexity bounds for this method closing the gap in the theory of stochastic\noptimization with heavy-tailed noise. Our method is based on a special variant\nof accelerated Stochastic Gradient Descent (SGD) and clipping of stochastic\ngradients. We extend our method to the strongly convex case and prove new\ncomplexity bounds that outperform state-of-the-art results in this case.\nFinally, we extend our proof technique and derive the first non-trivial\nhigh-probability complexity bounds for SGD with clipping without light-tails\nassumption on the noise.\n