Random features provide a practical framework for large-scale kernel approximation and supervised learning. It has been shown that data-dependent sampling of random features using leverage scores can significantly reduce the number of features required to achieve optimal learning bounds. Leverage scores introduce an optimized distribution for features based on an infinite-dimensional integral operator (depending on input distribution), which is impractical to sample from. Focusing on empirical leverage scores in this paper, we establish an out-of-sample performance bound, revealing an interesting trade-off between the approximated kernel and the eigenvalue decay of another kernel in the domain of random features defined based on data distribution. Our experiments verify that the empirical algorithm consistently outperforms vanilla Monte Carlo sampling, and with a minor modification the method is even competitive to supervised data-dependent kernel learning, without using the output (label) information.

本文通过实证杠杆得分的方式，研究在随机特征的领域中，在核逼近和数据分布之间的权衡，提出一种算法可以有效地减少所需的特征数量，且不需要使用输出信息。实验结果表明，与普通的蒙特卡罗采样相比，该算法始终表现出优势，并且在进行了轻微的修改后，该算法在没有使用输出（标签）信息的情况下与监督的数据相关核学习方法相当竞争力。

从经验杠杆得分中采样随机特征：实现和理论保证