d-VMP: Distributed Variational Message Passing

Andrés R. Masegosa, Ana M. Martínez, Helge Langseth, Thomas D. Nielsen, Antonio Salmerón, Darío Ramos-López, Anders L. MadsenProbabilistic Graphical Models 2016 · OpenReview

Introduction

Scaling Bayesian inference to "Big Data" regimes remains a significant challenge in machine learning. While Stochastic Variational Inference (SVI) has become the standard approach for large-scale probabilistic modeling, it often falters when applied to complex, real-world datasets. SVI relies on mini-batching to update global parameters, but this approach introduces three critical vulnerabilities:

  1. Sensitivity to Rare Events: In imbalanced datasets (e.g., financial fraud or loan defaults), small mini-batches frequently miss critical but rare data points, leading to poor model generalization.
  2. Data Sparsity and Noise: Real-world data is often "spiky," characterized by heavy tails, zero-inflation, and high rates of missing values. The noisy gradient estimates inherent in SVI struggle to achieve convergence under these conditions.
  3. Communication Bottlenecks: In distributed environments, the constant exchange of small mini-batches between worker nodes and a central master creates significant network overhead, limiting the benefits of horizontal scaling.

To address these issues, we present d-VMP (Distributed Variational Message Passing), a framework that reframes traditional message passing as a robust optimization algorithm capable of scaling to models with over a billion nodes.

The d-VMP Framework

The core theoretical contribution of this work is the proof that Variational Message Passing (VMP) is mathematically equivalent to a projected natural gradient ascent algorithm with a step size of one. This insight bridges the gap between local message-passing heuristics and classical optimization theory.

By leveraging the geometry of the probability distribution through natural gradients, d-VMP achieves more reliable convergence than standard gradient methods. Furthermore, this formulation allows for the parallelization of updates: instead of the sequential variable updates required by standard VMP, d-VMP can update entire "blocks" of independent parameters simultaneously across a distributed cluster.

Distributed architecture of d-VMP showing Master-Slave coordination for global and local parameter updates.

Distributed Implementation

The d-VMP algorithm is implemented using a Master-Slave architecture within the Apache Flink big data framework. This setup allows for efficient Map-Reduce style processing:

  • Slave Nodes: Process local data and latent variables in parallel, computing local messages based on the current global model state.
  • Master Node: Aggregates these messages to perform a global update of the model parameters.
Pseudocode for the Distributed Variational Message Passing (d-VMP) algorithm.

This architecture leverages Flink's sophisticated memory management to handle models with millions of latent variables, preventing the out-of-memory errors that often plague large-scale Bayesian implementations.

Experimental Evaluation

We evaluated d-VMP against SVI using two primary datasets: a real-world Spanish Financial Dataset (55,000 clients, 33 features) and a Massive Synthetic Dataset designed to test extreme scalability. The synthetic model, when unrolled, represented over one billion nodes, 75% of which were latent variables.

Key Results

  • Superior Accuracy: d-VMP consistently achieved a higher Evidence Lower Bound (ELBO) compared to SVI across various learning rates and batch sizes. This indicates a higher quality posterior approximation.
  • Robustness to Heavy Tails: Qualitative analysis of the financial data showed that d-VMP accurately captured the heavy tails of the distribution. In contrast, SVI tended to underestimate variance, missing the extreme events that are often the most critical in financial modeling.
  • Linear Scalability: The algorithm demonstrated near-linear scalability on a cluster with 128 processing units. Doubling computational resources resulted in a 1.7x speedup. For the billion-node model, a task that required 25 hours on 2 nodes was completed in less than 3.5 hours on 16 nodes.

Conclusion and Future Work

d-VMP provides a theoretically grounded and computationally efficient alternative to SVI for large-scale Bayesian learning. By processing the full dataset in a distributed manner rather than relying on noisy subsampling, it ensures that rare but critical data points are preserved in the model fit.

Current limitations include a restriction to conjugate exponential models, excluding non-conjugate architectures like Bayesian Neural Networks. Future research will focus on adapting d-VMP for streaming data to handle concept drift and exploring its performance on high-dimensional text corpora using Latent Dirichlet Allocation (LDA).

Summary updated

BibTeX
@inproceedings{masegosa2016d,
  author = {Andrés R. Masegosa and Ana M. Martínez and Helge Langseth and Thomas D. Nielsen and Antonio Salmerón and Darío Ramos-López and Anders L. Madsen},
  title = {{d-VMP: Distributed Variational Message Passing}},
  booktitle = {Probabilistic Graphical Models},
  year = {2016},
  url = {https://openreview.net/forum?id=06ecrjEM5t},
}
Figure