The Geometry of Spurious Local Minima

24 concepts25 papers1 proposal

Classic optimization theory warns us that non-convex functions are an algorithmic minefield. They can contain countless spurious local minima—suboptimal points where the gradient vanishes and the loss surface curves upward in all directions, trapping gradient-based algorithms far from the global optimum.

Yet, in modern machine learning, we routinely solve highly non-convex problems using simple first-order methods like gradient descent. Why don't these algorithms get stuck?

The answer lies in the geometry of the loss landscape. A growing body of theoretical work shows that for many structured non-convex problems, the landscape is "benign." A benign landscape satisfies two core geometric properties:

  1. No spurious local minima: Every local minimum is also a global minimum.
  2. Strict saddles: Every other critical point (where the gradient is zero) is a saddle point with at least one direction of strictly negative curvature, allowing algorithms to easily escape.

By analyzing these geometric properties, researchers have begun to explain why non-convex optimization is not just practically viable, but often provably efficient.


What Makes a Landscape Benign?

To understand why simple algorithms succeed, it helps to look at low-rank matrix and signal processing problems, where the geometric transition from chaotic to benign can be rigorously mapped.

In matrix completion—the task of filling in missing entries of a low-rank matrix—the objective function is inherently non-convex. However, Lee et al. proved that for the standard non-convex matrix completion objective, every local minimum is a global minimum. Ge et al. extended this insight into a unified geometric framework, demonstrating that a wide class of low-rank problems—including matrix sensing, matrix completion, and robust PCA—share this exact property. Because there are no bad local traps and all saddle points are strict, simple gradient descent initialized randomly is guaranteed to find the global solution.

This phenomenon isn't restricted to matrices. In phase retrieval (reconstructing a signal from magnitude-only measurements), the loss landscape depends heavily on the number of data samples. Sun et al. showed that once the number of measurements crosses a critical threshold, the phase retrieval landscape undergoes a geometric phase transition, becoming entirely benign and free of spurious local minima. Similarly, Zilber proved that inductive matrix completion possesses a benign landscape, ensuring reliable convergence for iterative solvers like the Gauss-Newton method.


How Over-Parameterization Annihilates Traps

While matrix problems have clean algebraic structures, neural networks introduce complex non-linearities. Why do their loss landscapes behave so well in practice? The primary mechanism is over-parameterization—making a network wider than strictly necessary to represent the target function.

Intuitively, adding hidden units adds dimensions to the optimization space. Imagine being trapped at a local minimum in a narrow network; the loss increases in every direction available to you. However, when you add more neurons, you introduce new degrees of freedom. What was once a "cupped" trap in a lower-dimensional space can open up in a higher-dimensional space, transforming the local minimum into an escapable saddle point.

[Narrow Network: 2D Space]       -->   [Over-parameterized: 3D Space]
   Local Minimum (Trapped)                Saddle Point (Descent Path Opens)
          \___/                                      \___  ___/
                                                         \/

Arjevani et al. formalized this intuition for two-layer ReLU networks, proving that over-parameterization mathematically "annihilates" spurious local minima by turning them into saddle points. Using a teacher-student framework with quadratic activations, Martin et al. showed that having even a single extra student neuron beyond the teacher's rank is enough to eliminate bad local minima and guarantee perfect signal recovery.

Conversely, when a network lacks sufficient width, the landscape degrades. Sharif-Nassab et al. demonstrated that if a shallow ReLU network is not wide enough relative to the size of the training dataset, the landscape develops isolated, "cupped" local minima from which no descent path to a global optimum exists. To map these boundaries, Pollaci leveraged algebraic geometry to determine the exact hidden layer widths required to eliminate these "spurious valleys" entirely for given target functions.


Data Diversity and Landscape Design

Beyond network width, the geometry of the optimization landscape is heavily shaped by the interaction between the network architecture and the structure of the training data.

If the data forces the network's internal neurons to learn distinct, non-redundant features, the optimization process avoids collapsing into suboptimal configurations. Xie et al. proved that for one-hidden-layer ReLU networks, if the internal units maintain a high degree of diversity, the optimization landscape contains no spurious local minima. Even in minimal architectures, such as a network with just two hidden units, Wu et al. showed that the landscape remains benign under favorable data distributions.

When data distributions are highly complex—such as a Gaussian Mixture Model—standard random initialization can still land an algorithm in a poorly behaved region of the landscape. To circumvent this, researchers use Landscape Design or structured initialization.

Lee et al. demonstrated that by using tensor decomposition to engineer a specific surrogate objective function, one can guarantee an optimization landscape completely free of bad local minima without relying on over-parameterization. This strategy of combining tensor-based initialization with gradient descent allows algorithms to bypass non-convex traps entirely, a principle successfully applied to graph neural networks by Zhang et al. and to non-Gaussian data mixtures by Li et al..


Escaping Traps with Dynamics and Noise

Even when a landscape is largely benign, finite-width models or adversarial label noise can introduce flat regions, ill-conditioned valleys, or mild local traps (Wang et al.; Diakonikolas et al.). When the static geometry of the landscape isn't perfectly benign, the dynamics of the optimization algorithm can compensate.

Injecting noise into the optimization process acts as a dynamic landscape smoother. Zhou et al. proved that adding noise to gradient descent and gradually annealing it over time allows an algorithm to escape spurious local optima in two-layer convolutional networks. The noise provides the necessary kinetic energy to bounce out of shallow, suboptimal basins, while the underlying benign geometry ensures that once the algorithm finds a descent path, it flows reliably toward the global minimum.

Key Foundational Work

Diverse Neural Network Learns True Target Functions (2017) — contributed 1 concept elements to this direction.
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017) — contributed 1 concept elements to this direction.
Matrix Completion has No Spurious Local Minimum (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_spurious_local_minima_non_convex_optimiz_a0de087d,
  title = {spurious local minima (non-convex optimization landscape)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spurious-local-minima-non-convex-optimization-landscape/rdr_a0de087d7cf74fd6acc1cd14ce55904e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_spurious_local_minima_non_convex_optimiz_a0de087d_v1,
  title = {spurious local minima (non-convex optimization landscape)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spurious-local-minima-non-convex-optimization-landscape/rdr_a0de087d7cf74fd6acc1cd14ce55904e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake