mlsanityData to 14 Oct 2026

When Are Nonconvex Problems Not Scary?

arXiv 1510.06096 ↗First posted 21 Oct 2015math.OC cs.IT math.ITcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 6; 2023: 4; 2024: 5; 2025: 0; 2026: 3.

28 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 227
  2. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  3. 2021An Unconstrained Layer-Peeled Perspective on Neural Collapsecited by 87
  4. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  5. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  6. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  7. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  8. 2023Neural Collapse in Multi-label Learning with Pick-all-label Losscited by 14
  9. 2021Submodular + Concavecited by 13
  10. 2024A Global Geometric Analysis of Maximal Coding Rate Reductioncited by 13
  11. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  12. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
16 more
  1. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  2. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  3. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  4. 2024On Newton's Method to Unlearn Neural Networkscited by 5
  5. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 4
  6. 2023Matrix Completion in Almost-Verification Timecited by 4
  7. 2024Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalitiescited by 3
  8. 2023Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learningcited by 2
  9. 2021On the Optimization Landscape of Maximum Mean Discrepancycited by 1
  10. 2022Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurementscited by 1
  11. 2026When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networkscited by 1
  12. 2022Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Pointscited by 0
  13. 2024Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithmscited by 0
  14. 2024Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problemcited by 0
  15. 2026Learning the Supports for Categorical Critic in Reinforcement Learningcited by 0
  16. 2026Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Frameworkcited by 0