Distributed Variational Inference in Sparse Gaussian Process Regression and Latent Variable Models

Yarin Gal, Mark van der Wilk, Carl E. Rasmussen

TL;DR

This paper introduces a novel distributed inference algorithm that allows Gaussian Processes (GPs)—traditionally limited by their high computational cost—to scale to datasets with millions of records. By re-parameterizing the variational lower bound to decouple data points, the authors enable a Map-Reduce implementation that achieves near-ideal parallel speedup while maintaining the rigorous uncertainty estimates GPs are known for.

What Problem Does This Paper Address?

Gaussian Processes are "gold standard" models for regression and dimensionality reduction because they provide principled uncertainty estimates and are robust to overfitting. However, they suffer from a "big data" problem: standard GP inference scales at $O(n^3)$, where $n$ is the number of data points. Even "sparse" approximations, which reduce this to $O(nm^2)$ (where $m$ is a small set of "inducing points"), struggle when $n$ reaches the millions.

Previous attempts to scale GPs, like Stochastic Variational Inference (SVI), often require manual tuning of learning rates and result in looser mathematical bounds. The authors aim to create a distributed system that scales linearly with computational resources without sacrificing the tightness of the original variational bounds.

Methods

The core innovation is a re-parametrization of the Evidence Lower Bound (ELBO).

  1. Decoupling: The authors exploit the fact that, conditioned on a set of inducing points ($Z$), the individual data points become independent.
  2. Distributed Summation: They show that the global objective function can be rewritten as a sum of independent terms ($A, B, C, D$, and a KL divergence term). Each term can be computed locally on a subset of the data.
  3. Map-Reduce Framework:
    • Map Step: Worker nodes receive global parameters (like kernel settings and inducing inputs) and compute partial sums based on their local slice of the data.
  4. Reduce Step: A central node aggregates these partial sums to update the global parameters.
  5. Unification: This approach works for both Sparse GP Regression and the Gaussian Process Latent Variable Model (GPLVM), treating the latter as a case where inputs are latent variables to be optimized in parallel.

Datasets

The authors evaluated their method on three primary benchmarks:

  • Synthetic Data: A 100K-point dataset generated from a 1D latent space to test scaling properties.
  • US Flight Dataset (2008): A massive real-world regression task. They tested subsets (7K, 70K, 700K) and a full 2-million-record version to predict flight delays.
  • MNIST: The classic handwritten digit dataset (60K images). This was used to test the GPLVM for dimensionality reduction and classification.

Key Insights and Ideas

  • Near-Ideal Scaling: The algorithm demonstrates "strong scaling"—doubling the number of CPU cores nearly halves the execution time. Running time per iteration vs available cores
  • Constant Time with Growth: In "weak scaling" tests (where data and cores increase proportionally), the time per iteration remains almost constant. This suggests that with enough hardware, GPs can handle virtually any dataset size. Time per iteration when scaling resources and data together
  • Load Balancing: A critical hurdle in distributed systems is the "straggler" problem. The authors found that their method distributes work extremely evenly, with only a ~1.9% difference in execution time between the fastest and slowest nodes.
  • More Data = Better GPs: A common myth is that GPs are only for small data. This work shows that GP performance continues to improve as you move from 10K to 60K points (on MNIST) and up to 2M points (on Flights), outperforming common "big data" baselines like Random Forests.
Figure 1: Running time per iteration for 100K points synthetic dataset, as a function of avail- able cores on log-scale.
Figure 2: Time per iteration when scaling the computational resources proportionally to dataset size up to 50K points. Also shown standard inference (GPy) for comparison.

Key Results

  • Flight Delay Prediction: On the 2M record dataset, the Distributed GP achieved an RMSE of 35.31, significantly better than Linear Regression (37.65) or Random Forests (37.33).
  • MNIST Classification: By training one GP model per digit, the authors achieved a classification error of 5.95% using the full 60K dataset, down from 8.98% when using only 10K points.
  • Efficiency: Training on 2 million flight records on a 64-core machine took approximately 13.8 minutes per iteration.
  • Reconstruction: The GPLVM successfully reconstructed digits even with significant missing data. MNIST digit reconstruction using GPLVM
MNIST digit reconstruction using GPLVM

Limitations and Future Work

  • Optimization Sensitivity: The authors noted that Scaled Conjugate Gradient (SCG) optimization sometimes converged to poor local optima on large datasets because the likelihood surface becomes very "sharp." L-BFGS proved more robust but requires careful initialization.
  • Global Bottleneck: While the data-heavy parts are distributed, the central node still performs an $O(m^3)$ matrix inversion (where $m$ is the number of inducing points). While $m$ is usually small (e.g., 100), this remains a theoretical limit to scaling the number of inducing points.
  • Communication Overhead: Although low, the Map-Reduce steps still require synchronization, which could become a factor in extremely high-latency network environments.

Summary updated

Abstract

Gaussian processes (GPs) are a powerful tool for probabilistic inference over functions. They have been applied to both regression and non-linear dimensionality reduction, and offer desirable properties such as uncertainty estimates, robustness to over-fitting, and principled ways for tuning hyper-parameters. However the scalability of these models to big datasets remains an active topic of research. We introduce a novel re-parametrisation of variational inference for sparse GP regression and latent variable models that allows for an efficient distributed algorithm. This is done by exploiting the decoupling of the data given the inducing points to re-formulate the evidence lower bound in a Map-Reduce setting. We show that the inference scales well with data and computational resources, while preserving a balanced distribution of the load among the nodes. We further demonstrate the utility in scaling Gaussian processes to big data. We show that GP performance improves with increasing amounts of data in regression (on flight data with 2 million records) and latent variable modelling (on MNIST). The results show that GPs perform better than many common models often used for big data.
BibTeX
@inproceedings{gal2014distributed,
  author = {Yarin Gal and Mark van der Wilk and Carl E. Rasmussen},
  title = {{Distributed Variational Inference in Sparse Gaussian Process Regression and Latent Variable Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}

Loading related content...

Figure