The Cube-Root Barrier for Almost-Sure Last-Iterate Convergence of SGD

Almost-sure last-iterate convergence is the natural pathwise guarantee for stochastic gradient descent (SGD), which is typically run once with a deterministic stepsize schedule and returns its last iterate. We determine the fastest polynomial order of almost-sure last-iterate convergence that such a schedule can guarantee for smooth convex objectives under the standard conditional ABC second-moment condition, up to a slowly varying logarithmic correction. We establish a sharp cube-root barrier: the optimal polynomial exponent is $1/3$, with a single schedule achieving every smaller exponent, while no deterministic schedule can guarantee a larger one. We further show that the lower bound already holds for one-dimensional smooth convex problems with fixed i.i.d. finite-variance gradient noise, and that a logarithmically corrected schedule attains this optimal cube-root order up to a polylogarithmic factor.