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

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2016.

## Built on by (most cited first, 30 of 46)

- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs](https://mlsanity.com/paper/2109.08046/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [Global Optimality in Bivariate Gradient-based DAG Learning](https://mlsanity.com/paper/2306.17378/) (2023)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method](https://mlsanity.com/paper/2112.06556/) (2021)
- [Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations](https://mlsanity.com/paper/2211.17244/) (2022)
- [From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguation](https://mlsanity.com/paper/2312.05995/) (2023)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Manifold learning and optimization using tangent space proxies](https://mlsanity.com/paper/2501.12678/) (2025)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)
- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Higher Order Generalization Error for First Order Discretization of Langevin Diffusion](https://mlsanity.com/paper/2102.06229/) (2021)
- [From Digital Humanities to Quantum Humanities: Potentials and Applications](https://mlsanity.com/paper/2103.11825/) (2021)
- [Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points](https://mlsanity.com/paper/2112.13269/) (2021)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)

## 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.