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.
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.
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