The Price of Linear Time: Error Analysis of Structured Kernel Interpolation

Structured Kernel Interpolation (SKI) (Wilson & Nickisch, 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 ≤ 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. Error Bounds for Structured Kernel Interpolation Gaussian Processes, Structured Kernel Interpolation and Convolutional Cubic Interpolation This section provides background on Gaussian Processes (GPs) and two key techniques for enabling scalable inference: Structured Kernel Interpolation (SKI) and Convolu-