文章基本信息

标题：Rate optimal Chernoff bound and application to community detection in the stochastic block models
本地全文：下载
作者：Zhixin Zhou ; Ping Li
期刊名称：Electronic Journal of Statistics
印刷版ISSN：1935-7524
出版年度：2020
卷号：14
期号：1
页码：1302-1347
DOI：10.1214/20-EJS1686
语种：English
出版社：Institute of Mathematical Statistics
摘要：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.
关键词：Chernoff information; Bayes error probability; hypothesis testing; community detection; stochastic block models