Product Kernel Interpolation for Scalable Gaussian Processes

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

Abstract

Recent work shows that inference for Gaussian processes (GPs) can be performed efficiently using iterative methods that rely only on matrix-vector multiplications (MVMs). While Structured Kernel Interpolation (SKI) provides a path to nearly linear time complexity, it is historically limited by the "curse of dimensionality," where the number of grid points required grows exponentially with the number of dimensions. This paper introduces SKIP (Structured Kernel Interpolation for Products), a method that leverages the mathematical properties of product kernels and low-rank approximations to transform this exponential growth into a linear scaling problem, enabling efficient learning on high-dimensional datasets with hundreds of thousands of points.

The Challenge: Scaling Beyond 5 Dimensions

Gaussian Processes are highly valued for uncertainty-aware regression but suffer from a massive computational overhead of $O(n^3)$. Structured Kernel Interpolation (SKI) was developed to mitigate this, using a grid of $m$ inducing points to achieve $O(n + m \log m)$ complexity. However, to maintain accuracy in higher dimensions, the number of grid points must grow as $m^d$. In practice, this exponential explosion causes SKI methods to hit a computational wall at approximately 5 dimensions.

Methodology: The SKIP Approach

SKIP exploits the fact that many popular kernels, such as RBF or ARD, can be decomposed into a product of one-dimensional kernels. The resulting covariance matrix $K$ is the element-wise (Hadamard) product of matrices from each dimension: $K = K^{(1)} \circ K^{(2)} \dots \circ K^{(d)}$.

The SKIP decomposition approximates the Hadamard product of dimensional matrices using low-rank components derived from the Lanczos algorithm.

To perform efficient matrix-vector multiplications (MVMs) without expanding the full Hadamard product, SKIP employs the following steps:

  1. Low-Rank Decomposition: The Lanczos algorithm is used to find low-rank approximations ($Q T Q^\top$) for each dimensional matrix.
  2. Efficient MVMs: By combining these low-rank approximations with a clever change of basis, the method approximates MVMs with the full high-dimensional matrix using only the low-rank components.
  3. Complexity Shift: This moves the computational complexity from $O(n + m^d \log m^d)$ to $O(dn + dm \log m)$, making the cost linear rather than exponential in the number of dimensions ($d$).

Scalability and Performance

The authors evaluated SKIP against existing state-of-the-art methods like KISS-GP and Sparse Variational GPs (SGPR) across various high-dimensional benchmarks, including the 32-dimensional Pumadyn and 18-dimensional Elevators datasets.

SKIP maintains stable training times as the number of inducing points increases, whereas previous SKI methods (KISS-GP) scale exponentially.

As illustrated in the scaling analysis, SKIP successfully breaks the curse of dimensionality. While KISS-GP becomes computationally impossible as the number of inducing points per dimension increases, SKIP's training time remains efficient and even outperforms SGPR at higher scales. On the Elevators dataset, SKIP matched the accuracy of an exact "Full GP" solution while being orders of magnitude faster.

Key Insights and Applications

  • Modularity: SKIP provides a "black-box" framework. It does not require knowledge of the internal structure of component kernels, only the ability to perform an MVM with them.
  • Multi-Task Acceleration: The method is particularly effective for multi-task GPs, where related tasks are modeled as a product kernel problem. SKIP can speed up these models by 20x or more, as demonstrated in a child development study where it identified latent growth clusters.
  • Implementation: This research was released as part of GPyTorch, providing the machine learning community with a robust library for scalable, high-dimensional Gaussian Process modeling.

Conclusion

By leveraging Hadamard product structures and Lanczos-based low-rank approximations, SKIP enables Gaussian Processes to handle the scale and dimensionality of modern datasets. While it requires careful management of GPU memory for very large ranks, it represents a significant step forward in making exact GP inference practical for high-dimensional real-world applications.

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 ...
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