Abstract
In this paper, we propose a new accelerated stochastic first-order methodcalled clipped-SSTM for smooth convex stochastic optimization with heavy-taileddistributed noise in stochastic gradients and derive the first high-probabilitycomplexity bounds for this method closing the gap in the theory of stochasticoptimization with heavy-tailed noise. Our method is based on a special variantof accelerated Stochastic Gradient Descent (SGD) and clipping of stochasticgradients. We extend our method to the strongly convex case and prove newcomplexity bounds that outperform state-of-the-art results in this case.Finally, we extend our proof technique and derive the first non-trivialhigh-probability complexity bounds for SGD with clipping without light-tailsassumption on the noise.