Traditional optimization relies on the predictability of convex functions—smooth, bowl-shaped surfaces where every local step downward leads closer to a single global minimum. Deep neural networks shatter this paradigm. The moment non-linear activation functions or multi-layer architectures are introduced, the optimization landscape transforms into a rugged, high-dimensional terrain filled with an astronomical number of local minima, saddle points, and flat plateaus.
Historically, as noted by Yoshua Bengio et al. in On the Expressive Power of Deep Architectures, this non-convexity was so daunting that it was mistaken for a fundamental lack of expressive capacity in deep models. Today, we know deep networks are highly expressive, but understanding how gradient descent successfully navigates these treacherous landscapes remains one of the central challenges of deep learning theory.
The Anatomy of Non-Convex Complexity
Why exactly are these landscapes so difficult to analyze? The complexity begins at the most fundamental level. As Gilad Yehudai et al. demonstrate in Learning a Single Neuron with Gradient Methods, optimizing even a single non-linear neuron is an inherently non-convex problem, complicating convergence guarantees even when a perfect target solution exists.
When these neurons are combined into networks, the topological properties become deeply pathological. Philipp Petersen et al. proved in Topological Properties of the Set of Functions Generated by Neural Networks of Fixed Size that the set of functions generated by a fixed-size neural network is non-convex, not closed, and numerically unstable to invert. This means a simple weighted average of two valid network functions might not even be representable by the same architecture.
Furthermore, real-world loss landscapes rarely resemble the neat, quadratic approximations used in classical optimization theory. Sho Yaida highlights in Fluctuation-dissipation relations for stochastic gradient descent that these landscapes are highly anharmonic (non-quadratic), meaning standard curvature measures fail to capture how stochastic gradient descent (SGD) explores local minima. This structural irregularity obscures how layers coordinate to learn features, as explored by Arthur Jacot et al. in Feature Learning in $L_2$-regularized DNNs: Attraction/Repulsion and Sparsity, and prevents us from easily deriving clean mathematical rules like a non-linear equivalent of the max-margin principle, as discussed by Mary Phuong et al. in The inductive bias of ReLU networks on orthogonally separable data.
The Smoothing Power of Overparameterization
If the landscape is so chaotic, why does gradient descent work so well in practice? The answer often lies in scale. When we make neural networks vastly wider than necessary—a property known as overparameterization—the geometry of the loss landscape changes dramatically.
In the infinite-width limit, the highly non-convex training dynamics simplify into a predictable linear model. As shown by the authors of Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent, wide networks track a first-order Taylor expansion around their initial parameters, evolving similarly to linear Gaussian Processes. This "linearization" effectively bypasses the rugged non-convex terrain.
By leveraging this near-convex behavior in overparameterized regimes, researchers can establish formal guarantees that were previously impossible. For instance, Jason D. Lee et al. in Regret Guarantees for Online Deep Control provided the first sublinear regret guarantees for online deep control, bridging deep learning with Online Convex Optimization (OCO). Similarly, Mei Song et al. utilized mean-field theory in Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit to offer dimension-free bounds, providing a continuous view that tames the high-dimensional discrete weight updates.
Reshaping and Pruning the Terrain
Beyond simply expanding network width, we can actively alter or exploit specific geometric conditions to ease optimization. One prominent approach is leveraging the Polyak-Łojasiewicz (PL) condition, which guarantees that the gradient norm grows sufficiently fast relative to the suboptimality of the loss, allowing gradient descent to converge exponentially fast despite non-convexity. Yixuan Chen et al. demonstrated in Over-parameterized Model Optimization with Polyak-Łojasiewicz Condition that by identifying and pruning "poorly-behaved" sub-networks that disrupt this condition, one can accelerate training convergence in highly irregular landscapes.
Architectural choices also play a critical role in reshaping the landscape. Yonatan Dukler et al. showed in Optimization Theory for ReLU Neural Networks Trained with Normalization Layers that incorporating normalization layers (like Weight Normalization) mathematically decomposes the learning process into separate length and direction components. This structural decomposition significantly reduces the amount of overparameterization required to guarantee global convergence, smoothing out the non-smooth hurdles inherent to ReLU networks.
Circumventing Non-Convexity Entirely
When navigating a non-convex landscape proves too computationally or theoretically expensive, an alternative strategy is to bypass it altogether by reframing the objective into a convex formulation.
For example, training Recurrent Neural Networks (RNNs) typically introduces severe non-convexity, leading to vanishing gradients and local minima entrapment. To solve this, Fatih Dinc introduced CORNN: Convex optimization of recurrent neural networks for rapid inference of neural dynamics, a framework that reformulates neural dynamics training as a strictly convex optimization problem, accelerating inference and training by up to 100 times.
In a similar vein, Yitao Liang et al. proposed Learning Logistic Circuits. By combining the structural properties of logical circuits with an inherently convex loss function, they achieved state-of-the-art accuracy on image benchmarks while completely avoiding the black-box, non-convex pitfalls of standard deep networks.