mlsanityData to 14 Oct 2026

Matrix Completion has No Spurious Local Minimum

arXiv 1605.07272 ↗First posted 24 May 2016cs.LG cs.DS stat.MLcited by 125

Not on the map. Why?

Abstract (arXiv)

Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for textitpositive semidefinite matrix completion has no spurious local minima --- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve positive semidefinite matrix completion with textitarbitrary initialization in polynomial time. The result can be generalized to the setting when the observed entries contain noise. We believe that our main proof strategy can be useful for understanding geometric properties of other statistical problems involving partial or noisy observations.

Key facts. Cited by 125 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 39; 2022: 25; 2023: 16; 2024: 21; 2025: 14; 2026: 10.

125 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. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  4. 2021An Unconstrained Layer-Peeled Perspective on Neural Collapsecited by 87
  5. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  6. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  7. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  8. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  9. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  10. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
  11. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  12. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
38 more
  1. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  2. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  3. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  4. 2022Implicit Full Waveform Inversion with Deep Neural Representationcited by 26
  5. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  6. 2022Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Functioncited by 21
  7. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  8. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  9. 2023The Law of Parsimony in Gradient Descent for Learning Deep Linear Networkscited by 20
  10. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
  11. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  12. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  13. 2022Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomialscited by 13
  14. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  15. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  16. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  17. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  18. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  19. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  20. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 11
  21. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  22. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  23. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  24. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  25. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  26. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  27. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  28. 2024Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivitycited by 9
  29. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  30. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  31. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7
  32. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  33. 2023Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learningcited by 7
  34. 2021For Manifold Learning, Deep Neural Networks can be Locality Sensitive Hash Functionscited by 6
  35. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
  36. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  37. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  38. 2022Simple Alternating Minimization Provably Solves Complete Dictionary Learningcited by 6

50 most cited of 125 All 125 (JSON)