A Convergence Theory for Deep Learning via Over-Parameterization
Zeyuan Allen-ZhuYuanzhi LiZhao Song
Proves that standard stochastic gradient descent finds global minima in polynomial time for deep, over-parameterized neural networks with ReLU activations across fully-connected, convolutional, and residual architectures.
Modern deep neural networks achieve exceptional practical performance across computer vision and speech tasks, yet their theoretical foundation has historically lagged behind. While empirical practice routinely trains deep networks to near-zero training error using standard first-order optimization, existing optimization theory primarily addressed shallow, two-layer models or relied on idealized assumptions such as infinite network width. The article addresses this fundamental gap by establishing why standard first-order optimization methods reliably succeed on multi-layer deep neural networks.
The main objective of the article is to prove that standard gradient descent and stochastic gradient descent can efficiently find global minimum training solutions in polynomial time for multi-layer, over-parameterized neural networks using non-smooth rectified linear unit (ReLU) activations.
The authors analyze the optimization behavior by evaluating network parameter trajectories in a region surrounding random Gaussian weight initialization. The analysis relies on two minimal assumptions: the input training data points are distinct (non-degenerate), and the network hidden layer width is sufficiently large (over-parameterized polynomially relative to the sample size and depth). The investigation encompasses fully-connected networks, convolutional neural networks, and residual networks across various smooth and non-convex loss functions, supported by empirical landscape visualizations on benchmark image classification datasets.
The article demonstrates several core findings. First, gradient descent and stochastic gradient descent achieve a linear convergence rate, minimizing training regression error exponentially fast or attaining 100% classification accuracy on training datasets in polynomial time and iterations. Second, within a sufficiently large neighborhood around random initialization, the optimization landscape is proven to be almost-convex and semi-smooth, meaning gradients remain large whenever the loss is high and bad local minima or saddle points are avoided. Third, the authors show that finite, polynomially wide networks behave equivalently to the neural tangent kernel, avoiding the exponential gradient explosion or vanishing dependencies that previously hindered deep network theory.
These findings provide rigorous justification for current engineering practices, reducing algorithmic risk by proving that standard first-order optimization methods do not get trapped in sub-optimal local minima when models are sufficiently wide. Furthermore, the analysis demonstrates that deep architectures like residual networks and standard multi-layer networks do not face exponential training slowdowns as depth increases, explaining why practitioners can scale model depth and width effectively.
For engineering and development teams, the results suggest that organizations can confidently utilize standard first-order optimizers on wide, deep architectures without requiring complex second-order curvature corrections during optimization. Future theoretical work should aim to refine the mathematical bounds for smoother activation functions and further explore generalization performance on unseen test data.
The primary limitation noted in the article is that the theoretical width requirements derived from worst-case non-smooth ReLU analysis involve large polynomial factors that exceed the network widths commonly utilized in practical deployments. Nonetheless, high confidence in the qualitative convergence behavior is supported by rigorous mathematical proof and consistent empirical landscape observations across realistic architectures.
- Paper: Neural Tangent Kernel: Convergence and Generalization in Neural Networks, Arthur Jacot et al. (2018). Introduces the Neural Tangent Kernel framework in the infinite-width limit, which serves as the direct theoretical foundation that the source paper adapts and establishes for finite, polynomial-width networks.
- Paper: Understanding deep learning requires rethinking generalization, Chiyuan Zhang et al. (2017). Demonstrates empirically that over-parameterized deep neural networks can achieve zero training error even on arbitrary labels, establishing the optimization phenomenon that the source paper explains theoretically.
- Paper: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, Andrew M. Saxe et al. (2014). Provides fundamental exact analytical solutions for gradient descent dynamics and depth independence in deep linear networks, establishing key mathematical techniques for analyzing deep learning optimization.
- Paper: Visualizing the Loss Landscape of Neural Nets, Hao Li et al. (2017). Visualizes how network width and residual connections transform chaotic loss surfaces into benign, nearly convex landscapes, offering intuitive geometric insight into the almost-convexity properties proven in the source.
- Paper: Deep Residual Learning for Image Recognition, Kaiming He et al. (2016). Presents deep residual learning and identity mappings, which form one of the primary practical multi-layer architectures analyzed by the source paper's convergence theory.
- Paper: Identity Mappings in Deep Residual Networks, Kaiming He et al. (2016). Analyzes the unobstructed forward and backward signal propagation enabled by identity skip connections in deep ResNets, a crucial property leveraged in over-parameterized convergence proofs.
- Paper: A Closer Look at Memorization in Deep Networks, Devansh Arpit et al. (2017). Characterizes the distinct optimization trajectories of gradient-based training on real patterns versus memorized data in high-capacity networks.
- Paper: On the importance of initialization and momentum in deep learning, Ilya Sutskever et al. (2013). Demonstrates the essential role of random initialization scaling and momentum schedules in ensuring successful first-order optimization across deep architectures.
- Paper: Understanding the difficulty of training deep feedforward neural networks, Xavier Glorot et al. (2010). Examines how activation choices and variance-preserving initializations prevent gradient vanishing or saturation, providing critical background for analyzing optimization near random initialization.
- Paper: Approximation by Superpositions of a Sigmoidal Function, George Cybenko (1989). Establishes classical universal approximation theorems for neural networks, framing the expressive capacity that modern over-parameterization theories aim to optimize in polynomial time.
- Paper: When and why PINNs fail to train: A neural tangent kernel perspective, Sifan Wang et al. (2020). Applies the neural tangent kernel and over-parameterization theory to diagnose spectral bias and optimization failure modes in physics-informed neural networks.
- Paper: On the Spectral Bias of Neural Networks, Nasim Rahaman et al. (2019). Extends the study of deep ReLU network learning dynamics under gradient descent by uncovering a spectral bias toward low-frequency functions during training.
- Paper: Correlated initialization of deep residual networks, Felix Benning et al. (2026). Generalizes the asymptotic behavior of deep residual networks at initialization to include correlated parameter regimes beyond standard i.i.d. scalings.
- Paper: Low-dimensional topology of deep neural networks, Junyu Ren et al. (2026). Investigates topological constraints on classification expressivity in narrow architectures, complementing the convergence guarantees of over-parameterized networks.
- Paper: Revenge of Monosemanticity: Specialized Neurons Improve Data Efficiency in MLPs, Amirhesam Abedsoltan et al. (2026). Explores how feature learning and neuron specialization emerge in multilayer perceptrons beyond the purely static kernel regime described by wide-network NTK dynamics.
