Skip to yearly menu bar Skip to main content


The non-convex Burer-Monteiro approach works on smooth semidefinite programs

Nicolas Boumal · Vlad Voroninski · Afonso Bandeira

Area 5+6+7+8 #106

Keywords: [ (Other) Optimization ] [ Convex Optimization ] [ Large Scale Learning and Big Data ] [ Combinatorial Optimization ]


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.

Live content is unavailable. Log in and register to view live content