The Non-Convex Optimization Paradox
Classical optimization theory paints a grim picture for deep learning. Because neural networks are highly non-linear systems, their loss landscapes are inherently non-convex. In typical non-convex optimization, an algorithm like gradient descent is expected to fail: it should get trapped in suboptimal local minima, wander aimlessly in high-dimensional saddle points, or stall on flat plateaus where gradients vanish.
Yet, in practice, the opposite happens. Standard first-order optimization methods consistently guide massive neural networks to a global minimum with zero training loss.
The resolution to this paradox lies in overparameterization. When a network's capacity (its width or number of parameters) vastly exceeds the size of the training dataset, the geometry of the loss landscape undergoes a fundamental phase transition. As reviewed by Cong Fang et al. in their synthesis of Mathematical Models of Overparameterized Neural Networks, adding parameters effectively "convexifies" the optimization landscape. Overparameterization transforms a jagged, trap-filled terrain into a benign, well-behaved basin where local search algorithms are guaranteed to succeed.
How Extra Dimensions Eliminate Optimization Traps
To understand why overparameterization works, consider what happens to a local minimum when you add dimensions to a optimization space. In a low-dimensional space, a valley is a trap—every direction goes up. But as you inject thousands or millions of extra parameters, you introduce new directional degrees of freedom. For a point to remain a local minimum in a higher-dimensional space, the curvature must be positive in every single one of those new directions. If even one direction slopes downward, the trap opens up and becomes a saddle point, allowing the optimizer to escape.
In the overparameterized regime, this structural transformation becomes absolute. Jason D. Lee et al. proved in On the Power of Over-parametrization in Neural Networks with Quadratic Activation that overparameterization alters the loss surface such that all local minima are global minima, and any remaining saddle points possess clear directions of negative curvature.
Even if suboptimal local minima do manage to exist under certain conditions, they lose their power to stall optimization. Henning Petzka et al. demonstrated in Non-attracting Regions of Local Minima in Deep and Wide Neural Networks that when a network is sufficiently wide relative to the training data, every suboptimal local minimum is guaranteed to be "non-attracting." These minima belong to continuous, connected sets of solutions from which an optimizer can escape via a path that never increases the loss. Similarly, Benjamin David Haeffele et al. showed in Global Optimality in Neural Network Training that extreme overparameterization ensures a non-increasing path to a global minimum exists from any arbitrary starting point.
The Dynamics of Linear Convergence
It is not enough for a path to a global minimum to exist; the optimizer must also be able to find it efficiently. In overparameterized networks, gradient descent does not just crawl toward a solution—it converges at an exponential, linear rate.
For shallow networks, Mahdi Soltanolkotabi et al. established in Theoretical insights into the optimization landscape of over-parameterized shallow neural networks that overparameterization conditions the local geometry around solutions so well that gradient descent achieves a linear convergence rate. This behavior extends directly to deep architectures. Simon Shaolei Du et al. in Gradient Descent Provably Optimizes Over-parameterized Neural Networks and Difan Zou et al. in Gradient descent optimizes over-parameterized deep ReLU networks proved that randomly initialized gradient descent reliably finds global minima with zero training loss in deep ReLU networks.
The mathematical intuition behind this rapid convergence is often explained through the lens of the Neural Tangent Kernel (NTK). When a network is infinitely wide, individual weights change by an infinitesimally small amount during training, yet their collective shift linearly updates the network's outputs. Because the network behaves approximately linearly with respect to its parameters throughout the optimization trajectory, the loss landscape mirrors a perfectly convex kernel regression problem, guaranteeing a direct and rapid path to zero loss.
Localized Overparameterization: The Power of a Single Wide Layer
Early global convergence proofs came with a significant caveat: they required every layer in the network to be uniformly, massively wide, scaling polynomially with the number of training samples ($N$). This requirement does not reflect the architectures used in practice.
Subsequent research relaxed these constraints by demonstrating that global convergence does not require uniform overparameterization. Instead, a single wide layer can act as an optimization engine for the entire network.
Quynh Nguyen et al. proved in The Loss Surface of Deep and Wide Neural Networks that if even one hidden layer contains more neurons than the total number of training samples, the complex loss landscape simplifies significantly, turning almost all local minima into global minima. The location of this wide layer can vary:
- At the beginning: Quynh Nguyen et al. showed in Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology that a single wide first layer ($n_1 \ge N$) followed by a narrowing, constant-width pyramidal structure is sufficient to guarantee linear convergence to a global optimum.
- At the end: Quynh Nguyen 0001 demonstrated in On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths that overparameterizing only the last hidden layer provides the same global convergence guarantees while drastically reducing the width requirements for the rest of the network.
The intuition behind localized overparameterization is that a single wide layer provides enough degrees of freedom to linearly separate or perfectly fit the intermediate representations of the data. This localized capacity creates a region of strong local convexity. As shown by Fangshuo Liao et al. in Provable Accelerated Convergence of Nesterov's Momentum for Deep ReLU Neural Networks, a well-behaved, wide final layer can dominate the network's optimization dynamics, pulling the remaining, narrower layers along toward a global minimum.
Beyond Lazy Training: Feature Learning in Wide Networks
While the NTK framework successfully explains why overparameterized networks converge, it introduces a new conceptual problem: "lazy training." In a strict NTK regime, the network's features are effectively fixed at random initialization, meaning the model behaves like a static kernel and fails to learn useful, data-dependent representations.
To reconcile global convergence with actual representation learning, researchers developed alternative mathematical frameworks, such as the Mean-Field regime and Maximal Update Parametrization ($\mu$P).
Cong Fang et al. introduced a mean-field framework in Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks, proving that overparameterized residual networks can escape the lazy training regime. By tracking the continuous distribution of hidden features rather than individual static weights, the authors showed that skip connections facilitate a non-linear feature evolution that avoids suboptimal traps while still converging to a global minimum.
Taking this further, Zixiang Chen et al. proved in Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $\mu$ Parametrization that deep networks optimized under $\mu$P simultaneously achieve rich feature learning and global convergence. Under $\mu$P, the scaling of the learning rates and weights allows representations to change significantly from their initial state. Crucially, this feature evolution preserves the linear independence of the network's hidden outputs, ensuring that the underlying optimization landscape remains benign and that any convergent point is guaranteed to be a global optimum.
Key Foundational Work
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017) — contributed 2 concept elements to this direction.
The Loss Surface of Deep and Wide Neural Networks (2017) — contributed 1 concept elements to this direction.
Global Optimality in Neural Network Training (2017) — contributed 1 concept elements to this direction.