Smoothed analysis for lowrank solutions to semidefinite programs in quadratic penalty form
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:32433270, 2018.
Abstract
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of lowrank 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 secondorder stationary points are approximate global optima for the penalty formulation of appropriately rankconstrained SDPs, as long as the number of constraints scales subquadratically with the desired rank. Our result is based on a simple penalty function formulation of the rankconstrained SDP along with a smoothed analysis to avoid worstcase cost matrices. We particularize our results to two applications, namely, MaxCut and matrix completion.
Related Material


