mlsanityData to 7 Oct 2026

Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes

arXiv 2106.01121 ↗First posted 2 Jun 2021stat.ML cs.LG math.STcited by 17

Not on the map. Why?

Abstract (arXiv)

We investigate the connections between sparse approximation methods for making kernel methods and Gaussian processes (GPs) scalable to large-scale data, focusing on the Nystr"om method and the Sparse Variational Gaussian Processes (SVGP). While sparse approximation methods for GPs and kernel methods share some algebraic similarities, the literature lacks a deep understanding of how and why they are related. This may pose an obstacle to the communications between the GP and kernel communities, making it difficult to transfer results from one side to the other. Our motivation is to remove this obstacle, by clarifying the connections between the sparse approximations for GPs and kernel methods. In this work, we study the two popular approaches, the Nystr"om and SVGP approximations, in the context of a regression problem, and establish various connections and equivalences between them. In particular, we provide an RKHS interpretation of the SVGP approximation, and show that the Evidence Lower Bound of the SVGP contains the objective function of the Nystr"om approximation, revealing the origin of the algebraic equivalence between the two approaches. We also study recently established convergence results for the SVGP and how they are related to the approximation quality of the Nystr"om method.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 21 of its 66 references that are in the map. First posted on arXiv 2 Jun 2021.

Builds on

21 of 66 references.

References · 21

  1. 2013Gaussian Processes for Big Datacited by 377
  2. 2014Scalable Variational Gaussian Process Classificationcited by 226
  3. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  4. 2015Less is More: Nystr"om Computational Regularizationcited by 89
  5. 2020Kernel methods through the roof: handling billions of points efficientlycited by 88
  6. 2016Variational Fourier features for Gaussian processescited by 85
  7. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 82
  8. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 76
  9. 2016Understanding Probabilistic Sparse Gaussian Process Approximationscited by 68
  10. 2019Rates of Convergence for Sparse Variational Gaussian Process Regressioncited by 62
  11. 2017Bayesian Optimization with Gradientscited by 59
  12. 2019Generalized Variational Inference: Three arguments for deriving new Posteriorscited by 57
9 more
  1. 2015On Sparse variational methods and the Kullback-Leibler divergence between stochastic processescited by 56
  2. 2020Convergence of Sparse Variational Inference in Gaussian Processes Regressioncited by 53
  3. 2015MCMC for Variationally Sparse Gaussian Processescited by 44
  4. 2020Sparse Gaussian Processes with Spherical Harmonic Featurescited by 43
  5. 2020A Tutorial on Sparse Gaussian Processes and Variational Inferencecited by 29
  6. 2020Sparse within Sparse Gaussian Processes using Neighbor Informationcited by 18
  7. 2016Fast DPP Sampling for Nystr"om with Application to Kernel Methodscited by 15
  8. 2020Doubly Sparse Variational Gaussian Processescited by 14
  9. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 2; 2024: 2; 2025: 3; 2026: 1.

17 papers.

Sort:

  1. 2022Accelerated Linearized Laplace Approximation for Bayesian Deep Learningcited by 27
  2. 2023Sampling from Gaussian Process Posteriors using Stochastic Gradient Descentcited by 27
  3. 2022Posterior and Computational Uncertainty in Gaussian Processescited by 23
  4. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  5. 2024Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inferencecited by 8
  6. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  7. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  8. 2022Log-Linear-Time Gaussian Processes Using Binary Tree Kernelscited by 4
  9. 2021Variational Gaussian Processes: A Functional Analysis Viewcited by 3
  10. 2022Gaussian Process Koopman Mode Decompositioncited by 3
  11. 2021Kernel PCA with the Nystr"om methodcited by 2
  12. 2025New Bounds for Sparse Variational Gaussian Processescited by 2
5 more
  1. 2023Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion priorcited by 1
  2. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  3. 2025Gradient-based Sample Selection for Faster Bayesian Optimizationcited by 0
  4. 2025Co-Exploration and Co-Exploitation via Shared Structure in Multi-Task Banditscited by 0
  5. 2026Adaptive Nystr"om for Gaussian Process Regressioncited by 0