High-Probability Convergence for Composite and Distributed Stochastic
  Minimization and Variational Inequalities with Heavy-Tailed Noise
Eduard Gorbunov Abdurakhmon Sadiev Marina Danilova Samuel Horváth Gauthier Gidel Pavel Dvurechensky Alexander Gasnikov Peter Richtárik
High-probability analysis of stochastic first-order optimization methods
under mild assumptions on the noise has been gaining a lot of attention in
recent years. Typically, gradient clipping is one of the key algorithmic
ingredients to derive good high-probability guarantees when the noise is
heavy-tailed. However, if implemented na\"ively, clipping can spoil the
convergence of the popular methods for composite and distributed optimization
(Prox-SGD/Parallel SGD) even in the absence of any noise. Due to this reason,
many works on high-probability analysis consider only unconstrained
non-distributed problems, and the existing results for composite/distributed
problems do not include some important special cases (like strongly convex
problems) and are not optimal. To address this issue, we propose new stochastic
methods for composite and distributed optimization based on the clipping of
stochastic gradient differences and prove tight high-probability convergence
results (including nearly optimal ones) for the new methods. Using similar
ideas, we also develop new methods for composite and distributed variational
inequalities and analyze the high-probability convergence of these methods.