mlsanityData to 14 Oct 2026

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

arXiv 2202.04005 ↗First posted 8 Feb 2022cs.LG stat.MLcited by 18

Not on the map. Why?

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.

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

25 of 48 references.

References · 25

  1. 2013Gaussian Processes for Big Datacited by 383
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2018When Gaussian Process Meets Big Data: A Review of Scalable GPscited by 206
  4. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  5. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  6. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  7. 2016GPflow: A Gaussian process library using TensorFlowcited by 140
  8. 2015Less is More: Nystr"om Computational Regularizationcited by 91
  9. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  10. 2019Rates of Convergence for Sparse Variational Gaussian Process Regressioncited by 63
  11. 2015On Sparse variational methods and the Kullback-Leibler divergence between stochastic processescited by 57
  12. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
13 more
  1. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  2. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  3. 2020Convergence of Sparse Variational Inference in Gaussian Processes Regressioncited by 53
  4. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  5. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  6. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  7. 2014Fast Randomized Kernel Methods With Statistical Guaranteescited by 21
  8. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  9. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
  10. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  11. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  12. 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 13
  13. 2018Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spacescited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

18 papers.

Sort:

By area:

  1. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  2. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  3. 2023Delayed Feedback in Kernel Banditscited by 10
  4. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  5. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  6. 2025Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?cited by 5
  7. 2023Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with Online Learningcited by 4
  8. 2025Differentially Private Kernelized Contextual Banditscited by 3
  9. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  10. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 3
  11. 2023Variational Gaussian Processes For Linear Inverse Problemscited by 2
  12. 2023Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion priorcited by 1
6 more
  1. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  2. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1
  3. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  4. 2024Further Understanding of a Local Gaussian Process Approximation: Characterising Convergence in the Finite Regimecited by 0
  5. 2025Variational bagging: a robust approach for Bayesian uncertainty quantificationcited by 0
  6. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0