Techniques for proving Asynchronous Convergence results for Markov Chain Monte Carlo methods
This work addresses the convergence issues in asynchronous MCMC methods for applied statistics and machine learning, offering a foundational solution to enable reliable parallelization.
The paper tackles the problem of proving convergence for asynchronous Markov Chain Monte Carlo (MCMC) methods, which are used in parallel and distributed systems for improved performance but can diverge in some cases. It provides a generic theoretical framework to analyze and ensure convergence for any MCMC algorithm, including those not based on Gibbs sampling.
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.