Phase Transitions in Semidefinite Relaxations

Abstract

Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family, and are surprisingly well-suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that, when the `statistical noise' is small enough, SDP relaxations correctly detect the underlying combinatorial structures. In this paper we develop asymptotic predictions for several `detection thresholds,' as well as for the estimation error above these thresholds. We study some classical SDP relaxations for statistical problems motivated by graph synchronization and community detection in networks. We map these optimization problems to statistical mechanics models with vector spins, and use non-rigorous techniques from statistical mechanics to characterize the corresponding phase transitions. Our results clarify the effectiveness of SDP relaxations in solving high-dimensional statistical problems.

71 pages, 24 pdf figures

References in corpus (3)

• Spectral Clustering of Graphs with the Bethe Hessian
• Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints
• The m-component spin glass on a Bethe lattice

Cited by in corpus (47)

• Nonconvex phase synchronization
• Near-optimal bounds for phase synchronization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Message-passing algorithms for synchronization problems over compact groups
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Approximating the XY model on a random graph with a $q$-state clock model
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Subexponential-Time Algorithms for Sparse PCA
• Community Recovery in Graphs with Locality
• Algorithmic detectability threshold of the stochastic block model
• Distributed Certifiably Correct Pose-Graph Optimization
• Kernel k-Groups via Hartigan's Method
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Comparison of Gabay-Toulouse and de Almeida-Thouless instabilities for the spin glass XY model in a field on sparse random graphs
• Matrix Completion with Hierarchical Graph Side Information
• Exact Minimax Estimation for Phase Synchronization
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Convex Relaxation Methods for Community Detection
• 2x2 convexifications for convex quadratic optimization with indicator variables
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
• Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints
• Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
• Typical Approximation Performance for Maximum Coverage Problem
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• The planted XY model: thermodynamics and inference
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Exact Recovery of Community Detection in k-partite Graph Models
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Partial recovery bounds for clustering with the relaxed $K$means
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Efficient semidefinite bounds for multi-label discrete graphical models
• Nonconvex landscapes for ${\mathbf{Z}}_2$ synchronization and graph clustering are benign near exact recovery thresholds
• The threshold for SDP-refutation of random regular NAE-3SAT
• SpaRTA - Tracking across occlusions via global partitioning of 3D clouds of points
• Exact threshold for approximate ellipsoid fitting of random points