Embarrassingly Parallel Inference for Gaussian Processes

Michael Minyi Zhang, Sinead A. Williamson

TL;DR

This paper introduces an "Embarrassingly Parallel Inference for Gaussian Processes" (IS-MOE) method that tackles the computational bottleneck of training Gaussian Processes (GPs) on large datasets. By using a mixture-of-experts approach with importance sampling, IS-MOE achieves scalable and parallelizable inference, offering comparable performance to full GPs at a significantly reduced computational cost.

What Problem Does This Paper Address?

Training Gaussian Processes (GPs) is notoriously computationally expensive, with inference typically involving an O(N³) matrix inversion, where N is the number of data points. This cubic scaling makes GPs impractical for "big data" scenarios. While existing methods like sparse GPs and local GPs offer some improvements, they often suffer from limitations such as missing long-range correlations, inability to model non-stationarity, or are not easily parallelizable. The authors aim to bridge this gap by developing a method that is both flexible, scalable, and amenable to distributed computing.

Methods

The core of the proposed method is the Importance Sampled Mixture of Experts (IS-MOE). Instead of inverting a single large N×N covariance matrix, IS-MOE models the function as a mixture of K independent Gaussian processes. The key innovations are:

  • Mixture-of-Experts Structure: The input space is partitioned, and each partition is modeled by a separate GP. This allows for capturing non-stationarity and reduces the size of the matrices to be inverted (to K smaller, block-diagonal matrices).
  • Importance Sampling for Partitions: Instead of relying on computationally expensive MCMC for inferring the distribution over partitions, IS-MOE uses importance sampling. This allows for parallel sampling of partitions and their associated GPs.
  • Parallelization: The "embarrassingly parallel" nature comes from the fact that each importance sample (and its associated GP fitting) can be computed independently. Global communication is only needed at the end for normalizing weights and combining predictions.
  • Minibatching (Stochastic Approximation): To further reduce memory and computational constraints, the authors propose using minibatches of data to approximate the full posterior. This involves raising the likelihood contribution to the (N/B)-th power, where B is the minibatch size.

Datasets

The paper evaluates its method on several synthetic datasets and one real-world dataset:

  • Synthetic Datasets:
    • Stationary data with long-range correlations.
  • Stationary data with short-range correlations.
  • Non-stationary data combining fast and slow moving periodic functions.
  • A large-scale synthetic dataset with 1000 observations and 100 covariates.
  • A synthetic dataset with 10,000 training observations, 2,000 test observations, and 100 covariates, sampled from a GMM.
  • Real-world Datasets:
    • AIRS dataset: A large empirical dataset of 209,631 mid-tropospheric CO2 measurements.
  • UCI Repository Datasets: For classification tasks, the Pima Indians diabetes dataset, the Parkinsons dataset, and the Wisconsin diagnostic breast cancer (WDBC) dataset were used.
  • Higgs-Boson dataset: A large-scale binary classification dataset with one million observations and 28 features.

Key Insights and Ideas

  • Parallelism is Key for Scalability: The core insight is that by decomposing the problem into independent subproblems (partitions) and using importance sampling, the inference can be made "embarrassingly parallel," drastically reducing wall-clock time on multi-core systems.
  • Mixture-of-Experts for Non-stationarity: The mixture-of-experts framework naturally handles non-stationary functions by allowing different GPs to model different regions of the input space, a capability often lacking in standard sparse GP methods.
  • Importance Sampling as a Scalable Alternative to MCMC: For inferring partitions, importance sampling offers a computationally cheaper and more parallelizable alternative to MCMC, which is often slow to mix and difficult to distribute.
  • Trade-offs in Model Complexity and Performance: The paper demonstrates that parameters like the number of experts (K), importance samples (J), and minibatch size (B) offer tunable knobs to balance computational cost and predictive accuracy.

Key Results

  • Computational Efficiency: IS-MOE achieves significant speedups compared to full GPs, especially on large datasets. For instance, on the AIRS dataset, IS-MOE with J=100 and B=1000 was significantly faster than SVI at comparable computational complexity.
  • Performance: IS-MOE generally performs comparably to full GPs and often outperforms other scalable methods like RBCM and SVI, particularly in capturing predictive variance and handling non-stationary data.
  • Handling Non-stationarity: On synthetic non-stationary data, IS-MOE demonstrated superior performance compared to methods using stationary kernels.
  • Robustness: The method shows good performance across various synthetic data regimes and real-world datasets, including classification tasks.
  • Minibatching Effectiveness: The stochastic approximation via minibatches significantly reduces memory and computational requirements without a dramatic drop in quality.

Limitations and Future Work

  • Proposal Distribution Choice: The performance of importance sampling is sensitive to the choice of the proposal distribution. The paper notes that it's not always obvious how to select the optimal distribution, and further research into improving proposal distributions is suggested.
  • Theoretical Behavior of Proposal Distributions: The authors express interest in investigating the theoretical behavior of proposal distributions for more sophisticated inference settings.
  • Beyond Regression: While the paper demonstrates applications beyond regression (e.g., classification), exploring its use in more complex models like deep Gaussian processes and non-Gaussian likelihoods is a future direction.
  • GPU Acceleration: The authors suggest exploring GPU-based computation for further speed-ups.
  • Particle Filters: For more sophisticated inference, the paper mentions the potential need for particle filters or other sequential Monte Carlo techniques.

Summary updated

Abstract

Training Gaussian process-based models typically involves an $ O(N^3)$ computational bottleneck due to inverting the covariance matrix. Popular methods for overcoming this matrix inversion problem cannot adequately model all types of latent functions, and are often not parallelizable. However, judicious choice of model structure can ameliorate this problem. A mixture-of-experts model that uses a mixture of $K$ Gaussian processes offers modeling flexibility and opportunities for scalable inference. Our embarrassingly parallel algorithm combines low-dimensional matrix inversions with importance sampling to yield a flexible, scalable mixture-of-experts model that offers comparable performance to Gaussian process regression at a much lower computational cost.
BibTeX
@article{zhang2019embarrassingly,
  author = {Michael Minyi Zhang and Sinead A. Williamson},
  title = {{Embarrassingly Parallel Inference for Gaussian Processes}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
}
Figure