Overview
This paper introduces VISH (Variational Inference with Spherical Harmonics), a novel sparse Gaussian Process (GP) framework. By mapping data onto a hypersphere and leveraging spherical harmonic basis functions, VISH achieves a diagonal covariance matrix for its inducing variables. This breakthrough enables inference that is up to 100x faster than standard sparse GPs on datasets with millions of entries, all while maintaining state-of-the-art accuracy.
The Computational Bottleneck of GPs
Gaussian Processes are powerful tools for modeling uncertainty, but they suffer from a massive computational bottleneck: exact inference scales as $O(N^3)$, where $N$ is the number of data points.
To mitigate this, researchers often use Sparse GPs, which rely on $M$ "inducing points" to summarize the data, reducing complexity to $O(M^2N)$. However, standard sparse GPs have a "local" influence—they only provide good approximations near the inducing points. Variational Fourier Features (VFF) were proposed to give inducing variables "global" influence, but VFF fails in higher dimensions because the number of required features grows exponentially (the "curse of dimensionality").
The authors seek a method that provides global influence, scales well to higher dimensions, and avoids the expensive matrix inversions typically required in GP inference.
The VISH Method
The core innovation of this paper is a three-step process called VISH:
- Mapping to the Hypersphere: The authors append a "bias" term to the input data and project it onto a unit hypersphere ($S^{d-1}$). This geometric trick is inspired by the relationship between neural networks and kernels (like the arc-cosine kernel).
- Spherical Harmonic Inducing Features: Instead of using function values at specific points as inducing variables, VISH uses projections of the GP onto spherical harmonics. These act as global basis functions, meaning fewer features can often capture more of the underlying function's structure.
- Exploiting Mercer’s Theorem: On a sphere, stationary kernels (zonal kernels) have spherical harmonics as their eigenfunctions. Because of this mathematical property, the covariance matrix between these inducing variables ($K_{uu}$) becomes perfectly diagonal.
Why is this a big deal? In standard GPs, you have to invert a large $M \times M$ matrix. With VISH, you just divide by the diagonal elements. This bypasses the most expensive part of GP training, turning a cubic-time bottleneck into a linear-time operation. Furthermore, spherical harmonics have a natural frequency-based ordering, allowing users to prioritize the most important low-frequency features first.
Key Results
The authors evaluated VISH on a variety of benchmarks, including toy problems (the "Banana" dataset), UCI Regression Benchmarks, and large-scale datasets like the 2008 U.S. Airline Delay dataset (5.9 million records) and the SUSY classification dataset (5 million records).
- Speed: On the 6-million-row Airline dataset, VISH took about 41 seconds to train and predict. In comparison, the standard Sparse Variational GP (SVGP) took 15 minutes—a nearly 22x speedup. Compared to exact GPs, the speedup is several orders of magnitude.
- Accuracy: Despite the massive speedup, VISH remained competitive with or outperformed SVGP and VFF across UCI benchmarks and the SUSY classification task.
- Scalability: Unlike VFF, which is practically limited to 1D or 2D inputs, VISH was successfully applied to 8-dimensional and 9-dimensional problems without an exponential explosion in parameters.
Limitations and Future Work
While VISH significantly pushes the boundaries of sparse GP scalability, it does not entirely eliminate the curse of dimensionality. The current implementation is stable only up to about 9 dimensions. This is not a theoretical limit of the mathematics, but a practical one: there are currently few software libraries that provide stable, high-dimensional spherical harmonic computations. Future work may involve developing more robust libraries for high-dimensional harmonics or exploring how this spherical mapping relates to deep neural network architectures.
Summary updated