Parallel Markov Chain Monte Carlo via Spectral Clustering

Autor:	Basse, Guillaume W., Pillai, Natesh S., Smith, Aaron
Rok vydání:	2016
Předmět:	Statistics - Methodology Statistics - Computation
Druh dokumentu:	Working Paper
Popis:	As it has become common to use many computer cores in routine applications, finding good ways to parallelize popular algorithms has become increasingly important. In this paper, we present a parallelization scheme for Markov chain Monte Carlo (MCMC) methods based on spectral clustering of the underlying state space, generalizing earlier work on parallelization of MCMC methods by state space partitioning. We show empirically that this approach speeds up MCMC sampling for multimodal distributions and that it can be usefully applied in greater generality than several related algorithms. Our algorithm converges under reasonable conditions to an `optimal' MCMC algorithm. We also show that our approach can be asymptotically far more efficient than naive parallelization, even in situations such as completely flat target distributions where no unique optimal algorithm exists. Finally, we combine theoretical and empirical bounds to provide practical guidance on the choice of tuning parameters. Comment: Appeared in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) 2016
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1605.09454 Zobrazit plný text záznamu View this record from Arxiv