Title: Techniques for proving Asynchronous Convergence results for Markov Chain Monte Carlo methods,
Abstract: Markov Chain Monte Carlo (MCMC) methods such as Gibbs sampling are finding
widespread use in applied statistics and machine learning. These often lead to
difficult computational problems, which are increasingly being solved on
parallel and distributed systems such as compute clusters. Recent work has
proposed running iterative algorithms such as gradient descent and MCMC in
parallel asynchronously for increased performance, with good empirical results
in certain problems. Unfortunately, for MCMC this parallelization technique
requires new convergence theory, as it has been explicitly demonstrated to lead
to divergence on some examples. Recent theory on Asynchronous Gibbs sampling
describes why these algorithms can fail, and provides a way to alter them to
make them converge. In this article, we describe how to apply this theory in a
generic setting, to understand the asynchronous behavior of any MCMC algorithm,
including those implemented using parameter servers, and those not based on
Gibbs sampling.