Phase transitions in semidefinite relaxations
From MaRDI portal
Publication:2962328
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Estimation in multivariate analysis (62H12) Applications of mathematical programming (90C90) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial optimization (90C27)
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.
Recommendations
- Phase transitions in parameter rich optimization problems
- Phase transition and semi-global reducibility
- Phase transitions in integer linear problems
- Phase transitions for greedy sparse approximation algorithms
- scientific article; zbMATH DE number 6469137
- Linear phase transition in random linear constraint satisfaction problems
- scientific article; zbMATH DE number 2046061
- Simplified semidefinite and completely positive relaxations
- Semidefinite relaxation and nonconvex quadratic optimization
Cites work
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 975608 (Why is no real title available?)
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A survey of max-type recursive distributional equations
- Angular synchronization by eigenvectors and semidefinite programming
- Asymptotic mutual information for the balanced binary stochastic block model
- Atomic Decomposition by Basis Pursuit
- Bayesian model selection and model averaging
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Community structure in social and biological networks
- Grothendieck-type inequalities in combinatorial optimization
- Heuristics for semirandom graph problems
- How robust are reconstruction thresholds for community detection?
- Information, Physics, and Computation
- Neighborliness of randomly projected simplices in high dimensions
- Phase recovery, MaxCut and complex semidefinite programming
- Phase retrieval via matrix completion
- Phase retrieval with polarization
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Semidefinite programs on sparse random graphs and their application to community detection
- Semidefinite relaxation and nonconvex quadratic optimization
- Spectral redemption in clustering sparse networks
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Cited in
(48)- A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
- Notes on computational-to-statistical gaps: predictions using statistical physics
- How well do local algorithms solve semidefinite programs?
- Edge of spiked beta ensembles, stochastic Airy semigroups and reflected Brownian motions
- Joint community detection and rotational synchronization via semidefinite programming
- Community detection and stochastic block models: recent developments
- Optimal bipartite network clustering
- Subexponential-time algorithms for sparse PCA
- scientific article; zbMATH DE number 7370563 (Why is no real title available?)
- On semidefinite relaxations for the block model
- Phase transitions for greedy sparse approximation algorithms
- Entrywise eigenvector analysis of random matrices with low expected rank
- On the local stability of semidefinite relaxations
- Typical performance of approximation algorithms for NP-hard problems
- Semidefinite programs on sparse random graphs and their application to community detection
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
- Community detection with a subsampled semidefinite program
- Scalable low-rank semidefinite programming for certifiably correct machine perception
- Near-optimal bounds for phase synchronization
- Phase transition and semi-global reducibility
- Convex relaxation methods for community detection
- Optimal couplings between sparse block models
- Precise statistical analysis of classification accuracies for adversarial training
- Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Nonconvex phase synchronization
- Optimal rates of estimation for multi-reference alignment
- Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
- Riemannian Langevin algorithm for solving semidefinite programs
- The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
- The random fractional matching problem
- Graph powering and spectral robustness
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
- TAP free energy, spin glasses and variational inference
- Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
- Local laws for multiplication of random matrices
- Group synchronization on grids
- A unified approach to synchronization problems over subgroups of the orthogonal group
- An information-percolation bound for spin synchronization on general graphs
- Universal completability, least eigenvalue frameworks, and vector colorings
- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- Estimation of low-rank matrices via approximate message passing
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
This page was built for publication: Phase transitions in semidefinite relaxations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2962328)
