PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Error of Random Fourier Features

Danica J. Sutherland, Jeff Schneider

arXiv:1506.02785v1cs.LGstat.ML

TL;DR

Kernel methods scale poorly because standard algorithms require full pairwise kernel evaluations, motivating random Fourier feature approximations whose quality is not fully understood. The paper analyzes their variance and approximation error, tightens uniform error bounds, and finds that ˜z is superior to ˘z for the Gaussian kernel. It also extends results on learned-model changes and empirically verifies aspects of the bounds.

  • Problem

    Full N × N pairwise kernel matrices make kernel methods difficult to scale, while the quality of random Fourier feature approximations remains incompletely understood.

  • Method

    The paper directly analyzes random Fourier feature variance, uniform and L2 approximation error, concentration, and effects on learned models, with empirical evaluation.

  • Results

    ˜z is superior to ˘z for the popular Gaussian kernel, including lower variance and better approximation behavior.

  • Takeaways & Limitations

    For the Gaussian kernel, the less widely used ˜z embedding is preferable; for other kernels, the choice depends on the kernel and ∆.

  • Takeaways & Limitations

    A bound considered in the paper becomes loose as training-set size increases, limiting its usefulness for determining the number of features needed for a target accuracy.

Abstract

from arXiv · show

Kernel methods give powerful, flexible, and theoretically grounded approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding's variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.

1 INTRODUCTION

Random Fourier features address the scalability of kernel methods by replacing full pairwise kernel computations with finite-dimensional embeddings, but the two variants differ in approximation quality and variance. This paper directly analyzes those differences and finds that the ˜z embedding is preferable for the Gaussian kernel.

  • Motivation: Full N × N kernel matrices make traditional kernel algorithms challenging to scale beyond thousands of data points.Random Fourier features were proposed to address this scalability problem.
  • Random Fourier features: Random Fourier embeddings approximate continuous shift-invariant kernels using the kernel’s Fourier transform.Rahimi and Recht (2007) introduced two embedding forms based on P(ω), the Fourier transform of k.
  • Variant comparison: For a fixed embedding dimension, ˘z uses twice as many frequency samples but introduces additional non-shift-invariant noise from phase shifts.Each reconstruction remains a mean of bounded terms with expectation k(x, y).
  • Main finding: ˜z is superior for the popular Gaussian kernel, while the preferable embedding for other kernels depends on the kernel and the value of ∆.The paper specifically reports that ˜s is uniformly lower-variance for the Gaussian kernel.
  • Paper scope: The paper studies approximation quality directly, complementing prior analyses focused on induced-RKHS learning error and eigengap exploitation.Its analysis covers variance, uniform convergence, L2 convergence, machine-learning effects, and empirical evaluation.

2 APPROXIMATION ERROR

The paper analyzes approximation error for both random Fourier feature embeddings, sharpening uniform bounds and comparing variance, expected maximal error, concentration, and L2 behavior. For the Gaussian kernel, the ˜z embedding is consistently preferable in variance and approximation quality, while the ˘z embedding incurs additional noise and looser bounds.

  • 2.1 VARIANCE: The ˜z embedding is always lower-variance than ˘z, with the largest difference when k(∆) is largest.For the Gaussian kernel, this lower variance is illustrated in Figure 1.
  • Error Measures: The analysis directly studies approximation error f(x, y) := s(x, y) − k(x, y), including its maximal error across the kernel domain.The paper also considers less stringent L2-type error measures over X × X.
  • 2.2.1 Original High-Probability Bound: The paper tightens the original high-probability bound for ˜z and proves a comparable bound for ˘z with worse constants.The ˜z proof uses an ε-net, Hoeffding or Bernstein inequalities, and an optimized net radius; ˘z additionally suffers from non-shift-invariant noise.
  • 2.2.2 Expected Max Error: The expected maximal-error analysis uses Dudley’s entropy integral after direct integration of the high-probability bounds becomes unavailable or analytically difficult.The direct integral diverges near zero, while integrating the minimum of the bound and 1 requires solving a transcendental equation.
  • 2.2.3 Concentration About Mean: The ˘z embedding can have tighter concentration about its mean, but its higher mean maximal error makes it stochastically dominate the ˜z error in the reported experiment.The paper attributes the difference to higher base variance and a larger space of possible errors for ˘f.
  • L2 Convergence: For the Gaussian kernel, ˜z is again superior under L2 convergence, while the simpler bound for ˘z has an asymptotic denominator coefficient of 512 versus 128 for the alternative bound.The L2 analysis assumes a σ-finite measure over X × X and derives exponential concentration for the ˜z approximation.

