Data-Dependent Sampling for Random Fourier Features

This direction is merged into another direction: kernel method scalability (computational complexity of kernel methods). Its last version stays readable and citable here.

Version 1 of 130 papers31 conceptsfrozen 2026-10-04

Kernel methods are among the most mathematically elegant tools in machine learning, offering a way to learn complex, non-linear patterns by implicitly mapping data into an infinite-dimensional space. However, they face a notorious "scalability wall": as the number of data points $n$ increases, the computational cost of standard kernel algorithms explodes at $O(n^3)$.

To break this wall, researchers often use Random Fourier Features (RFF). By Bochner’s Theorem, any shift-invariant kernel can be represented as the Fourier transform of a probability distribution. RFF leverages this by sampling a finite set of random frequencies from that distribution to create a low-dimensional approximation of the kernel. While this makes kernel methods scalable, it introduces a new problem: standard RFF is "blind" to the actual data.

The Inefficiency of Blind Sampling

In the classic RFF framework, features are sampled independently of the training data. As noted by Shahin Shahrampour and Ahmad Beirami in On Data-Dependent Random Features for Improved Generalization in Supervised Learning, this data-agnostic approach is often highly inefficient. Because the sampling distribution is based solely on the kernel's spectral properties, it may prioritize regions of the feature space where no data actually exists.

To compensate for this mismatch, practitioners are often forced to use an excessively large number of features to ensure the sampled space covers the relevant data manifold. This redundancy increases memory and computational overhead, potentially offsetting the efficiency gains of using random features in the first place. As Brian Bullins and colleagues argue in Not-So-Random Features, these "random" features often result in high-dimensional representations where many dimensions are uninformative or redundant.

Learning the Posterior Distribution

The core insight of recent research is to move from data-independent sampling to data-dependent selection. Instead of treating the kernel's Fourier transform as a fixed sampling distribution, we can treat it as a prior and use the training data to find a more effective posterior.

Gaël Letarte and Pascal Germain formalize this in Pseudo-Bayesian Learning with Kernel Fourier Transform as Prior. By framing RFF through PAC-Bayesian theory, they show that one can learn a data-dependent distribution over trigonometric hypotheses. This ensures that the features are optimally aligned with the specific patterns in the dataset, leading to better generalization with fewer dimensions.

Importance Sampling via Leverage Scores

One of the most effective ways to implement this data-awareness is through leverage scores. In linear algebra, leverage scores identify which rows or columns of a matrix are most "influential" to its structure. In the context of kernels, leverage scores tell us which Fourier frequencies are most critical for representing the specific dataset at hand.

However, calculating exact leverage scores is computationally expensive—often as expensive as the $O(n^3)$ problem we are trying to avoid. To solve this, Fanghui Liu and Yudong Chen introduced a "fast surrogate" sampling strategy in Random Fourier Features via Fast Surrogate Leverage Weighted Sampling. By replacing expensive matrix inversions with a simpler surrogate function, they reduce the complexity of data-dependent sampling to $O(ns^2)$, achieving the accuracy of sophisticated sampling with the speed of random methods.

Supervised and Task-Specific Selection

While some methods look only at the distribution of the input data ($X$), others incorporate the labels ($y$) to find features that are specifically useful for the target task.

Why It Works: Breaking the Variance Bound

The theoretical justification for these methods lies in variance reduction. As proven by Luke Sernau and Silvano Bonacina in All Random Features Representations are Equivalent, while many different feature mappings exist, an optimal importance sampling strategy (like leverage score sampling) achieves the minimum possible variance for a given number of features.

By moving away from "blind" sampling and toward data-dependent mechanisms, these researchers have shown that we can achieve state-of-the-art accuracy with significantly smaller models. Whether through leverage scores, PAC-Bayesian priors, or energy-based selection, the goal remains the same: making kernel methods truly scalable by ensuring every random feature counts.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_data_dependent_sampling_for_random_fouri_b9cfb3aa,
  title = {Data-Dependent Sampling for Random Fourier Features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-dependent-sampling-for-random-fourier-features/rdr_b9cfb3aa9ceb49f8bc7d656cf7e70dcd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_data_dependent_sampling_for_random_fouri_b9cfb3aa_v1,
  title = {Data-Dependent Sampling for Random Fourier Features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-dependent-sampling-for-random-fourier-features/rdr_b9cfb3aa9ceb49f8bc7d656cf7e70dcd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}