Phase Transitions in Semidefinite Relaxations
arXiv:1511.08769 · doi:10.1073/pnas.1523097113
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.
arXiv comment71 pages, 24 pdf figures
References in corpus (14)
- Community structure in social and biological networks
- Message Passing Algorithms for Compressed Sensing
- The Bethe lattice spin glass revisited
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- A survey of max-type recursive distributional equations
- The Dantzig selector: Statistical estimation when is much larger than
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Stochastic Block Models and Reconstruction
- MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
- Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
- Spectral Clustering of Graphs with the Bethe Hessian
- Synchronization over and community detection in multiplex signed networks with constraints
- The m-component spin glass on a Bethe lattice
Cited by in corpus (48)
- 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
- Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
- Approximating the XY model on a random graph with a -state clock model
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
- Community Recovery in Graphs with Locality
- 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
- 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: 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
- Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
- The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
- Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints
- Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
- Typical Performance of Approximation Algorithms for NP-hard Problems
- Typical Approximation Performance for Maximum Coverage Problem
- Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
- Asymptotic mutual information in quadratic estimation problems over compact groups
- Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
- The planted XY model: thermodynamics and inference
- Exact Recovery of Community Detection in k-partite Graph Models
- Partial recovery bounds for clustering with the relaxed means
- Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
- Exact threshold for approximate ellipsoid fitting of random points
- Efficient semidefinite bounds for multi-label discrete graphical models
- Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
- SpaRTA - Tracking across occlusions via global partitioning of 3D clouds of points
- The threshold for SDP-refutation of random regular NAE-3SAT
- Nonconvex landscapes for synchronization and graph clustering are benign near exact recovery thresholds