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

Satyen Kale, Ayush Sekhari, Karthik Sridharan

Abstract

Multi-epoch, small-batch Stochastic Gradient Descent (SGD) is the standard for training over-parameterized models. While popular theories attribute its success to "implicit regularization," this paper demonstrates that such explanations are insufficient. By analyzing Stochastic Convex Optimization (SCO), we show that SGD can succeed where any Regularized Empirical Risk Minimization (RERM) fails. We further establish a sample complexity separation between SGD and full-batch Gradient Descent (GD), proving that GD is fundamentally suboptimal in certain settings. Finally, we provide theoretical justification for multi-epoch training and extend these findings to two-layer diagonal neural networks, suggesting that the dynamic path of SGD is more critical than the static properties of the final objective.

Introduction

In modern machine learning, Stochastic Gradient Descent (SGD) is more than just an optimizer; it is often credited with the remarkable generalization capabilities of deep neural networks. Two primary theories have emerged to explain this: implicit regularization—the idea that SGD biases solutions toward "simpler" models—and the small-batch advantage, which suggests that the noise inherent in stochastic updates helps escape poor local minima.

This paper scrutinizes these theories within the framework of Stochastic Convex Optimization (SCO). By constructing specific mathematical instances where traditional optimization methods fail, we demonstrate that SGD’s success cannot be fully captured by static regularization terms. Instead, the algorithm's sequential, noisy nature provides a unique advantage in navigating complex loss landscapes.

The Failure of Implicit Regularization

A common hypothesis is that SGD acts as an implicit regularizer, effectively performing Regularized Empirical Risk Minimization (RERM). If this were true, one could replace SGD with a static optimization problem: $$\min_w \hat{L}(w) + R(w)$$ where $\hat{L}$ is the empirical loss and $R(w)$ is a regularizer like the $\ell_2$ norm.

However, this research proves a fundamental limitation of this view. Theorem 2 establishes that for any regularizer $R$, there exists an SCO problem where RERM fails to learn (incurring a constant error $\Omega(1)$), while SGD converges at the optimal rate of $O(1/\sqrt{n})$. This result implies that SGD’s success is tied to its dynamic trajectory rather than just the point it eventually reaches. You cannot always replicate the "magic" of SGD by simply adding a penalty term to the objective function.

SGD vs. Gradient Descent: The Power of Noise

Beyond regularization, the paper explores the gap between SGD and full-batch Gradient Descent (GD). In many practical scenarios, small-batch SGD generalizes better than large-batch GD. The authors formalize this observation by showing a "sample complexity separation."

They construct a problem where the population loss (the true objective) is well-behaved, but the empirical loss (the loss on the training set) contains "traps"—spurious coordinates and kinks that mislead batch methods. While GD, regardless of step size or iteration count, becomes stuck in these empirical artifacts and achieves a suboptimal rate of at least $\widetilde{\Omega}(1/n^{5/12})$, SGD uses its inherent sampling noise to "see through" the traps. The stochasticity allows SGD to ignore spurious features, hitting the optimal $O(1/\sqrt{n})$ rate. This confirms that the noise in SGD is not a drawback to be minimized, but a feature that drives generalization.

The Role of Multiple Epochs

While single-pass SGD is well-understood theoretically, practitioners almost always use multiple epochs. This paper provides a theoretical bridge for this practice. The authors analyze a multi-epoch variant of SGD and prove that it is at least as good as single-pass SGD in the worst case. More importantly, they show that for certain structured SCO problems, taking multiple passes over the dataset can significantly outperform single-pass methods, as the algorithm can refine its trajectory using the available data more effectively than a single pass allows.

Extension to Deep Learning

To ensure these findings are relevant to modern architectures, the authors extend their results to a two-layer diagonal ReLU neural network. They demonstrate a clear separation: for this architecture, any ERM-based algorithm (which includes most standard batch optimizers) fails to find a good solution with high probability. In contrast, SGD successfully learns the target function. This suggests that the gaps identified in the convex setting are likely prevalent in the non-convex landscapes of deep learning.

Conclusion

This work challenges the prevailing wisdom that SGD is simply a noisy version of a regularized optimizer. By proving that SGD can solve problems that are impossible for any RERM or full-batch GD, the authors highlight the unique role of the optimization path. The findings suggest that the "noise" of small batches and the repetition of multiple epochs are fundamental to how models learn to generalize, rather than just being computational shortcuts. Future research may look to extend these separations to more complex, non-diagonal architectures to further map the boundaries of SGD's superiority.

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: (a) 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. (b) 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})$. (c) 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{kale2021sgd,
  author = {Satyen Kale and Ayush Sekhari and Karthik Sridharan},
  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