Exponential error rates of SDP for block models: Beyond Grothendieck's inequality

Yingjie Fei, Yudong Chen

In this paper we consider the cluster estimation problem under the Stochastic Block Model. We show that the semidefinite programming (SDP) formulation for this problem achieves an…