PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh

arXiv:1804.09893v2cs.LGcs.DSmath.NAstat.ML

TL;DR

Random Fourier features can make kernel ridge regression scalable, but the statistical guarantees and feature counts needed for accuracy are not fully understood. The paper studies these questions through spectral approximation and shows that classical sampling has provable guarantees but is suboptimal, while leverage-based sampling improves the theoretical bounds in a low-dimensional Gaussian-kernel regime.

  • Problem

    Random Fourier features lack a sufficiently clear statistical analysis connecting approximation quality and feature count to kernel ridge regression guarantees.

  • Method

    The paper analyzes random Fourier features through spectral approximation of regularized kernel matrices and studies leverage-function-based Fourier sampling.

  • Results

    The paper gives bounds showing that classical random Fourier features can guarantee KRR performance, while leverage-based sampling yields improved theoretical bounds and an efficient Gaussian-kernel scheme for low-dimensional bounded datasets.

  • Takeaways & Limitations

    Random Fourier features can provably speed up KRR under reasonable assumptions, but modified sampling can provide better theoretical properties than classical Fourier sampling.

  • Takeaways & Limitations

    The proposed sampling construction is mostly theoretical because its bound has exponential dependence on the data dimension, limiting applicability to low-dimensional datasets.

Abstract

from arXiv · show

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression. Qualitatively, our results are twofold: on the one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of low-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.

1 Introduction

Kernel ridge regression is statistically powerful but computationally expensive, motivating random Fourier features as a scalable approximation. This paper analyzes when spectral approximation guarantees transfer to KRR and shows both benefits of classical sampling and improvements from leverage-based sampling.

  • Motivation: KRR can require Θ(n3) time and Θ(n2) memory, making scalable kernel methods necessary for large datasets.The paper identifies computational cost, rather than statistical weakness, as KRR's key limitation.
  • Random Fourier features: Random Fourier features approximate the kernel with s sampled features, reducing computation to O(ns2) time and O(ns) memory when s ≪ n.The approximation replaces the kernel matrix with a surrogate constructed from sampled Fourier features.
  • Research question: The central question is how large s must be for the approximate KRR estimator to match the exact estimator's quality.The paper frames this through spectral approximation of the regularized kernel matrix.
  • Spectral analysis: Spectral approximation bounds yield excess-risk guarantees for random-feature KRR and allow the surrogate regularized matrix to serve as a preconditioner.These implications motivate relating the feature count s to the approximation parameter ∆.
  • Main results: The paper gives an upper bound for achieving spectral approximation and a matching Gaussian-kernel lower bound, establishing guarantees under reasonable assumptions.Together, these results characterize the feature count needed by classical random Fourier features in the analyzed setting.
  • Improved sampling: Leverage-based Fourier sampling can dramatically improve the upper bound, while an efficient Gaussian-kernel distribution applies only to low-dimensional datasets because of exponential dimension dependence.The proposed distribution approximates the kernel leverage function and also yields a bound on the statistical dimension of Gaussian kernel matrices over bounded datasets.

2 Preliminaries

The preliminaries define kernel matrices, random Fourier feature approximations, and their computational representation. They also introduce modified importance sampling based on leverage functions and situate the paper's analysis relative to prior work.

  • Notation: The kernel matrix is K ∈ Rn×n with entries Kij ≡ k(xi, xj), and λ is the ridge regularization parameter.The notation also uses n for training examples and d for input dimension.
  • Classical random Fourier features: For shift-invariant kernels, random Fourier features sample frequencies from the Fourier-transform density to construct a surrogate kernel.The density assumption and normalization k(0) = 1 make the sampling distribution a probability density.
  • Approximate KRR: The resulting surrogate matrix is ˜K = ZZ∗, and the approximate KRR estimator solves (˜K + λIn)˜α = y.The feature matrix Z contains the sampled feature evaluations on the training data.
  • Computational cost: Computing the feature-space parameter w takes O(ns2) time, making random Fourier features attractive when s < n.This is obtained through the Woodbury formula and supports the method's computational savings.
  • Modified sampling: Modified random Fourier features sample frequencies from any suitable density q and reweight the features, preserving the kernel expectation through importance sampling.The paper motivates choosing q according to a kernel leverage function rather than the classical Fourier density.
  • Related analysis: The paper's analysis builds on spectral approximation, risk bounds, and leverage-function ideas from prior work, while targeting guarantees for classical KRR.Earlier random-feature analyses either focus on pointwise kernel error, require difficult assumptions, or become relevant only when s is near the training-set size.

