Scientific Computing and Numerics (SCAN) Seminar

Yudong ChenCornell University
Exponential error rates of semidefinite programming for block models

Monday, October 16, 2017 - 1:25pm
Gates 406

We consider the community detection problem under the Stochastic and Censored Block Models. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. Significantly, even though we are estimating a combinatorial structure by solving a continuous optimization problem, this error rate is achieved by the SDP itself without any further pre/post-processing or rounding. Our results improve upon existing polynomially-decaying error bounds obtained via the Grothendieck’s inequality. The analysis highlights the implicit regularization effect of the SDP, and its robustness in the sparse graph regime.