Rate optimal Chernoff bound and application to community detection in the stochastic block models
From MaRDI portal
Publication:2180063
DOI10.1214/20-EJS1686zbMath1439.62074arXiv1812.11269OpenAlexW3013444389MaRDI QIDQ2180063
Publication date: 13 May 2020
Published in: Electronic Journal of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.11269
hypothesis testingBayes error probabilitycommunity detectionstochastic block modelsChernoff information
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Parametric hypothesis testing (62F03) Statistical aspects of information-theoretic topics (62B10) Foundations of stochastic processes (60G05)
Cites Work
- Pseudo-likelihood methods for community detection in large sparse networks
- Consistency thresholds for the planted bisection model
- Minimax rates of community detection in stochastic block models
- An improvement of convergence rate estimates in the Lyapunov theorem
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral clustering in the dynamic stochastic block model
- Community detection in sparse networks via Grothendieck's inequality
- The Chernoff lower bound for symmetric quantum hypothesis testing
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- The tail of the hypergeometric distribution
- On semidefinite relaxations for the block model
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Random Laplacian matrices and convex relaxations
- Community detection in degree-corrected block models
- Entrywise eigenvector analysis of random matrices with low expected rank
- Theoretical and computational guarantees of mean field variational inference for community detection
- Consistency of spectral clustering in stochastic block models
- Second-order asymptotics for quantum hypothesis testing
- Spectral redemption in clustering sparse networks
- Phase transitions in semidefinite relaxations
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Mathematical Foundations of Infinite-Dimensional Statistical Models
- Asymptotic error probability of binary hypothesis testing for Poisson point-process observations (Corresp.)
- Hypothesis testing and information theory
- A Simple SVD Algorithm for Finding Hidden Partitions
- Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Optimal Bipartite Network Clustering
- Graph Powering and Spectral Robustness
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Community detection thresholds and the weak Ramanujan property
- Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
- Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels
- Second-Order and Moderate Deviation Asymptotics for Successive Refinement
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Semidefinite programs on sparse random graphs and their application to community detection
- Elements of Information Theory
- Lower bounds to error probability for coding on discrete memoryless channels. I
- 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
