Exact Gaussian Processes for Massive Datasets via Non-Stationary Sparsity-Discovering Kernels

Marcus Michael Noack, Harinarayan Krishnan, Mark D. Risser, Kristofer G. ReyesarXiv 2022 · OpenReview

TL;DR

This paper introduces a novel approach to scaling exact Gaussian Processes (GPs) to massive datasets by developing "sparsity-discovering" kernels. Instead of forcing sparsity through approximations, their method allows the kernel itself to learn and encode zero covariances, enabling exact GPs to handle datasets with millions of data points.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful tools for function approximation and uncertainty quantification in science and engineering. However, their computational complexity, scaling as $O(N^3)$ for computation and $O(N^2)$ for storage, severely limits their application to small datasets. Existing methods rely on approximations, such as using subsets of data or inducing points, which can introduce inaccuracies and restrict kernel flexibility. This paper tackles the challenge of performing exact GP inference on datasets that are too large for traditional methods, aiming to retain the benefits of GPs without sacrificing accuracy or flexibility.

Methods

The core innovation lies in the development of non-stationary, ultra-flexible, and compactly-supported kernel functions. These kernels are designed to:

  • Discover Sparsity: Unlike traditional kernels that assume correlations, these kernels can learn and explicitly represent zero covariances between data points. This is achieved through flexible parameterizations that can effectively "turn off" correlations.
  • Compact Support: This ensures that the kernel's influence is localized, which is crucial for identifying zero covariances.
  • Non-Stationarity: This allows the kernel to adapt its behavior across the input space, enabling it to learn complex, distance-unrelated dependencies.

The paper proposes a three-pronged approach:

  1. Sparsity-Discovering Kernels: The primary building block is a kernel that can learn and encode zero covariances. The paper explores several forms, including those based on sums of bump functions.
  2. High-Performance Computing (HPC): To handle the computation of the covariance matrix for large datasets, a distributed computing strategy is employed. This involves computing dense sub-matrices in parallel across multiple workers (CPUs/GPUs) and assembling them into a sparse master covariance matrix on a host machine. This approach mitigates RAM limitations.
  3. Augmented and Constrained Optimization: To encourage sparse solutions, the optimization process is either constrained to prefer sparsity or augmented with a sparsity term. This ensures that even if natural sparsity isn't perfect, the optimization leans towards sparser solutions.

Datasets

The paper demonstrates its methodology on a climate dataset:

  • Daily Maximum Temperatures: Data from circa 7500 gauge-based weather stations across the continental United States, spanning from 1990 to 2019. For their experiments, they used a randomly extracted subset of 5,165,718 data points. This dataset is publicly available.

Key Insights and Ideas

  • Sparsity is Natural, Not Induced: The fundamental idea is that for many real-world problems, the underlying covariance structure is inherently sparse. The paper argues that common kernels fail to discover this natural sparsity, whereas their proposed kernels are designed to do so.
  • Kernel Design is Key: The flexibility and structure of the kernel function are paramount to enabling exact GPs on large datasets. By designing kernels that can represent zero covariances, the computational bottleneck of dense matrices can be overcome.
  • Distributed Computing for Covariance: The paper shows that by breaking down the covariance matrix computation into manageable, sparse sub-matrices that can be processed in parallel, the $O(N^2)$ storage and $O(N^3)$ computation can be distributed effectively.
  • Exactness Preserved: The goal is not to approximate the GP but to perform exact inference. The sparsity discovered by the kernel allows for efficient computation of the exact covariance matrix.

Key Results

  • Scalability to Millions of Data Points: The paper demonstrates the ability to train exact GPs on datasets exceeding 5 million data points. They express confidence that their method can scale to 100 million data points.
  • Significant Sparsity Achieved: In their climate example, the resulting sparse covariance matrix had only 1.5% of the non-zero entries of a full dense matrix.
  • Efficient Computation: The distributed covariance computation exhibits strong and weak scaling, with theoretical predictions aligning with measured execution times. For a dataset of 200,000 points, computation time scales favorably with the number of workers.
  • Climate Example: A proof-of-concept on a large climate dataset showed a reasonable marginal log-likelihood convergence within 24 hours on 256 GPUs, demonstrating the feasibility of the approach.

Limitations and Future Work

  • Kernel Simplicity: The sparsity-discovering kernels used in the examples were relatively simple. Future work will explore more flexible bump-function-based kernels and their hyperparameter optimization.
  • Optimization Cost: More flexible kernels lead to more hyperparameters, potentially increasing optimization complexity and the risk of ill-posed problems.
  • MCMC Training: The current training method uses Markov Chain Monte Carlo (MCMC). The authors plan to extend the method to gradient-based optimization for hyperparameters.
  • Serialization of Linear System Solves: While covariance computation is distributed, linear system solutions and log-determinant computations are currently serialized. However, the observed substantial sparsity makes this less of a bottleneck.
  • Proof-of-Concept: The paper acknowledges that the current work is a proof-of-concept, and further refinement is needed for broader adoption.

Summary updated

Abstract

A Gaussian Process (GP) is a prominent mathematical framework for stochastic function approximation in science and engineering applications. This success is largely attributed to the GP's analytical tractability, robustness, non-parametric structure, and natural inclusion of uncertainty quantification. Unfortunately, the use of exact GPs is prohibitively expensive for large datasets due to their unfavorable numerical complexity of $O(N^3)$ in computation and $O(N^2)$ in storage. All existing methods addressing this issue utilize some form of approximation -- usually considering subsets of the full dataset or finding representative pseudo-points that render the covariance matrix well-structured and sparse. These approximate methods can lead to inaccuracies in function approximations and often limit the user's flexibility in designing expressive kernels. Instead of inducing sparsity via data-point geometry and structure, we propose to take advantage of naturally-occurring sparsity by allowing the kernel to discover -- instead of induce -- sparse structure. The premise of this paper is that GPs, in their most native form, are often naturally sparse, but commonly-used kernels do not allow us to exploit this sparsity. The core concept of exact, and at the same time sparse GPs relies on kernel definitions that provide enough flexibility to learn and encode not only non-zero but also zero covariances. This principle of ultra-flexible, compactly-supported, and non-stationary kernels, combined with HPC and constrained optimization, lets us scale exact GPs well beyond 5 million data points.
BibTeX
@misc{noack2022exact,
  author = {Marcus Michael Noack and Harinarayan Krishnan and Mark D. Risser and Kristofer G. Reyes},
  title = {{Exact Gaussian Processes for Massive Datasets via Non-Stationary Sparsity-Discovering Kernels}},
  year = {2022},
  eprint = {2205.09070},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.09070},
}
Figure