# On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

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

## Key facts

- Cited by 138 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2015.

## Built on by (most cited first, 30 of 138)

- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [On Computation and Generalization of Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2001.02792/) (2020)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime](https://mlsanity.com/paper/2403.08160/) (2024)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Error Bounds for Learning with Vector-Valued Random Features](https://mlsanity.com/paper/2305.17170/) (2023)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Precise Asymptotic Analysis of Deep Random Feature Models](https://mlsanity.com/paper/2302.06210/) (2023)
- [Koopman Kernel Regression](https://mlsanity.com/paper/2305.16215/) (2023)
- [Combining machine learning and data assimilation to forecast dynamical systems from noisy partial observations](https://mlsanity.com/paper/2108.03561/) (2021)
- [Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks](https://mlsanity.com/paper/2109.09304/) (2021)
- [Operator Learning Using Random Features: A Tool for Scientific Computing](https://mlsanity.com/paper/2408.06526/) (2024)
- [Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination](https://mlsanity.com/paper/2206.04734/) (2022)
- [Sampling weights of deep neural networks](https://mlsanity.com/paper/2306.16830/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [A Rainbow in Deep Network Black Boxes](https://mlsanity.com/paper/2305.18512/) (2023)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff](https://mlsanity.com/paper/2305.19008/) (2023)
- [On the expressivity of embedding quantum kernels](https://mlsanity.com/paper/2309.14419/) (2023)
- [Duality for Neural Networks through Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2211.05020/) (2022)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [TransNet: Transferable Neural Networks for Partial Differential Equations](https://mlsanity.com/paper/2301.11701/) (2023)
- [Fundamental limits of overparametrized shallow neural networks for supervised learning](https://mlsanity.com/paper/2307.05635/) (2023)

## Abstract (arXiv)

We show that kernel-based quadrature rules for computing integrals can be seen as a special case of random feature expansions for positive definite kernels, for a particular decomposition that always exists for such kernels. We provide a theoretical analysis of the number of required samples for a given approximation error, leading to both upper and lower bounds that are based solely on the eigenvalues of the associated integral operator and match up to logarithmic terms. In particular, we show that the upper bound may be obtained from independent and identically distributed samples from a specific non-uniform distribution, while the lower bound if valid for any set of points. Applying our results to kernel-based quadrature, while our results are fairly general, we recover known upper and lower bounds for the special cases of Sobolev spaces. Moreover, our results extend to the more general problem of full function approximations (beyond simply computing an integral), with results in L2- and L∞-norm that match known results for special cases. Applying our results to random features, we show an improvement of the number of random features needed to preserve the generalization guarantees for learning with Lipschitz-continuous losses.