Timezone: »
Variational approximation has been widely used in large-scale Bayesian inference recently, the simplest kind of which involves imposing a mean field assumption to approximate complicated latent structures. Despite the computational scalability of mean field, theoretical studies of its loss function surface and the convergence behavior of iterative updates for optimizing the loss are far from complete. In this paper, we focus on the problem of community detection for a simple two-class Stochastic Blockmodel (SBM). Using batch co-ordinate ascent (BCAVI) for updates, we give a complete characterization of all the critical points and show different convergence behaviors with respect to initializations. When the parameters are known, we show a significant proportion of random initializations will converge to ground truth. On the other hand, when the parameters themselves need to be estimated, a random initialization will converge to an uninformative local optimum.
Author Information
Soumendu Sundar Mukherjee (University of California, Berkeley)
Purnamrita Sarkar (UT Austin)
Y. X. Rachel Wang (University of Sydney)
Bowei Yan (Jump Trading)
More from the Same Authors
-
2021 Spotlight: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2021 Poster: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2018 Poster: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2018 Spotlight: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2017 Poster: Convergence of Gradient EM on Multi-component Mixture of Gaussians »
Bowei Yan · Mingzhang Yin · Purnamrita Sarkar -
2017 Poster: On clustering network-valued data »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Lizhen Lin -
2016 Poster: On Robustness of Kernel Clustering »
Bowei Yan · Purnamrita Sarkar -
2015 Poster: The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels »
Purnamrita Sarkar · Deepayan Chakrabarti · peter j bickel