Abstract: Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic accelerated method for both convex and strongly-convex functions. We also show that this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent in non-convex settings. Under interpolation, we further show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an $O(1/k^2)$ mistake bound for $k$ iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.
The Interpolation Regime in Modern Machine Learning
In classical optimization theory, Stochastic Gradient Descent (SGD) is typically viewed as a noisy approximation of Gradient Descent (GD). Because mini-batch gradients introduce variance that persists even near the optimum, researchers traditionally employ a decaying step size (e.g., $1/\sqrt{k}$) to ensure convergence. However, this approach forces sub-linear convergence rates, which are significantly slower than the linear rates possible with deterministic GD.
Modern deep learning models are often over-parameterized, meaning they possess enough capacity to achieve zero training loss, a property known as interpolation. In this regime, the "noise" in the stochastic gradient vanishes at the optimum because the gradient for every individual sample becomes zero. This paper bridges the gap between pessimistic classical theory and the empirical success of constant step-size SGD by leveraging this interpolation property.
Growth Conditions: Bridging Stochastic and Deterministic Optimization
The authors analyze SGD through two key mathematical conditions that emerge under interpolation:
- Strong Growth Condition (SGC): This condition bounds the norm of the stochastic gradient by the norm of the full gradient. It implies that as the full gradient approaches zero, the stochastic noise disappears, allowing SGD to behave more like its deterministic counterpart.
- Weak Growth Condition (WGC): A novel, more relaxed condition introduced in this work. The authors prove that any smooth loss function with a finite-sum structure satisfies the WGC if it can interpolate the data. This makes the theory applicable to a vast range of modern architectures.
Accelerated SGD and the $O(1/k^2)$ Rate
Traditionally, Nesterov acceleration is difficult to apply to SGD because it can amplify stochastic noise. However, under SGC or WGC, the noise is sufficiently well-behaved that acceleration becomes viable. The authors show that constant step-size SGD with Nesterov acceleration (Acc-SGD) can achieve the optimal $O(1/k^2)$ convergence rate for convex functions and linear convergence for strongly convex functions.
Furthermore, in non-convex settings, SGD under SGC finds first-order stationary points at a rate of $O(1/k)$, matching the efficiency of full GD and significantly outperforming the standard $O(1/\sqrt{k})$ rate for general stochastic non-convex optimization.
Empirical Validation on Real-World Datasets
To validate these theoretical findings, the authors conducted experiments on both synthetic and real-world datasets, including CovType (forest cover prediction) and Protein (tertiary structure prediction). To ensure the models were expressive enough to interpolate the training data, the authors utilized Non-parametric Radial Basis Function (RBF) features.
As shown in the results, Acc-SGD consistently converges faster and reaches lower loss levels than standard SGD when the interpolation property is satisfied. The results also highlight the practical utility of the Accelerated Perceptron. By replacing the classical non-smooth hinge loss with a smooth squared-hinge loss, the authors improved the mistake bound from $O(1/k)$ to $O(1/k^2)$.
Conclusion
This work demonstrates that interpolation is a powerful theoretical bridge. By recognizing that stochastic noise vanishes at the optimum in over-parameterized models, we can justify the use of constant step sizes and Nesterov acceleration. While challenges remain in automatically determining optimal step sizes and growth constants, these results provide a rigorous foundation for the high-speed convergence observed in modern deep learning practice.
Summary updated