The non-convex Burer-Monteiro approach works on smooth semidefinite programs / On the low-rank approach for semidefinite programs arising in synchronization and community detection

Vlad just sent me the following:

Hi Igor,

You may find of interest my new paper (joint work with Nicolas Boumal and Afonso Bandiera) on theoretical guarantees for the Burer Monteiro approach for smooth SDPs. We are able to show the following: consider a fixed set of m linear constraints for an SDP with compact domain, and the corresponding factorized BM formulation with rank constrained to be at most about sqrt(m). If the rank-constrained problem has a domain which is a smooth manifold, then generically in the cost matrix C of the SDP, this BM rank-constrained problem is non-convex in only a benign way, in that 2nd order critical points are global minimizers. We also establish quantitative bounds on the quality of candidate solution as a function of approximate 2nd order optimality and provide examples of applications and a numerical study.

http://arxiv.org/pdf/1606.04970.pdf


There is also a related paper with the same authors in which we analyze regimes of planted MaxCut and community detection. In these specific settings we provide much stronger guarantees, in that the BM factorization has no spurious local optima even at rank 2.


http://arxiv.org/pdf/1602.04426v2.pdf


Best,

-Vlad



Vladislav Voroninski
http://www.mit.edu/~vvlad/

Thank you Vlad

The non-convex Burer-Monteiro approach works on smooth semidefinite programs by Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

Semidefinite programs (SDP's) can be solved in polynomial time by interior point methods, but scalability can be an issue. To address this shortcoming, over a decade ago, Burer and Monteiro proposed to solve SDP's with few equality constraints via rank-restricted, non-convex surrogates. Remarkably, for some applications, local optimization methods seem to converge to global optima of these non-convex surrogates reliably. Although some theory supports this empirical success, a complete explanation of it remains an open question. In this paper, we consider a class of SDP's which includes applications such as max-cut, community detection in the stochastic block model, robust PCA, phase retrieval and synchronization of rotations. We show that the low-rank Burer-Monteiro formulation of SDP's in that class almost never has any spurious local optima.

On the low-rank approach for semidefinite programs arising in synchronization and community detection by Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

To address difficult optimization problems, convex relaxations based on semidefinite programming are now common place in many fields. Although solvable in polynomial time, large semidefinite programs tend to be computationally challenging. Over a decade ago, exploiting the fact that in many applications of interest the desired solutions are low rank, Burer and Monteiro proposed a heuristic to solve such semidefinite programs by restricting the search space to low-rank matrices. The accompanying theory does not explain the extent of the empirical success. We focus on Synchronization and Community Detection problems and provide theoretical guarantees shedding light on the remarkable efficiency of this heuristic.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.