Stochastic Gradient Descent (SGD) is the dominant optimization algorithm for training large, over-parameterized machine learning models. Despite its widespread empirical success, the theoretical underpinnings of why it generalizes so well remain heavily debated. Two prevailing hypotheses are that SGD acts as an "implicit regularizer" (biasing the model toward simpler solutions) and that small batch sizes inherently generalize better than full-batch methods.
This paper rigorously investigates these theories within the framework of Stochastic Convex Optimization (SCO). By constructing specific mathematical problem instances, the authors demonstrate that SGD possesses unique properties making it fundamentally superior to both full-batch Gradient Descent (GD) and Regularized Empirical Risk Minimization (RERM) in terms of generalization.
Theoretical Framework and Methodology
Rather than relying on standard empirical benchmarks like ImageNet or CIFAR-10, this study employs rigorous mathematical proofs and synthetic problem constructions. The researchers utilize the SCO framework, where the "population loss" (average error over the entire data distribution) is convex, even if the "instantaneous loss" (error on a single data point) is not.
The core methodology involves designing "hard" mathematical instances to create theoretical separations between algorithms. By doing so, the authors can definitively prove scenarios where certain optimization methods fail while SGD succeeds, thereby isolating the unique advantages of SGD.
Debunking the Implicit Regularization Hypothesis
A major contribution of this work is challenging the popular "implicit regularization" theory. The authors mathematically prove that for any conceivable regularization function, there exists an SCO problem where RERM completely fails to learn, yet SGD succeeds perfectly.
This finding indicates that SGD's generalization capabilities cannot be fully explained by assuming it merely mimics a regularized objective. Instead, SGD inherently avoids certain spurious correlations in the training data that inevitably trick RERM-based approaches.
Sample Complexity: SGD vs. Full-Batch GD
The paper establishes a strict separation in sample complexity between SGD and full-batch GD. The authors prove that for certain SCO problems, full-batch GD—regardless of the chosen step size or number of iterations—learns at a suboptimal rate bounded by $\Omega(1/n^{5/12})$.
In contrast, SGD achieves the optimal learning rate of $O(1/\sqrt{n})$. This provides concrete theoretical evidence that SGD is not just a noisy, computationally cheaper approximation of GD, but a statistically superior method in specific optimization landscapes.
The Advantage of Multiple Epochs
While theoretical analyses often restrict themselves to single-pass (one epoch) SGD for simplicity, practical applications almost always dictate multiple passes over the training data. The authors validate this empirical norm by proving that multi-epoch SGD is at least as good as single-pass SGD in the worst case. Furthermore, for specific SCO problems, taking multiple passes significantly outperforms a single pass. Multi-epoch SGD can achieve a suboptimality of $O(1/\sqrt{nk})$ (where $k$ is the number of epochs), improving upon the standard $O(1/\sqrt{n})$ rate of single-pass SGD.
Implications for Deep Learning
To bridge the gap between convex theory and non-convex deep learning, the authors extend their constructions to a two-layer diagonal neural network with ReLU activations. In this setting, they prove that SGD successfully finds a solution with $O(1/\sqrt{n})$ risk, whereas any ERM-based algorithm fails to achieve better than a constant error (essentially failing to learn).
Additionally, the authors introduce the concept of "linearizability"—referring to functions that can be upper-bounded by a linear function. They propose this as a potential framework for understanding why SGD succeeds in non-convex landscapes typical of deep learning.
Limitations and Future Directions
The primary limitation of this theoretical work is its reliance on artificially constructed, high-dimensional problems (exponential in the number of samples) to prove these algorithmic separations. While mathematically rigorous, these specific structures may not perfectly reflect the properties of standard, real-world datasets.
Future research directions include investigating whether these theoretical gaps between SGD and ERM manifest in more practical architectures, such as Convolutional Neural Networks (CNNs) or Transformers. Further developing the theory of linearizability may also provide a more generalized explanation for deep learning optimization.
Summary updated