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

摘要: We study the statistical performance of semidefinite programming (SDP) relaxations for clustering under random graph models. Under $\mathbb {Z}_{2}$ Synchronization model, Censored Block Model (CBM) and Stochastic (SBM), we show that SDP achieves an error rate form $\exp [-(1-o(1)) \bar { n}{ {I}^{*}}]$ . Here $ n}$ is appropriate multiple number nodes ${ {I}^{*}}$ information-theoretic measure signal-to-noise ratio. provide matching lower bounds on Bayes each model therefore demonstrate approach optimal. As a corollary, our results imply optimal exact recovery threshold model. Furthermore, robust: above bound remains valid semirandom versions models in which observed modified by monotone adversary. Our proof based novel primal-dual analysis unified framework all three models, shows tightly approximates joint majority voting procedure.