mlsanityData to 7 Oct 2026

On the Error of Random Fourier Features

arXiv 1506.02785 ↗First posted 9 Jun 2015cs.LG stat.MLcited by 76

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 8; 2023: 10; 2024: 18; 2025: 13; 2026: 13.

76 papers.

Sort:

By area:

  1. 2022Relaxing Equivariance Constraints with Non-stationary Continuous Filterscited by 41
  2. 2023Sampling from Gaussian Process Posteriors using Stochastic Gradient Descentcited by 27
  3. 2024Towards a Scalable Reference-Free Evaluation of Generative Modelscited by 25
  4. 2021Generalization Bounds for Sparse Random Feature Expansionscited by 22
  5. 2023Potential and limitations of random Fourier features for dequantizing quantum machine learningcited by 22
  6. 2021Periodic Activation Functions Induce Stationaritycited by 21
  7. 2022Chefs' Random Tables: Non-Trigonometric Random Featurescited by 20
  8. 2021Vector-valued Gaussian Processes on Riemannian Manifolds via Gauge Independent Projected Kernelscited by 19
  9. 2024Unveiling Differences in Generative Models: A Scalable Differential Clustering Approachcited by 16
  10. 2021Bias-Free Scalable Gaussian Processes via Randomized Truncationscited by 15
  11. 2024Federated Causal Discovery from Heterogeneous Datacited by 15
  12. 2021On Learning the Transformer Kernelcited by 14
38 more
  1. 2023Compress Then Test: Powerful Kernel Testing in Near-linear Timecited by 14
  2. 2021Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learningcited by 13
  3. 2024Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physicscited by 12
  4. 2022Improved Random Features for Dot Product Kernelscited by 11
  5. 2024PAK-UCB Contextual Bandit: An Online Learning Approach to Prompt-Aware Selection of Generative Models and LLMscited by 11
  6. 2022Neural Implicit Dictionary via Mixture-of-Expert Trainingcited by 9
  7. 2023Random Fourier Signature Featurescited by 9
  8. 2025Towards an Explainable Comparison and Alignment of Feature Embeddingscited by 9
  9. 2021Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Surveycited by 8
  10. 2021Quantization Algorithms for Random Fourier Featurescited by 7
  11. 2022Random Fourier Features for Asymmetric Kernelscited by 7
  12. 2024Fast Kernel Summation in High Dimensions via Slicing and Fourier Transformscited by 7
  13. 2024Fast Summation of Radial Kernels via QMC Slicingcited by 7
  14. 2024Exact, Fast and Expressive Poisson Point Processes via Squared Neural Familiescited by 6
  15. 2021Gauss-Legendre Features for Gaussian Process Regressioncited by 5
  16. 2021An Insect-Inspired Randomly, Weighted Neural Network with Random Fourier Features For Neuro-Symbolic Relational Learningcited by 5
  17. 2023Label Shift Quantification with Robustness Guarantees via Distribution Feature Matchingcited by 5
  18. 2024Dynamic Online Ensembles of Basis Expansionscited by 5
  19. 2024Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processescited by 5
  20. 2023FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Featurescited by 4
  21. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  22. 2021A Temporal Kernel Approach for Deep Learning with Continuous-time Informationcited by 3
  23. 2021Sharp Analysis of Random Fourier Features in Classificationcited by 3
  24. 2021Representing Prior Knowledge Using Randomly, Weighted Feature Networks for Visual Relationship Detectioncited by 3
  25. 2022Transparent Single-Cell Set Classification with Kernel Mean Embeddingscited by 3
  26. 2023On the Size and Approximation Error of Distilled Setscited by 3
  27. 2024Random Features Approximation for Control-Affine Systemscited by 3
  28. 2024Deep Nonparametric Conditional Independence Tests for Imagescited by 3
  29. 2025dynoGP: Deep Gaussian Processes for dynamic system identificationcited by 3
  30. 2025Sampling from Gaussian Processes: A Tutorial and Applications in Global Sensitivity Analysis and Optimizationcited by 3
  31. 2021Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Featurescited by 2
  32. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  33. 2023Linear-scaling kernels for protein sequences and small molecules outperform deep learning while providing uncertainty quantitation and improved interpretabilitycited by 2
  34. 2024On the design of scalable, high-precision spherical-radial Fourier featurescited by 2
  35. 2025F-StrIPE: Fast Structure-Informed Positional Encoding for Symbolic Music Generationcited by 2
  36. 2026KODA: Contrastive Representation Comparison and Alignment for Vision-Language Foundation Modelscited by 2
  37. 2022Provably Reliable Large-Scale Sampling from Gaussian Processescited by 1
  38. 2023Error Estimation for Random Fourier Featurescited by 1

50 most cited of 76 All 76 (JSON)