# Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2018.

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

- [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)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations](https://mlsanity.com/paper/2211.17244/) (2022)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (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)
- [The Nonconvex Geometry of Linear Inverse Problems](https://mlsanity.com/paper/2101.02776/) (2021)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [A practical, fast method for solving sum-of-squares problems for very large polynomials](https://mlsanity.com/paper/2410.19844/) (2024)
- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)
- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)
- [Scalable Learning of Determinantal Point Processes with Kernel-Structured Interactions](https://mlsanity.com/paper/2610.12829/) (2026)
- [Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness](https://mlsanity.com/paper/2610.18318/) (2026)

## Abstract (arXiv)

We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix X of size n. Following the Burer--Monteiro approach, we optimize a factor Y of size n × p instead, such that X = YYT. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if p is small, but results in a non-convex optimization problem with a quadratic cost function and quadratic equality constraints in Y. In this paper, we show that if the set of constraints on Y regularly defines a smooth manifold, then, despite non-convexity, first- and second-order necessary optimality conditions are also sufficient, provided p is large enough. For smaller values of p, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum Y maps to a global optimum X = YYT of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust-region subproblem and quadratic optimization over several spheres, as well as for the Max-Cut and Orthogonal-Cut SDPs which are common relaxations in stochastic block modeling and synchronization of rotations.