# Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 70 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 30 of 34)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Neural Collaborative Filtering vs. Matrix Factorization Revisited](https://mlsanity.com/paper/2005.09683/) (2020)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [Rank optimality for the Burer-Monteiro factorization](https://mlsanity.com/paper/1812.03046/) (2018)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds](https://mlsanity.com/paper/2104.10356/) (2021)

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

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)](https://mlsanity.com/paper/2502.09376/) (2025)
- [Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points](https://mlsanity.com/paper/2302.07828/) (2023)
- [Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations](https://mlsanity.com/paper/2211.17244/) (2022)
- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing](https://mlsanity.com/paper/2310.15549/) (2023)
- [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [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)
- [Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO](https://mlsanity.com/paper/2608.29018/) (2026)
- [Learning PDE Dynamics between Submanifolds Using Green's Observation Operators](https://mlsanity.com/paper/2610.01697/) (2026)

## Abstract (arXiv)

We consider minimizing a twice-differentiable, L-smooth, and μ-strongly convex objective φ over an n× n positive semidefinite matrix Msucceq0, under the assumption that the minimizer Mstar has low rank rstarll n. Following the Burer--Monteiro approach, we instead minimize the nonconvex objective f(X)=φ(XXT) over a factor matrix X of size n× r. This substantially reduces the number of variables from O(n2) to as few as O(n) and also enforces positive semidefiniteness for free, but at the cost of giving up the convexity of the original problem. In this paper, we prove that if the search rank r≥ rstar is overparameterized by a constant factor with respect to the true rank rstar, namely as in r>frac14(L/μ-1)2rstar, then despite nonconvexity, local optimization is guaranteed to globally converge from any initial point to the global optimum. This significantly improves upon a previous rank overparameterization threshold of r≥ n, which we show is sharp in the absence of smoothness and strong convexity, but would increase the number of variables back up to O(n2). Conversely, without rank overparameterization, we prove that such a global guarantee is possible if and only if φ is almost perfectly conditioned, with a condition number of L/μ<3. Therefore, we conclude that a small amount of overparameterization can lead to large improvements in theoretical guarantees for the nonconvex Burer--Monteiro factorization.