Skip to main content

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

Author(s): Boumal, Nicolas; Voroninski, Vladislav; Bandeira, Afonso S

To refer to this page use:
Abstract: Semidefinite programs (SDPs) 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 SDPs 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 SDPs 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 SDPs in that class almost never has any spurious local optima.
Publication Date: 2016
Citation: Boumal, Nicolas, Voroninski, Vladislav, Bandeira, Afonso S. (2016). The non-convex Burer-Monteiro approach works on smooth semidefinite programs. ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), 29
ISSN: 1049-5258
Type of Material: Journal Article
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.