  Kernel methods offer the flexibility to learn complex relationships in
modern, large data sets while enjoying strong theoretical guarantees on
quality. Unfortunately, these methods typically require cubic running time in
the data set size, a prohibitive cost in the large-data setting. Random feature
maps (RFMs) and the Nystrom method both consider low-rank approximations to the
kernel matrix as a potential solution. But, in order to achieve desirable
theoretical guarantees, the former may require a prohibitively large number of
features J+, and the latter may be prohibitively expensive for high-dimensional
problems. We propose to combine the simplicity and generality of RFMs with a
data-dependent feature selection scheme to achieve desirable theoretical
approximation properties of Nystrom with just O(log J+) features. Our key
insight is to begin with a large set of random features, then reduce them to a
small number of weighted features in a data-dependent, computationally
efficient way, while preserving the statistical guarantees of using the
original large set of features. We demonstrate the efficacy of our method with
theory and experiments--including on a data set with over 50 million
observations. In particular, we show that our method achieves small kernel
matrix approximation error and better test set accuracy with provably fewer
random features than state-of-the-art methods.
