Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition

Shengyang Sun, Jiaxin Shi, Andrew Gordon Wilson, Roger Baker Grosse

TL;DR

This paper introduces a novel method called Harmonic Kernel Decomposition (HKD) to make Gaussian Processes (GPs) more scalable and accurate. By decomposing a kernel into orthogonal components based on input symmetries, they enable GPs to use many more "inducing points" (a key to scalability) without sacrificing computational efficiency, leading to state-of-the-art results on challenging benchmarks.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful probabilistic models for functions, offering principled uncertainty estimates. However, their computational cost scales cubically with the number of data points ($O(N^3)$), making them impractical for large datasets. Sparse GP methods, which use a fixed number of "inducing points" to approximate the GP, reduce this cost but can still struggle with scalability and accuracy when dealing with millions of data points. Existing methods like Structured Kernel Interpolation (SKI) achieve scalability by imposing grid-like structures on inducing points, but this limits them to low-dimensional problems. The challenge is to develop GP approximations that are both scalable to large datasets and high-dimensional inputs, while maintaining high accuracy and principled uncertainty quantification.

Methods

The core contribution is the Harmonic Kernel Decomposition (HKD). This technique leverages symmetries in the input space (like translations or rotations) to decompose a kernel function into a sum of orthogonal kernels. This decomposition is achieved using Fourier series, where each component kernel corresponds to a specific symmetry or frequency.

The paper then proposes the Harmonic Variational Gaussian Process (HVGP). This method builds upon the HKD by using separate sets of inducing points for each of the decomposed kernel components. This "decoupled" approach allows for a much larger total number of inducing points to be used efficiently. The key advantages are:

  • Orthogonality: The decomposed kernels are orthogonal, meaning their associated function spaces are disjoint. This allows for independent variational approximations for each component, simplifying inference.
  • Scalability: By distributing inducing points across these orthogonal components, HVGPs can effectively utilize millions of inducing points at a much lower computational cost than standard sparse GPs.
  • Flexibility: Unlike SKI, which is limited by grid structures, HKD can exploit arbitrary symmetries and allows for trainable inducing points.

The paper also introduces an "inter-domain inducing points formulation" which shows an equivalence between the proposed HKD-based variational posterior and standard sparse GPs with specific inducing point configurations.

Datasets

The paper evaluates HVGPs on several datasets:

  • Earth Elevation Data: ETOPO1 dataset for fitting earth elevation.
  • MNIST: Used for a "flip-MNIST" experiment to test symmetry handling.
  • Regression Benchmarks: Standard regression datasets with sizes ranging from 200,000 to 1 million data points.
  • CIFAR-10: Used for image classification experiments, integrated with deep convolutional structures.

No new benchmarks were introduced.

Key Insights and Ideas

  • Symmetry is Key to Scalability: The paper demonstrates that exploiting input space symmetries is a powerful way to decompose complex kernels and enable scalable GP inference.
  • Orthogonal Decomposition Simplifies Inference: Decomposing a kernel into orthogonal components allows for independent variational approximations, significantly reducing computational complexity and improving accuracy.
  • HVGP Outperforms Standard SVGPs: By using more inducing points distributed across orthogonal kernel components, HVGPs achieve better accuracy and scalability than standard SVGPs, even when the latter use a comparable total number of inducing points.
  • Matching Transformation to Data is Crucial: The performance of HVGPs is highly dependent on choosing a transformation (G) that matches the symmetries present in the data distribution. For example, using negations along principal components (PCA directions) worked much better than negations along standard axes for certain datasets.

Key Results

  • State-of-the-Art on CIFAR-10: HVGPs achieved state-of-the-art results among pure GP models on the CIFAR-10 classification benchmark when integrated with deep convolutional structures.
  • Improved Accuracy and Scalability: On regression benchmarks, HVGPs with more inducing points (e.g., 8xM) significantly outperformed standard SVGPs with fewer points, achieving better RMSE and NLL.
  • Computational Efficiency: Despite using more inducing points, HVGPs can be faster due to parallelization across the decomposed kernel components. For instance, an 8xM HVGP had comparable running time to an MxM SVGP.
  • Earth Elevation Data: HVGP (13x1000) provided a finer fit to the earth elevation data compared to SVGP (M=1000), as visualized in Figure 3.
  • Translate-MNIST: HVGPs using translation transformations outperformed SVGPs, even when the latter used more inducing points.

Limitations and Future Work

  • Choice of Transformation: The performance of HVGPs is sensitive to the choice of the symmetry transformation G. Selecting an appropriate G that aligns with the data distribution is crucial.
  • Complex-Valued Kernels: While the paper addresses real-valued kernels by pairing components, the underlying decomposition can involve complex-valued kernels, which might require careful handling.
  • Future Work: The paper suggests that this method can be extended to more complex kernel structures and potentially applied to other areas where exploiting symmetries is beneficial. The authors also highlight the potential for further parallelism and integration with deep learning architectures.

Summary updated

Abstract

We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We propose the harmonic kernel decomposition (HKD), which uses Fourier series to decompose a kernel as a sum of orthogonal kernels. Our variational approximation exploits this orthogonality to enable a large number of inducing points at a low computational cost. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections, and it significantly outperforms standard variational methods in scalability and accuracy. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
BibTeX
@inproceedings{sun2021scalable,
  author = {Shengyang Sun and Jiaxin Shi and Andrew Gordon Wilson and Roger Baker Grosse},
  title = {{Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=s_o3SYeZ29E},
}
Figure