@article{10.1145/2611378,
author = {Lin, Ming and Weng, Shifeng and Zhang, Changshui},
title = {On the Sample Complexity of Random Fourier Features for Online Learning: How Many Random Fourier Features Do We Need?},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2611378},
doi = {10.1145/2611378},
abstract = {We study the sample complexity of random Fourier features for online kernel learning—that
is, the number of random Fourier features required to achieve good generalization
performance. We show that when the loss function is strongly convex and smooth, online
kernel learning with random Fourier features can achieve an O(log T /T) bound for
the excess risk with only O(1/λ2) random Fourier features, where T is the number of
training examples and λ is the modulus of strong convexity. This is a significant
improvement compared to the existing result for batch kernel learning that requires
O(T) random Fourier features to achieve a generalization bound O(1/√T). Our empirical
study verifies that online kernel learning with a limited number of random Fourier
features can achieve similar generalization performance as online learning using full
kernel matrix. We also present an enhanced online learning algorithm with random Fourier
features that improves the classification performance by multiple passes of training
examples and a partial average.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {13},
numpages = {19},
keywords = {sampling complexity, kernel learning, Nystr\"{o}m}
}