Phase transitions in semidefinite relaxations

DOI10.1073/PNAS.1523097113zbMATH Open1359.62188arXiv1511.08769OpenAlexW2174754147WikidataQ36831458 ScholiaQ36831458MaRDI QIDQ2962328FDOQ2962328

Authors: A. Javanmard, Federico Ricci-Tersenghi, Andrea Montanari 

Publication date: 16 February 2017

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.08769

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

Mathematics Subject Classification ID

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)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Title not available (Why is that?)
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Atomic Decomposition by Basis Pursuit
• Spectral redemption in clustering sparse networks
• Belief propagation, robust reconstruction and optimal recovery of block models
• Community structure in social and biological networks
• Community detection thresholds and the weak Ramanujan property
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Community detection in sparse networks via Grothendieck's inequality
• Bayesian model selection and model averaging
• Neighborliness of randomly projected simplices in high dimensions
• Semidefinite relaxation and nonconvex quadratic optimization
• A survey of max-type recursive distributional equations
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• Phase recovery, MaxCut and complex semidefinite programming
• Phase retrieval with polarization
• Information, Physics, and Computation
• Angular synchronization by eigenvectors and semidefinite programming
• Grothendieck-type inequalities in combinatorial optimization
• Title not available (Why is that?)
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Phase retrieval via matrix completion
• Semidefinite programs on sparse random graphs and their application to community detection
• Heuristics for semirandom graph problems
• Asymptotic mutual information for the balanced binary stochastic block model
• How robust are reconstruction thresholds for community detection?

Cited In (48)

• How well do local algorithms solve semidefinite programs?
• Notes on computational-to-statistical gaps: predictions using statistical physics
• 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
• Subexponential-time algorithms for sparse PCA
• Optimal bipartite network clustering
• Title not available (Why is that?)
• On semidefinite relaxations for the block model
• Phase transitions for greedy sparse approximation algorithms
• Entrywise eigenvector analysis of random matrices with low expected rank
• Typical performance of approximation algorithms for NP-hard problems
• On the local stability of semidefinite relaxations
• Semidefinite programs on sparse random graphs and their application to community detection
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• Scalable low-rank semidefinite programming for certifiably correct machine perception
• Community detection with a subsampled semidefinite program
• Near-optimal bounds for phase synchronization
• Phase transition and semi-global reducibility
• Optimal couplings between sparse block models
• Convex relaxation methods for community detection
• 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
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Optimal rates of estimation for multi-reference alignment
• Riemannian Langevin algorithm for solving semidefinite programs
• The random fractional matching problem
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• Graph powering and spectral robustness
• Partial recovery bounds for clustering with the relaxed \(K\)-means
• Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Title not available (Why is that?)
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• TAP free energy, spin glasses and variational inference
• 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
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists

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)