mlsanityData to 7 Oct 2026

No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis

arXiv 1704.00708 ↗First posted 3 Apr 2017cs.LG math.OC stat.MLcited by 127

Not on the map. Why?

Abstract (arXiv)

In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) no high-order saddle points exists. These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice. Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion. The framework naturally leads to new results for asymmetric matrix completion and robust PCA.

Key facts. Cited by 127 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Apr 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 36; 2022: 26; 2023: 18; 2024: 14; 2025: 18; 2026: 14.

127 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  2. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  3. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  4. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  5. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  6. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 43
  7. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  8. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  9. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  10. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  11. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  12. 2022Flat minima generalize for low-rank matrix recoverycited by 28
38 more
  1. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  2. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  3. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  4. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  5. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  6. 2023The Law of Parsimony in Gradient Descent for Learning Deep Linear Networkscited by 19
  7. 2025LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)cited by 19
  8. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  9. 2021Joint Learning of Linear Time-Invariant Dynamical Systemscited by 16
  10. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  11. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  12. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  13. 2024A Global Geometric Analysis of Maximal Coding Rate Reductioncited by 13
  14. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  15. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  16. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  17. 2022Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructionscited by 11
  18. 2023Bootstrapped Representations in Reinforcement Learningcited by 11
  19. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  20. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  21. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  22. 2022Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracycited by 10
  23. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  24. 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
  25. 2023Accelerated Algorithms for Nonlinear Matrix Decomposition with the ReLU functioncited by 9
  26. 2023Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programmingcited by 9
  27. 2024Implicit Regularization of Sharpness-Aware Minimization for Scale-Invariant Problemscited by 9
  28. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  29. 2023Learning Rich Rankingscited by 8
  30. 2025An entropy formula for the Deep Linear Networkcited by 8
  31. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  32. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  33. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
  34. 2024Federated Representation Learning in the Under-Parameterized Regimecited by 7
  35. 2021Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddingscited by 6
  36. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
  37. 2022MetaNOR: A Meta-Learnt Nonlocal Operator Regression Approach for Metamaterial Modelingcited by 6
  38. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6

50 most cited of 127 All 127 (JSON)