Extreme Stochastic Variational Inference: Distributed Inference for Large Scale Mixture Models

Jiong Zhang, Parameswaran Raman, Shihao Ji, Hsiang-Fu Yu, S. V. N. Vishwanathan, Inderjit S. DhillonAISTATS 2019 · OpenReview

Abstract

Mixture of exponential family models are fundamental tools in modern statistics, yet scaling them to massive datasets remains a significant challenge. Traditional Stochastic Variational Inference (SVI) is limited by serial processing and memory constraints of single machines. We present Extreme Stochastic Variational Inference (ESVI), a distributed, asynchronous algorithm designed to scale mixture models to billions of parameters. ESVI achieves simultaneous data and model parallelism through partial parameter updates and a nomadic parameter-passing scheme, bypassing the synchronization bottlenecks of conventional distributed systems.

Introduction

Latent Dirichlet Allocation (LDA) and Gaussian Mixture Models (GMM) are essential for discovering structure in large datasets. However, as datasets grow to millions of documents and thousands of topics, the resulting parameter matrices often exceed the memory capacity of individual processors. The current state-of-the-art, Stochastic Variational Inference (SVI), typically requires the entire global model to reside in a single machine's RAM. Furthermore, existing distributed implementations often suffer from "bulk synchronization" overhead, where the system's speed is limited by the slowest worker node.

The ESVI Framework

ESVI addresses these limitations through three core innovations that enable efficient scaling without sacrificing statistical accuracy.

Partial Coordinate Updates

Unlike standard variational methods that update all $K$ mixture components for every data point, ESVI utilizes a partial update strategy. The authors prove mathematically that updating only a small subset of coordinates is sufficient to guarantee an improvement in the Evidence Lower Bound (ELBO). This significantly reduces the computational load per iteration.

Visualization of the partial update mechanism for parameters $\tilde{\pi}$, $\tilde{\theta}$, and $\tilde{z}$, where only specific subsets are modified in each step.

Nomadic Parameter Passing

To achieve true distributed scaling, ESVI employs a lock-free, asynchronous communication protocol. Global parameters are partitioned across a cluster. Processors update their local data using a subset of parameters and then "push" those parameters to other nodes in a nomadic fashion. This ensures that all data points eventually interact with all model parameters, facilitating global mixing without the need for a centralized parameter server or global synchronization barriers.

ESVI-TOPK for Memory Efficiency

To further optimize memory usage, the ESVI-TOPK variant tracks only the top-$k$ most significant topics for each document. By discarding the "long tail" of negligible associations, the algorithm maintains high accuracy while drastically reducing the memory footprint.

Experimental Results

The performance of ESVI was evaluated on datasets ranging from standard benchmarks (NIPS, Enron) to the massive UMBC-3B corpus, which contains over 40 million documents and 3 billion tokens.

Convergence and Speed

In wall-clock time comparisons, ESVI consistently outperformed both standard Variational Inference (VI) and SVI. On the AP-DATA dataset, ESVI reached a superior ELBO solution in a fraction of the time required by its predecessors.

Comparison of ELBO convergence over time for ESVI, SVI, and VI on the AP-DATA dataset, demonstrating ESVI's superior speed and final objective value.

Extreme Scalability

ESVI successfully processed the UMBC-3B dataset using a 512-core cluster. This scale is inaccessible to standard SVI, as the global parameter matrix cannot fit into the memory of a single node. Notably, ESVI achieved these results without the need for tedious learning rate tuning, as it utilizes closed-form coordinate ascent updates.

Discussion

ESVI represents a significant step forward in scaling mixture models. By combining data and model parallelism with asynchronous updates, it enables the analysis of datasets that were previously computationally prohibitive. While currently optimized for conditionally conjugate models, future work may extend this nomadic, partial-update framework to non-conjugate models via Black Box Variational Inference. Additionally, exploring the algorithm's robustness to high-latency network environments remains a key area for further investigation.

Summary updated

Abstract

Mixture of exponential family models are among the most fundamental and widely used statistical models. Stochastic variational inference (SVI), the state-of-the-art algorithm for parameter estimati...
BibTeX
@inproceedings{zhang2019extreme,
  author = {Jiong Zhang and Parameswaran Raman and Shihao Ji and Hsiang-Fu Yu and S. V. N. Vishwanathan and Inderjit S. Dhillon},
  title = {{Extreme Stochastic Variational Inference: Distributed Inference for Large Scale Mixture Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=tOUJT843QP},
}
Figure