3 DOWNSTREAM ERROR

The paper analyzes how random Fourier feature approximation error propagates into kernel ridge regression, SVMs, and mean-embedding methods. These analyses account for approximated test-time kernel values and reveal practical accuracy and feature-dimension requirements.

  • Overview: The analysis directly studies prediction differences caused by replacing the exact kernel with its random Fourier feature approximation.This complements learning-theoretic analyses that instead study convergence of hypotheses or RKHS approximation.
  • 3.1 KERNEL RIDGE REGRESSION: Proposition 9 extends prior kernel ridge regression analysis to approximate both the training Gram matrix and test kernel values.The extension handles the setting actually used with Fourier features, where test-time kernel values are also approximated.
  • 3.1 KERNEL RIDGE REGRESSION: The prediction-error guarantee for kernel ridge regression uses uniform kernel approximation bounds and does not depend on the training-set size n.To match the O(1/√n) convergence rate of exact KRR predictions, the analysis requires D to be linear in n, ignoring logarithmic terms.
  • 3.2 SUPPORT VECTOR MACHINES: Proposition 10 extends the SVM analysis to approximate training and test kernel values, but its resulting feature bound becomes looser as the training set grows.The authors attribute this limitation to looseness in Proposition 10 and consider RKHS generalization analyses more useful for SVMs.
  • 3.3 MAXIMUM MEAN DISCREPANCY: Explicit embeddings approximate mean-kernel computations and can enable linear solvers, whereas other linear approximations may still require pairwise computation.For two-sample testing, the cited comparison reports ˘z as slower than the MMD-linear approximation but more accurate, and comparable in speed to a block-based B-test.
  • 3.3 MAXIMUM MEAN DISCREPANCY: Uniform kernel approximation bounds transfer directly to mean-kernel estimates, while the corresponding MMD error is at most 4 times ∥f∥∞.This bound applies uniformly to all sample sets on the input space, which is useful when MMD is used in a kernel method.

4 NUMERICAL EVALUATION

The experiments evaluate approximation error for both embeddings across interval size, feature dimension, concentration bounds, L2 error, and MMD estimation. Results generally favor ˜z for Gaussian-kernel approximation, while empirical errors decrease approximately as 1/D.

  • 4.1 APPROXIMATION ON AN INTERVAL: ˜z shows almost no error near zero, then error rises through one or two bandwidths before becoming approximately linear in ℓ/σ.This behavior matches the prediction of Proposition 3.
  • 4.1 APPROXIMATION ON AN INTERVAL: For fixed b = 3, all expected-maximal-error bounds are fairly loose, but the first bound version is substantially tighter than the second when d = 1.The comparison uses bounds with dimension-dependent βd and αε against the simpler second version.
  • 4.1 APPROXIMATION ON AN INTERVAL: The empirical scaling exponent for E∥˜f∥∞ is −0.502 to −0.496, while ˘f has exponent −0.503 to −0.497 at 95% confidence.The integrated bounds do not fit the observed dependence on D nearly as well.
  • 4.1 APPROXIMATION ON AN INTERVAL: Empirical survival probabilities for D = 500 compare evaluations with integrated bounds and empirical-mean bounds; the latter are tighter for low ε, especially at low D.The empirical-mean bounds have a lower slope.
  • 4.1 APPROXIMATION ON AN INTERVAL: The mean squared errors are approximately 0.66/D for ˜f and 0.83/D for ˘f under the uniform distribution on X².Convergence to the mean is substantially faster than guaranteed by the McDiarmid bound.
  • 4.2 MAXIMUM MEAN DISCREPANCY: For biased MMD estimation, ˜z performs mildly better than ˘z, while mean absolute error follows an empirical O(1/√D) pattern with wide constants.The 95% confidence intervals for the D exponent are [−0.515, −0.468] for ˜z and [−0.520, −0.486] for ˘z.

5 DISCUSSION

