# Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2018.

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

- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [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)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization](https://mlsanity.com/paper/2302.05865/) (2023)
- [Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion](https://mlsanity.com/paper/2409.19550/) (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)

Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer--Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the penalty formulation of appropriately rank-constrained SDPs as long as the number of constraints scales sub-quadratically with the desired rank of the optimal solution. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion.