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)}$.
To perform efficient matrix-vector multiplications (MVMs) without expanding the full Hadamard product, SKIP employs the following steps:
- Low-Rank Decomposition: The Lanczos algorithm is used to find low-rank approximations ($Q T Q^\top$) for each dimensional matrix.
- 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.
- 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.
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