In classical optimization theory, Stochastic Gradient Descent (SGD) is viewed as a noisy approximation of full-batch Gradient Descent (GD). Because each mini-batch provides an imperfect estimate of the true gradient, a persistent "noise floor" remains even near the optimum. To prevent the model from bouncing around this minimum indefinitely, textbooks mandate a decaying learning rate schedule. This safety measure comes at a steep cost: it slows convergence from an exponential (linear) rate down to a sluggish sublinear rate ($O(1/T)$ or $O(1/\sqrt{T})$).
Yet, in modern deep learning, practitioners routinely train massive, overparameterized models using constant learning rates and achieve rapid, high-precision convergence. Why does the textbook theory fail to predict this success?
The answer lies in the interpolation regime—a setting where models possess more parameters than data points, allowing them to perfectly fit every single training sample simultaneously.
The Core Mechanism: Vanishing Gradient Variance
To build intuition, let us look at the objective function we minimize:
$$F(w) = \frac{1}{n} \sum_{i=1}^n f_i(w)$$
where $f_i(w)$ is the loss on the $i$-th sample. In traditional optimization, the global minimizer $w^*$ minimizes the average loss, but individual losses $f_i(w^*)$ remain positive and their gradients $\nabla f_i(w^*)$ point in conflicting directions. This conflict is the source of stochastic gradient noise.
In the interpolation regime, the model is expressive enough to achieve zero loss on every single sample at the global optimum. That is, $f_i(w^*) = 0$ for all $i$. Because each $f_i$ is non-negative and smooth, reaching its absolute minimum implies that its individual gradient must also vanish:
$$\nabla f_i(w^*) = 0$$
As the parameters $w$ approach $w^*$, the variance between the mini-batch gradients and the true gradient doesn't just stay bounded—it naturally drops to zero. This implicit variance reduction mechanism changes the fundamental nature of the optimization landscape. Near the solution, SGD stops acting like a noisy random walk and begins behaving like deterministic gradient descent.
Constant Learning Rates and Linear Convergence
Because the stochastic noise naturally vanishes, the need for a decaying learning rate schedule disappears. In their foundational work, Siyuan Ma et al. demonstrated in The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning that constant step-size SGD achieves exponential (linear) convergence rates under the interpolation condition. By bounding the stochastic gradients via structural growth conditions, Sharan Vaswani showed in Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron that this property allows stochastic methods to match full-batch deterministic rates without the heavy per-iteration computational cost.
This deterministic behavior near the optimum also explains why alternative data-sampling strategies excel. For instance, Shaocong Ma et al. in Understanding the Impact of Model Incoherence on Convergence of Incremental SGD with Random Reshuffle and Lam M. Nguyen in On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms proved that shuffling data without replacement (Random Reshuffling) allows the optimization trajectory to converge exactly to the global minimum, bypassing the persistent variance limitations of standard random sampling.
Unlocking Painless Hyperparameter Tuning
The vanishing noise property does more than just accelerate standard SGD; it enables adaptive optimization techniques to function without tedious manual tuning.
Consider line-search and adaptive step-size methods, which historically struggled in stochastic settings because noise corrupts step-size estimates. In the interpolation regime, Sharan Vaswani et al. developed stochastic line-search methods in Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates, showing they achieve fast deterministic-style convergence because the gradient noise vanishes near the optimum.
Similarly, Nicolas Loizou et al. introduced the Stochastic Polyak Step-size (SPS) in Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence, which leverages individual sample losses to automatically compute optimal step sizes. Because individual losses go to zero at the optimum, the step sizes naturally adapt without requiring explicit knowledge of global smoothness constants. This self-diminishing update magnitude is also a core driver behind the success of adaptive methods like AdaGrad-Norm in overparameterized settings, as analyzed by Xiaoxia Wu et al. in Linear Convergence of Adaptive Stochastic Gradient Descent.
Conquering Heterogeneity in Federated Learning
The benefits of interpolation extend directly to distributed and federated learning architectures. In a typical federated setup, different clients possess highly heterogeneous (non-IID) datasets. This data diversity introduces "client drift," where local updates pull the global model in conflicting directions, creating a persistent noise floor that prevents convergence to a true global optimum.
However, overparameterization fundamentally alters this dynamic. When a global model is large enough to interpolate the combined dataset, the local objectives of all benign clients align perfectly at the global minimum—they all reach zero loss simultaneously. Anastasia Koloskova et al. leveraged this insight in A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, demonstrating that decentralized optimization can achieve centralized linear convergence rates because local stochastic noise and data diversity vanish at the optimum.
Further confirming this, Bingqing Song et al. proved in FedAvg Converges to Zero Training Loss Linearly for Overparameterized Multi-Layer Neural Networks that standard Federated Averaging (FedAvg) converges linearly to zero training loss regardless of data heterogeneity, provided the network is sufficiently wide. As explored by Prashant Khanduri et al. in Linear Convergence of Decentralized FedAvg for PL Objectives: The Interpolation Regime, this self-correcting mechanism allows decentralized systems to bypass complex gradient tracking or correction schemes, as the variance of local updates drops proportionally with the global loss.
When the Interpolation Assumption Fails
Understanding why interpolation works also clarifies its boundaries. If a model is heavily regularized, trained on extreme label noise, or structurally underparameterized, it cannot perfectly fit every training point. In these non-interpolating regimes, individual gradients do not vanish at the optimum, and the steady-state noise floor returns.
As noted by Kanan Gupta et al. in Nesterov acceleration despite very noisy gradients and Holger Rauhut in Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models, failing to satisfy the interpolation condition forces a reliance on traditional noise-reduction schedules or step-size decay to manage persistent gradient variance.
Key Foundational Work
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition (2013) — contributed 3 concept elements to this direction.