Optimal Rates for Random Fourier Features

By Bharath K. Sriperumbudur, Zoltán Szabó. 2015

142 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “Theoretical results on the preservation of kernel evaluation can be found in, e.g., Sutherland and Schneider (2015) and Sriperumbudur and Szabo (2015).”
Gradient-free Hamiltonian Monte Carlo with Efficient Kernel Exponential Families (2015, methodology): “Future work includes establishing theoretical consistency and uniform convergence rates for the empirical estimators, for example via using recent analysis of random Fourier Features with tight bounds [21], and a thorough experimental study in the ABC-MCMC context where we see a lot of potential for”
Orthogonal Random Features (2016, methodology): “In this paper, we focus on approximating Gaussian kernels following the seminal Random Fourier Features (RFF) framework [19], which has been extensively studied both theoretically and empirically [26, 20, 23].”
Domain Generalization by Marginal Transfer Learning (2017, result): “There are recent developments that give faster rates for approximation quality of random Fourier features and could potentially be combined with our analysis (Sriperumbudur and Szabó, 2015; Sutherland and Schneider, 2015).”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “For example, see (Sriperumbudur and Szabo 2015, Rudi and Rosasco 2017, Ullah, Mianjy, Marinov and Arora 2018, Szabo and Sriperumbudur 2019, Wang 2019).”
Generalization Properties of Learning with Random Features (2016, background): “Several papers considered the properties of random features for approximating the kernel function, see [17] and references therein, an interesting line of research with connections to sketching [24] and non-linear (one-bit) compressed sensing [18].”
Sampled Softmax with Random Fourier Features (2019, background): “Moreover, these features and their extensions are also theoretically better understood (see, e.g., [25, 26, 27]).”
From Dependence to Causation (2016, background): “Sriperumbudur and Szabó (2015) characterize the approximation error of d-dimensional shift-invariant kernels on S ⊂ Rd using Bochner’s theorem P ( sup x,x′∈S ∣∣∣k̂(x, x′)− k(x, x′) ∣∣∣ ≥ h(d, |S|, ck) + √ 2t√ m ) ≤ exp (−t) , (3.12) where S ⊂ Rd is a compact set of diameter |S|, and h(d, |S|, ck)…”
Learning with SGD and Random Features (2018, background): “can be shown to converge to a corresponding positive definite kernel k as M tends to infinity [6, 14].”