Analyzing Hogwild Parallel Gaussian Gibbs Sampling
Sampling inference methods are computationally difficult to scale for many models in part because global dependencies can reduce opportunities for parallel computation. Without strict conditional independence structure among variables, standard 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 simply 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 Hogwild Gibbs sampler, with any update schedule or allocation of variables to processors, yields a stable sampling process with the correct sample mean.
The authors present analysis of "hogwild" parallel 
      Gibbs sampling, where Gibbs updates are run for blocks of variables 
      separately on each processor without communicating each iteration, so that 
      the sampler is no longer "correct" at least in the traditional sense. The 
      analysis focuses on sampling Gaussian graphical models, with the main 
      result being that under a condition on the precision matrix (being 
      generalised diagonally dominant) hogwild Gaussian Gibbs sampling is 
      stable, and gives the correct asympoptic mean. The story for variances is 
      a little more complex: a finite error is introduced when there are cross 
      processor interactions that are ignored, and these become more important 
      if the mixing at each processor is faster, but in the limit of drawing 
      exact samples at each processor the variance can be corrected 
      analytically. Quality. The ideas and analysis are novel and 
      rigorous as far as I can tell. Clarity. The paper is reasonably 
      well written but could be better organised, especially for the typically 
      ML reader who is probably not overly familar with the linear algebra terms 
      or the various linear solvers introduced. Having a "background material" 
      section first laying this groundwork might be helpful. 
      Originality. I am not aware of other analysis of this type of 
      sampling. Significance. Scaling sampling methods is of significant 
      interest to the NIPS community, so analysis of methods that attempt to do 
      this is valuable, especially if it points the way towards algorithmic 
      improvements. This paper laid out some nice ideas, many of which seem 
      intuitive: hogwild sampling is dependent on the cross processor 
      interactions not being too strong, and faster local mixing might actually 
      be detrimental in some ways. However, the connection of these ideas to 
      potential algorithm improvements was only hypothetical and then only 
      hinted at. The paper begs the question in several cases. The generalised 
      diagonally dominant condition in practice means I should try to put highly 
      interacted variables: how should I try to do this? How well does it work 
      in practice? Proposition 5 gives an analytic correct for the variance when 
      q=inf: what happens if I use this for q large? I think this would have 
      been a stronger paper if these questions had been addressed: if not 
      empirically, at least in the discussion. But I accept there is a space 
      limitation. A relevant reference that also used "hogwild" sampling 
      is Finale Doshi-Velez, Shakir Mohamed, David A. Knowles and Zoubin 
      Ghahramani. Large scale nonparametric Bayesian inference: Data 
      parallelisation in the Indian buffet process. NIPS 2009. Minor 
      notes Equation 1: am I missing something or there should be a minus 
      sign?! Next equation (line 141): hat over v