# Error Estimation for Random Fourier Features

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 23 of 23)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Randomized Nonlinear Component Analysis](https://mlsanity.com/paper/1402.0119/) (2014)
- [FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test](https://mlsanity.com/paper/1405.2664/) (2014)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Recycling Randomness with Structure for Sublinear time Kernel Expansions](https://mlsanity.com/paper/1605.09049/) (2016)
- [Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation](https://mlsanity.com/paper/1811.00155/) (2018)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Statistical properties of sketching algorithms](https://mlsanity.com/paper/1706.03665/) (2017)
- [Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap](https://mlsanity.com/paper/1803.08021/) (2018)
- [A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication](https://mlsanity.com/paper/1708.01945/) (2017)
- [Error Estimation for Sketched SVD via the Bootstrap](https://mlsanity.com/paper/2003.04937/) (2020)
- [Bootstrapping the Operator Norm in High Dimensions: Error Estimation for Covariance Matrices and Sketching](https://mlsanity.com/paper/1909.06120/) (2019)
- [Wind Field Reconstruction with Adaptive Random Fourier Features](https://mlsanity.com/paper/2102.02365/) (2021)
- [Diffusion Maps meet Nystr"om](https://mlsanity.com/paper/1802.08762/) (2018)

## Built on by (most cited first, 1 of 1)

- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)

## Abstract (arXiv)

Random Fourier Features (RFF) is among the most popular and broadly applicable approaches for scaling up kernel methods. In essence, RFF allows the user to avoid costly computations on a large kernel matrix via a fast randomized approximation. However, a pervasive difficulty in applying RFF is that the user does not know the actual error of the approximation, or how this error will propagate into downstream learning tasks. Up to now, the RFF literature has primarily dealt with these uncertainties using theoretical error bounds, but from a user's standpoint, such results are typically impractical -- either because they are highly conservative or involve unknown quantities. To tackle these general issues in a data-driven way, this paper develops a bootstrap approach to numerically estimate the errors of RFF approximations. Three key advantages of this approach are: (1) The error estimates are specific to the problem at hand, avoiding the pessimism of worst-case bounds. (2) The approach is flexible with respect to different uses of RFF, and can even estimate errors in downstream learning tasks. (3) The approach enables adaptive computation, so that the user can quickly inspect the error of a rough initial kernel approximation and then predict how much extra work is needed. Lastly, in exchange for all of these benefits, the error estimates can be obtained at a modest computational cost.