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 nonrigorous techniques from statistical mechanics to characterize the corresponding phase transitions. Our results clarify the effectiveness of SDP relaxations in solving high-dimensional statistical problems.

Keywords: community detection; phase transitions; semidefinite programming; synchronization.

Fig. 1.

Estimating ${\mathit{x}}_0\in {\left\{+1,-1\right\}}^n$ under the noisy ${\mathrm{\mathbb{Z}}}_2$ synchronization model of Eq. 1. Curves correspond to (asymptotic) analytical predictions, and dots correspond to numerical simulations (averaged over 100 realizations).

Fig. 2.

Community detection under the hidden partition model of Eq. 2, for average degree $\left(a+b\right)/2=5$. Dots indicate performance of the SDP reconstruction method (averaged over 500 realizations). Dashed curve indicates asymptotic analytical prediction for the Gaussian model (which captures the large-degree behavior). Solid curve indicates analytical prediction for the sparse graph case (within the vectorial ansatz; SI Appendix).

Fig. 3.

Phase transition for the SDP estimator: for $\lambda >{\lambda }_c^{\text{SDP}}\left(d\right)$, the SDP estimator has positive correlation with the ground truth; for $\lambda \le {\lambda }_c^{\text{SDP}}\left(d\right)$ the correlation is vanishing [here $\lambda =\left(a-b\right)/\sqrt{2\left(a+b\right)}$ and $d=\left(a+b\right)/2$]. Solid line indicates prediction ${\tilde{\lambda }}_c^{\text{SDP}}\left(d\right)$ from the cavity method (vectorial ansatz; SI Appendix) (compare Eq. 25). Dashed line indicates ideal phase transition $\lambda =1$. Red circles indicate numerical estimates of the phase transition location for $d=2$, 5, and 10.