# Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

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

- [Kernel Interpolation for Scalable Online Gaussian Processes](https://mlsanity.com/paper/2103.01454/) (2021)
- [Posterior Coreset Construction with Kernelized Stein Discrepancy for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2206.01162/) (2022)
- [Formulation Graphs for Mapping Structure-Composition of Battery Electrolytes to Device Performance](https://mlsanity.com/paper/2307.03811/) (2023)
- [High-dimensional additive Gaussian processes under monotonicity constraints](https://mlsanity.com/paper/2205.08528/) (2022)
- [STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2301.12038/) (2023)
- [Online, Informative MCMC Thinning with Kernelized Stein Discrepancy](https://mlsanity.com/paper/2201.07130/) (2022)
- [Adaptive Sparse Gaussian Process](https://mlsanity.com/paper/2302.10325/) (2023)
- [GPTreeO: An R package for continual regression with dividing local Gaussian processes](https://mlsanity.com/paper/2410.01024/) (2024)
- [Wasserstein-Splitting Gaussian Process Regression for Heterogeneous Online Bayesian Inference](https://mlsanity.com/paper/2107.12797/) (2021)
- [DAO-GP Drift Aware Online Non-Linear Regression Gaussian-Process](https://mlsanity.com/paper/2512.08879/) (2025)

## Abstract (arXiv)

Gaussian processes provide a framework for nonlinear nonparametric Bayesian inference widely applicable across science and engineering. Unfortunately, their computational burden scales cubically with the training sample size, which in the case that samples arrive in perpetuity, approaches infinity. This issue necessitates approximations for use with streaming data, which to date mostly lack convergence guarantees. Thus, we develop the first online Gaussian process approximation that preserves convergence to the population posterior, i.e., asymptotic posterior consistency, while ameliorating its intractable complexity growth with the sample size. We propose an online compression scheme that, following each a posteriori update, fixes an error neighborhood with respect to the Hellinger metric centered at the current posterior, and greedily tosses out past kernel dictionary elements until its boundary is hit. We call the resulting method Parsimonious Online Gaussian Processes (POG). For diminishing error radius, exact asymptotic consistency is preserved (Theorem 1(i)) at the cost of unbounded memory in the limit. On the other hand, for constant error radius, POG converges to a neighborhood of the population posterior (Theorem 1(ii))but with finite memory at-worst determined by the metric entropy of the feature space (Theorem 2). Experimental results are presented on several nonlinear regression problems which illuminates the merits of this approach as compared with alternatives that fix the subspace dimension defining the history of past points.