On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
This work addresses the challenge of scalable kernel methods for machine learning practitioners, offering an incremental improvement over existing data-dependent sampling techniques.
The paper tackles the problem of efficiently sampling random features for kernel approximation by using empirical leverage scores, establishing an out-of-sample performance bound that reveals a trade-off between kernel approximation and eigenvalue decay. Experiments show the method consistently outperforms vanilla Monte Carlo sampling and, with a minor modification, is competitive with supervised kernel learning without using label information.
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.