  Gibbs sampling is the de facto Markov chain Monte Carlo method used for
inference and learning on large scale graphical models. For complicated factor
graphs with lots of factors, the performance of Gibbs sampling can be limited
by the computational cost of executing a single update step of the Markov
chain. This cost is proportional to the degree of the graph, the number of
factors adjacent to each variable. In this paper, we show how this cost can be
reduced by using minibatching: subsampling the factors to form an estimate of
their sum. We introduce several minibatched variants of Gibbs, show that they
can be made unbiased, prove bounds on their convergence rates, and show that
under some conditions they can result in asymptotic single-update-run-time
speedups over plain Gibbs sampling.
