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

Alexander Moreno, Justin Xiao, Jonathan Mei
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:44825-44853, 2025.

Abstract

Structured Kernel Interpolation (SKI) scales Gaussian Processes (GPs) by approximating the kernel matrix via inducing point interpolation, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges this gap by proving error bounds for the SKI Gram matrix and examining their 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 for the SKI Gram matrix spectral norm error vs. complexity trade-off. For $d<3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d\geq 3$, the error must increase with sample size for our guarantees to hold. Our analysis provides key insights into SKI’s scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled error.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-moreno25b, title = {The Price of Linear Time: Error Analysis of Structured Kernel Interpolation}, author = {Moreno, Alexander and Xiao, Justin and Mei, Jonathan}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {44825--44853}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/moreno25b/moreno25b.pdf}, url = {https://proceedings.mlr.press/v267/moreno25b.html}, abstract = {Structured Kernel Interpolation (SKI) scales Gaussian Processes (GPs) by approximating the kernel matrix via inducing point interpolation, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges this gap by proving error bounds for the SKI Gram matrix and examining their 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 for the SKI Gram matrix spectral norm error vs. complexity trade-off. For $d<3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d\geq 3$, the error must increase with sample size for our guarantees to hold. Our analysis provides key insights into SKI’s scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled error.} }
Endnote
%0 Conference Paper %T The Price of Linear Time: Error Analysis of Structured Kernel Interpolation %A Alexander Moreno %A Justin Xiao %A Jonathan Mei %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-moreno25b %I PMLR %P 44825--44853 %U https://proceedings.mlr.press/v267/moreno25b.html %V 267 %X Structured Kernel Interpolation (SKI) scales Gaussian Processes (GPs) by approximating the kernel matrix via inducing point interpolation, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges this gap by proving error bounds for the SKI Gram matrix and examining their 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 for the SKI Gram matrix spectral norm error vs. complexity trade-off. For $d<3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d\geq 3$, the error must increase with sample size for our guarantees to hold. Our analysis provides key insights into SKI’s scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled error.
APA
Moreno, A., Xiao, J. & Mei, J.. (2025). The Price of Linear Time: Error Analysis of Structured Kernel Interpolation. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:44825-44853 Available from https://proceedings.mlr.press/v267/moreno25b.html.

Related Material