Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

Yuan Cao, Quanquan Gu

Abstract

This research investigates the training and generalization dynamics of deep neural networks (DNNs) within the over-parameterized regime—where the number of hidden nodes per layer significantly exceeds the number of training data points. We demonstrate that the expected 0-1 loss of a sufficiently wide ReLU network, trained via stochastic gradient descent (SGD) from random initialization, is bounded by the training loss of a "neural tangent random feature" (NTRF) model. For data distributions classifiable by the NTRF model with minimal error, we establish a generalization error bound of $\tilde{\mathcal{O}}(n^{-1/2})$, which remains independent of the network width. This result provides a sharper and more general theoretical framework than previous bounds and establishes a formal connection to the neural tangent kernel (NTK).

Introduction: The Generalization Mystery

In classical statistical learning theory, a model's complexity is typically viewed as a liability; a model with more parameters than data points is expected to overfit, essentially "memorizing" training noise rather than learning underlying patterns. Modern deep learning, however, defies this intuition. Massive neural networks with millions of parameters frequently achieve excellent generalization on relatively small datasets.

Previous attempts to explain this phenomenon using uniform convergence measures, such as VC-dimension, often resulted in "vacuous" bounds—theoretical limits so high they exceeded the number of possible classes, offering no practical predictive value. This paper addresses this "Generalization Mystery" by deriving an algorithm-dependent bound that focuses on the specific optimization path taken by SGD through the parameter space of wide networks.

Theoretical Framework: The NTRF Model

The authors' analysis centers on the Neural Tangent Random Feature (NTRF) model, which leverages the unique properties of the over-parameterized regime.

Linearization at Initialization

In extremely wide networks, the network function behaves approximately like a linear function of its weights in the immediate vicinity of its random starting point. This "lazy training" regime implies that the weights do not need to move far from their initial values to achieve zero training error.

Local Convexity and Online-to-Batch Conversion

While the global loss landscape of a neural network is non-convex and complex, the authors prove that for sufficiently wide networks, the area surrounding a random initialization is "locally almost convex." By treating the SGD optimization process as an online learning task and applying online-to-batch conversion techniques, the researchers derive a final generalization bound for the test set based on the cumulative loss during training.

Key Insights and Results

Width-Independent Generalization

The most significant finding is that the generalization bound is $\tilde{\mathcal{O}}(n^{-1/2})$, where $n$ is the number of training samples. Crucially, this bound is independent of the width of the hidden layers ($m$). This provides a theoretical justification for why increasing the width of a network does not necessarily degrade its generalization performance, provided the data can be separated with a sufficient margin by the NTRF model.

Sharper Sample Complexity

The paper achieves a significant improvement in sample complexity. To reach a target error $\epsilon$, the proposed bound requires $O(\epsilon^{-2})$ samples, a substantial refinement over previous works that required $O(\epsilon^{-4})$. Furthermore, unlike many prior studies limited to two-layer architectures, this analysis holds for ReLU networks of any depth $L$.

The NTK Connection

The research establishes a formal bridge to the Neural Tangent Kernel (NTK). It demonstrates that the generalization performance of deep ReLU networks is intrinsically tied to the properties of the NTK matrix defined at the start of training. If the NTK matrix is well-conditioned and the data is "easy" (separable by the kernel), the network will generalize well.

Experimental Validation

To validate the theoretical findings, the authors conducted experiments using the MNIST dataset, specifically focusing on a binary classification task (distinguishing the digits '3' and '8').

The experiments aimed to prove that the theoretical bounds are "informative." By increasing the "ratio of label flip" (introducing synthetic noise into the training data), the authors observed that their theoretical bound increased accordingly. This confirms that the bound captures the inherent difficulty of the learning task and the quality of the data, rather than remaining constant or vacuous regardless of data integrity.

Limitations and Future Directions

Despite the advancement in sharpening these bounds, certain challenges remain:

  • Extreme Over-parameterization: The current theory requires a network width that is a high-degree polynomial of the number of samples and depth. In practice, networks generalize well even at widths much smaller than those required by this strict theoretical proof.
  • Architectural Scope: The analysis is currently focused on fully connected ReLU networks. Extending these sharp, width-independent bounds to more complex architectures like Convolutional Neural Networks (CNNs) or Transformers is a primary goal for future research.
  • Optimization Path: Future work may explore "last iterate" bounds for SGD—analyzing the performance of the final weight update rather than the average performance across the entire training trajectory.

Summary updated

Abstract

We study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime, where the network width (i.e., number of hidden nodes per layer) is much larger than the number of training data points. We show that, the expected $0$-$1$ loss of a wide enough ReLU network trained with stochastic gradient descent (SGD) and random initialization can be bounded by the training loss of a random feature model induced by the network gradient at initialization, which we call a neural tangent random feature (NTRF) model. For data distributions that can be classified by NTRF model with sufficiently small error, our result yields a generalization error bound in the order of $\tilde{\mathcal{O}}(n^{-1/2})$ that is independent of the network width. Our result is more general and sharper than many existing generalization error bounds for over-parameterized neural networks. In addition, we establish a strong connection between our generalization error bound and the neural tangent kernel (NTK) proposed in recent work.
BibTeX
@inproceedings{cao2019generalization,
  author = {Yuan Cao and Quanquan Gu},
  title = {{Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=jJnsakRLci},
}
Figure