Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:12351269, 2019.
Abstract
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[(1o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate informationtheoretic measure of the signaltonoise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are suboptimal 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 socalled 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 primaldual analysis of the SDP.
Related Material


