Large-Scale Stochastic Sampling from the Probability Simplex

Jack Baker, Paul Fearnhead, Emily B. Fox, Christopher Nemeth

TL;DR

This paper introduces the Stochastic Cox-Ingersoll-Ross (SCIR) process, a novel method for efficiently sampling from probability simplex distributions, which are common in many large-scale Bayesian models. SCIR overcomes a key limitation of existing methods by eliminating discretization errors, leading to more accurate and unbiased inference, especially in sparse data scenarios.

What Problem Does This Paper Address?

Many popular large-scale Bayesian models, such as topic models and network models, rely on parameters that lie on a probability simplex. This means these parameters must be non-negative and sum to one. Standard methods for sampling from these distributions, like Stochastic Gradient Markov Chain Monte Carlo (SGMCMC), approximate continuous-time processes with discrete steps. While this is efficient for large datasets, it introduces "discretization error." This error becomes particularly problematic when parameters are close to zero (sparse simplex spaces), leading to biased and inaccurate results. Existing SGMCMC methods struggle to handle these sparse, boundary-heavy distributions, limiting their applicability to important real-world problems.

Methods

The core contribution is the Stochastic Cox-Ingersoll-Ross (SCIR) process. Unlike existing SGMCMC methods that discretize continuous processes like the Langevin diffusion, SCIR is based on the Cox-Ingersoll-Ross (CIR) process. The CIR process has a key advantage: its transition density is known exactly, meaning it can be simulated without any discretization error.

The authors adapt the CIR process for large datasets by using minibatch approximations of the data, similar to how SGMCMC works. This results in the SCIR process, which they prove is asymptotically unbiased. They also show how this approach can be extended to other constrained spaces beyond the simplex.

Datasets

Not discussed in the paper. The experiments use synthetic datasets and publicly available datasets for Latent Dirichlet Allocation (LDA) and a Bayesian Nonparametric Mixture Model.

Key Insights and Ideas

  • Discretization Error is a Major Bottleneck: The paper convincingly demonstrates that discretization error, not just minibatch noise, is the primary cause of poor performance for SGMCMC methods on sparse simplex spaces.
  • CIR Process as a Discretization-Free Alternative: The Cox-Ingersoll-Ross process offers a natural way to avoid discretization error because its transition dynamics are analytically known.
  • SCIR Bridges Theory and Practice: By combining the CIR process with stochastic approximation (minibatches), the authors create a scalable and theoretically sound sampler for constrained spaces.
  • Simplex Sparsity is a Critical Challenge: The paper highlights that many real-world applications inherently involve sparse simplex distributions, making the SCIR method highly relevant.

Key Results

  • Improved Accuracy on Sparse Data: Experiments show that SCIR significantly outperforms existing methods like SGRLD on sparse Dirichlet posteriors, as evidenced by lower Kolmogorov-Smirnov distances and more accurate boxplots of sampled values.
  • Comparable Performance on Dense Data: For dense Dirichlet posteriors, SCIR and SGRLD show similar performance, indicating SCIR is a robust choice for various simplex scenarios.
  • Better Performance in LDA and Mixture Models: Applying SCIR to Latent Dirichlet Allocation (LDA) and a Bayesian Nonparametric Mixture Model resulted in improved perplexity and log predictive scores compared to SGRLD.
  • Asymptotically Unbiased Sampling: Theoretical analysis proves that SCIR samples are asymptotically unbiased, a crucial property for reliable inference.

Limitations and Future Work

  • Non-Asymptotic Variance: While SCIR is asymptotically unbiased, its non-asymptotic variance can be higher than the exact CIR process. The authors suggest that techniques like control variates could be used to reduce this variance, especially since the mode of a gamma distribution (the stationary distribution of CIR) is known exactly.
  • Performance on Complex Models: For very complex Bayesian nonparametric models, scalable stochastic gradient methods (including SCIR) may still struggle to escape local modes compared to exact, non-scalable methods like Gibbs sampling. Improving the performance of SGMCMC for such models is identified as an important future research direction.
  • Extension to Other Constrained Spaces: The paper mentions that the SCIR approach can be extended to other constrained spaces, such as (0, ∞), and suggests exploring other diffusion processes with tractable transition densities for creating new discretization-free SGMCMC samplers.

Summary updated

Abstract

Stochastic gradient Markov chain Monte Carlo (SGMCMC) has become a popular method for scalable Bayesian inference. These methods are based on sampling a discrete-time approximation to a continuous time process, such as the Langevin diffusion. When applied to distributions defined on a constrained space the time-discretization error can dominate when we are near the boundary of the space. We demonstrate that because of this, current SGMCMC methods for the simplex struggle with sparse simplex spaces; when many of the components are close to zero. Unfortunately, many popular large-scale Bayesian models, such as network or topic models, require inference on sparse simplex spaces. To avoid the biases caused by this discretization error, we propose the stochastic Cox-Ingersoll-Ross process (SCIR), which removes all discretization error and we prove that samples from the SCIR process are asymptotically unbiased. We discuss how this idea can be extended to target other constrained spaces. Use of the SCIR process within a SGMCMC algorithm is shown to give substantially better performance for a topic model and a Dirichlet process mixture model than existing SGMCMC approaches.
BibTeX
@inproceedings{baker2018large,
  author = {Jack Baker and Paul Fearnhead and Emily B. Fox and Christopher Nemeth},
  title = {{Large-Scale Stochastic Sampling from the Probability Simplex}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
}
Figure