# Randomized Quasi-Monte Carlo Features for Kernel Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 52 references that are in the map.
- First posted on arXiv 8 Mar 2025.

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

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Kernel Partial Correlation Coefficient -- a Measure of Conditional Dependence](https://mlsanity.com/paper/2012.14804/) (2020)
- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [On the Complexity of Learning with Kernels](https://mlsanity.com/paper/1411.1158/) (2014)
- [How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets](https://mlsanity.com/paper/1411.4000/) (2014)

## Abstract (arXiv)

We investigate the application of randomized quasi-Monte Carlo (RQMC) methods in random feature approximations for kernel-based learning. Compared to the classical Monte Carlo (MC) approach citeprahimi2007random, RQMC improves the deterministic approximation error bound from OP(1/√M) to O(1/M) (up to logarithmic factors), matching the rate achieved by quasi-Monte Carlo (QMC) methods citephuangquasi. Beyond the deterministic error bound guarantee, we further establish additional average error bounds for RQMC features: some requiring weaker assumptions and others significantly reducing the exponent of the logarithmic factor. In the context of kernel ridge regression, we show that RQMC features offer computational advantages over MC features while preserving the same statistical error rate. Empirical results further show that RQMC methods maintain stable performance in both low and moderately high-dimensional settings, unlike QMC methods, which suffer from significant performance degradation as dimension increases.