The discussion consolidates the paper’s theoretical and empirical contributions, including refined error bounds, concentration results, and comparisons of the two embeddings. It concludes that ˜z is superior for the Gaussian kernel, the most common case considered.

  • 5 DISCUSSION: The paper investigates random Fourier feature approximation error, tightening existing bounds and introducing analytic and concentration results for uniform and L2 errors.It also extends results concerning changes in learned models caused by kernel approximation.
  • 5 DISCUSSION: The authors empirically verify aspects of the bounds for the Gaussian kernel.The numerical evaluations cover approximation error and MMD-related use.
  • 5 DISCUSSION: For the Gaussian kernel, ˜z is superior to ˘z despite using half as many sampled frequencies, because it avoids additional phase-shift noise.The paper identifies this as the most common case of the two embeddings’ use.

A.1 PROOF OF PROPOSITION 1

The proof of Proposition 1 follows an ε-net argument on pairwise differences, combining pointwise concentration with Lipschitz control. It tightens the original analysis by using variance-sensitive concentration and optimizing the net radius.

  • A.1 PROOF OF PROPOSITION 1: The proof covers X∆ with an ε-net of radius r containing at most T = (4ℓ/r)^d balls.The difference set X∆ is compact and has diameter at most 2ℓ.
  • A.1 PROOF OF PROPOSITION 1: Uniform error is controlled by requiring net-center errors below ε/2 and the Lipschitz constant below ε/(2r).These conditions extend pointwise control from net centers to all differences.
  • A.1 PROOF OF PROPOSITION 1: The proof justifies exchanging expectation and gradient using a Leibniz-rule result under integrability, differentiability, and finite-first-moment conditions.This establishes E∇˜s(∆) = ∇E˜s(∆) = ∇k(∆).
  • A.1 PROOF OF PROPOSITION 1: For fixed ∆, ˜f is a mean of D/2 bounded terms, so Hoeffding’s inequality and a union bound provide pointwise concentration.Bernstein’s inequality is an alternative when the known variance gives a tighter bound.
  • A.1 PROOF OF PROPOSITION 1: The refined bound improves when 3ε < 1; for the RBF kernel this holds whenever ε < 3/2, with larger gains for large k(∆) or small ε.The proof combines the concentration bounds and optimizes the radius r rather than using only the original algebraically convenient choice.
  • A.1 PROOF OF PROPOSITION 1: For ε ≤ σpℓ, the middle-term exponent can be loosened to 2, and the original proof’s ℓ > 1 assumption is unnecessary.The final feature-dimension statement follows by setting the bound to δ and solving for D.

A.2 PROOF OF PROPOSITION 2

The proof of Proposition 2 adapts the ε-net and concentration strategy to the non-shift-invariant embedding ˘z. Its larger domain and additional phase noise produce a different, looser bound structure.

  • A.2 PROOF OF PROPOSITION 2: The proof follows Proposition 1’s strategy but applies it to ˘s and ˘f, which are not shift-invariant.For D = 1, the approximation depends on both x − y and x + y through the phase term.
  • A.2 PROOF OF PROPOSITION 2: Because ˘s is not shift-invariant, the ε-net lies on X² rather than X∆, increasing the domain dimension to 2d.Additional noise also increases the expected Lipschitz constant and loosens summand bounds, despite twice as many terms.
  • A.2 PROOF OF PROPOSITION 2: For fixed x and y, ˘s averages D terms with expectation k(x,y), each bounded by ±2, enabling Hoeffding concentration.Bernstein’s inequality can be substituted using the variance in equation (6).
  • A.2 PROOF OF PROPOSITION 2: Bernstein’s inequality gives a tighter bound when 2 Var[cos(ω^T∆)] + 4/(3ε) < 7.This condition compares the variance-sensitive bound with the alternative concentration expression.
  • A.2 PROOF OF PROPOSITION 2: Optimizing the net radius requires solving 2dκ1r^−2d−1 − 2κ2r = 0, yielding the radius used in the final bound.The resulting expression has a middle exponent that is slightly worse than Proposition 1’s for small d.
  • A.2 PROOF OF PROPOSITION 2: For ε ≤ σpℓ, the middle-term exponent can again be loosened to 2, after which the feature-dimension guarantee follows by solving the bound for D.This parallels the final step of Proposition 1.

