Large-Scale Stochastic Sampling from the Probability Simplex

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

Abstract

Bayesian inference on constrained spaces, particularly the probability simplex, is a cornerstone of modern machine learning models like Latent Dirichlet Allocation (LDA) and Dirichlet Process (DP) mixtures. However, standard Stochastic Gradient Markov Chain Monte Carlo (SGMCMC) methods often fail in these settings because discretization errors accumulate near the boundaries, leading to significant asymptotic bias. This paper introduces the Stochastic Cox-Ingersoll-Ross (SCIR) algorithm, a discretization-free approach that leverages the known transition density of the CIR process. SCIR remains asymptotically unbiased and demonstrates superior performance on both synthetic benchmarks and large-scale real-world datasets.

Introduction

In the era of big data, SGMCMC has become a vital tool for scalable Bayesian inference. Despite its success, applying SGMCMC to the probability simplex—where parameters must be non-negative and sum to one—remains challenging. The primary obstacle is discretization error. Traditional methods like Stochastic Gradient Langevin Dynamics (SGLD) approximate continuous paths using discrete steps. When parameters approach the boundary (sparsity), these discrete steps can lead to "illegal" negative values or massive relative errors, forcing the sampler away from the true posterior.

The SCIR Methodology

To address these limitations, the authors propose the Stochastic Cox-Ingersoll-Ross (SCIR) process. Unlike Langevin-based methods that approximate a path, SCIR utilizes a process with a known exact solution.

Discretization-Free Sampling

The Cox-Ingersoll-Ross process, originally from mathematical finance, possesses a transition density that follows a non-central chi-squared distribution. By using this known density, the SCIR algorithm can "jump" between time steps without the approximation errors inherent in the Euler-Maruyama discretization. This makes the method inherently robust to boundary conditions.

Simplex Transformation and Stochastic Gradients

To sample from a Dirichlet distribution on the simplex, the algorithm samples independent Gamma random variables via SCIR and subsequently normalizes them. The method is adapted for large-scale data by replacing full-data parameters with unbiased stochastic gradient estimates from minibatches. Crucially, the paper provides a formal proof that SCIR is asymptotically unbiased, ensuring convergence to the true posterior mean.

Experimental Evaluation

Synthetic Benchmarks

The authors first evaluated SCIR against Stochastic Gradient Riemannian Langevin Dynamics (SGRLD) using synthetic Dirichlet distributions. They tested both dense and sparse settings to observe behavior near the simplex boundaries.

Figure 4: Kolmogorov-Smirnov (KS) distance between the true posterior and samples from SCIR, SGRLD, and an exact sampler across different minibatch sizes. SCIR consistently maintains lower error than SGRLD, especially as minibatch size decreases.

As shown in Figure 4, SCIR significantly reduces the Kolmogorov-Smirnov (KS) distance compared to SGRLD. While SGRLD's bias remains high even with larger minibatches, SCIR's performance approaches that of the exact sampler, demonstrating its robustness to the discretization issues that plague previous methods.

Real-World Applications: LDA and DP Mixtures

The algorithm was further tested on two large-scale tasks:

  1. Topic Modeling (LDA): Using a Wikipedia dataset with ~8,000 words.
  2. Nonparametric Mixture Models: Using a Microsoft web activity dataset (30,000 users) to test a Dirichlet Process mixture.
Figure 5: Performance on real-world datasets. (a) Perplexity on the Wikipedia LDA task; SCIR achieves lower perplexity than SGRLD. (b) Test log-predictive scores for the DP mixture model on the Microsoft user dataset; SCIR provides higher predictive accuracy and lower variance.

In the LDA task (Figure 5a), SCIR achieved lower perplexity than SGRLD. While both methods performed similarly initially, SGRLD eventually plateaued due to its inherent bias, whereas SCIR continued to improve. In the nonparametric setting (Figure 5b), SCIR provided better log-predictive scores. The authors noted that SGRLD's bias often led to an overestimation of the number of clusters, a problem SCIR avoids through its unbiased nature.

Conclusion

The Stochastic Cox-Ingersoll-Ross (SCIR) algorithm represents a significant step forward for SGMCMC on constrained spaces. By eliminating discretization error through the use of exact transition densities, SCIR provides a robust, asymptotically unbiased framework for sampling from the probability simplex. Its superior performance in sparse settings makes it particularly well-suited for modern, high-dimensional Bayesian models. Future work may involve integrating variance reduction techniques like control variates to further enhance the efficiency of the sampler.

Summary updated

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