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.

本文通过研究谱矩阵近似的角度，给出了随机傅里叶特征的数量界和核岭回归的统计保障，而从核的杠杆函数中改进傅里叶空间的分布采样可获得提高的性能与更优的采样方案。