Select Lab Publications


Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees (2011)

By: Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin

Abstract: We explore the task of constructing a parallel Gibbs sampler, to both improve mixing and the exploration of high likelihood states. Recent work in parallel Gibbs sampling has focused on update schedules which do not guarantee convergence to the intended stationary distribution. In this work, we propose two methods to construct parallel Gibbs samplers guaranteed to draw from the targeted distribution. The first method, called the Chromatic sampler, uses graph coloring to construct a direct parallelization of the classic sequential scan Gibbs sampler. In the case of 2-colorable models we relate the Chromatic sampler to the Synchronous Gibbs sampler (which draws all variables simultaneously in parallel), and reveal new ergodic properties of Synchronous Gibbs chains. Our second method, the Splash sampler, is a complementary strategy which can be used when the variables are tightly coupled. This constructs and samples multiple blocks in parallel, using a novel locking protocol and an iterative junction tree generation algorithm. We further improve the Splash sampler through adaptive tree construction. We demonstrate the benefits of our two sampling algorithms on large synthetic and real-world models using a 32 processor multi-core system.



Download Information
Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin (2011). "Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees." In Artificial Intelligence and Statistics (AISTATS). pdf   talk      
BibTeX citation

@inproceedings{Gonzalez+al:aistatspgibbs,
title = {Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees},
author = {Joseph Gonzalez and Yucheng Low and Arthur Gretton and Carlos Guestrin},
booktitle = {In Artificial Intelligence and Statistics (AISTATS)},
month = {May},
year = {2011},
address = {Ft. Lauderdale, FL},
wwwfilebase = {aistats2011-gonzalez-low-gretton-guestrin},
wwwtopic = {Parallel Learning}
}



full list