Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime
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 after iterations, with failure probability at most . In the strongly convex case, we derive a family of moment-based bounds of order for , 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.
Stochastic Optimization Convergence
Stochastic optimization convergence studies how noisy, sampled, or delayed updates approach solutions and how fast they do so.
See all 229 papers