# Convergence of Sparse Variational Inference in Gaussian Processes Regression

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2020.

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

- [The Promises and Pitfalls of Deep Kernel Learning](https://mlsanity.com/paper/2102.12108/) (2021)
- [CiteME: Can Language Models Accurately Cite Scientific Claims?](https://mlsanity.com/paper/2407.12861/) (2024)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [SigGPDE: Scaling Sparse Gaussian Processes on Sequential Data](https://mlsanity.com/paper/2105.04211/) (2021)
- [Last Layer Marginal Likelihood for Invariance Learning](https://mlsanity.com/paper/2106.07512/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [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)
- [Robust Uncertainty Bounds in Reproducing Kernel Hilbert Spaces: A Convex Optimization Approach](https://mlsanity.com/paper/2104.09582/) (2021)
- [Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression](https://mlsanity.com/paper/2201.06314/) (2022)
- [Memory-Based Dual Gaussian Processes for Sequential Learning](https://mlsanity.com/paper/2306.03566/) (2023)
- [COMO: Compact Mapping and Odometry](https://mlsanity.com/paper/2404.03531/) (2024)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Scalable Bayesian Optimization via Focalized Sparse Gaussian Processes](https://mlsanity.com/paper/2412.20375/) (2024)
- [Continuous Bayesian Model Selection for Multivariate Causal Discovery](https://mlsanity.com/paper/2411.10154/) (2024)
- [Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees](https://mlsanity.com/paper/2210.07893/) (2022)
- [Gaussian Processes on Hypergraphs](https://mlsanity.com/paper/2106.01982/) (2021)
- [Memory Safe Computations with XLA Compiler](https://mlsanity.com/paper/2206.14148/) (2022)
- [Sparse Gaussian Process Hyperparameters: Optimize or Integrate?](https://mlsanity.com/paper/2211.02476/) (2022)
- [Fast post-process Bayesian inference with Variational Sparse Bayesian Quadrature](https://mlsanity.com/paper/2303.05263/) (2023)
- [Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processes](https://mlsanity.com/paper/2308.14142/) (2023)
- [B'ezier Gaussian Processes for Tall and Wide Data](https://mlsanity.com/paper/2209.00343/) (2022)
- [Evaluation of machine learning architectures on the quantification of epistemic and aleatoric uncertainties in complex dynamical systems](https://mlsanity.com/paper/2306.15159/) (2023)
- [Gradient and Uncertainty Enhanced Sequential Sampling for Global Fit](https://mlsanity.com/paper/2310.00110/) (2023)
- [Recommendations for Baselines and Benchmarking Approximate Gaussian Processes](https://mlsanity.com/paper/2402.09849/) (2024)
- [New Bounds for Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2502.08730/) (2025)
- [Efficient Transformed Gaussian Process State-Space Models for Non-Stationary High-Dimensional Dynamical Systems](https://mlsanity.com/paper/2503.18309/) (2025)
- [Adaptive sparse variational approximations for Gaussian process regression](https://mlsanity.com/paper/2504.03321/) (2025)
- [Bayesian Data Sketching for Varying Coefficient Regression Models](https://mlsanity.com/paper/2506.00270/) (2025)
- [Bayesian-LoRA: Probabilistic Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2601.21003/) (2026)

## Abstract (arXiv)

Gaussian processes are distributions over functions that are versatile and mathematically convenient priors in Bayesian modelling. However, their use is often impeded for data with large numbers of observations, N, due to the cubic (in N) cost of matrix operations used in exact inference. Many solutions have been proposed that rely on M ll N inducing variables to form an approximation at a cost of O(NM2). While the computational cost appears linear in N, the true complexity depends on how M must scale with N to ensure a certain quality of the approximation. In this work, we investigate upper and lower bounds on how M needs to grow with N to ensure high quality approximations. We show that we can make the KL-divergence between the approximate model and the exact posterior arbitrarily small for a Gaussian-noise regression model with Mll N. Specifically, for the popular squared exponential kernel and D-dimensional Gaussian distributed covariates, M=O((log N)D) suffice and a method with an overall computational cost of O(N(log N)2D(loglog N)2) can be used to perform inference.