Paperlane

no. 14 · Friday 13 November 2026

Improved last-iterate bounds for SGD with and without replacement

Yimin Zhong and Jiaxin Zhou

math.OC · via stat.ML

Abstract

In this work, we study last-iterate convergence bounds for stochastic gradient descent (SGD) on convex and $β$-smooth loss functions and improve the bound from $\cO((\log T)^3/T)$ to $\cO((\log T)^3/(T\log\log T))$ in the interpolation regime. The improvement comes from applying a horizon-dependent multiscale estimate of gradients to the comparison of trajectories. The bound applies to both sampling with replacement and sampling without replacement within one pass.

fields
Optimization and Control
pdf ↗ page arXiv:2611.14811 ↗