Scaling Kernel Methods with Random Fourier Features

1,657 concepts905 papers13 proposals

Kernel methods are among the most mathematically elegant tools in machine learning. By utilizing the "kernel trick," algorithms like Support Vector Machines (SVMs) and Gaussian Processes (GPs) can implicitly map data into infinite-dimensional feature spaces, allowing them to learn highly complex, non-linear relationships.

However, this elegance comes with a severe computational penalty. Because the feature mapping is implicit, these methods must compute and store an $N \times N$ kernel matrix (or Gram matrix), where $N$ is the number of data points. Training typically scales quadratically ($O(N^2)$) or cubically ($O(N^3)$) with the dataset size. As Zhiyun Lu et al. note in How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets, this bottleneck historically prevented kernel methods from competing with Deep Neural Networks (DNNs) on massive, modern datasets.

To break this bottleneck, we need a way to bypass the implicit $N \times N$ matrix entirely. This is achieved through Random Fourier Features (RFF): a technique that constructs an explicit, low-dimensional approximation of the kernel space, turning a slow non-parametric problem into a fast parametric one.

The Intuition of Explicit Linearization

If we could explicitly map our input data $x$ into a finite, low-dimensional feature vector $z(x) \in \mathbb{R}^m$ such that the standard dot product approximates our kernel function—that is, $k(x, y) \approx z(x)^T z(y)$—we would no longer need the kernel trick.

Instead of manipulating a massive $N \times N$ matrix, we could transform our entire dataset into an $N \times m$ matrix. If the number of random features $m$ is much smaller than the number of data points $N$, we can solve our machine learning problem in the primal space. Optimization then scales linearly with $N$, allowing kernel methods to handle millions of training examples.

But how do we find a finite-dimensional mapping $z(x)$ that accurately mimics an infinite-dimensional kernel? The trick is to look at the kernel through the lens of the frequency domain.

Why it Works: Bochner's Theorem

For shift-invariant kernels—kernels where the similarity between two points depends only on the displacement between them, or $k(x, y) = k(x - y)$, such as the popular Radial Basis Function (RBF) Gaussian kernel—we can invoke a powerful result from Fourier analysis known as Bochner's Theorem.

Bochner's Theorem states that a continuous, shift-invariant kernel is positive-definite if and only if it is the Fourier transform of a positive finite measure $p(\omega)$. In the context of machine learning, this means that any valid shift-invariant kernel has an associated probability density function $p(\omega)$, which represents the kernel's spectral density (or power spectrum).

Mathematically, we can write the kernel as the inverse Fourier transform of its spectral density:

$$k(x - y) = \int_{\mathbb{R}^d} p(\omega) e^{i \omega^T (x - y)} d\omega$$

Because this integral is weighted by a probability distribution $p(\omega)$, it can be rewritten as an expectation:

$$k(x - y) = \mathbb{E}_{\omega \sim p} \left[ e^{i \omega^T (x - y)} \right]$$

Since the kernel is real-valued, we can discard the imaginary part of the complex exponential. Using trigonometric identities, this expectation simplifies to:

$$k(x - y) = \mathbb{E}_{\omega \sim p, b \sim \text{Uniform}(0, 2\pi)} \left[ \sqrt{2} \cos(\omega^T x + b) \cdot \sqrt{2} \cos(\omega^T y + b) \right]$$

This formulation reveals something extraordinary: the value of the kernel function is exactly equal to the expected inner product of two random cosine projections.

To approximate this expectation, we can use a standard Monte Carlo average. We draw $m$ random frequencies $\omega_1, \dots, \omega_m$ from the kernel's spectral density $p(\omega)$ (for a Gaussian kernel, $p(\omega)$ is simply another Gaussian distribution) and sample $m$ random phases $b_1, \dots, b_m$. This yields our explicit randomized feature map:

