betaFeedback

WorksComputer Science

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

Abstract

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.

Paper details

vlnc:W_8ut7asfr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…