# Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Builds on (most cited first, 12 of 12)

- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Rank optimality for the Burer-Monteiro factorization](https://mlsanity.com/paper/1812.03046/) (2018)
- [On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization](https://mlsanity.com/paper/1809.11083/) (2018)
- [Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery](https://mlsanity.com/paper/1404.4749/) (2014)
- [Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality](https://mlsanity.com/paper/1703.08729/) (2017)
- [Expander graphs are globally synchronizing](https://mlsanity.com/paper/2210.12788/) (2022)
- [Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs](https://mlsanity.com/paper/2307.02941/) (2023)
- [The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound](https://mlsanity.com/paper/2211.12389/) (2022)
- [Local Geometry Determines Global Landscape in Low-rank Factorization for Synchronization](https://mlsanity.com/paper/2311.18670/) (2023)
- [Nonconvex landscapes for Z2 synchronization and graph clustering are benign near exact recovery thresholds](https://mlsanity.com/paper/2407.13407/) (2024)

## Abstract (arXiv)

We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to significantly reduce the dimensionality of the problem at the cost of its convexity. We give a sharp condition on the conditioning of the Laplacian matrix associated with the SDP under which any second-order critical point of the non-convex problem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on mathbbZ2-synchronization problems and the Kuramoto model.