Parallel Sampling of DP Mixture Models using Sub-Clusters Splits
We present an MCMC sampler for Dirichlet process mixture models that can be parallelized to achieve significant computational gains. We combine a nonergodic, restricted Gibbs iteration with split/merge proposals in a manner that produces an ergodic Markov chain. Each cluster is augmented with two subclusters to construct likely split moves. Unlike some previous parallel samplers, the proposed sampler enforces the correct stationary distribution of the Markov chain without the need for finite approximations. Empirical results illustrate that the new sampler exhibits better convergence properties than current methods.
The authors propose a parallel algorithm for the DPMM 
      that parallelizes a RJMCMC sampler that jumps between finite models. While 
      the parallelization and the RJMCMC sampler are proposed together, I will 
      separate them for the purpose of this review, in order to ask questions 
      about each part separately. First, the RJMCMC algorithm (by which 
      I mean, the algorithm we would have on a single cluster). Here, we use a 
      reversible-jump MCMC algorithm to jump between finite-dimensional 
      Dirichlet distributions. As an aside, since $\bar{\pi}_{K+1}$ is not used 
      in the mixture model (the mixture model is defined on the renormalized 
      occupied K components), it would seem to make more sense to define a 
      K-dimensional, rather than a K-1 - dimensional, Dirichlet distribution; 
      this is valid under marginalization properties of the Dirichlet 
      distribution, since equation 10 samples from a distribution proportional 
      to $\pi_1 ... \pi_K$ To jump between model dimensionalities, the 
      authors propose a split/merge RJMCMC step that is reminiscent of that of 
      Green and Richardson. In fact, the “naive” choice is very similar to the 
      Green and Richardson method, and I am not sure why it is not valid in this 
      case.. I would like to see a more detailed comparison of the Green and 
      Richardson method (and other split/merge methods) and the proposed method, 
      and the reasons for the different design choices. The 
      parallelization method splits the clusters onto processors with 
      probability related to the similarity between clusters. Each data point 
      can only be assigned to processors within its own cluster. The split/merge 
      method of creating new clusters, and the fact that atoms are explicitly 
      instantiated, ensures that there is no alignment problem of new clusters 
      across processors. Update of cluster parameters can be done in parallel; 
      however contrary to line 194 I do not see how sampling the $\pi_k$ can be 
      done in parallel. Further, sampling the superclusters must be done in 
      parallel. The experiments suggest improved performance; however I 
      would be interested in seeing further experimental evaluation and 
      information. What is the number of superclusters? How often are $\pi$ and 
      the super-clusters updates? How does performance scale with number of 
      clusters? Also, it would be interesting to discuss why your split/merge 
      sampler performs so much better than the other split/merge sampler. 
      Additional points: Line 107: The Dirichlet process can 
      be sampled by normalizing an infinite sequence of gamma random variables, 
      not beta random variables (or more accurately, by normalizing a sample 
      from a gamma process). The Sethuraman paper cited describes an iterative 
      algorithm for sampling size-biased samples from a DP, but it is based on 
      the fact that the DP has Dirichlet marginals rather than normalization of 
      an unnormalized random measure. Line ~079, line ~131: In addition 
      to the approximate truncated and finite methods mentioned, there exist 
      instantiated-weight samplers that are asymptotically correct -- for 
      example slice sampling and retrospective sampling approaches, or the 
      recent paper by Favaro & Teh