# Polynomial time guarantees for the Burer-Monteiro method

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2019.

## Built on by (most cited first, 12 of 12)

- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [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)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuit](https://mlsanity.com/paper/2409.02708/) (2024)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [Well-Conditioned Oblivious Perturbations in Linear Space](https://mlsanity.com/paper/2604.23193/) (2026)

## Abstract (arXiv)

The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in Y, where Y is an n × p matrix such that X = Y YT. In this paper, we show that this method can solve SDPs in polynomial time in a smoothed analysis setting. More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints. We show that if p gtrsim √2(1+η)m, where m is the number of constraints and η>0 is any fixed constant, then the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. Our bound on p approaches the celebrated Barvinok-Pataki bound in the limit as η goes to zero, beneath which it is known that the nonconvex program can be suboptimal. Previous analyses were unable to give polynomial time guarantees for the Burer-Monteiro method, since they either assumed that the criticality conditions are satisfied exactly, or ignored the nontrivial problem of computing an approximately feasible solution. We address the first problem through a novel connection with tubular neighborhoods of algebraic varieties. For the feasibility problem we consider a least squares formulation, and provide the first guarantees that do not rely on the restricted isometry property.