Large-Scale Stochastic Sampling from the Probability Simplex

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

Standard stochastic sampling methods often fail when parameters are constrained to a probability simplex, especially in "sparse" settings where many components are near zero. This paper introduces the Stochastic Cox-Ingersoll-Ross (SCIR) algorithm, a novel Markov Chain Monte Carlo (MCMC) approach that eliminates discretization error entirely, providing an asymptotically unbiased way to sample from complex, large-scale models like Latent Dirichlet Allocation (LDA) and Dirichlet processes.

The Challenge of the Probability Simplex

In Bayesian machine learning, parameters often represent probabilities, meaning they must be non-negative and sum to one—a space known as the probability simplex. Common examples include topic distributions in text models or link probabilities in social networks.

To handle massive datasets, researchers typically rely on Stochastic Gradient MCMC (SGMCMC). These methods approximate continuous-time physical processes (like Langevin diffusion) using discrete time steps. However, this discretization creates a significant problem: when a parameter gets close to the boundary of the simplex (near zero), the approximation error explodes. This leads to invalid proposals or massive biases. While previous methods like Stochastic Gradient Riemannian Langevin Dynamics (SGRLD) attempted to fix this, they still suffer from discretization bias. This is particularly damaging in "sparse" models where most probabilities are very small, as the relative error becomes infinite as a parameter approaches zero.

The SCIR Algorithm

The authors propose a fundamental shift in the underlying "physics" of the sampler. Instead of using Langevin diffusion, they utilize the Cox-Ingersoll-Ross (CIR) process, a model commonly used in mathematical finance to describe interest rates.

  • Discretization-Free Sampling: The key advantage of the CIR process is that its transition density is known exactly (following a non-central chi-squared distribution). This allows the process to be simulated perfectly from one time step to the next without the standard "Euler-Maruyama" approximation used in SGMCMC, effectively removing the $O(h)$ bias (where $h$ is the step size).
  • Simplex Mapping: The method samples independent Gamma-distributed variables via the SCIR process and normalizes them to project the results onto the probability simplex.
  • Stochastic Adaptation: To ensure scalability, full-data gradients are replaced with minibatch-based unbiased estimates. Because the underlying process has no discretization error, the algorithm is asymptotically unbiased—a property standard SGLD lacks for fixed step sizes.

Experimental Validation and Key Results

The authors evaluated SCIR against the state-of-the-art SGRLD across synthetic data, Wikipedia documents (for LDA), and anonymous Microsoft user data (for a Bayesian Nonparametric Mixture Model). Notably, this represents one of the first successful applications of SGMCMC to Bayesian Nonparametric models, which are notoriously difficult to scale.

Accuracy on Synthetic Data

In synthetic tests focusing on sparse and dense Dirichlet posteriors, SCIR showed significantly lower Kolmogorov-Smirnov (KS) distance to the true posterior than SGRLD. This highlights SCIR's superior boundary behavior in sparse settings.

KS Distance Comparison

LDA Performance

On the large-scale Wikipedia dataset, SCIR achieved lower perplexity (better predictive power) than SGRLD. While both methods converged at similar rates initially, SCIR continued to improve while SGRLD plateaued due to its inherent bias.

LDA Performance: Perplexity and Test Log Predictive

Cluster Stability in Nonparametrics

In the Microsoft user dataset, SGRLD tended to propose far more clusters than necessary because its upward boundary bias mimicked a higher concentration parameter. In contrast, SCIR converged to a more parsimonious and accurate model with lower variance.

Limitations and Future Work

While SCIR successfully removes discretization error, it still encounters variance introduced by using minibatches instead of the full dataset. The authors note that the variance of SCIR is somewhat inflated compared to the exact CIR process. To address this, they suggest that control variates (a variance reduction technique) could be particularly effective for SCIR, as the mode of the target Gamma distribution is known exactly. Finally, like most SGMCMC methods, performance depends on choosing an appropriate step size $h$, though SCIR is more robust since $h$ only affects the resampling frequency rather than introducing bias.

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