Rate optimal Chernoff bound and application to community detection in the stochastic block models
From MaRDI portal
Publication:2180063
Abstract: Chernoff coefficient is an upper bound of Bayes error probability in classification problem. In this paper, we will develop sharp Chernoff type bound on 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 in a non-asymptotic setting. Moreover, we will apply this result to community detection in stochastic block model. As a clustering problem, the optimal error rate of community detection can be characterized by our Chernoff type bound. This can be formalized by deriving a minimax error rate over certain class of parameter space, then achieving such error rate by a feasible algorithm employ multiple steps of EM type updates.
Recommendations
- Minimax rates of community detection in stochastic block models
- Bayesian community detection
- Achieving optimal misclassification proportion in stochastic block models
- Optimal rates for community estimation in the weighted stochastic block model
- Community detection and stochastic block models: recent developments
Cites work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A non-uniform Berry-Esseen bound via Stein's method
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- A Simple SVD Algorithm for Finding Hidden Partitions
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Achieving optimal misclassification proportion in stochastic block models
- An improvement of convergence rate estimates in the Lyapunov theorem
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Asymptotic error probability of binary hypothesis testing for Poisson point-process observations (Corresp.)
- Community detection in degree-corrected block models
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Consistency of spectral clustering in stochastic block models
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Elements of Information Theory
- Entrywise eigenvector analysis of random matrices with low expected rank
- Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
- Graph powering and spectral robustness
- Hypothesis testing and information theory
- Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels
- Lower bounds to error probability for coding on discrete memoryless channels. I
- Mathematical foundations of infinite-dimensional statistical models
- Minimax rates of community detection in stochastic block models
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- On semidefinite relaxations for the block model
- Optimal bipartite network clustering
- Phase transitions in semidefinite relaxations
- Pseudo-likelihood methods for community detection in large sparse networks
- Random Laplacian matrices and convex relaxations
- Second-Order and Moderate Deviation Asymptotics for Successive Refinement
- Second-order asymptotics for quantum hypothesis testing
- Semidefinite programs on sparse random graphs and their application to community detection
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral clustering in the dynamic stochastic block model
- Spectral redemption in clustering sparse networks
- The Chernoff lower bound for symmetric quantum hypothesis testing
- The tail of the hypergeometric distribution
- Theoretical and computational guarantees of mean field variational inference for community detection
This page was built for publication: Rate optimal Chernoff bound and application to community detection in the stochastic block models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180063)
