Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

Understand

We study the statistical performance of semidefinite programming (SDP) relaxations for clustering under random graph models.

• Under the $\mathbb{Z}_{2}$ Synchronization model, Censored Block Model and Stochastic Block Model, we show that SDP achieves an error rate of the form \[ \exp\Big[-\big(1-o(1)\big)\bar{n} I^* \Big].
• \] Here $\bar{n}$ is an appropriate multiple of the number of nodes and $I^*$ is an information-theoretic measure of the signal-to-noise ratio.
• We provide matching lower bounds on the Bayes error for each model and therefore demonstrate that the SDP approach is Bayes optimal.