On the Error of Random Fourier Features

By Danica J. Sutherland, Jeff Schneider. 2015

217 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistics and Probability, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistics and Probability

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “Theoretical results on the preservation of kernel evaluation can be found in, e.g., Sutherland and Schneider (2015) and Sriperumbudur and Szabo (2015).”
The Geometry of Random Features (2018, background): “There has been much recent work in understanding the errors incurred by random feature approximations (Sutherland and Schneider, 2015), and in speeding up the computation of the random embeddings (Le et al., 2013).”
Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery (2017, methodology): “…mild conditions because we can guarantee that ) denotes the estimate of E ( f (cid:48) j | Z ) by kernel ridge regression; this holds so long as we choose d large enough for g ( Z ) (see Section 3.1 of (Sutherland and Schneider, 2015); the argument is complex and beyond the scope of this paper).”
Domain Generalization by Marginal Transfer Learning (2017, result): “There are recent developments that give faster rates for approximation quality of random Fourier features and could potentially be combined with our analysis (Sriperumbudur and Szabó, 2015; Sutherland and Schneider, 2015).”
Bayesian Nonparametric Kernel-Learning (2015, background): “For the applications we consider we only need real-valued kernels, hence we approximate the real part of (4): where again ϕ ( x ) An application of the random feature approximation bounds found in [18, 14, 25] yields that: Proposition 2.2.”
Large-scale kernel methods for independence testing (2016, result): “It is worth noting that the analysis of convergence of such estimator can possibly be done similarly to the analysis by Sutherland and Schneider (2015) forMMD.”