Rate optimal Chernoff bound and application to community detection in the stochastic block models

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)1302–1347
Journal / PublicationElectronic Journal of Statistics
Issue number1
Online published25 Mar 2020
Publication statusPublished - 2020
Externally publishedYes



The Chernoff coefficient is known to be an upper bound of Bayes error probability in classification problem. In this paper, we will develop a rate optimal Chernoff bound on the Bayes error probability. The new bound is not only an upper bound but also a lower bound of Bayes error probability up to a constant factor. Moreover, we will apply this result to community detection in the stochastic block models. As a clustering problem, the optimal misclassification rate of community detection problem can be characterized by our rate optimal Chernoff bound. This can be formalized by deriving a minimax error rate over certain parameter space of stochastic block models, then achieving such an error rate by a feasible algorithm employing multiple steps of EM type updates.

Research Area(s)

  • Chernoff information, Bayes error probability, hypothesis testing, community detection, stochastic block models

Download Statistics

No data available