Introduction
Gaussian Processes (GPs) are powerful tools for Bayesian modeling because they provide principled uncertainty estimates. However, they suffer from a well-known computational roadblock: exact inference scales cubically ($O(N^3)$) with the number of data points.
To solve this, researchers typically use Sparse Variational GPs (SVGPs), which approximate the full dataset using $M$ "inducing points." While this reduces the cost to $O(M^3)$, $M$ is usually limited to a few thousand points before the computational burden becomes too heavy. This limit prevents GPs from capturing fine-grained details in complex, high-dimensional datasets. Existing solutions like Structured Kernel Interpolation (SKI) work well but are often restricted to very low-dimensional problems.
This paper introduces Harmonic Kernel Decomposition (HKD), a method that uses Fourier series to break down a GP kernel into a sum of orthogonal components based on input-space symmetries. By exploiting this orthogonality, the authors develop Harmonic Variational Gaussian Processes (HVGPs), which can handle a massive number of inducing points at a fraction of the usual computational cost.
Methods: Decomposing the Kernel
The authors propose a two-step approach to bypass traditional scaling limits:
- Harmonic Kernel Decomposition (HKD): If a kernel is invariant to a specific cyclic transformation (like rotating an image 90°, negating a value, or shifting a coordinate), it can be decomposed into a set of orthogonal "harmonic" kernels using a Discrete Fourier Transform (DFT). This acts essentially as a Fourier series representation for kernels.
- Harmonic Variational Gaussian Process (HVGP): Because the decomposed kernels are orthogonal in the Reproducing Kernel Hilbert Space (RKHS), the authors can treat the GP as a sum of independent subprocesses. Each subprocess gets its own set of inducing points.
The Scaling Breakthrough: In a standard SVGP, using $T \times m$ inducing points costs $O(T^3 m^3)$. In an HVGP, because the components are independent, the variational posterior becomes block-diagonal, and the cost drops to $O(T m^3)$. This allows for a much higher total number of inducing points while remaining computationally efficient and highly parallelizable across multiple GPUs with almost no communication overhead.
Key Results and Performance
The authors evaluated their method on several diverse benchmarks, including global bedrock elevations (ETOPO1, >6M points), MNIST variants, UCI Regression Benchmarks, and CIFAR-10.
- Efficiency and Accuracy: On regression tasks, the HVGP model consistently outperformed standard SVGPs with equivalent or double the inducing points, while maintaining comparable or faster training times per iteration due to parallelism.
- Earth Elevation: HVGP used 13,000 inducing points to achieve a significantly better Negative Log-Likelihood (-0.314) compared to a standard SVGP (0.040). It also outperformed SKI, which ran out of memory on the full dataset.
- CIFAR-10: The HVGP achieved 84.85% accuracy, setting a new state-of-the-art for "pure" GP models (models not hybridized with standard deep neural networks).
Limitations and Future Work
While highly effective, the method relies on the existence of a $T$-cyclic transformation that the kernel is invariant to. While many standard kernels (like RBF or Matérn) are naturally invariant to translations or negations, the user must identify these symmetries beforehand. Furthermore, the efficiency gains are most pronounced when the input data distribution itself is somewhat invariant to the chosen transformation; highly asymmetric data may render the approximation less effective.
Future directions suggested by the authors include extending this framework to non-cyclic groups and exploring more complex transformations within deep GP architectures.
Summary updated