# On Random Subsampling of Gaussian Process Regression: A Graphon-Based Analysis

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2019.

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

- [Scalable Bayesian Optimization via Focalized Sparse Gaussian Processes](https://mlsanity.com/paper/2412.20375/) (2024)
- [Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression](https://mlsanity.com/paper/2306.14731/) (2023)
- [Fast Gaussian Process Posterior Mean Prediction via Local Cross Validation and Precomputation](https://mlsanity.com/paper/2205.10879/) (2022)
- [Statistical Hardware Design With Multi-model Active Learning](https://mlsanity.com/paper/2303.08054/) (2023)

## Abstract (arXiv)

In this paper, we study random subsampling of Gaussian process regression, one of the simplest approximation baselines, from a theoretical perspective. Although subsampling discards a large part of training data, we show provable guarantees on the accuracy of the predictive mean/variance and its generalization ability. For analysis, we consider embedding kernel matrices into graphons, which encapsulate the difference of the sample size and enables us to evaluate the approximation and generalization errors in a unified manner. The experimental results show that the subsampling approximation achieves a better trade-off regarding accuracy and runtime than the Nystr"om and random Fourier expansion methods.