In classical optimization, non-convexity is a nightmare. A landscape filled with jagged peaks and deep, suboptimal valleys suggests that a local search algorithm like Gradient Descent (GD) should get trapped almost immediately. Yet, in deep learning, we routinely optimize models with millions of parameters using simple first-order methods and reach near-zero training error.
The resolution to this paradox lies in the geometry of overparameterization. As we increase the width and capacity of a network, the loss landscape undergoes a fundamental transformation: it becomes smoother, more "convex-like," and eventually loses the "bad" local minima that hinder optimization.
From Local Minima to Escapable Saddles
The most intuitive benefit of overparameterization is the creation of new "escape routes." In a narrow network, a point in parameter space might be a local minimum because every available direction leads to an increase in loss. However, as Frank Zhengqing Wu and Berfin Simsek demonstrate in Loss Landscape of Shallow ReLU-like Neural Networks, expanding a network's width through unit replication can convert these local minima into saddle points.
By adding neurons, we introduce new degrees of freedom. What was once a valley in a low-dimensional space becomes a ridge in a higher-dimensional one, providing "escape neurons" that allow the gradient to find a downward path. This structural change ensures that for sufficiently wide networks, every differentiable local minimum is actually a global minimum, a guarantee explored by Daniel Soudry and Yair Carmon in No bad local minima.
Convexity Along the Trajectory
Even if the global landscape remains non-convex, what matters most is the curvature the optimizer actually encounters. Etai Littwin and Lior Wolf show in On the Convex Behavior of Deep Neural Networks that in wide networks, the gradient at initialization becomes approximately orthogonal to the non-convex components of the Hessian.
Essentially, the optimizer "sees" a locally convex landscape. As width increases, the probability that the curvature remains positive in the direction of the gradient approaches certainty. This "weak convexity" is a direct result of overparameterization; Dominic Richards and Michael Rabbat prove that increasing width reduces the magnitude of the most negative Hessian eigenvalues, stabilizing the training trajectory and allowing for larger step sizes without divergence.
The Smoothing Effect of Architecture
It isn't just the number of parameters that matters, but how they are arranged. Multi-branch architectures (like ResNeXt) and parallel sub-networks act as a physical realization of the Shapley-Folkman lemma: the sum of many non-convex functions tends toward convexity.
Hongyang Zhang and Junru Shao argue in Deep Neural Networks with Multi-Branch Architectures Are Intrinsically Less Non-Convex that adding parallel paths systematically reduces the "duality gap"—the distance between the non-convex problem and its convex relaxation. Similarly, Tolga Ergen and Mert Pilanci demonstrate that certain parallel ReLU structures can be exactly reformulated as convex programs, bypassing the non-convexity of sequential layers entirely.
Global Convergence in the Infinite Limit
When we push overparameterization to its logical conclusion—the infinite-width limit—the optimization dynamics simplify even further. In this regime, the training of a neural network can be viewed through two lenses:
- The Neural Tangent Kernel (NTK): The network behaves like a linear model, where the loss landscape is perfectly quadratic.
- The Mean-Field Regime: As described by Lénaïc Chizat and Francis Bach, the non-convex optimization in parameter space becomes a convex optimization problem in the space of probability measures.
This perspective explains why wide versions of complex architectures, such as Recurrent Neural Networks (Zeyuan Allen-Zhu et al., On the Convergence Rate of Training Recurrent Neural Networks) and Reinforcement Learning agents (Boyi Liu et al., Neural Trust Region/Proximal Policy Optimization), achieve global optimality. The overparameterization provides a "Goldilocks Zone" (Adam Scherlis) where the radial growth of the loss and the high-dimensional geometry conspire to make gradient descent behave as if it were navigating a simple, convex bowl.