Timezone: »
Poster
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Haim Avron · Michael Kapralov · Cameron Musco · Christopher Musco · Ameya Velingker · Amir Zandieh
Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression.
[
PDF]
[
Summary/Notes]
Summary/Notes]
Author Information
Haim Avron (Tel Aviv University)
Michael Kapralov (EPFL)
Cameron Musco
Christopher Musco
Ameya Velingker
Amir Zandieh (EPFL)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees »
Mon. Aug 7th 04:06 -- 04:24 AM Room C4.6 & C4.7
More from the Same Authors
-
2020 Poster: Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling »
David Woodruff · Amir Zandieh -
2018 Poster: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson -
2018 Oral: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson