Sriperumbudur, B; Szabo, Z; (2015) Optimal Rates for Random Fourier Feature Kernel Approximations. Presented at: Talk at UC Berkeley: AMPLab, Berkeley, California.

Preview

Text Zoltan_Szabo_invited_talk_UCBerkeley_20_11_2015.pdf Download (531kB) | Preview

Abstract

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices. In order to mitigate this serious computational limitation, recently randomized methods have been proposed in the literature, which allow the application of fast linear algorithms. Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels. Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this talk, I am going to present the main ideas and results of a detailed finite-sample theoretical analysis about the approximation quality of RFFs by (i) establishing optimal (in terms of the RFF dimension, and growing set size) performance guarantees in uniform norm, and (ii) providing guarantees in Lr (1≤r <∞) norms. I will also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item