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

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

## Key facts

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

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

- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Scalable Variational Gaussian Process Classification](https://mlsanity.com/paper/1411.2005/) (2014)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Understanding Probabilistic Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1606.04820/) (2016)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Bayesian Optimization with Gradients](https://mlsanity.com/paper/1703.04389/) (2017)
- [On Sparse variational methods and the Kullback-Leibler divergence between stochastic processes](https://mlsanity.com/paper/1504.07027/) (2015)
- [Generalized Variational Inference: Three arguments for deriving new Posteriors](https://mlsanity.com/paper/1904.02063/) (2019)
- [Convergence of Sparse Variational Inference in Gaussian Processes Regression](https://mlsanity.com/paper/2008.00323/) (2020)
- [MCMC for Variationally Sparse Gaussian Processes](https://mlsanity.com/paper/1506.04000/) (2015)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [A Tutorial on Sparse Gaussian Processes and Variational Inference](https://mlsanity.com/paper/2012.13962/) (2020)
- [Sparse within Sparse Gaussian Processes using Neighbor Information](https://mlsanity.com/paper/2011.05041/) (2020)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [Doubly Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2001.05363/) (2020)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)

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

- [Accelerated Linearized Laplace Approximation for Bayesian Deep Learning](https://mlsanity.com/paper/2210.12642/) (2022)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Log-Linear-Time Gaussian Processes Using Binary Tree Kernels](https://mlsanity.com/paper/2210.01633/) (2022)
- [Variational Gaussian Processes: A Functional Analysis View](https://mlsanity.com/paper/2110.12798/) (2021)
- [Gaussian Process Koopman Mode Decomposition](https://mlsanity.com/paper/2209.04111/) (2022)
- [Kernel PCA with the Nystr"om method](https://mlsanity.com/paper/2109.05578/) (2021)
- [New Bounds for Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2502.08730/) (2025)
- [Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion prior](https://mlsanity.com/paper/2310.00097/) (2023)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [Gradient-based Sample Selection for Faster Bayesian Optimization](https://mlsanity.com/paper/2504.07742/) (2025)
- [Co-Exploration and Co-Exploitation via Shared Structure in Multi-Task Bandits](https://mlsanity.com/paper/2512.12693/) (2025)
- [Adaptive Nystr"om for Gaussian Process Regression](https://mlsanity.com/paper/2607.27427/) (2026)

## 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.