Analyzing Hogwild Parallel Gaussian Gibbs Sampling

Abstract

Sampling inference methods are computationally difficult to scale for many mod-els in part because global dependencies can reduce opportunities for parallel com-putation. Without strict conditional independence structure among variables, stan-dard Gibbs sampling theory requires sample updates to be performed sequentially, even if dependence between most variables is not strong. Empirical work has shown that some models can be sampled effectively by going “Hogwild ” and sim-ply running Gibbs updates in parallel with only periodic global communication, but the successes and limitations of such a strategy are not well understood. As a step towards such an understanding, we study the Hogwild Gibbs sampling strategy in the context of Gaussian distributions. We develop a framework which provides convergence conditions and error bounds along with simple proofs and connections to methods in numerical linear algebra. In particular, we show that if the Gaussian precision matrix is generalized diagonally dominant, then any Hog-wild Gibbs sampler, with any update schedule or allocation of variables to proces-sors, yields a stable sampling process with the correct sample mean. 1