EE Seminar: Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
(The talk will be given in English)
Speaker: Dr. Haim Avron
Department of Applied Mathematics, Tel Aviv University
Monday, May 21st, 2018
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Abstract
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. The talk is based on a recent paper in which 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.
Qualitatively, our results are twofold: on one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of low-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.
This is joint work with Michael Kapralov (EPFL), Cameron Musco (MIT), Christopher Musco (MIT), Ameya Velingker (EPFL), and Amir Zandieh (EPFL).
Bio
My research focuses on numerical computing and high performance computing and their applications in scientific computing and machine learning. My interests and work range from mathematical and computational foundations to end-to-end implementation aspects.
I did my Ph.D. at the School of Computer Science at Tel Aviv University under the supervision of Prof. Sivan Toledo. Afterwards I spent two years as a Postdoctoral Researcher in the Business Analytics & Mathematical Sciences department at the IBM T.J. Watson Research Center. From 2012 to 2015 I was a Research Staff Member in the Mathematical Sciences & Analytics department at the IBM T.J. Watson Research Center. I joined the Department of Applied Mathematics, School of Mathematical Sciences at Tel Aviv University as a Senior Lecturer (equivalent to assistant professor) in 2015.
Finally, I am organizing the Applied Mathematics Seminar at Tel Aviv University.
