Deep learning theory has long grappled with a paradox: neural networks are non-convex and theoretically difficult to optimize, yet in practice, simple gradient descent consistently finds global minima. Early theoretical attempts to explain this relied on the "infinite-width" regime, such as the Neural Tangent Kernel (NTK), which required models to be astronomically large—often needing a number of neurons proportional to a high-degree polynomial of the dataset size ($n^6$ or more).
A growing body of research is now dismantling these "infinite-width" requirements. By refining our understanding of optimization landscapes and data-architecture alignment, researchers have shown that global convergence is achievable with much more "moderate" over-parameterization, often scaling linearly or quadratically with the number of samples.
The Shift Toward Moderate Over-parameterization
The core mission of this research direction is to bridge the gap between theoretical "infinite" models and the finite, practical architectures used in the real world. The primary breakthrough has been the reduction of the required hidden layer width ($m$) relative to the number of training samples ($n$).
While early proofs suggested $m$ must be massive to ensure a "benign" optimization landscape, Jason D. Lee and Simon S. Du demonstrated in On the Power of Over-parametrization in Neural Networks with Quadratic Activation that for certain shallow networks, a width proportional to $\sqrt{n}$ is sufficient. This suggests that the degree of over-parameterization needed to overcome non-convexity is significantly smaller than previously theorized.
Finding the Critical Thresholds
Different architectural choices and data properties further tighten these bounds:
- Linear and Subquadratic Scaling: For shallow ReLU networks, Ali Ramezani-Kebrya and Volkan Cevher proved that a width of $\tilde{\Omega}(n^{3/2})$—and even linear scaling in high dimensions—is sufficient for global convergence (Subquadratic Overparameterization for Shallow Neural Networks).
- The Power of a Single Layer: In deep architectures, the requirement is even more flexible. Quynh Nguyen and Guido Montúfar showed that a network only needs one sufficiently wide layer (proportional to $n$) to ensure the Neural Tangent Kernel remains positive definite, guaranteeing convergence even if all other layers are narrow (Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks).
- Implicit and Infinite Depth: For implicit neural networks—which solve for an equilibrium state rather than stacking layers—Hongyang Gao proved that global convergence is possible with a width that scales linearly with $n$, despite the model effectively having infinite depth (Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widths).
Why It Works: Data-Architecture Alignment
The intuition behind these tighter bounds often lies in how the architecture interacts with the data distribution. When data points are "weakly interacting" (low correlation), the requirements drop precipitously. Francis Bach and colleagues found that in high-dimensional settings with distinct features, a shallow network needs only $\log(n)$ neurons to reach zero training loss (Convergence of Shallow ReLU Networks on Weakly Interacting Data).
Furthermore, structural modifications like Weight Normalization help by decomposing the learning process into "length" and "direction." As shown by Yonatan Dukler and Quanquan Gu, this decomposition significantly reduces the necessary over-parameterization compared to standard un-normalized networks (Optimization Theory for ReLU Neural Networks Trained with Normalization Layers).
Implications for Practical Training
These theoretical refinements provide a "green light" for practical deep learning. They explain why frameworks like FedAvg (Local SGD) can converge linearly to zero loss on large-scale models (FedAvg Converges to Zero Training Loss Linearly for Overparameterized Multi-Layer Neural Networks) and why Nesterov acceleration effectively speeds up non-convex problems like matrix factorization with minimal width (Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks). By moving away from the "infinite-width" crutch, this research direction provides a mathematical foundation that finally aligns with the actual scale of modern AI.