Random Fourier Features via Fast Surrogate Leverage Weighted Sampling
Random Fourier Features via Fast Surrogate Leverage Weighted Sampling
复制标题
DOI：
10.1609/aaai.v34i04.5920
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Fanghui Liu;Xiaolin Huang;Yudong Chen;Jie Yang;J. Suykens
中科院分区：
文献类型：
--
作者：
Fanghui Liu;Xiaolin Huang;Yudong Chen;Jie Yang;J. Suykens
在本文中，我们提出了一种快速代理杠杆加权采样策略来生成用于核近似的精细随机傅立叶特征。与当前使用杠杆加权方案[Li-ICML2019]的最先进方法相比，我们的新策略更简单、更有效。它使用核对齐来指导采样过程，并且可以在计算杠杆函数时避免矩阵求逆运算符。给定 n 个观测值和 s 个随机特征，我们的策略可以将时间复杂度从 O(ns^2+s^3) 降低到 O(ns^2)，同时在应用于核岭回归 (KRR) 时实现可比（甚至稍好）的预测性能。此外，我们为我们的方法的泛化性能提供了理论保证，特别是描述了在 KRR 中实现统计保证所需的随机特征的数量。对多个基准数据集的实验表明，与 [Li-ICML2019] 相比，我们的算法实现了可比的预测性能，并且花费的时间成本更少。
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].