# On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature

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

## Key facts

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

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

- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness](https://mlsanity.com/paper/2001.10818/) (2020)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Convergence Guarantees for Adaptive Bayesian Quadrature Methods](https://mlsanity.com/paper/1905.10271/) (2019)
- [Active Multi-Information Source Bayesian Quadrature](https://mlsanity.com/paper/1903.11331/) (2019)
- [Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS](https://mlsanity.com/paper/2005.04832/) (2020)
- [Convergence guarantees for kernel-based quadrature rules in misspecified settings](https://mlsanity.com/paper/1605.07254/) (2016)

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

- [Nested Expectations with Kernel Quadrature](https://mlsanity.com/paper/2502.18284/) (2025)
- [Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization](https://mlsanity.com/paper/2401.05716/) (2024)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

In this paper, we study error bounds for em Bayesian quadrature (BQ), with an emphasis on noisy settings, randomized algorithms, and average-case performance measures. We seek to approximate the integral of functions in a em Reproducing Kernel Hilbert Space (RKHS), particularly focusing on the Mat'ern-nu and squared exponential (SE) kernels, with samples from the function potentially being corrupted by Gaussian noise. We provide a two-step meta-algorithm that serves as a general tool for relating the average-case quadrature error with the L2-function approximation error. When specialized to the Mat'ern kernel, we recover an existing near-optimal error rate while avoiding the existing method of repeatedly sampling points. When specialized to other settings, we obtain new average-case results for settings including the SE kernel with noise and the Mat'ern kernel with misspecification. Finally, we present algorithm-independent lower bounds that have greater generality and/or give distinct proofs compared to existing ones.