Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly

Yingjie Fei, Yudong Chen
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1235-1269, 2019.

Abstract

We study the statistical performance of the semidefinite programming (SDP) relaxation approach for clustering under the binary symmetric Stochastic Block Model (SBM). We show that the SDP achieves an error rate of the form $\exp\left[-(1-o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate information-theoretic measure of the signal-to-noise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are sub-optimal by a multiplicative constant in the exponent. As a corollary, our result implies that SDP achieves the optimal exact recovery threshold with the correct leading constant. We further show that this error rate of SDP is robust; that is, it remains unchanged under the so-called semirandom model where the graph is modified by a monotone adversary, as well as under the setting with heterogeneous edge probabilities. Our proof is based on a novel primal-dual analysis of the SDP.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-fei19a, title = {Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly}, author = {Fei, Yingjie and Chen, Yudong}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {1235--1269}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/fei19a/fei19a.pdf}, url = {https://proceedings.mlr.press/v99/fei19a.html}, abstract = {We study the statistical performance of the semidefinite programming (SDP) relaxation approach for clustering under the binary symmetric Stochastic Block Model (SBM). We show that the SDP achieves an error rate of the form $\exp\left[-(1-o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate information-theoretic measure of the signal-to-noise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are sub-optimal by a multiplicative constant in the exponent. As a corollary, our result implies that SDP achieves the optimal exact recovery threshold with the correct leading constant. We further show that this error rate of SDP is robust; that is, it remains unchanged under the so-called semirandom model where the graph is modified by a monotone adversary, as well as under the setting with heterogeneous edge probabilities. Our proof is based on a novel primal-dual analysis of the SDP.} }
Endnote
%0 Conference Paper %T Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly %A Yingjie Fei %A Yudong Chen %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-fei19a %I PMLR %P 1235--1269 %U https://proceedings.mlr.press/v99/fei19a.html %V 99 %X We study the statistical performance of the semidefinite programming (SDP) relaxation approach for clustering under the binary symmetric Stochastic Block Model (SBM). We show that the SDP achieves an error rate of the form $\exp\left[-(1-o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate information-theoretic measure of the signal-to-noise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are sub-optimal by a multiplicative constant in the exponent. As a corollary, our result implies that SDP achieves the optimal exact recovery threshold with the correct leading constant. We further show that this error rate of SDP is robust; that is, it remains unchanged under the so-called semirandom model where the graph is modified by a monotone adversary, as well as under the setting with heterogeneous edge probabilities. Our proof is based on a novel primal-dual analysis of the SDP.
APA
Fei, Y. & Chen, Y.. (2019). Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:1235-1269 Available from https://proceedings.mlr.press/v99/fei19a.html.

Related Material