# Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 7 May 2026.

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

- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Support points](https://mlsanity.com/paper/1609.01811/) (2016)
- [Stein's Method Meets Computational Statistics: A Review of Some Recent Developments](https://mlsanity.com/paper/2105.03481/) (2021)
- [Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature](https://mlsanity.com/paper/1411.0439/) (2014)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Probabilistic Integration: A Role in Statistical Computation?](https://mlsanity.com/paper/1512.00933/) (2015)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Convergence Guarantees for Adaptive Bayesian Quadrature Methods](https://mlsanity.com/paper/1905.10271/) (2019)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees](https://mlsanity.com/paper/1506.02681/) (2015)
- [Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination](https://mlsanity.com/paper/2206.04734/) (2022)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings](https://mlsanity.com/paper/1709.00147/) (2017)
- [Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithm](https://mlsanity.com/paper/1911.04415/) (2019)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Semi-Exact Control Functionals From Sard's Method](https://mlsanity.com/paper/2002.00033/) (2020)
- [Tight Bounds for Approximate Carath'eodory and Beyond](https://mlsanity.com/paper/1512.08602/) (2015)
- [On the Sampling Problem for Kernel Quadrature](https://mlsanity.com/paper/1706.03369/) (2017)
- [Sparse solutions of the kernel herding algorithm by improved gradient approximation](https://mlsanity.com/paper/2105.07900/) (2021)

## Abstract (arXiv)

Kernel quadrature can exploit RKHS spectral structure and outperform Monte Carlo on smooth integrands, but optimized quadrature weights are generally signed and may be numerically unstable. We study whether spectral acceleration remains possible when the weights are constrained to be positive, i.e., simplex weights. In the exact-target fixed-pool setting, an evaluated i.i.d. candidate pool of size N is already available and the task is to reweight it so as to approximate the kernel mean embedding. We show that this positive reweighting problem is governed not by the equal-weight empirical average, but by the random convex hull generated by the pool. Our main geometric result shows that the mean of a bounded d-dimensional random vector can be approximated by a convex combination of N i.i.d. samples at accuracy O(d/N) with high probability, sharper than equal-weight averaging in the fixed-dimensional regime. We transfer this d-dimensional convex-hull approximation to full RKHS worst-case error through an augmented Mercer-truncation argument. The resulting positive-weight KQ bounds consist of a spectral tail term and a finite-sample convex-hull term, yielding Monte-Carlo-beating rates in favorable spectral regimes, including near-O(1/N) rates up to logarithmic factors under exponential spectral decay. We also provide a constructive Frank--Wolfe algorithm that operates directly on the pool atoms, maintains simplex weights, and admits an explicit optimization-error bound.