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

Oct 18, 2026

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

We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance σ⋆2σ_\star^2 of the stochastic gradients at the optimum is small or zero. We establish that after TT steps of SGD on ββ-smooth convex losses with any constant stepsize 0<η<2/β0<η<2/β, the last iterate attains expected excess risk O~(1η(2−βη)3T+η(2−βη)4σ⋆2)\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr), which gives the rate O~(1/T)\smash{\widetilde O(1/T)} for every constant stepsize in the interpolation regime (σ⋆=0σ_\star=0), matching the Ω(1/T)Ω(1/T) lower bound up to logarithmic factors and improving upon the O(1/T)O(1/\sqrt T) rate of Attia et al. (2026) for η=1/βη=1/β. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an O(1/T)O(1/T) rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.
May 23, 2025

Bias-Optimal Bounds for Stochastic Gradient Descent

The non-asymptotic analysis of Stochastic Gradient Descent (SGD) typically yields bounds that decompose into a bias term and a variance term. In this work, we focus on the bias component and study the extent to which SGD can match the optimal convergence behavior of deterministic gradient descent. Assuming only (strong) convexity and smoothness of the objective, we derive new bounds for the full range of constant step-sizes γL∈(0,2)γL \in (0,2). This includes critical and large step-size regimes that were previously unexplored without additional variance assumptions, in both the convex and strongly convex cases. Those bounds are bias-optimal, in the sense that the bias term coincides with the worst-case rate of gradient descent, for all non-critical step-sizes. For critical step-sizes, we show that no bounds can be obtained with an optimal bias term, but that this optimal bias can be approximated arbitrarily closely. As an immediate application, we provide new complexity bounds for the Stochastic Proximal algorithm, without the need of regularity assumptions.
Oct 14, 2026

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

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex LL-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order 1/L1/L. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components nn. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying 0<η≲1/(L(1+log⁡(nK)))0<η\lesssim 1/(L(1 + \log(nK))), where KK is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit 1/n1/n factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.