Probabilistic Duality for Parallel Gibbs Sampling without Graph Coloring
This addresses the challenge of maintaining graph colorings for parallel Gibbs sampling in dynamic or densely connected graphical models, though it is incremental as it trades off mixing time for parallelism.
The paper tackles the problem of parallel Gibbs sampling in graphical models by introducing probabilistic duality for random variables, enabling a highly-parallelizable Gibbs sampler that requires minimal preprocessing and is easy to implement. The result is a method useful for large dynamic networks and densely connected graphs, though it leads to inferior mixing times compared to sequential Gibbs sampling.
We present a new notion of probabilistic duality for random variables involving mixture distributions. Using this notion, we show how to implement a highly-parallelizable Gibbs sampler for weakly coupled discrete pairwise graphical models with strictly positive factors that requires almost no preprocessing and is easy to implement. Moreover, we show how our method can be combined with blocking to improve mixing. Even though our method leads to inferior mixing times compared to a sequential Gibbs sampler, we argue that our method is still very useful for large dynamic networks, where factors are added and removed on a continuous basis, as it is hard to maintain a graph coloring in this setup. Similarly, our method is useful for parallelizing Gibbs sampling in graphical models that do not allow for graph colorings with a small number of colors such as densely connected graphs.