# Kernel Interpolation for Scalable Online Gaussian Processes

arXiv: https://arxiv.org/abs/2103.01454 · HTML: https://mlsanity.com/paper/2103.01454/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 2 Mar 2021.

## Builds on (most cited first, 17 of 17)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Gaussian Process Kernels for Pattern Discovery and Extrapolation](https://mlsanity.com/paper/1302.4245/) (2013)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Understanding Probabilistic Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1606.04820/) (2016)
- [Dirichlet-based Gaussian Processes for Large-scale Calibrated Classification](https://mlsanity.com/paper/1805.10915/) (2018)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Streaming Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1705.07131/) (2017)
- [Randomly Projected Additive Gaussian Processes for Regression](https://mlsanity.com/paper/1912.12834/) (2019)
- [Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck](https://mlsanity.com/paper/2004.11094/) (2020)
- [PBODL : Parallel Bayesian Online Deep Learning for Click-Through Rate Prediction in Tencent Advertising System](https://mlsanity.com/paper/1707.00802/) (2017)
- [Scalable Gaussian Processes with Grid-Structured Eigenfunctions (GP-GRIEF)](https://mlsanity.com/paper/1807.02125/) (2018)
- [GP-Localize: Persistent Mobile Robot Localization using Online Sparse Gaussian Process Observation Model](https://mlsanity.com/paper/1404.5165/) (2014)

## Built on by (most cited first, 18 of 18)

- [Bayesian Optimization with Conformal Prediction Sets](https://mlsanity.com/paper/2210.12496/) (2022)
- [Conditioning Sparse Variational Gaussian Processes for Online Decision-making](https://mlsanity.com/paper/2110.15172/) (2021)
- [Operator Learning with Gaussian Processes](https://mlsanity.com/paper/2409.04538/) (2024)
- [Data Fusion with Latent Map Gaussian Processes](https://mlsanity.com/paper/2112.02206/) (2021)
- [Incremental Ensemble Gaussian Processes](https://mlsanity.com/paper/2110.06777/) (2021)
- [Kernel Regression with Infinite-Width Neural Networks on Millions of Examples](https://mlsanity.com/paper/2303.05420/) (2023)
- [Dynamic Online Ensembles of Basis Expansions](https://mlsanity.com/paper/2405.01365/) (2024)
- [Adaptive Sparse Gaussian Process](https://mlsanity.com/paper/2302.10325/) (2023)
- [Recurrent Memory for Online Interdomain Gaussian Processes](https://mlsanity.com/paper/2502.08736/) (2025)
- [Incremental Transformer Neural Processes](https://mlsanity.com/paper/2602.18955/) (2026)
- [Streaming PAC-Bayes Gaussian process regression with a performance guarantee for online decision making](https://mlsanity.com/paper/2210.08486/) (2022)
- [Large-scale magnetic field maps using structured kernel interpolation for Gaussian process regression](https://mlsanity.com/paper/2310.16574/) (2023)
- [Online Student-t Processes with an Overall-local Scale Structure for Modelling Non-stationary Data](https://mlsanity.com/paper/2311.00564/) (2023)
- [A Kronecker product accelerated efficient sparse Gaussian Process (E-SGP) for flow emulation](https://mlsanity.com/paper/2312.10023/) (2023)
- [Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner](https://mlsanity.com/paper/2408.00206/) (2024)
- [Tensor network square root Kalman filter for online Gaussian process regression](https://mlsanity.com/paper/2409.03276/) (2024)
- [DAO-GP Drift Aware Online Non-Linear Regression Gaussian-Process](https://mlsanity.com/paper/2512.08879/) (2025)
- [Finding the Needle in a Haystack: Test-Time Analog Circuit Representation Adaptation for Bayesian Optimization](https://mlsanity.com/paper/2608.12687/) (2026)

## Abstract (arXiv)

Gaussian processes (GPs) provide a gold standard for performance in online settings, such as sample-efficient control and black box optimization, where we need to update a posterior distribution as we acquire data in a sequential fashion. However, updating a GP posterior to accommodate even a single new observation after having observed n points incurs at least O(n) computations in the exact setting. We show how to use structured kernel interpolation to efficiently recycle computations for constant-time O(1) online updates with respect to the number of points n, while retaining exact inference. We demonstrate the promise of our approach in a range of online regression and classification settings, Bayesian optimization, and active sampling to reduce error in malaria incidence forecasting. Code is available at https://github.com/wjmaddox/onlinegp.