Parallelizing MCMC with Random Partition Trees

Abstract

The modern scale of data has brought new challenges to Bayesian inference. In particular, conventional MCMC algorithms are computationally very expensive for large data sets. A promising approach to solve this problem is embarrassingly parallel MCMC (EP-MCMC), which first partitions the data into multiple subsets and runs independent sampling algorithms on each subset. The subset posterior draws are then aggregated via some combining rules to obtain the final approximation. Existing EP-MCMC algorithms are limited by approximation accuracy and difficulty in resampling. In this article, we propose a new EP-MCMC algorithm PART that solves these problems. The new algorithm applies random partition trees to combine the subset posterior draws, which is distribution-free, easy to resample from and can adapt to multiple scales. We provide theoretical justification and extensive experiments illustrating empirical performance.

25 pages, 9 figures

References in corpus (1)

• Boosted Decision Trees as an Alternative to Artificial Neural Networks for Particle Identification

Cited by in corpus (18)

• Quantile Regression Under Memory Constraint
• Unbiased Markov chain Monte Carlo with couplings
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• DECOrrelated feature space partitioning for distributed sparse regression
• Nonparametric Heterogeneity Testing For Massive Data
• Embarrassingly parallel MCMC using deep invertible transformations
• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• Federated Stochastic Gradient Langevin Dynamics
• Simple, Scalable and Accurate Posterior Interval Estimation
• Nonparametric Bayesian Aggregation for Massive Data
• QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
• Distributed Bayesian clustering using finite mixture of mixtures
• Parallelising MCMC via Random Forests
• Communication Efficient Parallel Algorithms for Optimization on Manifolds
• Efficient posterior sampling for high-dimensional imbalanced logistic regression
• A Decentralized Approach to Bayesian Learning
• Accelerating MCMC Algorithms
• An Algorithm for Distributed Bayesian Inference in Generalized Linear Models