# Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 8 Feb 2022.

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

- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [On Sparse variational methods and the Kullback-Leibler divergence between stochastic processes](https://mlsanity.com/paper/1504.07027/) (2015)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Convergence of Sparse Variational Inference in Gaussian Processes Regression](https://mlsanity.com/paper/2008.00323/) (2020)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1803.04371/) (2018)

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

- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with Online Learning](https://mlsanity.com/paper/2309.01730/) (2023)
- [Differentially Private Kernelized Contextual Bandits](https://mlsanity.com/paper/2501.07046/) (2025)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)
- [Variational Gaussian Processes For Linear Inverse Problems](https://mlsanity.com/paper/2311.00663/) (2023)
- [Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion prior](https://mlsanity.com/paper/2310.00097/) (2023)
- [Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2502.07715/) (2025)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [Further Understanding of a Local Gaussian Process Approximation: Characterising Convergence in the Finite Regime](https://mlsanity.com/paper/2404.06200/) (2024)
- [Variational bagging: a robust approach for Bayesian uncertainty quantification](https://mlsanity.com/paper/2511.20594/) (2025)
- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)

## Abstract (arXiv)

Kernel-based models such as kernel ridge regression and Gaussian processes are ubiquitous in machine learning applications for regression and optimization. It is well known that a major downside for kernel-based models is the high computational cost; given a dataset of n samples, the cost grows as O(n3). Existing sparse approximation methods can yield a significant reduction in the computational cost, effectively reducing the actual cost down to as low as O(n) in certain cases. Despite this remarkable empirical success, significant gaps remain in the existing results for the analytical bounds on the error due to approximation. In this work, we provide novel confidence intervals for the Nystr"om method and the sparse variational Gaussian process approximation method, which we establish using novel interpretations of the approximate (surrogate) posterior variance of the models. Our confidence intervals lead to improved performance bounds in both regression and optimization problems.