New Bounds for the Last Iterate of the Stochastic subGradient Method
For optimization theorists, it tightens bounds for the last iterate of SGD under i.i.d. noise and resolves an open problem about optimality under non-i.i.d. noise.
The paper proves that for one-dimensional convex Lipschitz objectives with i.i.d. subgradient noise, the last iterate of the stochastic subgradient method achieves an optimization error of order 1/√n, removing a log factor. Without i.i.d. noise, the error is (log n)/√n, showing suboptimality and resolving an open problem.
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 $η=Θ(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.