Source-linked AI summary
Optimal Rates for Random Fourier Features
Bharath K. Sriperumbudur, Zoltan Szabo
TL;DR
Kernel methods face computational challenges on large datasets, while finite-sample approximation guarantees for RFF have been limited. This paper develops finite-sample analyses for kernel and derivative approximations, establishing optimal rates in uniform and Lr norms under stated conditions.
Problem
Kernel methods face computational challenges on large datasets, and prior RFF approximation theory lacked optimal finite-sample guarantees, including for growing compact sets.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
The improved logarithmic dependence on set size reduces the feature count required for a given approximation accuracy compared with the prior bound.
Source: §3 · p. 5The derivative extension in Theorem 4 assumes bounded spectral support, an assumption that excludes many popular kernels including the Gaussian.
Source: §4 · p. 7
Abstract
from arXiv · showhide
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 $L^r$ ($1\le r<\infty$) norms. We also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.
1 Introduction
Random Fourier features (RFF) provide explicit low-dimensional approximations for shift-invariant kernels, enabling primal linear solvers where Gram-matrix methods are costly. This paper addresses limited finite-sample theory for their approximation quality, including kernel derivatives.
1 Introduction
- Kernel methods model complex relations across many machine-learning tasks, but their Gram-matrix computations create serious computational challenges on large datasets.RFF are one of several proposed remedies for this bottleneck and are constructed for shift-invariant kernels.Source: §1 · p. 1
- RFF replace implicit kernel features with explicit low-dimensional maps, allowing primal linear solvers and approximating the full kernel function rather than only its matrix.This is useful for out-of-sample data and online learning.Source: §1 · pp. 1–2
- Existing RFF guarantees were non-optimal or asymptotic, while this paper establishes finite-sample uniform and Lr guarantees with optimal m^-1/2 rates and logarithmic dependence on set size.For growing sets, the results also give sufficient growth conditions for almost-sure convergence and match the best attainable asymptotic growth rate.Source: §1 · p. 2
- The paper proposes finite-dimensional RFF approximations for kernel derivatives and gives finite-sample uniform- and Lr-norm approximation guarantees with m^-1/2 convergence rates.These approximations target derivative-based kernel algorithms, including gradient learning and Hermite learning.Source: §1 · p. 2
2 Notations & preliminaries
This section establishes notation and reviews random-feature approximation for bounded, continuous, translation-invariant kernels. It also motivates improved bounds by noting that prior compact-set guarantees have non-optimal rates and set-size dependence.
2 Notations & preliminaries
- For bounded, continuous, positive-definite translation-invariant kernels, the paper represents the kernel through a Fourier measure and assumes its value at zero is normalized to one.The Fourier measure is then a probability measure.Source: §2 · p. 3
- RFF approximate the Fourier integral empirically, yielding a finite-dimensional feature map whose inner product approximates the kernel.The explicit map supports solving kernel algorithms in the primal.Source: §2 · p. 3
- The existing compact-set guarantee establishes consistency, but its convergence rate and dependence on set size are non-optimal.The paper notes that set-size dependence controls how many features are needed for a target accuracy and how quickly sets can grow with m.Source: §2 · p. 4
3 Main results: approximation of k
The paper gives finite-sample guarantees for random Fourier feature kernel approximation, improving the uniform error rate and its dependence on set size. It also establishes Lr guarantees and examines convergence as compact sets grow.
3 Main results: approximation of k
- Theorem 1 gives a finite-sample uniform approximation rate of m^-1/2 with logarithmic dependence on |S|, improving the earlier rate and dependence.The resulting feature requirement is O(ε^-2 log |S|), instead of O(ε^-2|S|^2 log(|S|/ε)) for the same accuracy.Source: §3 · pp. 4–5
- The uniform error is treated as a supremum of an empirical process, bounded using McDiarmid concentration, symmetrization, and a Dudley entropy bound.The proof carefully bounds the L2(Λm)-covering number of the function class.Source: §3 · p. 4
- Uniform convergence remains consistent for growing compact sets when m^-1 log |Sm| tends to zero, allowing |Sm| to grow exponentially in m.The paper states this is best possible in general for almost sure convergence; faster growth can prevent even stochastic convergence under the conditions described.Source: §3 · p. 5
- The paper identifies the m^-1/2 rate and logarithmic dependence on |Sm| as optimal in the stated asymptotic settings.It relates these conclusions to prior characteristic-function convergence results, while distinguishing its own finite-sample probabilistic inequality.Source: §3 · pp. 4–5
- Corollary 2 and Theorem 3 provide Lr approximation guarantees, with Theorem 3 improving dependence on |S| for 2 ≤ r < ∞.For 1 < r < 2, Theorem 3 is slower than Corollary 2, so the paper recommends the latter bound.Source: §3 · pp. 5–6
4 Approximation of kernel derivatives
The section constructs a random Fourier feature approximation to kernel derivatives and studies its uniform and Lr approximation behavior on compact sets. It gives derivative guarantees under bounded spectral support and, with moment conditions, a slower-rate alternative for unbounded support.
4 Approximation of kernel derivatives
- The proposed derivative approximation replaces the spectral measure Λ with its empirical version Λm and is analyzed in uniform and Lr norms.The analysis seeks analogues of the kernel-approximation guarantees for ∂p,qk.Source: §4 · pp. 6–7
- Theorem 4 extends the kernel approximation result to derivatives under a bounded-support condition when both p and q are nonzero.Theorem 4 reduces to Theorem 1 when p=q=0.Source: §4 · p. 7
- The section also gives conditions for derivative approximation guarantees to persist as the compact sets grow with m.It discusses growth of |Sm| for uniform and Lr convergence; the supplied passages do not give a complete rate expression.Source: §4 · p. 7
- Theorem 5 relaxes the bounded-support requirement using moment conditions on Λ, but gives a worse rate than Theorem 4.Its proof uses a net, Bernstein's inequality, a union bound, and a probabilistic Lipschitz argument.Source: §4 · pp. 7–8
5 Discussion
The paper provides finite-sample theoretical guarantees for RFF approximation of kernels and their derivatives. Its guarantees concern compact subsets of Rd; approximation over all of Rd remains unresolved.
5 Discussion
- The paper gives an optimal-rate finite-sample uniform approximation bound, analyzes Lr approximation for 1≤r<∞, and provides uniform and Lr guarantees for a derivative approximation.The derivative guarantees apply over compact subsets of Rd.Source: §5 · p. 8
- All results concern compact subsets of Rd; the paper states that RFF cannot approximate the kernel uniformly or in Lr norm over all of Rd.Whether a representation retaining RFF's computational advantages can achieve such whole-space approximation remains an open question in the discussion.Source: §5 · p. 8
Supplement
The supplement introduces notation for function families and metric entropy used in the paper's arguments, alongside a definition of Banach-space type.
A Definitions & notation
- A separable Carathéodory family consists of maps indexed by a separable metric space that are continuous in the index for each fixed ω.The passage also introduces measurable maps on a measurable space.Source: A Definitions & notation · p. 10
- An r-net covers each point of a metric space within distance r, and the smallest such net's size defines the r-covering number.The logarithm of the covering number is called metric entropy.Source: A Definitions & notation · p. 10
- A normed space has type q when its stated inequality holds for every finite vector set; Lr spaces have type min(2,r).The constant in the Lr example depends only on r.Source: A Definitions & notation · p. 10
B Proofs
The supplementary material contains proofs of results from Sections 3 and 4.
B Proofs
- Proofs of the results in Sections 3 and 4 are provided in the supplementary material.The associated lemmas are listed in Section C.Source: B Proofs · p. 10
B.1 Proof of Theorems 1 and 4
The proof treats the uniform kernel approximation error as an empirical-process supremum and bounds it through concentration, symmetrization, and metric entropy. Theorem 4 yields Theorem 1 for p = q = 0.
B.1 Proof of Theorems 1 and 4
- Theorem 4 establishes Theorem 1 for p = q = 0.The proof concludes by combining its preceding bounds.Source: §B.1 · pp. 10, 12
- The uniform error is a supremum of an empirical process indexed by G, whose separable Carathéodory structure supports measurability and concentration.McDiarmid’s inequality is used for concentration.Source: §B.1 · p. 10
- Symmetrization reduces the expectation bound to a Rademacher average, which is controlled using Dudley’s entropy integral and the smooth parametrization over compact S∆.The proof bounds the metric entropy of G using compactness of S∆.Source: §B.1 · pp. 10–11
B.2 Proof of Theorem 3
The proof bounds the L^r kernel approximation error by concentration and symmetrization, then uses the type of L^r(S) to control the resulting Rademacher expression.
B.2 Proof of Theorem 3
- The L^r(S) approximation error concentrates around its expectation by bounded differences and McDiarmid’s inequality.The proof establishes the bounded-difference property for the error norm.Source: §B.2 · p. 12
- The type min(r, 2) of L^r(S), with a constant independent of S, supplies the bound used to finish the proof.The proof then combines its bounds and uses the volume bound for S.Source: §B.2 · pp. 12–13
- Symmetrization reduces the expected error to an Rademacher sum of cosine features measured in L^r(S).The proof uses the dual exponent and a countable subset of the dual space in the reduction.Source: §B.2 · pp. 12–13
B.3 Proof of Theorem 5
The proof obtains a uniform bound by controlling approximation error on a net of S∆, propagating it using Lipschitzness, and optimizing the net radius.
B.3 Proof of Theorem 5
- Compactness of S∆ provides an r-net, reducing uniform control to finitely many net centers.The net has a covering-size bound, with |S∆| ≤ 2|S|.Source: §B.3 · p. 13
- Bernstein’s inequality and a union bound control error at the net centers; Lipschitzness propagates that control to all of S∆.The proof also bounds the random Lipschitz constant with high probability.Source: §B.3 · pp. 13–15
- The proof controls the random Lipschitz constant using its expectation and Markov’s inequality, then optimizes the bound over r.The radius is chosen by matching the two terms in the bound.Source: §B.3 · pp. 14–15
B.4 Proof of bounded supp(Λ) ⇒(7)
The proof shows that bounded support of Λ implies boundedness of the function f used in condition (7).
B.4 Proof of bounded supp(Λ) ⇒(7)
- Together, bounded support of Λ implies boundedness of f, as required for (7).The proof identifies boundedness of supp(Λ) as the sufficient condition.Source: §B.4 · p. 16
- The triangle inequality and |h_a(v)| ≤ 1 provide the bound used for f.These are the inequalities applied in the proof.Source: §B.4 · p. 16
- Bounded support of Λ makes K = sup_{s∈supp(Λ)} |s^{p+q}| finite.The proof uses this finite bound to establish boundedness of f.Source: §B.4 · p. 16
C Supplementary results
Appendix C collects technical lemmas used in the proofs. These include concentration bounds and a countable-supremum representation of the Lr norm under specified measure-space conditions.
C Supplementary results
- McDiarmid's inequality gives an upper-tail bound for a function of independent variables when changing each input satisfies a bounded-difference condition.The stated condition bounds the change from replacing the rth input by c_r.Source: C Supplementary results · p. 16
- A supplementary Bernstein inequality is stated for a mean-zero random variable under assumed L and S bounds.Source: C Supplementary results · p. 16
- For compact S ⊆ Rd with its Borel sigma-algebra, the Lr norm is a supremum over a countable unit-norm set; the Lebesgue sigma-algebra is typically not countably generated.Source: C Supplementary results · p. 16