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.

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

References in corpus (3)

• Global rates of convergence for nonconvex optimization on manifolds
• Nonconvex phase synchronization
• Phase Transitions in Semidefinite Relaxations

Cited by in corpus (32)

• 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
• 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 proximal point method revisited
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• 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
• 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
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• On the simplicity and conditioning of low rank semidefinite programs
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Active Community Detection with Maximal Expected Model Change
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Learning in Gated Neural Networks