Nonconvex Optimization Landscapes
Nonconvex objectives have multiple minima, saddles, and plateaus, so no method guarantees a global optimum, yet local methods often work well in practice.
Beyond convexity
A convex function has a single connected set of minima, all global, and gradient methods provably find them. Most interesting objectives are not convex: neural-network training losses, matrix factorization, sensor localization, and physical inverse problems all have landscapes with many local minima, saddle points, ridges, and flat plateaus. In general, finding the global minimum of a nonconvex function is intractable.
What can be guaranteed
Because global optimization is hopeless in general, theory settles for weaker but useful guarantees. Gradient methods converge to a stationary point where the gradient is zero. With extra effort they converge to a second-order stationary point, a point that is also not a strict saddle, which for many problems is a local minimum. The practical question then becomes whether the reachable local minima are good enough.
- First-order stationary: gradient is zero (could be a saddle)
- Second-order stationary: also escapes strict saddles
- Local minimum: no nearby point is better
- Global minimum: best over the whole domain, generally unreachable to certify
Benign nonconvexity
A striking discovery is that many nonconvex problems of interest have benign landscapes: every local minimum is global (or nearly so), and all saddle points are strict and therefore escapable. Matrix completion, phase retrieval, and certain neural-network settings have been proven to have this structure under reasonable assumptions. When a landscape is benign, simple local methods find global optima despite nonconvexity, which explains much of deep learning's empirical success.
Practical strategies
When guarantees are unavailable, practitioners rely on tactics: multiple random restarts to sample different basins, good initialization to start in a favorable region, stochastic noise and momentum to escape saddles and shallow minima, and, for expensive black-box objectives, global methods like CMA-ES or Bayesian optimization. Understanding the geometry of a specific landscape, rather than treating all nonconvex problems alike, is the key to choosing the right approach.