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

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

Gaussian Processes (GPs) are often considered the "Swiss Army knife" of probabilistic modeling. They provide excellent uncertainty estimates, resist overfitting, and offer principled ways to tune hyperparameters. However, they have historically struggled with "Big Data" due to their $O(n^3)$ computational complexity. While "sparse" approximations reduced this to $O(nm^2)$ by using $m$ inducing points, even that becomes a bottleneck when the number of data points ($n$) reaches into the millions.

In their paper Distributed Variational Inference in Sparse Gaussian Process Regression and Latent Variable Models, Gal, van der Wilk, and Rasmussen introduce a method to break this $O(n)$ bottleneck. By distributing the workload across a cluster, they allow GPs to handle datasets that were previously out of reach.

The Scalability Challenge

The central hurdle for GPs is scalability. Standard GPs require inverting an $n \times n$ covariance matrix, which is computationally infeasible for massive datasets. Sparse GPs use a smaller set of $m$ "inducing points" to summarize the data, bringing complexity down to $O(nm^2)$.

However, processing millions of records remains a struggle for a single machine. Previous attempts to solve this relied on Stochastic Variational Inference (SVI), which processes data in mini-batches. While SVI scales well, it introduces noisy gradients, requires careful tuning of learning rates, and uses a looser variational bound that can lead to sub-optimal models. The authors sought a method that scales linearly with the number of computational nodes without sacrificing the accuracy and stability of the original sparse GP framework.

A Distributed Map-Reduce Framework

The key innovation in this paper is a novel re-parametrization of the Evidence Lower Bound (ELBO).

  1. Decoupling the Data: The authors demonstrate that by conditioning the model on the inducing points, the likelihood of the individual data points decouples. This means the complex global objective function can be algebraically rearranged into a sum of independent terms, where each term only depends on a specific subset of the data.
  2. Map-Reduce Architecture: Because the objective is a sum of independent terms, it is perfectly suited for a Map-Reduce setup:
  3. Map Step: Each worker node takes a subset of the data and computes "partial sums" (specific matrices required for the GP).
  4. Reduce Step: A central node collects these partial sums to compute the global log-likelihood and its gradients.
  5. Unified Approach: This derivation works for both supervised Regression and unsupervised Latent Variable Models (GPLVMs). In the GPLVM case, local latent variables can also be optimized in parallel on the worker nodes.

Unlike SVI, this distributed approach uses the optimal variational distribution for the inducing targets, leading to a tighter bound, more stable optimization, and nearly perfect load balancing across the cluster.

Key Results and Scaling Performance

The authors evaluated their distributed algorithm on massive datasets, including a 2008 US Flight dataset (up to 2 million records) and the classic MNIST dataset (60,000 images).

Strong and Weak Scaling

The distributed framework exhibits excellent scaling properties, proving that the theoretical decoupling translates to real-world performance.

Strong scaling: computation time per iteration decreases linearly as the number of cores increases.
  • Strong Scaling: When doubling the number of CPU cores (e.g., from 5 to 10), the computation time per iteration dropped by a factor of 1.93x—achieving nearly ideal linear speedup.
Weak scaling: execution time remains constant as dataset size and available cores increase proportionally, unlike standard GPy.
  • Weak Scaling: When increasing the dataset size and the number of cores proportionally (scaling up to 30x), the running time remained almost constant, showing only a nominal 4.3% increase. This is a stark contrast to standard single-machine implementations (like GPy), which fail to scale.

Predictive Performance

The results confirm a fundamental machine learning intuition: GP performance improves as you add more data.

  • Flight Data: On the 2 million record flight dataset, the Distributed GP achieved a Root Mean Square Error (RMSE) of 35.31, significantly outperforming baselines like Linear Regression (37.65) and Random Forests (37.33).
  • MNIST: Using the full dataset for a GPLVM improved classification error from 8.98% (when restricted to 10k points) to 5.95% (using all 60k points).

Limitations and Future Work

While this approach successfully distributes the $O(n)$ complexity, it does have limitations:

  • The Inducing Point Bottleneck: The central node still performs an $O(m^3)$ operation to invert the matrix of inducing points. If a highly complex function requires a massive number of inducing points ($m$), the central node could become a bottleneck.
  • Non-Stationarity: The authors noted that massive datasets (like the 2M flight records) often exhibit non-stationarity, which challenges standard GPs that assume a consistent underlying function across the entire space.
  • Communication Overhead: The algorithm requires two Map-Reduce synchronization steps per iteration. In environments with extremely high network latency, this communication overhead could impact overall performance.

By elegantly rearranging the math behind sparse GPs, this paper provides a robust, scalable path forward for probabilistic modeling in the age of Big Data.

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},
}
Figure