mlsanityData to 7 Oct 2026

The non-convex Burer-Monteiro approach works on smooth semidefinite programs

arXiv 1606.04970 ↗First posted 15 Jun 2016math.OC cs.NA math.NAcited by 44

Not on the map. Why?

Abstract (arXiv)

Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods, but scalability can be an issue. To address this shortcoming, over a decade ago, Burer and Monteiro proposed to solve SDPs with few equality constraints via rank-restricted, non-convex surrogates. Remarkably, for some applications, local optimization methods seem to converge to global optima of these non-convex surrogates reliably. Although some theory supports this empirical success, a complete explanation of it remains an open question. In this paper, we consider a class of SDPs which includes applications such as max-cut, community detection in the stochastic block model, robust PCA, phase retrieval and synchronization of rotations. We show that the low-rank Burer--Monteiro formulation of SDPs in that class almost never has any spurious local optima.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jun 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 11; 2023: 4; 2024: 6; 2025: 6; 2026: 5.

44 papers.

Sort:

By area:

  1. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  2. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  3. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  4. 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimizationcited by 21
  5. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  6. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  7. 2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
  8. 2021Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphscited by 12
  9. 2026Advances in Global Solvers for 3D Visioncited by 12
  10. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  11. 2021An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimizationcited by 10
  12. 2022Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracycited by 10
32 more
  1. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  2. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  3. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  4. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  5. 2021Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Methodcited by 4
  6. 2022Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxationscited by 4
  7. 2023From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguationcited by 4
  8. 2022Accelerating Certifiable Estimation with Preconditioned Eigensolverscited by 3
  9. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  10. 2023Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completioncited by 2
  11. 2024Quantization Avoids Saddle Points in Distributed Optimizationcited by 2
  12. 2025Manifold learning and optimization using tangent space proxiescited by 2
  13. 2025A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraintscited by 2
  14. 2025Scalable Second-order Riemannian Optimization for K-means Clusteringcited by 2
  15. 2021Higher Order Generalization Error for First Order Discretization of Langevin Diffusioncited by 1
  16. 2021From Digital Humanities to Quantum Humanities: Potentials and Applicationscited by 1
  17. 2021Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Pointscited by 1
  18. 2025Atlas-based Manifold Representations for Interpretable Riemannian Machine Learningcited by 1
  19. 2021Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programmingcited by 0
  20. 2022Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Resultscited by 0
  21. 2022Inference and Optimization for Engineering and Physical Systemscited by 0
  22. 2022Joint Reasoning on Hybrid-knowledge sources for Task-Oriented Dialogcited by 0
  23. 2024Low-Rank Extragradient Methods for Scalable Semidefinite Optimizationcited by 0
  24. 2024Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+cited by 0
  25. 2024Tailed Low-Rank Matrix Factorization for Similarity Matrix Completioncited by 0
  26. 2024A practical, fast method for solving sum-of-squares problems for very large polynomialscited by 0
  27. 2025Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecturecited by 0
  28. 2025Single-Snapshot Gridless 2D-DoA Estimation for UCAs: A Joint Optimization Approachcited by 0
  29. 2026Certifiable Factor Graph Optimizationcited by 0
  30. 2026Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexitycited by 0
  31. 2026Flexible Online Representation Learning Based on Similarity Matchingcited by 0
  32. 2026Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSOcited by 0