3 Spectral Bounds and Statistical Guarantees

The paper uses spectral approximation of the kernel matrix to connect random Fourier feature approximations with statistical risk and iterative-solver guarantees for KRR.

  • Motivation: Spectral approximation bounds on the surrogate kernel matrix translate into downstream statistical and algorithmic guarantees for approximate KRR.They support both excess-risk bounds and preconditioning analysis.
  • Risk bounds: The exact-KRR risk bound separates into bias and variance terms, with R(¯f) ≤ bR_K(f).The paper identifies the first term as bias and the second as variance.
  • Risk bounds: The approximate KRR risk is bounded by a multiplicative inflation of the exact-KRR risk plus an additive term depending on spectral error and approximate-kernel rank.The bound is R(˜f) ≤ (1−∆)^−1 bR_K(f) + ∆/(1+∆) · rank(˜K).
  • Risk bounds: The additive risk contribution becomes small when rank(˜K) is much smaller than n and the spectral error ∆ is small.The paper ideally seeks rank(˜K)/n → 0 as n grows.
  • Preconditioning: A ∆-spectral approximation enables preconditioned iterative KRR with O((1+∆)/(1−∆)) iterations and total cost O(ns^2+n^2).For ∆=1/2, the iteration count is bounded by a constant; when s=o(n), this improves over direct O(n^3) methods.

4 Ridge Leverage Function Sampling and Random Fourier Features

The paper analyzes Fourier-feature sampling through ridge leverage functions, showing that classical sampling can achieve spectral approximation but may be suboptimal relative to leverage-aware distributions.

  • Spectral approximation: The section derives upper bounds on the number of random Fourier features needed for ∆-spectral approximation of K+λI_n across shift-invariant kernels and sampling distributions.The framework includes classical random Fourier feature sampling.
  • Leverage function: The ridge leverage function is a continuous, dataset-specific analogue of leverage and ridge leverage scores used in linear sampling methods.It is defined relative to the fixed input dataset and the shift-invariant kernel.
  • Leverage-aware sampling: If an upper bound on the ridge leverage function is available, O(s_λ(K) log(s_λ(K))) samples suffice for spectral approximation under fixed ∆ and failure probability.The result follows from leverage-aware sampling with an upper-bounding density.
  • Classical sampling: Classical random Fourier features require s ≥ 8∆^-2 n_λ ln(16s_λ(K)/ρ) to obtain a ∆-spectral approximation with probability at least 1−ρ.This uses the Fourier-transform density p(·), with assumptions ∆≤1/2 and ||K||_2≥λ.
  • Classical sampling: When λ=ω(log(n)) and ∆ is fixed, o(n) classical random Fourier features suffice, so KRR can be provably accelerated.However, the bound depends on n_λ rather than s_λ(K), because the leverage-function upper bound can be loose.
  • Comparison of sampling distributions: The classical bound is unimprovable in general, while modified sampling can closely approximate the ridge leverage distribution and yield better Gaussian-kernel bounds.The classical distribution may need Ω(n_λ) features even when s_λ(K)=o(n_λ).

5 Lower Bound for Classic Random Fourier Features

