In classical optimization theory, non-convexity is often treated as a death knell for global convergence. The standard intuition suggests that unless you start your algorithm very close to the solution—a "warm start" or "spectral initialization"—you will inevitably get trapped in a poor local minimum or wander aimlessly among saddle points.
However, a massive body of recent research has overturned this caution. Across domains ranging from matrix completion to neural networks, researchers have discovered that many high-dimensional non-convex problems possess a "benign" geometric structure. In these landscapes, simple algorithms like Gradient Descent (GD) and Stochastic Gradient Descent (SGD) can be initialized completely at random and still find the global optimum with mathematical certainty.
The Myth of the Spurious Local Minimum
The primary fear in non-convex optimization is the "spurious" local minimum—a valley that looks like a solution but isn't. A breakthrough in understanding why we can ignore this fear came from the study of low-rank matrix problems.
In Matrix Completion has No Spurious Local Minimum, Jason D. Lee, Rong Ge, and Tengyu Ma proved that for the standard matrix completion objective, every local minimum is a global minimum. Furthermore, they showed that every saddle point is "strict," meaning there is always a direction of negative curvature that allows an algorithm to escape.
This geometric property is not a fluke. Srinadh Bhojanapalli and Nati Srebro demonstrated in Global Optimality of Local Search for Low Rank Matrix Recovery that under a mild "Restricted Isometry Property" (RIP), the factorized landscape of matrix recovery is inherently well-behaved. This explains why practitioners can use "vanilla" gradient descent from random starting points and achieve the same precision as complex, regularized solvers.
Escaping the Need for Spectral Initialization
For years, the "gold standard" for non-convex recovery was to use a spectral method to find a starting point in the "basin of attraction" of the global minimum. While effective, spectral initialization is computationally expensive and often requires the entire dataset to be processed at once.
Recent work shows this step is often unnecessary. In the context of Phase Retrieval—reconstructing a signal from magnitude-only measurements—Jian-Feng Cai and colleagues showed in The global landscape of phase retrieval I: perturbed amplitude models that by slightly smoothing the objective function, the landscape becomes so navigable that random initialization succeeds as reliably as spectral methods.
Similarly, in Principal Component Analysis (PCA), Ohad Shamir demonstrated in A Stochastic PCA Algorithm with an Exponential Convergence Rate that variance-reduced stochastic methods (VR-PCA) are empirically robust to random initialization. This was further solidified by Chris Junchi Li and Tong Zhang in Diffusion Approximations for Online Principal Component Estimation and Global Convergence, proving that Oja’s iteration converges to the optimal solution from nearly any starting point, matching the best possible statistical bounds.
Why It Works: High-Dimensional Geometry and Width
The intuition for why random initialization works often boils down to two factors: symmetry and over-parameterization.
- Symmetry and Manifolds: In problems like Dictionary Learning, the objective function is defined over a sphere or a manifold. John Wright and Ju Sun showed in Complete Dictionary Recovery Over the Sphere II that Riemannian second-order methods can recover the ground truth from arbitrary random initializations because the symmetries of the problem create a landscape where the "good" regions are surprisingly large and accessible.
- The Power of Width: In neural networks, the landscape is notoriously complex. However, Simon S. Du and Wei Hu proved in Width Provably Matters in Optimization for Deep Linear Neural Networks that as layers become wider, the non-convex landscape flattens out. This "over-parameterization" ensures that a random starting point is almost guaranteed to land in a region where gradient descent can slide down to a global optimum at a linear rate.
Beyond Simple Gradients: Message Passing and Swarms
The principle of global convergence from random starts extends beyond gradient-based methods. Approximate Message Passing (AMP), a powerful tool for high-dimensional statistics, was long thought to require spectral initialization. However, Gen Li and Yuting Wei proved in Approximate message passing from random initialization that these algorithms can amplify even the weakest signal components from a purely random start, eventually reaching Bayes-optimal performance.
Even nature-inspired metaheuristics follow this pattern. Lukang Sun demonstrated in Regularity and positivity of solutions of the Consensus-Based Optimization equation that swarm-based methods achieve "unconditional" global convergence. Because the search particles maintain a smooth density across the landscape, they are guaranteed to find the global minimizer regardless of where the swarm is initially released.
Summary of Intuition
The shift in this research area is from viewing non-convexity as a trap to viewing it as a structure. When a problem has:
- No spurious local minima (as in matrix completion),
- Escapable saddle points (as in dictionary learning),
- Or sufficient width (as in neural networks),
...then the specific starting point becomes irrelevant. The high-dimensional geometry of the problem acts like a funnel, ensuring that almost any random path eventually leads to the same global destination.