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

In stochastic (strongly) convex optimization, establishing last-iterate convergence guarantees for first-order methods has recently garnered increasing attention, as this not only deepens the theoretical understanding of these algorithms but also aligns more closely with practice. Notably, people have demonstrated that one of the most famous, simple, and popular methods, Stochastic Gradient Descent ($\mathtt{SGD}$), provably achieves last-iterate convergence. However, the existing results may have limited applicability, since they typically rely on strong conditions on the gradient noise (e.g., an exponentially decaying tail) rather than the more realistic heavy-tailed noise. Unfortunately, when faced with heavy-tailed noise, $\mathtt{SGD}$ is known to exhibit undesirable behavior or even fail to converge. To address the challenge of heavy-tailed noise, people have proposed $\mathtt{Clipped}\text{-}\mathtt{SGD}$, an algorithm that combines $\mathtt{SGD}$ with a simple mechanism, gradient clipping. Although $\mathtt{Clipped}\text{-}\mathtt{SGD}$ performs well in practice, its last-iterate convergence property remains highly underexplored. In this work, we prove the first optimal last-iterate rates in high probability for $\mathtt{Clipped}\text{-}\mathtt{SGD}$ under heavy-tailed noise, thereby closing a gap in the literature.

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon $n$, we consider the standard fixed stepsizes $η=Θ(1/\sqrt n)$. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order $1/\sqrt n$, thereby removing the extra $(\log n)$ factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order $(\log n)/\sqrt n$. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

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 $σ_\star^2$ of the stochastic gradients at the optimum is small or zero. We establish that after $T$ steps of SGD on $β$-smooth convex losses with any constant stepsize $0<η<2/β$, the last iterate attains expected excess risk $\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$, which gives the rate $\smash{\widetilde O(1/T)}$ for every constant stepsize in the interpolation regime ($σ_\star=0$), matching the $Ω(1/T)$ lower bound up to logarithmic factors and improving upon the $O(1/\sqrt T)$ rate of Attia et al. (2026) for $η=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)$ 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.