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

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 ∈ left]1,2right]. For the last iterate, we establish convergence in expectation for the objective values with rates of order (log1/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.