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.
- 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