Random Fourier Features via Fast Surrogate Leverage Weighted Sampling
This work addresses efficiency improvements in kernel methods for machine learning practitioners, but it is incremental as it builds on existing leverage weighted schemes.
The paper tackles the problem of kernel approximation by proposing a fast surrogate leverage weighted sampling strategy for random Fourier features, which reduces time complexity from O(ns^2+s^3) to O(ns^2) while achieving comparable or slightly better prediction performance in kernel ridge regression.
In this paper, we propose a fast surrogate leverage weighted sampling strategy to generate refined random Fourier features for kernel approximation. Compared to the current state-of-the-art method that uses the leverage weighted scheme [Li-ICML2019], our new strategy is simpler and more effective. It uses kernel alignment to guide the sampling process and it can avoid the matrix inversion operator when we compute the leverage function. Given n observations and s random features, our strategy can reduce the time complexity from O(ns^2+s^3) to O(ns^2), while achieving comparable (or even slightly better) prediction performance when applied to kernel ridge regression (KRR). In addition, we provide theoretical guarantees on the generalization performance of our approach, and in particular characterize the number of random features required to achieve statistical guarantees in KRR. Experiments on several benchmark datasets demonstrate that our algorithm achieves comparable prediction performance and takes less time cost when compared to [Li-ICML2019].