An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise

Abstract

In this paper, we provide novel optimal (or near optimal) convergence rates for a clipped version of the stochastic subgradient method. We consider nonsmooth convex problems over possibly unbounded domains, under heavy-tailed noise that possesses only the first $p$ moments for $p\in \left]1,2\right]$. For the last iterate, we establish convergence in expectation for the objective values with rates of order $({\log }^{1/p}k)/k^{(p-1)/p}$ and $1/k^{(p-1)/p}$, for anytime and finite-horizon respectively. We also derive new convergence rates, in expectation and with high probability, for the objective values along the average iterates--improving existing results by a ${\log }^{(2p-1)/p}k$ factor. Those results are applied to the problem of supervised learning with kernels demonstrating the effectiveness of our theory. Finally, we give preliminary experiments.

38 pages (Major update that needed a change in the title, abstract, and list of contributions)