stat.MLNov 10, 2026

Improved last-iterate bounds for SGD with and without replacement

Authors: Yimin Zhong, Jiaxin Zhou

Organizations: Department of Mathematics and Statistics, Auburn University, Auburn, AL 36830

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)\cO((\log T)^3/T) to \cO((log⁡T)3/(Tlog⁡log⁡T))\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.

Explore similar work

CardsList
  1. Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

    Oct 18, 2026Matan Schliserman, Tomer KorenSmooth Convex OptimizationLast-Iterate Convergence

  2. Bias-Optimal Bounds for Stochastic Gradient Descent

    May 23, 2025Daniel Cortild, Lucas Ketels, Juan Peypouquet +1Stochastic Gradient DescentStochastic Optimization Convergence

  3. Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

    Oct 14, 2026Zijun Chen, Zihan ZhangStochastic OptimizationLast-Iterate Convergence