2018/10/09 by Raj Agrawal, Trevor Campbell, Agrawal, Raj +5 · 5 citations
Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1810.04249
openalex publication_date 2018/10/09 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
Kernel methods offer the flexibility to learn complex relationships in\nmodern, large data sets while enjoying strong theoretical guarantees on\nquality. Unfortunately, these methods typically require cubic running time in\nthe data set size, a prohibitive cost in the large-data setting. Random feature\nmaps (RFMs) and the Nystrom method both consider low-rank approximations to the\nkernel matrix as a potential solution. But, in order to achieve desirable\ntheoretical guarantees, the former may require a prohibitively large number of\nfeatures J+, and the latter may be prohibitively expensive for high-dimensional\nproblems. We propose to combine the simplicity and generality of RFMs with a\ndata-dependent feature selection scheme to achieve desirable theoretical\napproximation properties of Nystrom with just O(log J+) features. Our key\ninsight is to begin with a large set of random features, then reduce them to a\nsmall number of weighted features in a data-dependent, computationally\nefficient way, while preserving the statistical guarantees of using the\noriginal large set of features. We demonstrate the efficacy of our method with\ntheory and experiments--including on a data set with over 50 million\nobservations. In particular, we show that our method achieves small kernel\nmatrix approximation error and better test set accuracy with provably fewer\nrandom features than state-of-the-art methods.\n