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

Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli
Proceedings of the 31st Conference On Learning Theory, PMLR 75:3243-3270, 2018.

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. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate 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. 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 this Paper

BibTeX
@InProceedings{pmlr-v75-bhojanapalli18a, 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 = {Proceedings of the 31st Conference On Learning Theory}, pages = {3243--3270}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/bhojanapalli18a/bhojanapalli18a.pdf}, url = {https://proceedings.mlr.press/v75/bhojanapalli18a.html}, 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. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate 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. 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.} }
Endnote
%0 Conference Paper %T Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form %A Srinadh Bhojanapalli %A Nicolas Boumal %A Prateek Jain %A Praneeth Netrapalli %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-bhojanapalli18a %I PMLR %P 3243--3270 %U https://proceedings.mlr.press/v75/bhojanapalli18a.html %V 75 %X 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. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate 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. 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.
APA
Bhojanapalli, S., Boumal, N., Jain, P. & Netrapalli, P.. (2018). Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:3243-3270 Available from https://proceedings.mlr.press/v75/bhojanapalli18a.html.

Related Material