Reviews: Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees

Summary: This paper introduces Poisson auxiliary variables to facilitate minibatch sampling. The key insight is with the appropriate Poisson parameterization, the joint distribution (Eq. The authors apply this insight to discrete-state Gibbs sampling (Algorithm 2), Metropolis Hastings (Supplement), and continuous-state Gibbs sampling (Alg 3. and 5). The authors also develop spectral gap lower bounds for all proposed Gibbs sampling methods, which provides a rough guideline for choosing a tuning parameter \lambda and comparing the (asymptotic) per iteration runtime of the methods (Table 1). Finally the authors evaluate the Gibbs methods on synthetic data, showing that their proposed method performs similarly to Gibbs while outperforming alternatives.