On the low-rank approach for semidefinite programs arising in synchronization and community detection

Abstract

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.

arXiv comment22 pages, Proceedings of The 29th Conference on Learning Theory (COLT), New York, NY, June 23-26, 2016

References in corpus (11)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Global rates of convergence for nonconvex optimization on manifolds
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Stochastic Block Models and Reconstruction
• Phase Transitions in Semidefinite Relaxations
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Grothendieck inequalities for semidefinite programs with rank constraint
• Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups

Cited by in corpus (34)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Learning One-hidden-layer Neural Networks with Landscape Design
• A Dimension Reduction-Based Joint Activity Detection and Channel Estimation Algorithm for Massive Access
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Fast, Robust and Non-convex Subspace Recovery
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Nonconvex Demixing From Bilinear Measurements
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• The proximal point method revisited
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Robust PCA by Manifold Optimization
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow
• Optimization Landscape of Tucker Decomposition
• A Grothendieck-type inequality for local maxima
• Thresholds of descending algorithms in inference problems
• Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• On the simplicity and conditioning of low rank semidefinite programs
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Active Community Detection with Maximal Expected Model Change
• Learning in Gated Neural Networks