# When Are Nonconvex Problems Not Scary?

arXiv: https://arxiv.org/abs/1510.06096 · HTML: https://mlsanity.com/paper/1510.06096/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2015.

## Built on by (most cited first, 28 of 28)

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features](https://mlsanity.com/paper/2203.01238/) (2022)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (2021)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Are All Losses Created Equal: A Neural Collapse Perspective](https://mlsanity.com/paper/2210.02192/) (2022)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [A Global Geometric Analysis of Maximal Coding Rate Reduction](https://mlsanity.com/paper/2406.01909/) (2024)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [On Newton's Method to Unlearn Neural Networks](https://mlsanity.com/paper/2406.14507/) (2024)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities](https://mlsanity.com/paper/2406.13036/) (2024)
- [Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning](https://mlsanity.com/paper/2306.02420/) (2023)
- [On the Optimization Landscape of Maximum Mean Discrepancy](https://mlsanity.com/paper/2110.13452/) (2021)
- [Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurements](https://mlsanity.com/paper/2205.10448/) (2022)
- [When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks](https://mlsanity.com/paper/2606.04476/) (2026)
- [Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Points](https://mlsanity.com/paper/2212.03765/) (2022)
- [Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms](https://mlsanity.com/paper/2405.03073/) (2024)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [Learning the Supports for Categorical Critic in Reinforcement Learning](https://mlsanity.com/paper/2607.01880/) (2026)
- [Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework](https://mlsanity.com/paper/2608.03001/) (2026)

## Abstract (arXiv)

In this note, we focus on smooth nonconvex optimization problems that obey: (1) all local minimizers are also global; and (2) around any saddle point or local maximizer, the objective has a negative directional curvature. Concrete applications such as dictionary learning, generalized phase retrieval, and orthogonal tensor decomposition are known to induce such structures. We describe a second-order trust-region algorithm that provably converges to a global minimizer efficiently, without special initializations. Finally we highlight alternatives, and open problems in this direction.