The non-convex Burer-Monteiro approach works on smooth semidefinite programs
arXiv:1606.04970
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.
arXiv comment19 pages, in the proceedings of NIPS 2016
References in corpus (9)
- Manopt, a Matlab toolbox for optimization on manifolds
- Global rates of convergence for nonconvex optimization on manifolds
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Matrix Completion has No Spurious Local Minimum
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Phase Transitions in Semidefinite Relaxations
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
- Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
Cited by in corpus (8)
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Nonconvex phase synchronization
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Practical Sparse Matrices in C++ with Hybrid Storage and Template-Based Expression Optimisation
- Faster quantum and classical SDP approximations for quadratic binary optimization
- A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow
- Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
- Using Negative Curvature in Solving Nonlinear Programs