The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
Moreno, Alexander Xiao, Justin Mei, Jonathan
Moreno, Alexander
Xiao, Justin
Mei, Jonathan
Supervisor
Department
Others
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Structured Kernel Interpolation (SKI) (Wilson & Nickisch, 2015) 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 nd/3 for spectral norm 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 ≥ 3, the error must increase with sample size for our guarantees to hold. Our analysis provides key insights into SKI’s scalability-accuracy tradeoffs, establishing precise conditions for achieving linear-time GP inference with controlled error.
Citation
A. Moreno, J. Xiao, and J. Mei, “The Price of Linear Time: Error Analysis of Structured Kernel Interpolation,” Oct. 06, 2025, PMLR. [Online]. Available: https://proceedings.mlr.press/v267/moreno25b.html
Source
Proceedings of Machine Learning Research
Conference
42nd International Conference on Machine Learning, ICML 2025
Keywords
Subjects
Source
42nd International Conference on Machine Learning, ICML 2025
Publisher
ML Research Press