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

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

    Oct 18, 2026Matan Schliserman, Tomer KorenSmooth Convex OptimizationLast-Iterate Convergence

  2. Improved last-iterate bounds for SGD with and without replacement

    Nov 10, 2026Yimin Zhong, Jiaxin ZhouLast-Iterate ConvergenceStochastic Optimization Convergence

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

    Sep 8, 2026Ruijie Li, Kang Chen, Tianyu WangLearning Rate SchedulingLast-Iterate Convergence