Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

  • 2020-05-21 17:05:27
  • Eduard Gorbunov, Marina Danilova, Alexander Gasnikov
  • 1


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.


Quick Read (beta)

loading the full paper ...