On the Error of Random Fourier Features
This work addresses scalability issues in kernel methods for large datasets, providing theoretical insights that could impact practitioners using random Fourier features, though it appears incremental as it builds on prior bounds.
The paper tackles the problem of understanding the approximation quality of random Fourier features for kernel methods, improving the uniform error bound and analyzing variance and approximation error, revealing that the more widely used variant has higher variance and worse bounds for the Gaussian kernel.
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.