A.3 PROOF OF PROPOSITION 3

The proof applies a Dudley entropy-integral argument to a conditioned random process, using Lipschitzness and covering-number bounds to control its uniform behavior.

  • A.3 PROOF OF PROPOSITION 3: The argument assumes k is L-Lipschitz over X∆ and applies a generalized Dudley entropy integral retaining the variance factor v.The theorem is stated first for finite pseudometric spaces and extended to separable spaces such as X∆.
  • A.3 PROOF OF PROPOSITION 3: Choosing ∆0 = 0 gives δ = ℓ and bounds the entropy by H(δ, X∆) ≤ d log (8ℓ/δ).This uses a covering-number bound together with the fact that the δ-packing number is at most the δ/2-covering number.
  • A.3 PROOF OF PROPOSITION 3: Hoeffding’s lemma bounds each centered process increment through 2 D2 (∥ωi∥+ L)2λ2∥∆−∆′∥2.The bound follows after controlling the absolute value of each mean-zero term.
  • A.3 PROOF OF PROPOSITION 3: To handle random frequencies, the proof conditions on a radius r and defines ˜gr with ∥ω1∥ = r and ∥ωi∥ ≤ r for i > 1.Independent log moment generating functions are additive, enabling the entropy argument for the conditioned process.
  • A.3 PROOF OF PROPOSITION 3: The resulting control uses R := E maxD/2 i=1 ∥ωi∥ and applies symmetrically to E sup(−˜f).Because both sup ˜f and sup(−˜f) are nonnegative, the claimed bound follows from their combined control.

A.4 PROOF OF PROPOSITION 4

The proof for ˘z features works on X 2 because the noise is not shift invariant, adapting the entropy argument to a radius ρ and accounting for the process’s sign behavior.

  • A.4 PROOF OF PROPOSITION 4: The error process for ˘z features is defined over X 2, while k remains assumed L-Lipschitz over X∆.The enlarged domain reflects the non-shift-invariant noise.
  • A.4 PROOF OF PROPOSITION 4: Using a convenient x0, the proof defines ρ := supx∈X d(x, x0) and obtains supq∈X 2 d(q, (x0, x0)) from this radius.Unlike X∆, X 2 need not contain an obvious point minimizing the relevant supremum distance.
  • A.4 PROOF OF PROPOSITION 4: The entropy comparison gives H(u, X 2) ≤ 2d log …, reflecting the doubled product-space geometry.The supplied passage presents this as the analogue of the preceding X∆ argument.
  • A.4 PROOF OF PROPOSITION 4: The radius satisfies 1/2ℓ ≤ ρ ≤ ℓ, with the lower bound achieved by a ball and the upper bound by a sphere.The proof then substitutes this radius into the entropy-integral bound.
  • A.4 PROOF OF PROPOSITION 4: The coefficient varies monotonically between γ′1 ≈ 1.541 and γ′2 ≈ 0.803 as shown in Figure 7.Figure 7 plots this coefficient as a function of ℓ/ρ.
  • A.4 PROOF OF PROPOSITION 4: Because ˘f(q) is not guaranteed to have a consistent sign, the bound uses a different treatment from the sign-controlled case.The proof explicitly notes that ˘f does not necessarily avoid crossing zero.
  • A.4 PROOF OF PROPOSITION 4: The probability that ˘f does not cross 0 is extremely close to 1 in “usual” situations.

B PROOFS FOR L2 ERROR BOUND (SECTION 2.3)

The L2-error proof analyzes how changing one frequency affects the error process, compares the two feature constructions on X 2, and tracks the resulting variance terms.

  • B PROOFS FOR L2 ERROR BOUND (SECTION 2.3): The proof studies µ as a function of ω1, …, ωD/2 and bounds the change caused by replacing ω1 with ˆω1.By symmetry, the same change bound applies to every ωi.
  • B PROOFS FOR L2 ERROR BOUND (SECTION 2.3): The displayed cosine expressions compare the original and replaced frequencies in terms involving x − y and x + y.
  • B PROOFS FOR L2 ERROR BOUND (SECTION 2.3): The resulting bound includes a D2 µ(X 2) term together with an additional 32 term.
Loading 1506.02785v1…