Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
复制标题
DOI：
--
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Tianbao Yang;Yu-Feng Li;M. Mahdavi;Rong Jin;Zhi-Hua Zhou
中科院分区：
文献类型：
--
作者：
Tianbao Yang;Yu-Feng Li;M. Mahdavi;Rong Jin;Zhi-Hua Zhou
随机傅立叶特征和Nystrom方法都被成功地应用于有效的核学习。在这项工作中，我们研究了这两种方法的根本差异，以及这种差异如何影响它们的泛化性能。与基于随机傅立叶特征的方法不同，其中基函数(即，余弦和正弦函数)是从独立于训练数据的分布中采样的，而Nystrom方法使用的基函数是从训练样本中随机采样的，因此是数据相关的。通过对这一差异的探讨，我们发现当核矩阵的特征谱有较大的间隙时，基于Nystrom方法的方法比基于随机傅立叶特征的方法可以得到更好的推广误差界。我们在广泛的大型数据集上实证验证了我们的理论发现。
Both random Fourier features and the Nystrom method have been successfully applied to efficient kernel learning. In this work, we investigate the fundamental difference between these two approaches, and how the difference could affect their generalization performances. Unlike approaches based on random Fourier features where the basis functions (i.e., cosine and sine functions) are sampled from a distribution independent from the training data, basis functions used by the Nystrom method are randomly sampled from the training examples and are therefore data dependent. By exploring this difference, we show that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based on the Nystrom method can yield impressively better generalization error bound than random Fourier features based approach. We empirically verify our theoretical findings on a wide range of large data sets.