Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition

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

TL;DR

This paper introduces Harmonic Kernel Decomposition (HKD), a novel method that uses Fourier series to decompose a Gaussian Process (GP) kernel into a sum of orthogonal sub-kernels. By exploiting this orthogonality alongside data symmetries, the proposed Harmonic Variational GP (HVGP) scales up the number of inducing points at a fraction of the usual computational cost through multi-GPU parallelization. The approach achieves state-of-the-art results for pure GP models on image classification and large-scale regression tasks.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful non-parametric Bayesian models favored for their rigorous uncertainty estimates. However, exact inference scales cubically ($O(N^3)$) with the number of data points $N$, making them impractical for large datasets.

Sparse Variational GPs (SVGPs) alleviate this bottleneck by using $M$ "inducing points" to summarize the dataset, reducing the cost to $O(M^3)$. Unfortunately, $M$ is still practically limited to a few thousand points because of this cubic complexity. This constraint severely limits the model's expressive capacity on massive or high-dimensional datasets. While grid-based methods like Structured Kernel Interpolation (SKI) allow millions of inducing points, they suffer from the curse of dimensionality because the grid size grows exponentially with the input dimension. The authors aim to bypass this trade-off, scaling up the number of trainable inducing points without incurring prohibitive computational or memory costs.

Methods

The authors introduce two core components:

  1. Harmonic Kernel Decomposition (HKD): If a kernel is invariant under a cyclic transformation $G$ (such as a $90^\circ$ rotation or a reflection), the Discrete Fourier Transform (DFT) can decompose it into a sum of orthogonal, complex-valued (Hermitian) sub-kernels. Each sub-kernel models a specific Fourier component of the target function.
  2. Harmonic Variational Gaussian Process (HVGP): Instead of using a single massive set of inducing points, HVGP models the GP as an additive combination of independent subprocesses, assigning a separate, smaller set of inducing points to each Fourier component.
Visualizing the harmonic kernel decomposition

Because the sub-kernels are mathematically orthogonal, the optimal variational posterior covariance matrix becomes block-diagonal when the input data distribution is symmetric under $G$. This structural decoupling allows researchers to train the subprocesses completely in parallel across multiple GPUs. Consequently, a massive $O((TM)^3)$ problem is broken down into $T$ independent $O(M^3)$ computations.

Datasets

The method was evaluated on a diverse set of benchmarks:

  • Flip-MNIST & Translate-MNIST: Modified versions of the MNIST digit dataset used to validate how well the model handles explicit spatial symmetries like flipping and translation.
  • Earth Elevation (ETOPO1): A massive spatial dataset containing 6,480,000 coordinate-elevation pairs, used to test large-scale coordinate regression.
  • UCI Regression Benchmarks: Five large-scale tabular datasets (year, 3droad, song, buzz, houseelectric) ranging from 200,000 to 1,000,000 samples.
  • CIFAR-10: A standard image classification benchmark used to evaluate HVGPs when integrated into deep convolutional GP architectures.

Key Insights and Ideas

  • Symmetry as a Computational Accelerator: Traditionally, researchers exploit data symmetries to make models invariant (ensuring a flipped image yields the same prediction). This paper flips the script: it uses data symmetries to mathematically decouple the variational optimization problem, enabling massive parallelization.
  • The Alignment Imperative: For HKD to be effective, the chosen cyclic transformation $G$ must closely match the actual distribution of the data. In the Flip-MNIST experiments, using an unaligned transformation (like simple numerical negation) performed poorly, whereas a true spatial flip matched the data structure perfectly and accelerated learning.
Figure 2. Flip-MNIST. We plot how left: train loss and right: test accuracy evolve with training. We observe the HVGP using FLIP: 4 × 100 perform similarly with the SVGP using 400 inducing points while the HVGP using NEG: 4 × 100 perform substantially worse.
  • PCA Negation for Tabular Data: For tabular datasets lacking obvious spatial symmetries, the authors discovered that performing negations along the principal component (PCA) directions keeps the transformed "virtual" points within the true data distribution. This significantly reduces Nyström approximation errors compared to negating standard coordinate axes.

Key Results

  • CIFAR-10 State-of-the-Art: When integrated with deep convolutional GPs, the 4-layer HVGP model achieved an accuracy of 84.85% and a Negative Log-Likelihood (NLL) of 0.58, setting a new state-of-the-art for pure GP models on CIFAR-10 while running faster than standard non-decomposed counterparts.
  • Earth Elevation Scaling: On the 6.4M point ETOPO1 dataset, an HVGP using 13 groups of 1,000 inducing points (13,000 total) achieved a Test NLL of -0.314, vastly outperforming a standard SVGP with 5,000 inducing points (NLL of -0.203) while cutting total training time in half via 4-GPU parallelization.
  • Nyström Error Reduction: Across all tabular regression benchmarks, HVGPs consistently yielded lower Nyström approximation residuals than standard SVGPs, proving that the decomposed inducing points summarize the data matrix much more effectively.

Limitations and Future Work

  • Dependence on Cyclic Groups: The framework strictly requires identifying a valid $T$-cyclic transformation $G$ under which the kernel is invariant. For complex tabular data without clear physical or spatial symmetries, finding an optimal $G$ remains challenging and relies on heuristics like PCA.
  • Complex-Valued Kernels: The raw Fourier decomposition naturally introduces complex numbers into the kernel space. Although the authors present a technique to pair them up into real-valued kernels, it adds an extra layer of implementation complexity.
  • Future Directions: Promising future avenues include extending the framework to non-cyclic symmetry groups or developing methods to automatically learn the optimal transformation matrix $G$ directly from the data during training.

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 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},
}

Loading related content...

Figure