mlsanityData to 7 Oct 2026

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

arXiv 1502.06800 ↗First posted 24 Feb 2015cs.LG cs.NA math.NAcited by 136

Not on the map. Why?

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.

Key facts. Cited by 136 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Feb 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 25; 2022: 20; 2023: 29; 2024: 19; 2025: 19; 2026: 23.

136 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  2. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  3. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  4. 2021Learning with invariances in random features and kernel modelscited by 89
  5. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  6. 2022Information Theory with Kernel Methodscited by 37
  7. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  8. 2020On Computation and Generalization of Generative Adversarial Imitation Learningcited by 27
  9. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  10. 2021Positively Weighted Kernel Quadrature via Subsamplingcited by 25
  11. 2023Error Bounds for Learning with Vector-Valued Random Featurescited by 23
  12. 2023Precise Asymptotic Analysis of Deep Random Feature Modelscited by 22
38 more
  1. 2023Koopman Kernel Regressioncited by 22
  2. 2024Asymptotics of Random Feature Regression Beyond the Linear Scaling Regimecited by 22
  3. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  4. 2022Nystr"om Kernel Mean Embeddingscited by 21
  5. 2024Operator Learning Using Random Features: A Tool for Scientific Computingcited by 21
  6. 2021Combining machine learning and data assimilation to forecast dynamical systems from noisy partial observationscited by 20
  7. 2022Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombinationcited by 20
  8. 2023Sampling weights of deep neural networkscited by 20
  9. 2023Six Lectures on Linearized Neural Networkscited by 19
  10. 2023A Rainbow in Deep Network Black Boxescited by 18
  11. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 17
  12. 2023Sampling-based Nystr"om Approximation and Kernel Quadraturecited by 17
  13. 2023Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoffcited by 17
  14. 2023On the expressivity of embedding quantum kernelscited by 17
  15. 2022Duality for Neural Networks through Reproducing Kernel Banach Spacescited by 15
  16. 2021The Separation Capacity of Random Neural Networkscited by 14
  17. 2023TransNet: Transferable Neural Networks for Partial Differential Equationscited by 13
  18. 2022HARFE: Hard-Ridge Random Feature Expansioncited by 12
  19. 2023Fundamental limits of overparametrized shallow neural networks for supervised learningcited by 12
  20. 2023Universal approximation property of Banach space-valued random feature models including random neural networkscited by 12
  21. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 12
  22. 2023Kernel quadrature with randomly pivoted Choleskycited by 11
  23. 2021Accumulation of Sub-Sampling Matrices with Applications to Statistical Computationcited by 10
  24. 2022Random Feature Models for Learning Interacting Dynamical Systemscited by 10
  25. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
  26. 2025Weighted quantization using MMD: From mean field to mean shift via gradient flowscited by 10
  27. 2021Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimescited by 9
  28. 2022Minimax risk classifiers with 0-1 losscited by 9
  29. 2022Causal Inference with Treatment Measurement Error: A Nonparametric Instrumental Variable Approachcited by 9
  30. 2021On Energy-Based Models with Overparametrized Shallow Neural Networkscited by 8
  31. 2021Nonparametric adaptive control and prediction: theory and randomized algorithmscited by 8
  32. 2024Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inferencecited by 8
  33. 2025Kernel ridge regression under power-law data: spectrum and generalizationcited by 8
  34. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  35. 2021Reliable Estimation of KL Divergence using a Discriminator in Reproducing Kernel Hilbert Spacecited by 7
  36. 2021Conditioning of Random Feature Matrices: Double Descent and Generalization Errorcited by 7
  37. 2024Nonlinear functional regression by functional deep neural network with kernel embeddingcited by 7
  38. 2024Fast Kernel Summation in High Dimensions via Slicing and Fourier Transformscited by 7

50 most cited of 136 All 136 (JSON)