math.OCNov 18, 2026

Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

Authors: Leonardo Galli, Daniela Angela Parletta, Andrea Paudice

Organizations: Mathematisches Institut, LMU Munich, Theresienstr. 39, 80333 Munich, Germany · Munich Center for Machine Learning · Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus, Denmark

Abstract

In this paper, we study stochastic gradient descent in the smooth interpolation regime, where the population objective shares a common minimizer with the sample losses. In contrast to prior work, which has largely focused on in-expectation analysis, we obtain high-probability convergence guarantees under the same assumptions. In the convex case, we prove a fast rate of order log⁡(β−1)⋅n−1\log(β^{-1}) \cdot n^{-1} after nn iterations, with failure probability at most ββ. In the strongly convex case, we derive a family of moment-based bounds of order β−p⋅exp⁡(−O(p⋅n))β^{-p} \cdot \exp(-\mathcal{O}(p \cdot n)) for p∈(0,1]p \in (0,1], and complement them with a matching lower bound showing that the corresponding deterioration in the exponential rate is essentially unavoidable. In both settings, our theoretical results are unified across a broad class of step-size schedules. Building on this analysis, we extend our results to a low-noise regime and to nonconvex objectives satisfying the Polyak-Lojasiewicz condition.

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.
Nov 10, 2026

Improved last-iterate bounds for SGD with and without replacement

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.
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.