The paper shows that classic random Fourier features require many samples for spectral approximation, with a lower bound essentially matching the corresponding upper bound. This exposes a gap versus leverage-based sampling, while the stated lower-bound theorem has scope limitations for fixed bounded domains.

  • Lower bound: The lower bound shows that Theorem 9’s sample-complexity upper bound for classic random Fourier features is essentially tight for the Gaussian kernel.The result establishes that the upper bound on samples needed for spectral approximation cannot generally be improved for this sampling distribution.
  • Lower bound: s = Ω(nλ/2^O(d)) is obtained for the Gaussian kernel, with a stronger s = Ω(nλ) implication via embedding lower-dimensional datasets.The theorem’s certificate dataset is a uniform grid in d dimensions, while zero-coordinate embedding yields the stronger asymptotic statement.
  • Comparison: Theorem 10 requires sample complexity at least linear in nλ for a 1/2-spectral approximation on the stated bounded dataset.This creates an asymptotic gap between classical random Fourier features and modified sampling based on the leverage function.
  • Mechanism: Classic Fourier sampling undersamples some low-frequency-range edges because its distribution is very small there, preventing spectral approximation.The lower-bound proof identifies this frequency mismatch as the mechanism behind the failure.
  • Scope: The theorem’s stated conditions do not fully cover the usual fixed-radius bounded-domain setting, although the analysis allows R to grow slowly with n.The authors conjecture that the upper bound remains tight for bounded domains despite this limitation.

6 Improved Sampling for the Gaussian Kernel

The paper proposes an efficiently samplable Gaussian-kernel distribution that approximates leverage-based sampling by reallocating probability toward higher frequencies. Under low-dimensional bounded-domain conditions, this yields spectral-approximation guarantees and can require exponentially fewer features than classical sampling.

  • Improved distribution: The improved Gaussian-kernel distribution is designed for bounded input sets and is simpler to sample from than the true ridge leverage function.The construction is stated for fixed bandwidth without loss of generality because points can be rescaled.
  • Improved distribution: The distribution caps probability near the origin and allocates more samples to higher frequencies undersampled by classical random Fourier features.This provides the central correction to the classic Fourier sampling distribution.
  • Guarantee: The proposed distribution upper-bounds the true ridge leverage function and supports a Δ-spectral approximation with probability at least 1−ρ under Theorem 12’s conditions.The guarantee applies to d-dimensional Gaussian kernels on points contained in an ℓ∞-ball of radius R, with the stated feature-count condition.
  • Scope: The modified distribution’s guarantee is limited to a low-dimensional regime because its upper bound has exponential dependence on the data dimension.The construction is therefore especially relevant for bounded datasets with small d.
  • Sampling procedure: O(d) expected time is sufficient to generate a sample, making the overall sampling procedure efficient in the dimension.The procedure combines sampling from a uniform component with rejection sampling for the tail.
  • Sample complexity: O(R log(nλ)) samples suffice in the stated one-dimensional regime, versus the classical lower bound Ω(nλ), giving a possibly exponential improvement.The comparison is made for d = 1 and R ≥ log^1.5(nλ).

7 Bounding the Ridge Leverage Function

