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.

本文介绍了核方法在机器学习问题中的应用，提到了采用随机傅里叶特征解决大规模数据集问题的方法，并给出了更好的误差界限及嵌入方式的理解、近似误差、在某些机器学习方法中的使用，同时指出了该特征的两种变体中，更常用的一种在高斯核中具有严格更高的方差且具有更糟糕的界限的令人惊讶的事实。