UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Optimal Rates for Random Fourier Features

Sriperumbudur, B; Szabo, Z; (2015) Optimal Rates for Random Fourier Features. Presented at: Neural Information Processing Systems (NIPS-2015), Montréal, Canada. (In press). Green open access

[thumbnail of sriperumbudurszabo15optimal.pdf]
Preview
Text
sriperumbudurszabo15optimal.pdf
Available under License : See the attached licence file.

Download (328kB) | 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 due to their capability to represent and model complex relations. 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 constructions 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 paper, we provide 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) presenting guarantees in Lr (1≤r<∞) norms. We also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.

Type: Conference item (UNSPECIFIED)
Title: Optimal Rates for Random Fourier Features
Event: Neural Information Processing Systems (NIPS-2015)
Location: Montréal, Canada
Dates: 07 December 2015 - 12 December 2015
Open access status: An open access version is available from UCL Discovery
Language: English
Additional information: contributed equally
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Gatsby Computational Neurosci Unit
URI: https://discovery.ucl.ac.uk/id/eprint/1469199
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item