Towards a Unified Analysis of Random Fourier Features
Towards a Unified Analysis of Random Fourier Features
复制标题
DOI：
--
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Zhu Li;Jean-Francois Ton;Dino Oglic;D. Sejdinovic
中科院分区：
文献类型：
--
作者：
Zhu Li;Jean-Francois Ton;Dino Oglic;D. Sejdinovic
随机傅立叶特征是一种应用广泛、简单有效的核方法扩展技术。然而，该方法的现有理论分析仍然集中在特定的学习任务上，并且通常给出与实证结果不一致的悲观界限。我们解决了这些问题，并使用平方误差和Lipschitz连续损失函数提供了第一个统一的具有随机傅立叶特征的学习风险分析。在我们的边界中，计算成本和预期风险收敛率之间的权衡是特定于问题的，并以正则化参数和\emph{有效自由度的数量}表示。我们研究了标准的随机傅立叶特征方法，该方法改进了保证核脊回归的相应的极大极小风险收敛率所需的特征数量的现有界限，以及一种数据相关的修改，该修改将特征与\emph{脊杠杆分数}成比例地采样，并进一步减少所需的特征数量。由于脊杠杆分数计算成本高，我们设计了一种简单的近似方案，可证明在不损失统计效率的情况下降低了计算成本。
Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems and provide the first unified risk analysis of learning with random Fourier features using the squared error and Lipschitz continuous loss functions. In our bounds, the trade-off between the computational cost and the expected risk convergence rate is problem specific and expressed in terms of the regularization parameter and the \emph{number of effective degrees of freedom}. We study both the standard random Fourier features method for which we improve the existing bounds on the number of features required to guarantee the corresponding minimax risk convergence rate of kernel ridge regression, as well as a data-dependent modification which samples features proportional to \emph{ridge leverage scores} and further reduces the required number of features. As ridge leverage scores are expensive to compute, we devise a simple approximation scheme which provably reduces the computational cost without loss of statistical efficiency.