Product Kernel Interpolation for Scalable Gaussian Processes

Jacob R. Gardner, Geoff Pleiss, Ruihan Wu, Kilian Q. Weinberger, Andrew Gordon Wilson

TL;DR

This paper introduces SKIP, a novel method for efficiently performing matrix-vector multiplications (MVMs) with product kernels in Gaussian Processes (GPs). By exploiting the structure of product kernels, SKIP dramatically improves scalability for high-dimensional problems and multi-task learning, overcoming the curse of dimensionality that plagues existing methods like SKI.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful tools for regression and extrapolation, but their computational cost, particularly for large datasets and high-dimensional inputs, has been a major bottleneck. Traditional methods involve expensive matrix decompositions (O(n³)), while more recent iterative methods rely on fast matrix-vector multiplications (MVMs). Structured Kernel Interpolation (SKI) is one such method that achieves fast MVMs by approximating the kernel with a structure that allows for efficient computation. However, SKI's reliance on Kronecker factorizations for higher dimensions leads to an exponential increase in computational complexity with the number of dimensions, making it impractical for problems beyond a few dimensions. Furthermore, existing MVM-based methods lack modularity, making it difficult to leverage fast MVMs for composite kernels, such as product kernels, which are common in practice. This paper addresses these limitations by developing a general and efficient method for MVMs with product kernels, enabling scalable GP inference in high-dimensional and multi-task settings.

Methods

The core contribution of this paper is the Structured Kernel Interpolation for Product Kernels (SKIP) method. SKIP tackles the challenge of computing MVMs with a product kernel $K = \prod_{i=1}^d K^{(i)}$ by:

  1. Leveraging Lanczos Decomposition: For each component kernel $K^{(i)}$, SKIP computes a low-rank approximation using the Lanczos decomposition. This allows for fast MVMs with each component kernel.
  2. Exploiting Rank-r Approximations: The paper shows how to efficiently compute MVMs with the product of two rank-r approximated kernels by combining their low-rank factorizations. This is generalized to multiple kernels using a divide-and-conquer strategy.
  3. Applying SKI to Component Kernels: SKIP further enhances efficiency by applying the Structured Kernel Interpolation (SKI) approximation to each one-dimensional component kernel. This means that instead of needing a dense grid for the full d-dimensional input space, SKIP uses a grid for each individual dimension.

This approach results in a significant reduction in computational complexity. For a product of $d$ kernels, each with $m$ inducing points, SKIP achieves MVMs in $O(dr\mu(K^{(i)}) + r^3n \log d + r^2n)$ time, where $r$ is the rank of the Lanczos decomposition. Crucially, subsequent MVMs can be performed in $O(r^2n)$ time after the initial decomposition. For multi-task GPs, SKIP reduces the complexity to $O(n + m \log m + s)$ for $s$ tasks.

Datasets

The paper evaluates SKIP on several benchmark datasets:

  • Precipitation dataset: Hourly rainfall measurements from hundreds of stations.
  • Pumadyn dataset: A dataset from the UCI machine learning repository.
  • Elevators dataset: A dataset from the UCI machine learning repository.
  • KEGG dataset: A dataset from the UCI machine learning repository.
  • Protein dataset: A dataset from the UCI machine learning repository.
  • Child development dataset: A dataset from the Gates foundation, used for multi-task learning experiments.

The paper notes that for datasets with $d > 5$ dimensions, standard KISS-GP (SKI with Kronecker factorization) is not applicable, and the full GP is not applicable on the four largest datasets.

Key Insights and Ideas

  • Product Kernels as a Bottleneck: The paper highlights that while MVMs with individual kernels can be fast, computing MVMs with their product is non-trivial and doesn't simply distribute. This is a key challenge for building scalable models with composite kernels.
  • Decomposition is Key: The core idea is to break down the complex product kernel MVM into a series of simpler operations on low-rank approximations of the component kernels.
  • SKI on 1D Components: Applying SKI to each one-dimensional component kernel, rather than the full d-dimensional space, is a crucial step that avoids the exponential complexity of Kronecker factorizations in higher dimensions.
  • Modularity and Generality: SKIP offers a modular approach, allowing for fast MVMs with product kernels without needing to know the internal structure of the component kernels beyond their MVM capabilities. This makes it broadly applicable.
  • Multi-task GPs Benefit Greatly: The method's ability to efficiently compute MVMs for product kernels directly translates to significant speedups in multi-task GP inference, enabling new modeling capabilities like task clustering.

Key Results

  • Linear Scalability in Dimension: SKIP reduces the runtime complexity of SKI in $d$ dimensions from exponential $O(n + dmd \log m)$ to linear $O(dn + dm \log m)$ for product kernels.
  • State-of-the-Art Complexity for Multi-Task GPs: SKIP achieves $O(n + m \log m + s)$ complexity for multi-task GPs with $s$ tasks, a significant improvement over previous methods.
  • High Accuracy: The paper demonstrates that SKIP achieves very accurate MVM approximations with a small number of Lanczos iterations (e.g., less than 1% error with $k=30$ for 12-dimensional data).
  • Significant Speedups: SKIP provides substantial runtime improvements over existing methods like SGPR and KISS-GP, especially in higher dimensional settings. For example, on the precipitation dataset, SKIP is faster than SGPR.
  • Enables Task Clustering: The efficient inference enabled by SKIP allows for the development of a novel MTGP model that discovers latent task clusters, leading to more interpretable models.

Limitations and Future Work

  • Space Complexity: The paper notes that while SKIP's space complexity is better than full GP regression or standard inducing point methods, it is worse than SKI's linear storage. Storing multiple Lanczos decompositions can be memory-intensive, especially on GPUs.
  • Stochastic Diagonal Estimation: The authors mention that while their method relies on quickly computing diagonals, alternative techniques for stochastic diagonal estimation exist. These might converge slower but could be more appropriate for kernels with high rank structure.
  • Higher-Order Product Kernels: For very high-order product kernels, the rank of the approximations might need to increase, potentially impacting performance. The paper suggests that in such cases, using the SKI approximation directly in place of Lanczos decomposition might be an option.
  • Future Work: The paper implicitly suggests exploring further applications of SKIP in various domains where product kernels are prevalent, as well as investigating more advanced techniques for managing memory usage. The development of a cluster-based MTGP model also opens avenues for more sophisticated latent structure discovery in multi-task learning.

Summary updated

Abstract

Recent work shows that inference for Gaussian processes can be performed efficiently using iterative methods that rely only on matrix-vector multiplications (MVMs). Structured Kernel Interpolation (SKI) exploits these techniques by deriving approximate kernels with very fast MVMs. Unfortunately, such strategies suffer badly from the curse of dimensionality. We develop a new technique for MVM based learning that exploits product kernel structure. We demonstrate that this technique is broadly applicable, resulting in linear rather than exponential runtime with dimension for SKI, as well as state-of-the-art asymptotic complexity for multi-task GPs.
BibTeX
@inproceedings{gardner2018product,
  author = {Jacob R. Gardner and Geoff Pleiss and Ruihan Wu and Kilian Q. Weinberger and Andrew Gordon Wilson},
  title = {{Product Kernel Interpolation for Scalable Gaussian Processes}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=r9UWSTTQMQq},
}
Figure