Scaling Kernel Methods with Random Fourier Features

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 21,106 papers1,618 conceptsfrozen 2026-10-04

Kernel methods were once the gold standard of machine learning, prized for their ability to model complex, non-linear relationships with elegant mathematical guarantees. However, they hit a "computational wall": as datasets grew, the cost of computing and storing the kernel matrix grew quadratically ($O(N^2)$), and solving the resulting systems often required cubic time ($O(N^3)$).

The research direction centered on Random Fourier Features (RFF) provides a way over this wall. By approximating infinite-dimensional kernels with low-dimensional, randomized feature maps, researchers have transformed kernel methods from slow, memory-intensive algorithms into scalable linear models that can compete with deep neural networks on massive datasets.

The Kernel Bottleneck and the Primal Shift

In traditional kernel methods, we avoid defining an explicit feature map $\phi(x)$ because it might be infinite-dimensional. Instead, we use the "kernel trick," working entirely with the inner products $K(x, y) = \langle \phi(x), \phi(y) \rangle$. This forces us into the dual representation, where the complexity is tied to the number of samples $N$.

As Zhiyun Lu, Avner May, and their colleagues argue in How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets, the key to scalability is shifting back to the primal representation. If we can find a finite-dimensional randomized mapping $z(x)$ such that $z(x)^\top z(y) \approx K(x, y)$, we can treat the problem as a simple linear regression or classification task. This reduces the computational cost from quadratic to linear ($O(N)$), allowing models to train on millions of examples using standard stochastic gradient descent.

The Intuition: Bochner’s Theorem

The magic of Random Fourier Features lies in Bochner’s Theorem. It states that any continuous, shift-invariant kernel (like the popular Gaussian RBF kernel) is the Fourier transform of a unique probability measure.

Think of a kernel as a way to measure similarity. Bochner’s Theorem tells us that this similarity can be decomposed into a sum of random sinusoids. By sampling frequencies from the kernel’s spectral density—essentially its "fingerprint" in the frequency domain—we can construct a randomized feature map.

In Learning Random Kernel Approximations for Object Recognition, Eduard Gabriel Băzăvan and Fuxin Li demonstrate how this transformation allows non-linear pattern recognition to scale to hundreds of thousands of examples. Instead of a massive, rigid Gram matrix, we get a flexible, finite-dimensional vector that captures the essence of the kernel.

Beyond Simple Kernels: Distributions and Dot Products

The RFF framework is not limited to standard RBF kernels. Researchers have extended these randomized approximations to handle more complex structures:

  • Distributional Data: Junier Oliva and Barnabás Póczos introduced Deep Mean Maps, which use RFFs to treat neural network features as entire distributions rather than single points. This allows models to learn patterns in the "spread" and "shape" of data, improving scene and style classification.
  • Dot Product Kernels: While RFFs typically handle shift-invariant kernels, Purushottam Kar and Harish Karnick developed Random Feature Maps for Dot Product Kernels. By using Maclaurin series expansions, they achieved massive speedups for polynomial and exponential kernels, bypassing the "Curse of Support" that slows down traditional SVMs.

Real-Time Inference and Robotics

One of the most impactful applications of this scalability is in real-time systems. Gaussian Processes (GPs) are powerful for modeling uncertainty but are notoriously slow ($O(N^3)$). By using Sparse Spectrum Gaussian Processes (SSGPs)—which rely on RFF approximations—researchers have brought GP-level reasoning to robotics.

In Adaptive Probabilistic Trajectory Optimization via Efficient Approximate Inference, the authors show how these approximations allow robots to adapt to changing environments in real-time. Similarly, Evangelos Theodorou and Yunpeng Pan utilize these features in Pseudospectral Model Predictive Control to handle unmodeled dynamics in aerospace and robotic systems, turning a computationally prohibitive inference problem into a fast, linear update.

Causal Inference as Supervised Learning

Perhaps the most creative use of RFFs is in reframing causal inference. Traditionally, determining if $X$ causes $Y$ involved rigid statistical tests. David López-Paz, Krikamol Muandet, and Benjamin Recht introduced the Randomized Causation Coefficient (RCC), which treats causal inference as a supervised learning problem.

By using RFFs to embed entire probability distributions into low-dimensional vectors, they trained a classifier to recognize the "shape" of causation. This approach is not only faster but often more accurate than traditional methods, as it learns the nuances of causal relationships directly from data rather than relying on fixed mathematical assumptions.

Conclusion

The shift toward randomized kernel approximations represents a fundamental change in how we view non-linear modeling. By leveraging the spectral properties of kernels, researchers like Dino Sejdinovic and Arthur Gretton have shown that we don't need to choose between the expressivity of kernels and the scalability of linear models. Random Fourier Features provide the bridge, allowing us to map the infinite into the finite and the quadratic into the linear.

Papers in this version

Showing 60 of 1,106 papers.

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 1, frozen text):

@misc{lacuna_scaling_kernel_methods_with_random_fouri_52f924b7_v1,
  title = {Scaling Kernel Methods with Random Fourier Features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-kernel-methods-with-random-fourier-features/rdr_52f924b713f2447283416ed6b8c06a6d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}