Abstract
Stochastic variational inference (SVI), the state-of-the-art algorithm for scaling variational inference to large-datasets, is inherently serial. Moreover, it requires the parameters to fit in the memory of a single processor; this is problematic when the number of parameters is in billions. In this paper, we propose extreme stochastic variational inference (ESVI), an asynchronous and lock-free algorithm to perform variational inference for mixture models on massive real world datasets. ESVI overcomes the limitations of SVI by requiring that each processor only access a subset of the data and a subset of the parameters, thus providing data and model parallelism simultaneously. We demonstrate the effectiveness of ESVI by running Latent Dirichlet Allocation (LDA) on UMBC-3B, a dataset that has a vocabulary of 3 million and a token size of 3 billion. In our experiments, we found that ESVI not only outperforms VI and SVI in wallclock-time, but also achieves a better quality solution. In addition, we propose a strategy to speed up computation and save memory when fitting large number of topics.
Introduction
In Bayesian modeling, Variational Inference (VI) is a fundamental technique for estimating hidden parameters. While effective, it has historically struggled with massive datasets. Stochastic Variational Inference (SVI) addressed the data bottleneck by processing mini-batches, yet it remains limited by its serial nature and the "Memory Wall"—the requirement that all model parameters reside in a single processor's memory. For large-scale topic models with millions of words ($D$) and thousands of topics ($K$), the $D \times K$ parameter matrix can exceed hundreds of gigabytes, making standard SVI impractical for "extreme" scale problems.
Methodology: Extreme Stochastic Variational Inference (ESVI)
ESVI introduces an asynchronous, lock-free architecture that achieves both data and model parallelism.
Simultaneous Data and Model Parallelism
Unlike previous methods that only partition data, ESVI partitions both data and parameters. Each processor manages a subset of the data and a subset of the global parameters. To ensure global model consistency, parameters move nomadically across the network between workers without requiring global locks.
Partial Local Updates
A key theoretical contribution is Lemma 1, which demonstrates that improving the model does not require updating all $K$ coordinates of a local variable simultaneously. Instead, updating a small subset $\mathcal{K} \subset \{1, \dots, K\}$ is sufficient. This allows for fine-grained parallelism and reduces the computational burden per iteration.
The TOPK Strategy
To further optimize memory for models with a massive number of topics, the authors developed ESVI-LDA-TOPK. This strategy exploits the sparsity of topic assignments: since most words belong to only a few topics, the algorithm only tracks the "Top K" most relevant assignments, significantly reducing memory overhead with negligible impact on accuracy.
Experimental Setup and Datasets
The performance of ESVI was evaluated across several real-world datasets:
- Standard Benchmarks: AP-DATA, NIPS, Enron, and NY Times.
- Large Scale: PubMed (8.2 million documents).
- Extreme Scale: UMBC-3B, featuring 40 million documents, a 3.4 million-word vocabulary, and over 3 billion tokens.
Key Results
- Superior Efficiency: ESVI consistently reached higher Evidence Lower Bound (ELBO) values faster than traditional VI and SVI in wall-clock time comparisons.
- Solution Quality: Beyond speed, ESVI often achieved better final solutions (higher ELBO and lower perplexity) than its predecessors.
- Unprecedented Scalability: ESVI successfully processed the UMBC-3B dataset using 32 nodes (512 cores). Standard SVI failed on this dataset due to memory constraints, while traditional VI was significantly slower.
- Memory Optimization: The Top-K strategy allowed fitting models that would typically require 4x more memory, maintaining high performance even when retaining only 25% of the topic coordinates.
Discussion and Future Work
ESVI's asynchronous nature introduces "stale" parameters, but experiments show mixture models are robust to this. While current work focuses on GMMs and LDA, the ESVI framework is extensible to other latent variable models like Stochastic Block Models and Bayesian Matrix Factorization. Future research may also explore automated hyperparameter tuning for the coordinate update size ($K'$) and the Top-K cutoff ($C$).
Summary updated