Title: Exponential error rates of SDP for block models: Beyond Grothendieck's inequality,
Abstract: 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 error rate that decays exponentially in the
signal-to-noise ratio. The error bound implies weak recovery in the sparse
graph regime with bounded expected degrees, as well as exact recovery in the
dense regime. An immediate corollary of our results yields error bounds under
the Censored Block Model. Moreover, these error bounds are robust, continuing
to hold under heterogeneous edge probabilities and a form of the so-called
monotone attack.
Significantly, this error rate is achieved by the SDP solution itself without
any further pre- or post-processing, and improves upon existing
polynomially-decaying error bounds proved using the Grothendieck\textquoteright
s inequality. Our analysis has two key ingredients: (i) showing that the graph
has a well-behaved spectrum, even in the sparse regime, after discounting an
exponentially small number of edges, and (ii) an order-statistics argument that
governs the final error rate. Both arguments highlight the implicit
regularization effect of the SDP formulation.