Local Strong Convexity in Nonconvex Optimization Landscapes

This direction is split into other directions: local strong convexity. Its last version stays readable and citable here.

Version 1 of 173 papers91 conceptsfrozen 2026-10-04

In classical optimization theory, convexity is the gold standard. If a function is convex, any local minimum is a global minimum, and gradient descent is guaranteed to find it. However, modern machine learning—from matrix completion to deep neural networks—operates almost entirely in the realm of non-convexity. On paper, these problems should be intractable, riddled with "bad" local minima and saddle points that trap optimizers.

Yet, in practice, simple first-order methods like Gradient Descent (GD) and Stochastic Gradient Descent (SGD) find high-quality solutions with remarkable consistency. A growing body of research suggests this success isn't a fluke of luck, but a consequence of local strong convexity: the phenomenon where globally non-convex landscapes behave like well-conditioned convex bowls in the neighborhoods surrounding their global optima.

The Two-Stage Convergence Recipe

The prevailing explanation for why we can solve non-convex problems like phase retrieval or matrix factorization relies on a two-stage framework. First, a "smart" initialization places the optimizer within a specific basin of attraction. Second, the local geometry of that basin ensures rapid, linear convergence to the global optimum.

Shuyang Ling and Thomas Strohmer demonstrate this in Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing. They show that while the global landscape for signal separation is complex, a spectral initialization provides a "warm start" that lands the estimate in a region where the objective function exhibits a benign local structure. Once inside this region, the error reduces exponentially—a hallmark of convex optimization.

This "basin of attraction" is not just a theoretical convenience; it has a measurable radius. Yann Traonmilin and Jean-François Aujol in The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension link the size of this basin to the quality of the measurements (often via the Restricted Isometry Property). As you collect more data, the basin grows larger and the landscape becomes "flatter," making it easier for even coarse initializations to succeed.

Geometry of the Benign Neighborhood

What does it mean for a non-convex function to be "locally convex"? Mathematically, it often means the Hessian matrix (the matrix of second derivatives) is positive definite within a specific radius of the solution.

In Recovery Guarantees for One-hidden-layer Neural Networks, Kai Zhong and colleagues prove that for simple neural networks, the loss surface contains a local basin where the function is strongly convex. Similarly, Felix Benning proves in In almost all shallow analytic neural network optimization landscapes, efficient minimizers have strongly convex neighborhoods that almost all "efficient" local minima are non-degenerate, meaning they are surrounded by these strongly convex bowls.

This local structure explains several empirical observations:

  1. Linear Convergence: In Implicit Regularization in Nonconvex Statistical Estimation, Cong Ma 0001 and Yuxin Chen show that GD converges at a geometric rate for phase retrieval because the Hessian is well-conditioned near the optimum.
  2. Stability: Eitan Levin and Tamir Bendory note in A note on Douglas-Rachford, subgradients, and phase retrieval that this local convexity ensures that once an algorithm reaches the vicinity of a solution, it remains stable despite irregularities elsewhere.

Implicit Regularization: Staying in the Bowl

A critical question remains: if the landscape is only convex locally, why doesn't gradient descent simply wander out of the "good" region and into a "bad" one?

The answer lies in implicit regularization. Masaaki Imaizumi and Johannes Schmidt-Hieber argue in On Generalization Bounds for Deep Networks Based on Loss Surface Implicit Regularization that the geometry of the loss surface itself traps the optimizer. They propose the concept of local essential convexity, where the loss surface is convex along the specific paths the optimizer takes.

This is echoed by Guy Gur-Ari in Gradient Descent Happens in a Tiny Subspace. He observes that during training, the gradient actually collapses into a tiny subspace associated with the largest eigenvalues of the Hessian. In this subspace, the landscape is effectively convex, allowing the optimizer to ignore the high-dimensional non-convexity of the rest of the parameter space.

Applications Across Domains

The principle of local strong convexity has been identified as the engine behind many successful non-convex algorithms:

By shifting the focus from global landscape properties to local geometric regularity, this research direction provides a rigorous mathematical foundation for the surprising efficacy of modern optimization. It suggests that the "hardness" of non-convexity is often a global mirage that disappears once the optimizer finds its way into the right neighborhood.

Papers in this version

Showing 60 of 73 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_local_strong_convexity_in_nonconvex_opti_1f9ead6f,
  title = {Local Strong Convexity in Nonconvex Optimization Landscapes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-strong-convexity-in-nonconvex-optimization-landscapes/rdr_1f9ead6f665a4ce8937e86ecb5e7fb91},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_local_strong_convexity_in_nonconvex_opti_1f9ead6f_v1,
  title = {Local Strong Convexity in Nonconvex Optimization Landscapes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-strong-convexity-in-nonconvex-optimization-landscapes/rdr_1f9ead6f665a4ce8937e86ecb5e7fb91/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}