Mixing Time of Metropolis-Hastings for Bayesian Community Detection
Abstract
We study the computational complexity of a Metropolis-Hastings algorithm for Bayesian community detection. We first establish a posterior strong consistency result for a natural prior distribution on stochastic block models under the optimal signal-to-noise ratio condition in the literature. We then give a set of conditions that guarantee rapidly mixing of a simple Metropolis-Hastings algorithm. The mixing time analysis is based on a careful study of posterior ratios and a canonical path argument to control the spectral gap of the Markov chain.
Cite
Text
Zhuo and Gao. "Mixing Time of Metropolis-Hastings for Bayesian Community Detection." Journal of Machine Learning Research, 2021.Markdown
[Zhuo and Gao. "Mixing Time of Metropolis-Hastings for Bayesian Community Detection." Journal of Machine Learning Research, 2021.](https://mlanthology.org/jmlr/2021/zhuo2021jmlr-mixing/)BibTeX
@article{zhuo2021jmlr-mixing,
title = {{Mixing Time of Metropolis-Hastings for Bayesian Community Detection}},
author = {Zhuo, Bumeng and Gao, Chao},
journal = {Journal of Machine Learning Research},
year = {2021},
pages = {1-89},
volume = {22},
url = {https://mlanthology.org/jmlr/2021/zhuo2021jmlr-mixing/}
}