# Contraction rates for conjugate gradient and Lanczos approximate posteriors in Gaussian process regression

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 38 references that are in the map.
- First posted on arXiv 18 Jun 2024.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Distributed Gaussian Processes](https://mlsanity.com/paper/1502.02843/) (2015)
- [Hierarchical Nearest-Neighbor Gaussian Process Models for Large Geostatistical Datasets](https://mlsanity.com/paper/1406.7343/) (2014)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Variational Bayes for high-dimensional linear regression with sparse priors](https://mlsanity.com/paper/1904.07150/) (2019)
- [Vecchia approximations of Gaussian-process predictions](https://mlsanity.com/paper/1805.03309/) (2018)
- [Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era](https://mlsanity.com/paper/1902.10078/) (2019)
- [Distributed Bayesian Varying Coefficient Modeling Using a Gaussian Process Prior](https://mlsanity.com/paper/2006.00783/) (2020)
- [A Divide-and-Conquer Bayesian Approach to Large-Scale Kriging](https://mlsanity.com/paper/1712.09767/) (2017)
- [Adaptation using spatially distributed Gaussian Processes](https://mlsanity.com/paper/2312.14130/) (2023)

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

- [Adaptive sparse variational approximations for Gaussian process regression](https://mlsanity.com/paper/2504.03321/) (2025)
- [Randomised Postiterations for Calibrated BayesCG](https://mlsanity.com/paper/2504.04247/) (2025)

## Abstract (arXiv)

Due to their flexibility and theoretical tractability Gaussian process (GP) regression models have become a central topic in modern statistics and machine learning. While the true posterior in these models is given explicitly, numerical evaluations depend on the inversion of the augmented kernel matrix  K + σ2 I , which requires up to  O(n3)  operations. For large sample sizes n, which are typically given in modern applications, this is computationally infeasible and necessitates the use of an approximate version of the posterior. Although such methods are widely used in practice, they typically have very limtied theoretical underpinning. In this context, we analyze a class of recently proposed approximation algorithms from the field of Probabilistic numerics. They can be interpreted in terms of Lanczos approximate eigenvectors of the kernel matrix or a conjugate gradient approximation of the posterior mean, which are particularly advantageous in truly large scale applications, as they are fundamentally only based on matrix vector multiplications amenable to the GPU acceleration of modern software frameworks. We combine result from the numerical analysis literature with state of the art concentration results for spectra of kernel matrices to obtain minimax contraction rates. Our theoretical findings are illustrated by numerical experiments.