In classical optimization theory, non-convex functions are considered notoriously difficult to solve. They are filled with local minima, saddle points, and rugged plateaus that can trap local optimization algorithms like gradient descent. Training a deep neural network is inherently a non-convex problem, yet in practice, simple first-order optimization methods consistently find global minima with near-zero training error.
This tension between worst-case theoretical complexity and empirical ease is often called the global convergence mystery. To resolve this paradox, researchers have shifted their focus from worst-case analysis to the specific geometric properties of neural network loss landscapes. Their findings reveal a shared conclusion: overparameterization fundamentally alters the geometry of the loss surface, effectively "convexifying" the optimization landscape.
The Geometry of Width: Eliminating Bad Local Minima
To understand why gradient descent succeeds, we must look at the topography of the loss surface. In a low-dimensional non-convex landscape, it is easy to get trapped in a local minimum—a valley with no downward exit. However, as we add parameters (increasing the width of the network), we add dimensions to the optimization space. A local minimum in a lower-dimensional space often reveals an escape route when a new dimension is added, transforming a trap into a saddle point.
Nguyen et al. formalized this intuition by proving that if even a single hidden layer in a deep network is wider than the number of training points, the loss landscape simplifies dramatically: almost all local minima become global minima.
Low-Dimensional Landscape (Narrow) High-Dimensional Landscape (Wide)
_ _ _ _
/ \/ \ <- Local Minimum / \/ \ <- Escape route opens
/ \ (Trapped!) / \ \ in extra dimension
_____/ \_____ _____/ \ \_____
This structural simplification means that the optimizer rarely encounters "bad" valleys. In fact, Nguyen demonstrated that for overparameterized networks with piecewise linear activations (like ReLU or Leaky-ReLU), the sublevel sets of the loss function are connected. This implies that from nearly any point in the parameter space, there exists a continuous, non-increasing path leading directly to a global optimum.
Even when looking at simpler architectures, this absence of poor local minima holds true. For instance, Kawaguchi proved that for deep linear networks, every local minimum is a global minimum, suggesting that the primary challenge is navigating complex saddle points rather than escaping suboptimal local traps. Later, Kawaguchi et al. extended this perspective by showing that every differentiable local minimum of a non-convex model corresponds to a global minimum of an appropriately "induced" model class, bridging the gap between non-convex landscapes and convex-like guarantees.
Two Paths to Convexification: NTK and Mean-Field
How exactly does overparameterization grant these guarantees during an active training run? Theoretical work has converged on two primary mathematical frameworks to explain this behavior, as reviewed by Fang et al.: the Neural Tangent Kernel (NTK) regime and the Mean-Field (MF) regime.
1. The NTK (Lazy Training) Regime
When a network is extremely wide, its predictions become highly sensitive to minute changes in its weights. As a result, gradient descent can find a global minimum while the individual weights barely move from their initial random values.
As explored by Misiakiewicz et al., this is known as the "lazy training" or linearized regime. Because the weights stay close to their initialization, the network's output can be accurately approximated by a first-order Taylor expansion around the initial parameters. This linearization turns the highly non-convex neural network optimization problem into a simple linear least-squares problem, which is inherently convex and easily solved by gradient descent. Under this regime, Lee et al. and Zou et al. rigorously proved that gradient descent achieves a linear convergence rate to the global minimum for deep ReLU networks.
2. The Mean-Field Regime
While the NTK regime explains optimization by freezing the network's features, it doesn't capture how networks learn new representations. The Mean-Field regime addresses this by treating the parameters not as individual coordinates, but as a large system of interacting particles.
Vanden‐Eijnden demonstrated that as the width approaches infinity, the evolution of these parameters can be described by a continuous probability distribution. Remarkably, while the loss function is highly non-convex with respect to individual weight vectors, it is strictly convex with respect to the distribution of those weights. By framing optimization in the space of measures rather than parameters, the authors showed that gradient descent behaves like a fluid flowing smoothly toward the global optimum. Similarly, Akiyama et al. leveraged this distributional perspective in a teacher-student setting to prove that a student network can exactly recover a teacher network's parameters despite the rugged landscape.
Beyond Infinite Width: Topology and Relaxations
Early proofs required astronomical network widths to guarantee convergence, but recent work has relaxed these extreme conditions to match practical architectures.
For example, you do not need every layer in a deep network to be massive. Nguyen et al. proved that a network requires only one wide initial layer (proportional to the number of training samples $N$), followed by a narrowing "pyramidal" topology, to guarantee that gradient descent converges linearly to a global optimum.
[ Layer 1: Wide ] Width >= N
\ /
[ Layer 2 ] Narrower
\ /
[ Layer 3 ] Narrower still
Furthermore, initialization strategies play a crucial role in avoiding early optimization traps. Yuandong Tian showed that while perfectly symmetric initializations can cause gradient descent to stall at dead-end saddle points, "symmetry-breaking" initializations allow the dynamics of the system to steer clear of these obstacles and achieve global convergence.
To unify these empirical realities with mathematical theory, researchers are developing broader optimization frameworks. Khaled et al. introduced a unified parametric assumption that subsumes traditional conditions like convexity and the Polyak-Łojasiewicz (PL) condition, providing general convergence guarantees that hold across complex, non-convex landscapes. From an algorithmic perspective, Kim et al. demonstrated that a Gaussian relaxation of a convex reformulation can approximate the global optimum of two-layer ReLU networks in polynomial time.
Ultimately, the theoretical-practical discrepancy in deep learning optimization is resolved by recognizing that worst-case complexity bounds do not apply to overparameterized architectures. By expanding the network's width, the loss landscape is structurally altered—either linearized locally or convexified globally—allowing simple gradient descent algorithms to reliably find optimal solutions.
Key Foundational Work
Global Optimality in Neural Network Training (2017) — contributed 1 concept elements to this direction.
Symmetry-Breaking Convergence Analysis of Certain Two-layered Neural Networks with ReLU nonlinearity (2017) — contributed 1 concept elements to this direction.
The Loss Surface of Deep and Wide Neural Networks (2017) — contributed 1 concept elements to this direction.