How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?

Zixiang Chen, Yuan Cao, Difan Zou, Quanquan Gu

This research provides a significant theoretical breakthrough in our understanding of why deep learning works. It bridges the gap between the "extremely wide" networks required by previous theories and the more modestly sized networks used in practice.

The Core Breakthrough

The authors prove that deep ReLU networks only need a "mild" amount of over-parameterization—specifically, a width that grows polylogarithmically with the number of samples and the inverse of the target error—to successfully converge and generalize. This result moves theoretical guarantees for deep learning away from unrealistic "infinite width" assumptions and toward the practical settings used by engineers every day.

The Problem with Previous Theories

In recent years, the "Neural Tangent Kernel" (NTK) regime has been the dominant framework for proving that neural networks can find global minima. However, these proofs typically required the network width ($m$) to be a high-degree polynomial of the number of training samples ($n$) and the inverse of the target error ($1/\epsilon$). In plain English: the theory suggested you needed billions or trillions of neurons to learn even simple patterns, contradicting the reality of successful, smaller models.

While previous work had shown that two-layer (shallow) networks could work with much smaller, polylogarithmic widths, extending this to deep networks was an open challenge. Deep networks lack certain mathematical properties (like 1-homogeneity) that made the two-layer proofs possible. This paper successfully answers whether deep networks also only need a "mild" width to function.

A New Methodological Approach

The authors focus on training deep ReLU networks for binary classification using standard Gradient Descent (GD) and Stochastic Gradient Descent (SGD) with random Gaussian initialization.

Their core innovation is a more refined analysis of the linear approximation error. In the NTK regime, a neural network is treated as being "almost linear" near its starting point. Previous proofs required this approximation to be nearly perfect, which necessitated extreme width.

This paper proves that a constant linear approximation error is actually sufficient. They introduce a "Key Technical Lemma" that bounds the training loss based on how far the weights move from initialization. Crucially, their method does not rely on the specific geometry of two-layer networks, making it applicable to networks of any depth $L$.

Key Insights

  • The "Lazy Training" Threshold: The paper confirms that even in the "lazy training" regime (where weights don't move far from their starting points), infinite width is not required. Polylogarithmic width—meaning width that grows very slowly as you add more data—is enough.
  • Relaxed Requirements: The network does not need to perfectly mimic a linear model. As long as it stays within a certain "neighborhood" of its initialization, the optimization landscape remains friendly enough for GD/SGD to find a global optimum.
  • Handling Depth: By moving away from "homogeneity" arguments used in shallow network theory, the authors created a framework that naturally scales with the number of layers ($L$), showing that deeper networks still enjoy these benefits as long as the width is sufficient.

Improved Theoretical Guarantees

The most significant contributions of this paper are the drastically tighter bounds on required network width and sample complexity compared to prior work.

Comparison of theoretical guarantees showing the dramatic reduction in required network width and sample complexity achieved by this paper.
  • Optimization Guarantee: For GD, they prove the network achieves a training loss comparable to the best possible linear model in the "Neural Tangent Random Feature" (NTRF) class, provided the width $m$ is at least polylogarithmic in $n$.
  • Improved Sample Complexity: For SGD, they establish a sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-1}) \cdot \text{poly}(L)$, which is a significant improvement over the $\tilde{\mathcal{O}}(\epsilon^{-2})$ found in earlier deep learning theory.
  • Empirical Alignment: While previous theories required polynomial scaling, the authors' theoretical bounds now align much closer to empirical observations where the minimum width required to reach zero training error grows very slowly.

Limitations and Future Work

  • The NTK Regime: While this paper makes the NTK regime more practical by reducing the required width, it still operates in the "lazy training" framework. It doesn't fully account for "feature learning," where the network's internal representations change significantly during training.
  • Generalization Bounds: The authors note that for two-layer networks, other researchers have found even tighter generalization bounds that are independent of width. Finding similar width-independent bounds for deep networks is a promising future direction.
  • Architectural Scope: The current proof is tailored for fully connected ReLU networks. Extending these polylogarithmic width guarantees to Convolutional Neural Networks (CNNs) or Transformers remains a task for future research.

Summary updated

Abstract

A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size $n$ and the inverse of the target error $\epsilon^{-1}$, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumptions on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2020). However, whether deep neural networks can be learned with such a mild over-parameterization is still an open question. In this work, we answer this question affirmatively and establish sharper learning guarantees for deep ReLU networks trained by (stochastic) gradient descent. In specific, under certain assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in $n$ and $\epsilon^{-1}$. Our results push the study of over-parameterized deep neural networks towards more practical settings.
BibTeX
@inproceedings{chen2021how,
  author = {Zixiang Chen and Yuan Cao and Difan Zou and Quanquan Gu},
  title = {{How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=hJVpRebn2Nw},
}
Figure