Optimization Papers

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

Ou et al.

The last iterate of SGD on convex problems converges almost surely at rate \(k^{-1/3}\) for smooth objectives with a stationary minimiser and \(k^{-1/4}\) otherwise, up to logarithmic factors, and both exponents are optimal.

Filed under Optimization, Probability

Most guarantees for stochastic gradient descent hold in expectation or for averaged iterates. This paper asks how fast the optimisation error of the last iterate goes to zero along almost every sample path, for convex objectives.

For smooth objectives the authors prove rates of order \(k^{-1/3}\) when a stationary minimiser exists and \(k^{-1/4}\) otherwise, up to polylogarithmic factors, where \(k\) is the iteration count. The second rate also holds for nonsmooth convex objectives. All rates are reached with deterministic, anytime step sizes, and matching lower bounds show that the exponents \(-1/3\) and \(-1/4\) cannot be improved for these problem classes.