Smoothed Analysis for Low-Rank Solutions to Semidefinite Programs in Quadratic Penalty Form
Abstract
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.
Cite
Text
Bhojanapalli et al. "Smoothed Analysis for Low-Rank Solutions to Semidefinite Programs in Quadratic Penalty Form." Annual Conference on Computational Learning Theory, 2018.Markdown
[Bhojanapalli et al. "Smoothed Analysis for Low-Rank Solutions to Semidefinite Programs in Quadratic Penalty Form." Annual Conference on Computational Learning Theory, 2018.](https://mlanthology.org/colt/2018/bhojanapalli2018colt-smoothed/)BibTeX
@inproceedings{bhojanapalli2018colt-smoothed,
title = {{Smoothed Analysis for Low-Rank Solutions to Semidefinite Programs in Quadratic Penalty Form}},
author = {Bhojanapalli, Srinadh and Boumal, Nicolas and Jain, Prateek and Netrapalli, Praneeth},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2018},
pages = {3243-3270},
url = {https://mlanthology.org/colt/2018/bhojanapalli2018colt-smoothed/}
}