math.OCNov 18, 2026

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

Authors: Weiming Ou, Andrea Paudice, Xiao Wang

Organizations: School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, No.777 Guoding Road, 200433 Shanghai, China · Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus, Denmark · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, No.777 Guoding Road, 200433 Shanghai, China

Abstract

We study the almost sure convergence of the last-iterate optimization error of Stochastic (sub)Gradient Descent (SGD) for convex objectives. For smooth objectives, we establish convergence rates of order k−1/3k^{-1/3} when a stationary minimizer exists, and k−1/4k^{-1/4} otherwise, up to polylogarithmic factors, where kk denotes the iteration counter. We further show that the latter rate extends to nonsmooth convex objectives. All these rates are achieved by deterministic, anytime stepsize policies. Finally, we establish matching lower bounds showing that the exponents −1/3-1/3 and −1/4-1/4 are optimal, up to polylogarithmic factors, for the corresponding problem classes.

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.
Apr 15, 2026

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. We prove that Θ(log⁡(T)/T)Θ(\sqrt{\log(T)/T}) is the optimal anytime rate attainable with a fixed stepsize schedule (that does not depend on the total number of steps TT). The upper bound holds already for SGD, and improves on the log⁡(T)/T\log(T)/\sqrt{T} rate of Shamir and Zhang [2013], as well as the log⁡(T)/T\sqrt{\log(T)/T} rate of Zamani and Glineur [2023] which was proven only for deterministic GD. The matching lower bound holds already for GD, and confirms the conjecture of Jain et al. [2019], namely that the optimal 1/T1/\sqrt{T} rate for the last iterate cannot be obtained without prior knowledge of TT.
Sep 8, 2026

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to log⁡n/n\sqrt{\log n / n} but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence hh satisfying h(n)=o(n)h(n) = o(\sqrt{n}), a bound of order h(n)/nh(n)/\sqrt{n}, holding simultaneously for all nn with probability at least 1−α1-α and uniformly over the problem class, is achievable if and only if ∑j=1∞1h(2j)2<∞.\sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.