# On the Error of Random Fourier Features

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2015.

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

- [Relaxing Equivariance Constraints with Non-stationary Continuous Filters](https://mlsanity.com/paper/2204.07178/) (2022)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Towards a Scalable Reference-Free Evaluation of Generative Models](https://mlsanity.com/paper/2407.02961/) (2024)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Potential and limitations of random Fourier features for dequantizing quantum machine learning](https://mlsanity.com/paper/2309.11647/) (2023)
- [Periodic Activation Functions Induce Stationarity](https://mlsanity.com/paper/2110.13572/) (2021)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Vector-valued Gaussian Processes on Riemannian Manifolds via Gauge Independent Projected Kernels](https://mlsanity.com/paper/2110.14423/) (2021)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Unveiling Differences in Generative Models: A Scalable Differential Clustering Approach](https://mlsanity.com/paper/2405.02700/) (2024)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Federated Causal Discovery from Heterogeneous Data](https://mlsanity.com/paper/2402.13241/) (2024)
- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [PAK-UCB Contextual Bandit: An Online Learning Approach to Prompt-Aware Selection of Generative Models and LLMs](https://mlsanity.com/paper/2410.13287/) (2024)
- [Towards an Explainable Comparison and Alignment of Feature Embeddings](https://mlsanity.com/paper/2506.06231/) (2025)
- [Neural Implicit Dictionary via Mixture-of-Expert Training](https://mlsanity.com/paper/2207.03691/) (2022)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey](https://mlsanity.com/paper/2108.04172/) (2021)
- [Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms](https://mlsanity.com/paper/2401.08260/) (2024)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Random Fourier Features for Asymmetric Kernels](https://mlsanity.com/paper/2209.08461/) (2022)
- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [Exact, Fast and Expressive Poisson Point Processes via Squared Neural Families](https://mlsanity.com/paper/2402.09608/) (2024)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [An Insect-Inspired Randomly, Weighted Neural Network with Random Fourier Features For Neuro-Symbolic Relational Learning](https://mlsanity.com/paper/2109.06663/) (2021)
- [Label Shift Quantification with Robustness Guarantees via Distribution Feature Matching](https://mlsanity.com/paper/2306.04376/) (2023)
- [Dynamic Online Ensembles of Basis Expansions](https://mlsanity.com/paper/2405.01365/) (2024)

## Abstract (arXiv)

Kernel methods give powerful, flexible, and theoretically grounded approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding's variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.