Introduction
Gibbs sampling is a workhorse for inference in graphical models, but it suffers from a major scaling problem: updating a single variable usually requires summing up contributions from every related "factor" in the model. In large-scale machine learning, where models might have millions of factors, this becomes computationally prohibitive.
Researchers have attempted to use "minibatching"—evaluating only a small random subset of factors at each step—to speed up the process. However, standard minibatching often introduces bias or requires an expensive "Metropolis-Hastings" (M-H) correction step, which can negate the speed gains. Furthermore, most existing minibatched Gibbs variants only work for discrete variables, leaving continuous-space problems in the dark.
This paper introduces Poisson-minibatching Gibbs (Poisson-Gibbs), a new Markov Chain Monte Carlo (MCMC) method that scales Gibbs sampling to massive graphical models. It eliminates the need for expensive correction steps, supports continuous variables, and provides rigorous theoretical guarantees that its convergence rate remains close to that of standard, full-batch Gibbs sampling.
The Poisson-Gibbs Methodology
The core innovation of Poisson-Gibbs lies in how the minibatch is selected:
- Poisson Auxiliary Variables: Instead of picking a fixed-size random minibatch, the algorithm augments the model with Poisson random variables ($s_\phi$) for each factor. These variables determine if and how much a factor contributes to the current update.
- State-Dependent Minibatches: Crucially, the minibatch selection depends on the current state of the variables. While this sounds counter-intuitive for maintaining a valid distribution, the authors prove that this specific state-dependency results in a reversible Markov chain that converges to the correct target distribution without needing an M-H correction step.
- Continuous State Spaces (PGDA): To handle continuous variables, the authors introduce Poisson-Gibbs with Double Chebyshev Approximation (PGDA). Because sampling from an arbitrary continuous conditional distribution is difficult, they use Chebyshev polynomials to approximate the energy function and the resulting probability density. They then use fast inverse transform sampling to generate new values.
Experimental Results
The authors evaluated their method on three distinct types of models: Potts Models (discrete), Continuous Spin Models, and Truncated Gaussian Mixtures.
Speed vs. Accuracy in Discrete Models
In experiments using a fully connected Potts model with 400 variables, Poisson-Gibbs matched the accuracy (measured by marginal error) of plain Gibbs sampling while being significantly faster.
As shown above, Poisson-Gibbs successfully converges alongside standard Gibbs, whereas previous state-of-the-art methods like DoubleMIN-Gibbs struggled to converge unless provided with very large minibatches.
Efficiency in Continuous Models
On continuous spin models, the PGDA variant proved to be vastly more efficient than standard rejection sampling.
Rejection sampling required over 300 steps to accept a single sample, whereas the Chebyshev-based approach provided high-quality samples with far fewer evaluations, leading to a much faster drop in Symmetric KL Divergence over time.
Key Insights and Theoretical Guarantees
- Efficiency of Poisson vs. Bernoulli: Previous "Firefly MCMC" methods used Bernoulli variables to pick minibatches, which can be inefficient. Poisson variables allow for much faster sampling of the minibatch itself, proportional to the minibatch size rather than the total number of factors.
- The Spectral Gap Guarantee: The authors provide a rigorous recipe for the minibatch size ($\lambda$). They prove that if $\lambda$ is set proportional to the square of the local maximum energy ($L^2$), the convergence rate is guaranteed to be within a constant factor of the full-batch version.
- Eliminating the M-H Bottleneck: By making the minibatch state-dependent in a mathematically sound way, the algorithm bypasses the correction step that typically slows down stochastic MCMC, achieving a better asymptotic time complexity ($O(DL^2)$ for discrete cases).
Limitations and Future Work
While powerful, the method has a few theoretical and practical boundaries:
- Bounded Factors: The theoretical guarantees rely on the factor functions being bounded ($M_\phi$). If a model has factors that can approach infinity, the current theory might not hold.
- Analytic Functions: The continuous version (PGDA) assumes that the energy functions are "analytic" (smooth enough to be approximated by polynomials). This might not apply to models with non-smooth components, such as ReLU activations in neural networks.
- Hyperparameter Tuning: Although the paper provides a theoretical range for the minibatch parameter $\lambda$, finding the absolute optimal value for a specific real-world problem still requires some manual tuning.
Summary updated