$$z(x) = \frac{\sqrt{2}}{\sqrt{m}} \begin{bmatrix} \cos(\omega_1^T x + b_1) \\ \cos(\omega_2^T x + b_1) \\ \vdots \\ \cos(\omega_m^T x + b_m) \end{bmatrix}$$

As Maxim Raginsky et al. demonstrate in Locality-sensitive binary codes from shift-invariant kernels, the inner product $z(x)^T z(y)$ directly converges to $k(x, y)$ as $m$ increases. Furthermore, Bharath K. Sriperumbudur et al. proved in Optimal Rates for Random Fourier Features that the approximation error decreases at a steady rate of $m^{-1/2}$ and depends only logarithmically on the diameter of the data domain, guaranteeing high fidelity even with a modest number of features.

From Non-Parametric to Parametric

By substituting $k(x, y)$ with $z(x)^T z(y)$, we fundamentally alter the architecture of the underlying model. A non-parametric model, whose complexity grows with the size of the dataset, is transformed into a parametric model with a fixed number of parameters.

Consider a Gaussian Process. Standard GP inference requires inverting the Gram matrix, an $O(N^3)$ operation. When we apply Random Fourier Features, the GP's covariance structure is mapped onto a finite-rank basis of trigonometric functions. As the authors of Deep Gaussian Process autoencoders for novelty detection point out, this expansion structurally converts the non-parametric GP into a standard linear Bayesian regression model—effectively a two-layer neural network where the first layer's weights are fixed random draws from the spectral distribution.

Property Traditional Kernel Methods Random Fourier Features
Representation Implicit (Infinite-Dimensional) Explicit (Finite $m$-Dimensional)
Model Type Non-parametric (Grows with $N$) Parametric (Fixed by $m$)
Time Complexity $O(N^2)$ to $O(N^3)$ $O(N \cdot m)$
Memory Complexity $O(N^2)$ (Stores Gram Matrix) $O(N \cdot m)$ (Stores Features)

Unlocking Real-Time and Large-Scale Applications

The transition from quadratic/cubic scaling to linear scaling has allowed researchers to deploy kernel methods in domains where they were previously computationally impossible.

Real-Time Robotic Control

In reinforcement learning and continuous control, agents must update their models and choose actions within milliseconds. Exact Gaussian Processes are too slow for these tight loops. By utilizing RFF to approximate value functions and transition dynamics, Philippe Morere et al. in Bayesian RL for Goal-Only Rewards and Joe Watson et al. in Inferring Smooth Control: Monte Carlo Posterior Policy Iteration with Gaussian Processes successfully reduced the computational overhead of Bayesian updates from cubic to quadratic or linear, enabling real-time, uncertainty-aware robotic control.

Linear-Time Statistical Testing

Statistical metrics like Maximum Mean Discrepancy (MMD) are widely used to determine if two sets of samples come from the same underlying distribution. However, exact MMD scales quadratically with sample size. In FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test, the authors use RFF to project data into a randomized space where distribution discrepancies can be calculated in linear time. Similarly, Dan Amir demonstrates in Understanding and Simplifying Perceptual Distances that complex perceptual losses in deep networks can be reframed and simplified as MMD calculations over image patches using a fixed, two-layer random Fourier network.

Analytic Global Optimization

In Bayesian optimization, finding the next point to evaluate requires maximizing an acquisition function across the entire search space. José Miguel Hernández-Lobato shows in Predictive Entropy Search for Efficient Global Optimization of Black-box Functions that by approximating a GP with a finite-dimensional RFF model, one can analytically optimize sample paths. This bypasses expensive grid searches or discrete approximations, making global optimization over continuous spaces highly efficient.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 997 papers
  2. Version 1 · 2026-10-04 · 1106 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_random_feature_kernel_approximation_52f924b7,
  title = {random feature kernel approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-feature-kernel-approximation/rdr_52f924b713f2447283416ed6b8c06a6d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_random_feature_kernel_approximation_52f924b7_v2,
  title = {random feature kernel approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-feature-kernel-approximation/rdr_52f924b713f2447283416ed6b8c06a6d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake