stat.MLNov 10, 2026
SaveImproved last-iterate bounds for SGD with and without replacement
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 to 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.
More in this topic
Last-Iterate Convergence
Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.
See all 47 papersWe 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 of the stochastic gradients at the optimum is small or zero. We establish that after steps of SGD on -smooth convex losses with any constant stepsize , the last iterate attains expected excess risk , which gives the rate for every constant stepsize in the interpolation regime (), matching the lower bound up to logarithmic factors and improving upon the rate of Attia et al. (2026) for . 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 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.
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 . 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.
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 -smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order . 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 . We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying , where is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.