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

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. MSC 2010 subject classifications: Primary 62F03; secondary 60G05.

• Publication year

  2020

• Venue

  Electronic Journal of Statistics

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/20-ejs1686
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2019influential reference
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

  2019influential reference
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting

  2018cited by this paper
• Second-Order Asymptotically Optimal Statistical Classification

  2018cited by this paper
• Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs

  2018cited by this paper
• Graph powering and spectral robustness

  2018cited by this paper
• Optimal Bipartite Network Clustering

  2018cited by this paper
• Theoretical and Computational Guarantees of Mean Field Variational Inference for Community Detection

  2017cited by this paper
• ENTRYWISE EIGENVECTOR ANALYSIS OF RANDOM MATRICES WITH LOW EXPECTED RANK.

  2017influential reference
• Spectral clustering in the dynamic stochastic block model

  2017cited by this paper
• Performance of a community detection algorithm based on semidefinite programming

  2016cited by this paper
• Community Detection in Degree-Corrected Block Models

  2016cited by this paper
• Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery

  2015influential reference
• Random Laplacian Matrices and Convex Relaxations

  2015cited by this paper
• Achieving Optimal Misclassification Proportion in Stochastic Block Models

  2015influential reference
• Minimax Rates of Community Detection in Stochastic Block Models

  2015influential reference
• Multisection in the Stochastic Block Model using Semidefinite Programming

  2015cited by this paper
• Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery

  2015influential reference
• On Measures of Entropy and Information

  2015cited by this paper
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

  2015cited by this paper
• Semidefinite programs on sparse random graphs and their application to community detection

  2015cited by this paper
• Community detection in sparse networks via Grothendieck’s inequality

  2014cited by this paper
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

  2014cited by this paper
• Consistency Thresholds for the Planted Bisection Model

  2014influential reference
• A Simple SVD Algorithm for Finding Hidden Partitions

  2014cited by this paper
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms

  2014cited by this paper
• On semidefinite relaxations for the block model

  2014cited by this paper
• Spectral redemption in clustering sparse networks

  2013cited by this paper
• Consistency of Spectral Clustering in Sparse Stochastic Block Models

  2013cited by this paper
• Community detection thresholds and the weak Ramanujan property

  2013cited by this paper
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown

  2012cited by this paper
• Second Order Asymptotics for Quantum Hypothesis Testing

  2012cited by this paper
• Pseudo-likelihood methods for community detection in large sparse networks

  2012cited by this paper
• Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels

  2012cited by this paper
• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• An improvement of convergence rate estimates in the Lyapunov theorem

  2010cited by this paper
• Discriminating States: the quantum Chernoff bound.

  2006cited by this paper
• THE CHERNOFF LOWER BOUND FOR SYMMETRIC QUANTUM HYPOTHESIS TESTING

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• A non-uniform Berry–Esseen bound via Stein's method

  2001cited by this paper
• Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels. I

  1993cited by this paper
• A shortest augmenting path algorithm for dense and sparse linear assignment problems

  1987cited by this paper
• Asymptotic error probability of binary hypothesis testing for Poisson point-process observations

  1986cited by this paper
• The tail of the hypergeometric distribution

  1979cited by this paper
• Hypothesis testing and information theory

  1974cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• Statistical Guarantees for Consensus Clustering

  2023cites this paper
• Principal Subspace Estimation Under Information Diffusion

  2021cites this paper
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method

  2021cites this paper
• On Variational Inference in Biclustering Models

  2021cites this paper
• Rate-Optimal Subspace Estimation on Random Graphs

  2021cites this paper
• Community Detection and Matrix Completion With Social and Item Similarity Graphs

  2020cites this paper