Fall 2018

Smoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization

Wednesday, Sep. 26, 2018 3:30 pm4:00 pm

Add to Calendar


Praneeth Netrapalli (Microsoft Research India)

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.