The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
It addresses the scalability-accuracy trade-offs in Gaussian Processes for practitioners, offering insights into when linear-time inference is feasible with controlled error, though it is incremental as it builds on existing SKI methods.
This paper provides the first rigorous theoretical error analysis for Structured Kernel Interpolation (SKI) in Gaussian Processes, proving error bounds for the Gram matrix and offering a practical guide for selecting inducing points, such as requiring them to grow as n^{d/3} for error control with convolutional cubic interpolation.
Structured Kernel Interpolation (SKI) (Wilson et al. 2015) helps scale Gaussian Processes (GPs) by approximating the kernel matrix via interpolation at inducing points, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges the gap: we prove error bounds for the SKI Gram matrix and examine the error's effect on hyperparameter estimation and posterior inference. We further provide a practical guide to selecting the number of inducing points under convolutional cubic interpolation: they should grow as $n^{d/3}$ for error control. Crucially, we identify two dimensionality regimes governing the trade-off between SKI Gram matrix spectral norm error and computational complexity. For $d \leq 3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d > 3$, the error must increase with sample size to maintain linear time. Our analysis provides key insights into SKI's scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled approximation error.