Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
This provides theoretical guarantees for efficient algorithms in learning and optimization, though it is incremental as it builds on existing Burer-Monteiro approaches.
The paper tackles the problem of finding low-rank solutions to semidefinite programs (SDPs) by showing that all approximate local optima are global optima for a penalty formulation when constraints scale sub-quadratically with rank, with applications in Max-Cut and matrix completion.
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.