# Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2014.

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

- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding](https://mlsanity.com/paper/2106.02795/) (2021)
- [Visual Attention Methods in Deep Learning: An In-Depth Survey](https://mlsanity.com/paper/2204.07756/) (2022)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Hermite Polynomial Features for Private Data Generation](https://mlsanity.com/paper/2106.05042/) (2021)
- [Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models](https://mlsanity.com/paper/2210.15458/) (2022)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [DiJiang: Efficient Large Language Models through Compact Kernelization](https://mlsanity.com/paper/2403.19928/) (2024)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [Quantum Adaptive Fourier Features for Neural Density Estimation](https://mlsanity.com/paper/2208.00564/) (2022)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [A spectral mixture representation of isotropic kernels with application to random Fourier features](https://mlsanity.com/paper/2411.02770/) (2024)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)
- [Sampling from Gaussian Processes: A Tutorial and Applications in Global Sensitivity Analysis and Optimization](https://mlsanity.com/paper/2507.14746/) (2025)
- [MetaKernel: Learning Variational Random Features with Limited Labels](https://mlsanity.com/paper/2105.03781/) (2021)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [On the design of scalable, high-precision spherical-radial Fourier features](https://mlsanity.com/paper/2408.13231/) (2024)
- [Towards Unbiased Random Features with Lower Variance For Stationary Indefinite Kernels](https://mlsanity.com/paper/2104.06204/) (2021)
- [Decentralized Online Ensembles of Gaussian Processes for Multi-Agent Systems](https://mlsanity.com/paper/2502.05301/) (2025)
- [Single Image Inpainting and Super-Resolution with Simultaneous Uncertainty Guarantees by Universal Reproducing Kernels](https://mlsanity.com/paper/2506.23221/) (2025)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)

## Abstract (arXiv)

We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead, where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.