# Optimal Rates for Random Fourier Features

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

## Key facts

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

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

- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [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)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [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)
- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [Causal Inference with Treatment Measurement Error: A Nonparametric Instrumental Variable Approach](https://mlsanity.com/paper/2206.09186/) (2022)
- [The Representation Jensen-Shannon Divergence](https://mlsanity.com/paper/2305.16446/) (2023)
- [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)
- [Bridging the reality gap in quantum devices with physics-aware machine learning](https://mlsanity.com/paper/2111.11285/) (2021)
- [SRMD: Sparse Random Mode Decomposition](https://mlsanity.com/paper/2204.06108/) (2022)
- [Maximum Mean Discrepancy on Exponential Windows for Online Change Detection](https://mlsanity.com/paper/2205.12706/) (2022)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [A spectral mixture representation of isotropic kernels with application to random Fourier features](https://mlsanity.com/paper/2411.02770/) (2024)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Random Feature Representation Boosting](https://mlsanity.com/paper/2501.18283/) (2025)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [A Temporal Kernel Approach for Deep Learning with Continuous-time Information](https://mlsanity.com/paper/2103.15213/) (2021)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [Graph-Aided Online Multi-Kernel Learning](https://mlsanity.com/paper/2102.04690/) (2021)
- [Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features](https://mlsanity.com/paper/2106.02614/) (2021)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [On the design of scalable, high-precision spherical-radial Fourier features](https://mlsanity.com/paper/2408.13231/) (2024)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)

## Abstract (arXiv)

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives due to their capability to represent and model complex relations. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices. In order to mitigate this serious computational limitation, recently randomized constructions have been proposed in the literature, which allow the application of fast linear algorithms. Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels. Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this paper, we provide a detailed finite-sample theoretical analysis about the approximation quality of RFFs by (i) establishing optimal (in terms of the RFF dimension, and growing set size) performance guarantees in uniform norm, and (ii) presenting guarantees in Lr (1≤ r<∞) norms. We also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.