The section characterizes the Gaussian-kernel ridge leverage function through primal-dual optimization problems and constructs test functions that yield upper and lower bounds. These bounds establish improved sampling guarantees and, together, a tight statistical-dimension characterization for bounded low-dimensional datasets.

  • 7.1 Primal-Dual Characterization: The ridge leverage function is equivalently characterized by primal minimization and dual maximization problems, extending finite-dimensional characterizations to an infinite-dimensional setting.The primal formulation supports upper bounds, while the dual formulation supports lower bounds.
  • 7.2 Bounding the Gaussian Kernel Leverage Function: Upper Bound: Theorem 16 bounds the ridge leverage function over frequencies satisfying ∥η∥∞≤10√log nλ for Gaussian kernels and points contained in an ℓ∞-ball of radius R.The result assumes σ=(2π)^−1, 0<λ≤n, and d≤nλ/4.
  • 7.2 Bounding the Gaussian Kernel Leverage Function: Upper Bound: Theorem 12 follows by combining Theorem 16 inside this frequency range with Proposition 4 outside it, yielding an improved sampling bound.The construction is designed to keep the test-function norm controlled while preserving the desired Fourier behavior on bounded data.
  • 7.2 Bounding the Gaussian Kernel Leverage Function: Upper Bound: For Gaussian kernels on bounded datasets, the upper-bound proof constructs frequency-dependent test functions whose weighted Fourier transforms approximate pure cosine targets at the data points.The construction replaces an invalid Dirac delta with a bounded-energy soft spike, then uses a Gaussian-damped sinc function.
  • 7.3 Bounding the Gaussian Kernel Leverage Function: Lower Bound: A dual construction gives a near-matching lower bound for Gaussian-kernel leverage, using coefficients related to the upper-bound test function and evenly spaced grid points.The lower-bound construction chooses data points spread across an L∞ ball to increase the statistical dimension.
  • 7.4 Bounding the Statistical Dimension of Gaussian Kernel Matrices: Theorems 16 and 17 together imply a tight bound on the statistical dimension of Gaussian kernel matrices for bounded point sets.The resulting corollary applies under explicit restrictions on dimension, radius, sample size, and regularization.

8 Numerical Experiments

The experiments compare classical and modified random Fourier features on synthetic low-dimensional datasets. Modified features produce estimators closer to exact KRR, even when classical features have lower entry-wise kernel error.

  • The experiments use synthetic low-dimensional datasets that illustrate the paper’s theoretical claims rather than realistic data.The authors explicitly state that the datasets are not designed to be realistic.
  • Wiggly function: For the one-dimensional wiggly function, modified random Fourier features achieve lower risk and in-sample error than classical random Fourier features, with risk close to KRR.The comparison uses 200 features for each random-feature estimator.
  • Wiggly function: Classical random Fourier features can have lower entry-wise kernel error while producing worse estimators, showing that entry-wise error is not predictive of estimator quality.The generalized condition number is more predictive, although not completely predictive, of estimator quality.
  • Varying s: As s increases, modified-feature risk quickly converges to KRR risk, whereas classical-feature risk decreases slowly and can remain larger than KRR even when s > n.Classical features nevertheless continue reducing entry-wise error and can outperform modified features on that metric.
  • Two-dimensional function: On the two-dimensional wiggly function with n = 1600 and s = 400, the modified-feature estimator is very close to KRR, while the classical estimator misses or distorts features.The experiment uses a 40 × 40 uniform grid, σ = 0.181167, and λ = 0.00106475.

9 Conclusions

The paper analyzes random Fourier features through spectral approximation of kernel matrices and derives both positive and negative theoretical conclusions. It shows that modified sampling can improve guarantees, while the proposed construction remains limited to low-dimensional settings and worst-case analysis.

  • Spectral approximation bounds provide statistical guarantees for KRR and can also extend to kernel k-means and kernel PCA through recent results.
  • The conclusions expose potential sub-optimality in classic random Fourier sampling and motivate improved sampling distributions, but the proposed construction is mostly theoretical.The paper also leaves distributional rather than worst-case leverage-score analysis for future work.
  • The analysis relies primarily on Fourier analysis and Gaussian-distribution properties, supported by matrix concentration bounds for random matrices.

C Proof of Theorem 16

The proof of Theorem 16 upper-bounds the Gaussian kernel’s ridge leverage function using softened spike test functions. Fourier-transform and norm estimates control the resulting bound under bounded-data and parameter assumptions.

  • The proof assumes, without loss of generality, that all data points lie in [−R, R]^d because common shifts preserve the leverage function.
  • A softened spike function yη,u is constructed to upper-bound the ridge leverage function through a test-function minimization argument.Its weighted form combines a Gaussian centered at η with a sinc factor.
  • The Fourier transform of the weighted test function is controlled by combining Gaussian smoothing with a box-like factor derived from the sinc transform.The box is chosen to cover nearly all relevant Gaussian mass for bounded data.
  • The proof bounds the test function’s ℓ2 norm and Fourier-transform error using tail estimates, integral decompositions, and Gaussian concentration claims.
  • Choosing u = 2000 log nλ and combining the preceding lemmas yields the theorem under the stated bounds on n, λ, d, R, and η.

