Theoretical and Computational Guarantees of Mean Field Variational Inference for Community Detection

The mean field variational Bayes method is becoming increasingly popular in\nstatistics and machine learning. Its iterative Coordinate Ascent Variational\nInference algorithm has been widely applied to large scale Bayesian inference.\nSee Blei et al. (2017) for a recent comprehensive review. Despite the\npopularity of the mean field method there exist remarkably little fundamental\ntheoretical justifications. To the best of our knowledge, the iterative\nalgorithm has never been investigated for any high dimensional and complex\nmodel. In this paper, we study the mean field method for community detection\nunder the Stochastic Block Model. For an iterative Batch Coordinate Ascent\nVariational Inference algorithm, we show that it has a linear convergence rate\nand converges to the minimax rate within $\\log n$ iterations. This complements\nthe results of Bickel et al. (2013) which studied the global minimum of the\nmean field variational Bayes and obtained asymptotic normal estimation of\nglobal model parameters. In addition, we obtain similar optimality results for\nGibbs sampling and an iterative procedure to calculate maximum likelihood\nestimation, which can be of independent interest.\n