SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs

Ayush Sekhari, Karthik Sridharan, Satyen Kale

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

Abstract

Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been the method of choice for learning with large over-parameterized models. A popular theory for explaining why SGD works well in practice is that the algorithm has an implicit regularization that biases its output towards a good solution. Perhaps the theoretically most well understood learning setting for SGD is that of Stochastic Convex Optimization (SCO), where it is well known that SGD learns at a rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. In this paper, we consider the problem of SCO and explore the role of implicit regularization, batch size and multiple epochs for SGD. Our main contributions are threefold: * We show that for any regularizer, there is an SCO problem for which Regularized Empirical Risk Minimzation fails to learn. This automatically rules out any implicit regularization based explanation for the success of SGD. * We provide a separation between SGD and learning via Gradient Descent on empirical loss (GD) in terms of sample complexity. We show that there is an SCO problem such that GD with any step size and number of iterations can only learn at a suboptimal rate: at least $\widetilde{\Omega}(1/n^{5/12})$. * We present a multi-epoch variant of SGD commonly used in practice. We prove that this algorithm is at least as good as single pass SGD in the worst case. However, for certain SCO problems, taking multiple passes over the dataset can significantly outperform single pass SGD. We extend our results to the general learning setting by showing a problem which is learnable for any data distribution, and for this problem, SGD is strictly better than RERM for any regularization function. We conclude by discussing the implications of our results for deep learning, and show a separation between SGD and ERM for two layer diagonal neural networks.
BibTeX
@inproceedings{sekhari2021sgd,
  author = {Ayush Sekhari and Karthik Sridharan and Satyen Kale},
  title = {{SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=jqjsLUrB8F},
}
Figure