# Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

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

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2018.

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

- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks](https://mlsanity.com/paper/2109.09304/) (2021)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Universal approximation property of Banach space-valued random feature models including random neural networks](https://mlsanity.com/paper/2312.08410/) (2023)
- [PAK-UCB Contextual Bandit: An Online Learning Approach to Prompt-Aware Selection of Generative Models and LLMs](https://mlsanity.com/paper/2410.13287/) (2024)
- [No-Regret Algorithms for Private Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2102.12467/) (2021)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Learning Counterfactually Invariant Predictors](https://mlsanity.com/paper/2207.09768/) (2022)
- [Localized Contrastive Learning on Graphs](https://mlsanity.com/paper/2212.04604/) (2022)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)
- [Concentration of Random Feature Matrices in High-Dimensions](https://mlsanity.com/paper/2204.06935/) (2022)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Overparameterized random feature regression with nearly orthogonal data](https://mlsanity.com/paper/2211.06077/) (2022)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [Random Features for the Neural Tangent Kernel](https://mlsanity.com/paper/2104.01351/) (2021)
- [Bridging the reality gap in quantum devices with physics-aware machine learning](https://mlsanity.com/paper/2111.11285/) (2021)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)

## Abstract (arXiv)

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression. Qualitatively, our results are twofold: on the one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of low-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.