In classical optimization theory, non-convexity is often viewed as an insurmountable barrier. If a loss function isn't convex, gradient descent might get trapped in a sub-optimal local minimum or wander aimlessly near a saddle point. Yet, in practice, simple local search algorithms like Gradient Descent (GD) and Expectation-Maximization (EM) routinely solve massive non-convex problems—from training deep neural networks to reconstructing 3D molecules in cryo-electron microscopy.
The resolution to this paradox lies in the relationship between the empirical risk (the loss we calculate on a finite dataset) and the population risk (the ideal loss we would see with infinite data). Recent research suggests that for many important problems, the empirical landscape "inherits" a benign geometric structure from the population landscape as the sample size grows.
The Population Risk as a North Star
To understand why optimization works, we first look at the "ideal" version of the problem. The population risk is the expected error over the entire data distribution. Because it is an expectation, it is often smoother and more symmetric than any loss function calculated from a handful of samples.
Arnulf Jentzen, Florian Rossmannek, and Patrick Cheridito demonstrate this in Landscape Analysis for Shallow Neural Networks. By analyzing the true expected loss, they provide a complete classification of critical points, showing that for certain activations like Leaky ReLU, the population landscape contains only global minima and escapable saddle points. This "benign" structure is the target that our finite-sample optimization is trying to hit.
Uniform Convergence of Gradients and Hessians
The bridge between the finite and the infinite is built using uniform convergence. It isn't enough for the empirical loss to be close to the population loss at a single point; the entire "shape" of the landscape—its slopes (gradients) and its curves (Hessians)—must align across the entire parameter space.
Mei Song and Yu Bai established in The landscape of empirical risk for nonconvex losses that as sample size increases, the empirical risk landscape converges to the population risk landscape. Specifically, they show that if the first and second derivatives converge uniformly, the empirical landscape preserves the optimization topology of the population risk. This means that if the infinite-data problem has no spurious local minima, the finite-data problem won't either, provided you have enough samples.
This principle is applied to specific architectures by Xiao Zhang and Quanquan Gu in Learning One-hidden-layer ReLU Networks via Gradient Descent. They prove that the gradient of the empirical loss maintains uniform convergence to the population gradient within a local region, ensuring that the optimization path on a real dataset closely mirrors the idealized path.
Topological Inheritance and Morse Theory
How do we know that a local minimum in our training data actually corresponds to a "real" solution in the underlying distribution? Researchers use tools from differential topology, such as Morse Theory, to prove a one-to-one correspondence between stationary points.
In Empirical Risk Landscape Analysis for Understanding Deep Neural Networks, Pan Zhou and Jiashi Feng show that there is a high probability of a one-to-one mapping between non-degenerate local minima in the training data and those in the population risk. This "topological inheritance" ensures that when an algorithm finds a minimum on a finite dataset, it is likely located very close to a meaningful solution in the true weight space.
Even when the population risk is "degenerate" (e.g., having a Hessian that isn't strictly positive definite), Shuang Li, Gongguo Tang, and Michael B. Wakin argue in The Landscape of Non-convex Empirical Risk with Degenerate Population Risk that the empirical risk still inherits a benign structure. This suggests that the "lack of spurious minima" is a robust property that survives the transition from infinite to finite data.
Why Local Methods Succeed
This framework explains the success of local methods across diverse domains:
- Matrix Sensing: Jiacheng Zhuo and Constantine Caramanis show in On the computational and statistical complexity of over-parameterized matrix sensing that while over-parameterization creates "flat" regions, the empirical optimization path still tracks the population trajectory, achieving optimal error.
- Phylogenetics: In Sample Complexity of Branch-length Estimation by Maximum Likelihood, David Clancy Jr. and Sebastien Roch use the Uniform Matrix Bernstein Inequality to prove that the likelihood landscape for evolutionary trees becomes strongly concave and smooth with enough data, explaining why simple hill-climbing works.
- Bilevel Optimization: Fares El Khoury and Michael Arbel demonstrate in Learning Theory for Kernel Bilevel Optimization that empirical critical points in meta-learning approximate population ones with a predictable decay in error.
As Tengyu Ma summarizes in Why Do Local Methods Solve Nonconvex Problems?, the "worst-case" hardness of non-convexity is often avoided in practice because the concentration of measure ensures that our finite-sample landscapes are much better behaved than theory would otherwise predict. By studying the population risk, we gain a window into the geometric simplicity that makes modern machine learning possible.