2016 Poster Sessions : Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling

Student Name : Christopher De Sa
Advisor : Oyekunle Olukotun
Research Areas: Computer Systems
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, a technique called Hogwild! 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 poster, we will illustrate the two main challenges of asynchronous Gibbs, sampling bias and mixing time — and give practical conditions under which asynchronous Gibbs sampling will work well. We show experimentally that our theoretical results match practical outcomes.

Chris De Sa is a fifth-year Ph.D. student working with Kunle Olukotun and Chris Ré. His research focuses on theoretically-guaranteed fast implementations of ubiquitous machine learning algorithms such as stochastic gradient descent and Gibbs sampling.