The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
Alexander Moreno, Justin Xiao, Jonathan Mei · 2025
Read The Price of Linear Time: Error Analysis of Structured Kernel Interpolation by Alexander Moreno, Justin Xiao, Jonathan Mei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-00298.txt.
Introduction
Alexander Moreno, Justin Xiao, and Jonathan Mei analyze the hidden error cost of a fast Gaussian process method in a paper from 2025. The method, structured kernel interpolation, approximates a huge kernel matrix by interpolating at chosen points. It runs in linear time but lacked rigorous error bounds. The authors prove bounds for the approximated matrix and trace how error affects tuning and prediction.
They give a rule for how many inducing points are needed as data grows. In low dimensions, any accuracy target can keep linear time. Beyond three dimensions, error must grow with data size to stay linear. The results map the exact trade-off between speed and accuracy. Practitioners get guidance for safe use.
Catalog record
| CREATOR | Alexander Moreno, Justin Xiao, Jonathan Mei |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-00298
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Price of Linear Time: Error Analysis of Structured Kernel Interpolation Alexander Moreno, Justin Xiao, Jonathan Mei Abstract 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 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 d\leq 3 , any error tolerance can achieve linear time for sufficiently large sample size. For d > 3 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. † † affiliationnotice: 1 Introduction Gaussian Processes (GPs) ( Kolmogorov, 1940 ; Rasmussen & Williams, 2006 ) are an important class of stochastic processes used in machine learning and statistics, with use cases including spatial data analysis ( Liu & Onnela, 2021 ) , time series forecasting ( Girard et al., 2002 ) , bioinformatics ( Huang et al., 2023 ) and Bayesian optimization ( Frazier, 2018 ) . GPs offer a non-parametric framework for modeling distributions over functions, enabling both flexibility and uncertainty quantification. These capabilities, combined with the ability to incorporate prior knowledge and specify relationships by choice of kernel function, make Gaussian Processes effective for both regression and classification. However, GPs have substantial computational and memory bottlenecks. Both training and inference require computing the action of the inverse kernel Gram matrix, while training requires computing its log-determinant: both are O(n^{3}) operations with sample size n . Further, storing the full Gram matrix requires O(n^{2}) memory. These bottlenecks require scalable approximations for larger datasets. Structured Kernel Interpolation (SKI) ( Wilson & Nickisch, 2015 ) helps scale Gaussian Processes (GPs) to large datasets by approximating the kernel matrix using interpolation on a set of inducing points. For stationary kernels, this requires O(n+m\log m) computational complexity. The core idea is to express the original kernel as a combination of interpolation functions and a kernel matrix defined on a set of inducing points. However, despite its effectiveness, popularity (over 600 citations, a large number for a GP paper) and high quality software availability ( ( Gardner et al., 2018 ) has 3.5k stars on github), it currently lacks theoretical analysis. A key initial question is, given a fixed error bound for the SKI Gram matrix and use of cubic convolutional interpolation, how many inducing points are required to achieve that error bound? Given the required value of m as a function of n , for what error tolerance is O(n+m\log m) still linear? Following this, what do these errors imply for hyperparameter estimation and posterior inference? Quantity Bound SKI kernel error O(\frac{c^{2d}}{m^{3/d}}) SKI Gram matrix error O(\frac{nc^{2d}}{m^{3/d}}) SKI cross-kernel matrix error O(\frac{\max(n,T)c^{2d}}{m^{3/d}}) SKI score function error O(\frac{\sqrt{p}n^{2}c^{4d}}{m^{3/d}}) SKI posterior mean error O(c^{2d}\frac{\max(T,n)+\sqrt{Tn}n}{m^{3/d}}) SKI posterior covariance error O(\frac{Tn^{2}mc^{4d}+\sqrt{Tn}mc^{4d}\max(T,n)}{m^{3/d}}) Table 1: Summary of Theoretical Results when using SKI with convolutional cubic interpolation. This shows the rate at which the error of using SKI (vs the exact kernel) grows as a function of important variables. Here n and T are the train/test sample sizes, d is the dimensionality, m the number of inducing points, p is the number of hyperparameters and c>0 is a constant. Most importantly, the Gram matrix error grows linearly with the sample size, exponentially with the dimension while decaying at an m^{3/d} rate in the inducing points. In this paper, we begin to bridge the gap between practice and a theoretical understanding of SKI. We have three primary contributions: 1) The first error analysis for the SKI kernel and relevant quantities, including the SKI gram matrix’s spectral norm error. Based on this we provide a practical guide to select the number of inducing points : they should grow as n^{d/3} to control error. 2) SKI hyperparameter estimation analysis. 3) SKI inference analysis: the error of the GP posterior means and variances at test points. We find two interesting results: 1) we identify two dimensionality regimes relating SKI Gram matrix error to computational complexity. For d\leq 3 , for any fixed spectral norm error, we can achieve it in linear time using SKI with a sufficient sample size. For d>3 , the error must increase with the sample size to maintain our guarantee of linear time. 2) For a \mu -smooth log-likelihood, gradient ascent on the SKI log-likelihood will approach a neighborhood of a stationary point of the true log-likelihood at a O\left(\frac{1}{K}\right) rate, with the neighborhood size determined by the SKI score function’s error, which aside from the response variables grows linearly with the sample size when increasing inducing points as we suggested. To obtain this, we leverage a recent result ( Stonyakin et al., 2023 ) from the inexact gradient descent ( d’Aspremont, 2008 ; Devolder et al., 2014 ) literature. In section 2 we describe related work. In section 3 we give a brief background on SKI. In section 4 we bound the error of important quantities: specifically the SKI kernel, Gram matrix and cross-kernel matrix errors. In section 5 we use these to analyze the error of the SKI MLE and posteriors. We conclude in section 6 by summarizing our results and discussing limitations and future work. 2 Related Work We can divide related works into three groups: those theoretically analyzing Gaussian process regression or kernel methods when using approximate kernels, SKI and its extensions, and papers developing techniques we use to obtain our guarantees. In the first group, the most relevant works are ( Burt et al., 2019 ; Burt et al., 2020 ) , where they analyzed the sparse variational GP framework ( Titsias, 2009 ; Hensman et al., 2013 ) and derived bounds on the Kullback-Leibler divergence between the true posterior and the variational approximate posterior. ( Moreno et al., 2023 ) gave bounds on the approximation error of the SKI Gram matrix. However, they only handled the case of univariate features and only bounded how much worse the SKI Gram matrix can be than the Nyström one. Further, they did not analyze the downstream effects on the approximate MLE or GP posterior. Also relevant are ( Wynne & Wild, 2022 ; Wild et al., 2021 ) , who gave a Banach space view of sparse variational GPs and connected them to the Nyström method, respectively. Finally, ( Modell, 2024 ) provide entry-wise error bounds for low-rank approximations of kernel matrices: our approach also relies on entry-wise error bounds, but theirs are for the best low-rank approximation to a given gram matrix, while ours are for the SKI gram matrix. Only one of these papers ( Moreno et al., 2023 ) treated SKI specifically, and it only covered a very special case setting. In the second group, the foundational work