On the Error of Random Fourier Features

Danica Sutherland Carnegie Mellon University, Jeff Schneider Carnegie Mellon Univ
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:516-525, 2015.

Abstract

Kernel methods give powerful, flexible, and theoretically well-understood approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well-understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding’s variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15j, title = {On the Error of Random {F}ourier Features}, author = {University, Danica Sutherland Carnegie Mellon and Univ, Jeff Schneider Carnegie Mellon}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {516--525}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15j/university15j.pdf}, url = {https://proceedings.mlr.press/r13/university15j.html}, abstract = {Kernel methods give powerful, flexible, and theoretically well-understood approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well-understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding’s variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On the Error of Random Fourier Features %A Danica Sutherland Carnegie Mellon University %A Jeff Schneider Carnegie Mellon Univ %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15j %I PMLR %P 516--525 %U https://proceedings.mlr.press/r13/university15j.html %V R13 %X Kernel methods give powerful, flexible, and theoretically well-understood approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well-understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding’s variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds. %Z Reissued by PMLR on 04 October 2026.
APA
University, D.S.C.M. & Univ, J.S.C.M.. (2015). On the Error of Random Fourier Features. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:516-525 Available from https://proceedings.mlr.press/r13/university15j.html. Reissued by PMLR on 04 October 2026.

Related Material