Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

Leonardo Galli, Daniela Angela Parletta, Andrea PaudicearXiv 2026 · arXiv

TL;DR

This paper provides the first high-probability convergence guarantees for Stochastic Gradient Descent (SGD) in the "interpolation regime" (where models are large enough to fit training data perfectly) without requiring the typical, overly restrictive noise assumptions. The authors prove that in this regime, SGD achieves "fast" convergence rates—matching deterministic Gradient Descent—not just on average, but with high confidence for a single run.

What Problem Does This Paper Address?

Most theoretical guarantees for SGD are "in-expectation," meaning they describe the average behavior over many hypothetical runs. However, in practice, a researcher only runs an algorithm once. To ensure that a single run won't fail or behave wildly differently from the average, we need high-probability bounds.

Historically, obtaining these bounds required assuming the "noise" in the gradients was very well-behaved (e.g., bounded or sub-Gaussian). In the interpolation regime—highly relevant to modern deep learning where models have more parameters than data points—SGD is known to converge much faster. Yet, existing high-probability analyses for this regime either didn't exist or relied on those same restrictive assumptions that don't always hold in practice. This paper fills that gap, showing that the structural property of interpolation itself is enough to "tame the tails" of SGD.

Methods

The authors analyze SGD under Assumption 4 (Step Size Condition), a unified framework that covers various popular schedules, including constant step sizes, Stochastic Line Search (SLS), and Stochastic Polyak Step Size (SPS).

The technical "secret sauce" of their proof is Fejér monotonicity. In the interpolation regime, the iterates of SGD are shown to stay within a deterministic ball around the optimal solution. This property allows the authors to use self-normalized martingale techniques. Instead of the noise being an external "enemy," the variance of the noise is bounded by the optimization error itself. As the algorithm gets closer to the solution, the noise naturally vanishes, allowing for much tighter concentration of the results than in standard stochastic optimization.

Datasets

Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs and convergence analysis. No empirical experiments or datasets were used.

Key Insights and Ideas

  • Interpolation as a Regularizer of Noise: The paper highlights that interpolation isn't just about fitting data; it changes the fundamental nature of the stochastic noise. Because the noise vanishes at the optimum, the "tails" of the distribution are naturally suppressed.
  • The "Lazy Event" Obstruction: In the strongly convex case, the authors found a fundamental limit. They proved a lower bound showing that you cannot have both an exponential convergence rate in $n$ and a very mild (logarithmic) dependence on the failure probability $\beta$. This is due to a "lazy event" where all sampled gradients happen to be zero, causing the algorithm to "freeze" momentarily.
  • No Extra Assumptions Needed: Remarkably, for smooth convex functions, they achieve a high-probability rate of $O(\frac{\log(1/\beta)}{n})$. This matches the best-known "in-expectation" rates while only adding a logarithmic penalty for the confidence level, all without requiring bounded noise.

Key Results

  • Convex Objectives: Achieves a "fast rate" of $O(n^{-1})$ with probability $1-\beta$. This is a significant jump over the standard $O(n^{-1/2})$ rate found in non-interpolated settings.
  • Strongly Convex Objectives: Establishes an exponential convergence rate. However, it reveals a trade-off: to get better confidence (smaller $\beta$), you must accept a slightly slower (though still exponential) rate in $n$.
  • Low-Noise Extension: When interpolation is almost true (low noise at the optimum), the rate degrades gracefully from $O(n^{-1})$ to $O(n^{-1/2})$, providing a bridge between the interpolation regime and classical settings.
  • Nonconvex (PL) Objectives: The authors extend the results to functions satisfying the Polyak-Łojasiewicz (PL) condition, proving an exponential high-probability rate even without global convexity.

Limitations and Future Work

  • Adaptivity in Extensions: While the main results for convex/strongly convex cases work with adaptive step sizes (like SLS), the extensions to low-noise and nonconvex (PL) regimes currently require step sizes tuned to unknown problem constants (like the noise level $\sigma_\star$ or the PL constant $\mu$).
  • Last-Iterate vs. Average: The convex result focuses on the average of the iterates ($\bar{x}_n$). While common in theory, practitioners often care about the very last iterate.
  • Mirror Descent: The current analysis is specific to SGD in Hilbert spaces. Extending these high-probability "fast rates" to the more general Mirror Descent framework remains an open challenge.

Summary updated

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}) \cdot n^{-1}$ after $n$ iterations, with failure probability at most $β$. In the strongly convex case, we derive a family of moment-based bounds of order $β^{-p} \cdot \exp(-\mathcal{O}(p \cdot n))$ for $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.
BibTeX
@misc{galli2026taming,
  author = {Leonardo Galli and Daniela Angela Parletta and Andrea Paudice},
  title = {{Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime}},
  year = {2026},
  eprint = {2611.24562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24562},
}
Figure