New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives.

For a fixed horizon $n$, we consider the standard fixed stepsizes $\eta =\Theta(1/\sqrt n)$.

We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order $1/\sqrt n$, thereby removing the extra $(\log n)$ factor present in existing generic bounds.

On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order $(\log n)/\sqrt n$.

Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.