# Rates of Convergence for Sparse Variational Gaussian Process Regression

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2019.

## Built on by (most cited first, 30 of 63)

- [On Feature Collapse and Deep Kernel Learning for Single Forward Pass Uncertainty](https://mlsanity.com/paper/2102.11409/) (2021)
- [On the Practicality of Deterministic Epistemic Uncertainty](https://mlsanity.com/paper/2107.00649/) (2021)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [Accelerated Linearized Laplace Approximation for Bayesian Deep Learning](https://mlsanity.com/paper/2210.12642/) (2022)
- [Deep Neural Networks as Point Estimates for Deep Gaussian Processes](https://mlsanity.com/paper/2105.04504/) (2021)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Conditioning Sparse Variational Gaussian Processes for Online Decision-making](https://mlsanity.com/paper/2110.15172/) (2021)
- [Additive Gaussian Processes Revisited](https://mlsanity.com/paper/2206.09861/) (2022)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Markovian Gaussian Process Variational Autoencoders](https://mlsanity.com/paper/2207.05543/) (2022)
- [Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces](https://mlsanity.com/paper/2507.03910/) (2025)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Sparse Algorithms for Markovian Gaussian Processes](https://mlsanity.com/paper/2103.10710/) (2021)
- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition](https://mlsanity.com/paper/2106.05992/) (2021)
- [Adaptive Inducing Points Selection For Gaussian Processes](https://mlsanity.com/paper/2107.10066/) (2021)
- [Variational Nearest Neighbor Gaussian Process](https://mlsanity.com/paper/2202.01694/) (2022)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [Combining Pseudo-Point and State Space Approximations for Sum-Separable Gaussian Processes](https://mlsanity.com/paper/2106.10210/) (2021)
- [Fast and Scalable Spike and Slab Variable Selection in High-Dimensional Gaussian Processes](https://mlsanity.com/paper/2111.04558/) (2021)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Koopman-Equivariant Gaussian Processes](https://mlsanity.com/paper/2502.06645/) (2025)
- [Information-theoretic Inducing Point Placement for High-throughput Bayesian Optimisation](https://mlsanity.com/paper/2206.02437/) (2022)
- [Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees](https://mlsanity.com/paper/2210.07893/) (2022)
- [Lightweight Distributed Gaussian Process Regression for Online Machine Learning](https://mlsanity.com/paper/2105.04738/) (2021)
- [High-dimensional additive Gaussian processes under monotonicity constraints](https://mlsanity.com/paper/2205.08528/) (2022)

## Abstract (arXiv)

Excellent variational approximations to Gaussian process posteriors have been developed which avoid the Oleft(N3right) scaling with dataset size N. They reduce the computational cost to Oleft(NM2right), with Mll N being the number of inducing variables, which summarise the process. While the computational cost seems to be linear in N, the true complexity of the algorithm depends on how M must increase to ensure a certain quality of approximation. We address this by characterising the behavior of an upper bound on the KL divergence to the posterior. We show that with high probability the KL divergence can be made arbitrarily small by growing M more slowly than N. A particular case of interest is that for regression with normally distributed inputs in D-dimensions with the popular Squared Exponential kernel, M=O(logD N) is sufficient. Our results show that as datasets grow, Gaussian process posteriors can truly be approximated cheaply, and provide a concrete rule for how to increase M in continual learning scenarios.