mlsanityData to 7 Oct 2026

Rates of Convergence for Sparse Variational Gaussian Process Regression

arXiv 1903.03571 ↗First posted 8 Mar 2019stat.ML cs.LGcited by 62

Not on the map. Why?

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.

Key facts. Cited by 62 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Mar 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 14; 2023: 9; 2024: 9; 2025: 8; 2026: 3.

62 papers.

Sort:

  1. 2021On Feature Collapse and Deep Kernel Learning for Single Forward Pass Uncertaintycited by 87
  2. 2021On the Practicality of Deterministic Epistemic Uncertaintycited by 62
  3. 2023Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisationcited by 32
  4. 2022Accelerated Linearized Laplace Approximation for Bayesian Deep Learningcited by 27
  5. 2021Deep Neural Networks as Point Estimates for Deep Gaussian Processescited by 26
  6. 2021Conditioning Sparse Variational Gaussian Processes for Online Decision-makingcited by 23
  7. 2022Posterior and Computational Uncertainty in Gaussian Processescited by 23
  8. 2022Additive Gaussian Processes Revisitedcited by 19
  9. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  10. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
  11. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 17
  12. 2022Markovian Gaussian Process Variational Autoencoderscited by 16
38 more
  1. 2021Bias-Free Scalable Gaussian Processes via Randomized Truncationscited by 15
  2. 2025Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spacescited by 13
  3. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  4. 2021Sparse Algorithms for Markovian Gaussian Processescited by 10
  5. 2022Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlationscited by 10
  6. 2021Scalable Variational Gaussian Processes via Harmonic Kernel Decompositioncited by 8
  7. 2021Adaptive Inducing Points Selection For Gaussian Processescited by 8
  8. 2022Variational Nearest Neighbor Gaussian Processcited by 8
  9. 2024Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inferencecited by 8
  10. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  11. 2021Combining Pseudo-Point and State Space Approximations for Sum-Separable Gaussian Processescited by 7
  12. 2021Fast and Scalable Spike and Slab Variable Selection in High-Dimensional Gaussian Processescited by 7
  13. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  14. 2025Koopman-Equivariant Gaussian Processescited by 6
  15. 2022Information-theoretic Inducing Point Placement for High-throughput Bayesian Optimisationcited by 5
  16. 2022Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Treescited by 5
  17. 2021Lightweight Distributed Gaussian Process Regression for Online Machine Learningcited by 4
  18. 2022High-dimensional additive Gaussian processes under monotonicity constraintscited by 4
  19. 2023Actually Sparse Variational Gaussian Processescited by 4
  20. 2024Multi-fidelity Gaussian process surrogate modeling for regression problems in physicscited by 4
  21. 2025Verification and Validation for Trustworthy Scientific Machine Learningcited by 4
  22. 2021Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefitscited by 3
  23. 2022Memory Safe Computations with XLA Compilercited by 3
  24. 2023On the Size and Approximation Error of Distilled Setscited by 3
  25. 2023Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processescited by 3
  26. 2024On Uncertainty Quantification for Near-Bayes Optimal Algorithmscited by 3
  27. 2023Variational Gaussian Processes For Linear Inverse Problemscited by 2
  28. 2024Recommendations for Baselines and Benchmarking Approximate Gaussian Processescited by 2
  29. 2025Recurrent Memory for Online Interdomain Gaussian Processescited by 2
  30. 2021Gaussian Experts Selection using Graphical Modelscited by 1
  31. 2021On MCMC for variationally sparse Gaussian processes: A pseudo-marginal approachcited by 1
  32. 2021Machine Learning based optimization for interval uncertainty propagationcited by 1
  33. 2021Modular Gaussian Processes for Transfer Learningcited by 1
  34. 2023Efficient Sensor Placement from Regression with Sparse Gaussian Processes in Continuous and Discrete Spacescited by 1
  35. 2023Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion priorcited by 1
  36. 2024Adjusting Model Size in Continual Gaussian Processes: How Big is Big Enough?cited by 1
  37. 2025Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Methodcited by 1
  38. 2021Wasserstein-Splitting Gaussian Process Regression for Heterogeneous Online Bayesian Inferencecited by 0

50 most cited of 62 All 62 (JSON)