Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly


Yingjie Fei, Yudong Chen ;
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1235-1269, 2019.


We study the statistical performance of the semidefinite programming (SDP) relaxation approach for clustering under the binary symmetric Stochastic Block Model (SBM). We show that the SDP achieves an error rate of the form $\exp\left[-(1-o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate information-theoretic measure of the signal-to-noise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are sub-optimal by a multiplicative constant in the exponent. As a corollary, our result implies that SDP achieves the optimal exact recovery threshold with the correct leading constant. We further show that this error rate of SDP is robust; that is, it remains unchanged under the so-called semirandom model where the graph is modified by a monotone adversary, as well as under the setting with heterogeneous edge probabilities. Our proof is based on a novel primal-dual analysis of the SDP.

Related Material