This paper provides a theoretical bridge between the idealized world of "infinitely wide" neural networks and the practical reality of the models we actually train. The authors prove that even "mildly parameterized" neural networks—those without extreme over-parameterization—experience a provably fast drop in loss during the early stages of training. By introducing a novel "neuron partition" analysis, they demonstrate how Gradient Descent (GD) and Stochastic Gradient Descent (SGD) escape initial saddle points to achieve significant early-stage convergence and, under specific conditions, global convergence to zero loss.
The Problem: Beyond the Neural Tangent Kernel
In recent years, the "Neural Tangent Kernel" (NTK) theory has been the dominant framework used to explain why neural networks converge. However, NTK relies on a massive over-parameterization regime where the network is so wide it essentially behaves like a linear model.
In practice, practitioners use "mildly parameterized" or even under-parameterized networks that are highly non-convex and full of spurious local minima and saddle points. Existing theories often fail to explain why these practical-sized networks still converge so quickly, especially in the very first few iterations of training. The authors set out to answer a critical question: Does this fast early-stage convergence provably exist for realistic network sizes, and can we prove global convergence without relying on the NTK regime?
Methods: The "Neuron Partition" Technique
The researchers focus on two-layer ReLU neural networks trained with GD or SGD. Their primary innovation is a technique they call "neuron partition."
Instead of treating the network as a single mathematical entity, they perform a microscopic analysis of how each training sample affects each individual neuron. They categorize neurons into four groups based on their activation patterns relative to the target:
- True-Living ($TL$): Correct sign, active.
- True-Dead ($TD$): Correct sign, inactive.
- False-Living ($FL$): Wrong sign, active.
- False-Dead ($FD$): Wrong sign, inactive.
By tracking how neurons move between these categories, the authors derive a more powerful lower bound for the gradient. This allows them to prove that the gradient remains large enough to drive the loss down significantly, even when the network is not infinitely wide. For example, "True-dead" neurons (those that should be active for a sample but aren't) quickly become "True-living" in the very first iteration, contributing to the massive initial drop in loss.
Key Insights and Results
Through this microscopic lens, the authors uncover several key insights about network dynamics:
- Escaping the "Zero" Saddle Point: At initialization, networks are often close to a saddle point at zero. The neuron partition analysis shows that neurons rapidly adjust their directions to enter a "good region" that lacks spurious local minima.
- Mild Parameterization is Sufficient: Unlike NTK, which requires the number of neurons ($m$) to be a large polynomial of the number of samples ($n$), this paper shows that $m = \Omega(\log(n/\delta))$ is often enough to guarantee fast early convergence.
- Early Stage Convergence: For quadratic and general classification losses, the authors prove that the loss descends by a significant amount ($\Omega(1)$) within the first $\Theta(1/\eta)$ iterations (where $\eta$ is the learning rate).
- Global Convergence: For exponential-type loss functions (like cross-entropy) and well-separated data, they prove that GD converges to zero loss at either a polynomial or exponential rate, depending on whether all parameters or just the input layer are trained.
To validate their theoretical bounds, the authors tested their findings on standard datasets, specifically using the first 1,000 samples of MNIST and CIFAR-10. The theoretical "loss descent bound" (calculated at ~0.26) was remarkably close to the actual loss descent observed in the first 34 iterations (ranging from ~0.34 to ~0.65). This suggests the theory captures real-world dynamics exceptionally well.
Limitations and Future Work
While a significant step forward, the paper notes a few limitations:
- Two-Layer Limit: The current proofs are restricted to two-layer networks. Extending this "neuron partition" analysis to deep, multi-layer architectures remains a mathematical challenge.
- Data Assumptions: Some results rely on "well-separated" data, which may not hold for extremely noisy or overlapping real-world datasets.
- Population Risk: The study focuses on empirical risk (training loss). Extending this to population risk (generalization to unseen data) is a key direction for future research.
By moving beyond the "linearized" NTK regime, this work provides a more realistic theoretical foundation for understanding why the neural networks we use every day are so efficient at optimization.
Summary updated