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

Zixiang Chen, Yuan Cao, Difan Zou, Quanquan Gu

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, 2019). 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.

Introduction

In deep learning theory, the "Neural Tangent Kernel" (NTK) regime has been a popular framework for explaining how neural networks optimize. However, a significant gap has existed between theory and practice: most NTK proofs require the network width ($m$) to be a high-degree polynomial of the number of training samples ($n$)—sometimes as extreme as $m \geq \Omega(n^{12})$.

In practice, engineers observe that much smaller networks perform exceptionally well. While recent research demonstrated that shallow (two-layer) networks could function with polylogarithmic width, it remained an open question whether this "mild" over-parameterization was sufficient for deep networks. This paper provides a theoretical breakthrough by proving that deep ReLU networks only require a polylogarithmic width relative to $n$ to successfully converge and generalize, provided the data exhibits certain separability.

Methodology

The researchers analyzed deep ReLU networks trained with Gradient Descent (GD) and Stochastic Gradient Descent (SGD) using standard He initialization. Their core approach involves three key theoretical pillars:

  1. NTRF Function Class: They define a "Neural Tangent Random Feature" (NTRF) class, representing the set of functions a network can learn if it stays within the "lazy training" regime (close to its initial state).
  2. Relaxed Linear Approximation: While previous proofs required neural networks to behave almost exactly like linear models, this work demonstrates that a constant linear approximation error is sufficient to guarantee global convergence.
  3. Trajectory Analysis: The authors prove that during training, weights remain within a small neighborhood of their initialization. This allows them to leverage the "almost linear" properties of wide networks without requiring astronomical widths.

To validate these theoretical findings, the authors utilized CIFAR-10 subsets for binary classification tasks (e.g., "cat vs. dog") and synthetic datasets to test the relationship between sample size $n$ and the minimum width required for zero training error.

Key Results

The paper significantly tightens the requirements for deep learning optimization and generalization. The most notable achievement is reducing the width requirement from $\Omega(n^{\text{large power}})$ to $\text{polylog}(n, \epsilon^{-1})$ for deep networks under data separation assumptions.

Comparison of over-parameterization conditions and sample complexity across different studies.

As shown in the comparison table above, this work improves upon previous bounds in several ways:

  • Optimization: GD is guaranteed to find a global minimum within a polynomial number of iterations even with mild over-parameterization.
  • Generalization: The authors proved that these networks achieve a test error that diminishes as the number of samples $n$ increases, ensuring they are not merely memorizing data.
  • Sample Complexity: For SGD, they established a sample complexity of $\tilde{O}(\epsilon^{-1})$, which is tighter than many previous bounds for deep architectures.

Experimental results on CIFAR-10 further confirmed these theories, showing that the minimum width needed for zero training error follows a logarithmic curve relative to $n$, rather than a linear or polynomial one.

Discussion and Future Work

While this work marks a major step toward practical deep learning theory, some limitations remain. The current proofs are tailored for binary classification using cross-entropy loss; extending these results to multi-class problems or Mean Squared Error (MSE) loss is a natural next step. Additionally, the analysis operates within the "lazy training" regime where weights do not move far from initialization, meaning it does not fully capture "feature learning" where weights change significantly to discover new representations. Finally, as the analysis is specific to ReLU activations, future research could explore whether similar polylogarithmic bounds apply to other functions like GELU or Swish.

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, 2019). 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