D Proof of Theorem 17

The proof of Theorem 17 constructs bounded-grid data and a Fourier-based witness vector to lower-bound the Gaussian ridge leverage function. Fourier identities, sampling arguments, and Gaussian tail bounds establish the result under restrictive low-dimensional parameter conditions.

  • The lower-bound construction places n = m^d data points on an evenly spaced grid in [−R, R]^d.
  • The witness vector α consists of samples of a modified weighted Fourier-transform function evaluated at the grid points.Its construction is linked to the softened-spike test function used in the upper-bound analysis.
  • Fourier-transform and convolution identities characterize the witness function as shifted Gaussian terms multiplied by sinc factors.
  • Nyquist-Shannon sampling and grid-sum bounds control the discrete witness quantities needed for the leverage lower bound.
  • The final theorem follows by combining the lemmas after setting v = R and b = R/(8√log nλ), under explicit restrictions on dimension, regularization, grid size, and boundedness.

E Proof of Corollary 18

The corollary bounds statistical dimension using Gaussian-tail estimates and proves the result by combining naive and refined bounds. Its proof also establishes the needed high-probability control over the relevant norm.

  • Auxiliary claims: The proof states a d-dimensional ball-volume claim used in deriving the corollary.The volume is expressed through the Gamma function.
  • Statistical-dimension upper bound: The first corollary claim provides an upper bound on statistical dimension using t = 10√log nλ.The argument begins with a naive bound and then applies a refined bound for η satisfying ∥η∥∞ ≤ t.
  • Tail estimate: The tail estimate relies on converting polar coordinates to Cartesian coordinates and controlling rd−1e−r2/2 by e−r2/4 when |r| ≥ t.This comparison holds under the lemma’s condition d ≤ t2/(4 log t).
  • Conclusion: Combining the refined bound with the preceding estimate completes the lemma.The proof explicitly invokes Claim 46 for the second inequality and combines equations (59) and (60).
  • Second corollary claim: The second corollary claim reuses the point construction from Theorem 17 and applies its result to the relevant η range.The proof notes the non-negativity of τ and attributes the final equality to Claim 46.

F Proof of Theorem 10

The theorem proof establishes a lower bound for classical random Fourier feature sampling by constructing a high-leverage frequency and showing that insufficient sampling fails spectral approximation with constant probability.

  • Lower-bound strategy: The proof targets a lower bound on samples required for spectral approximation by classical random Fourier features.It connects this lower bound to the leverage-score lower bound of Theorem 17 and the maximization characterization in Lemma 15.
  • Leverage-score mechanism: A high ridge-leverage frequency implies an α concentrated at that frequency, so inadequate sampling can leave αT(K + λIn)α poorly approximated.The proof formalizes this mechanism through the definitions of Z and ϕ and the sample distribution p.
  • Hard-instance construction: The construction reuses n data points from Definition 39, selects η∗, and defines α to make the approximation failure condition hold with high probability.The goal is to show that for too few samples there exists α satisfying the target inequality with at least constant probability.
  • Norm control: With probability 0.99, the constructed frequency satisfies ∥η∗∥∞ ≤ 80√log nλ.This follows from the corresponding bound on η∗ and a union-bound argument over the relevant entries.
  • Case analysis: The remaining estimates bound the terms in the failure inequality using Lemmas 47, 45, 43, and 44, with separate treatments for d = 1 and d > 1.The d > 1 case uses conditions implying R ≥ 40 and d < R/25.
  • Final probability bound: Combining inequalities (64)–(67) yields the desired failure event with probability at least 0.4.The proof concludes the lower-bound argument after combining the four preceding estimates.
Loading 1804.09893v2…