Abstract
Gibbs sampling is a Markov chain Monte Carlo
technique commonly used for estimating marginal
distributions. To speed up Gibbs sampling, there
has recently been interest in parallelizing it by
executing asynchronously. While empirical results suggest that many models can be efficiently
sampled asynchronously, traditional Markov chain
analysis does not apply to the asynchronous case,
and thus asynchronous Gibbs sampling is poorly
understood. In this paper, we derive a better understanding of the two main challenges of asynchronous Gibbs: bias and mixing time. We show
experimentally that our theoretical results match
practical outcomes