Kernel methods allow machine learning models to capture complex, non-linear relationships, but they traditionally suffer from a "curse of support": as the number of data points $N$ grows, the cost of computing the kernel matrix scales quadratically ($O(N^2)$) or even cubically. To bypass this, researchers use Random Features (RFs) to map data into a lower-dimensional linear space where the inner product approximates the kernel function.
While the original Random Fourier Features (RFF) revolutionized the field, they rely on standard Monte Carlo sampling, which introduces significant statistical noise. Recent research focuses on reducing this variance to achieve high-precision approximations with fewer features, enabling kernels to scale to massive datasets without sacrificing accuracy.
The Variance Bottleneck
The core challenge in random feature approximation is the trade-off between computational efficiency and statistical stability. Standard Monte Carlo sampling exhibits a slow convergence rate of $O(1/\sqrt{M})$, where $M$ is the number of features. As noted by Fuxin Li and Guy Lebanon, this slow decay necessitates a prohibitively large number of features to reach acceptable error levels, which can negate the speed advantages of linearization.
Furthermore, Krzysztof Marcin Choromanski and colleagues highlight that many estimators are "unbalanced"—they might be precise for large kernel values but become highly volatile for values near zero. This variance leads to noisy gradients and unstable training in downstream models like "linearized" Transformers.
Beyond Monte Carlo: Structured Sampling
To achieve higher precision, researchers have moved away from pure randomness toward structured, deterministic, or "quasi-random" sampling strategies:
- Quasi-Monte Carlo (QMC): Jiyan Yang and Michael W. Mahoney demonstrated that using low-discrepancy sequences instead of random draws prevents "clumping" of points, leading to much more accurate feature maps. Yian Huang further refined this with Randomized QMC (RQMC), which maintains these benefits while remaining robust in high-dimensional spaces.
- Numerical Quadrature: Instead of sampling, methods like those proposed by Marina Munkhoeva and Ivan Oseledets treat kernel approximation as an integration problem. By using spherical-radial quadrature rules and "butterfly" matrices, they achieve higher-order accuracy that significantly outperforms standard RFF.
- Moment Matching: Weiwei Shen and Jun Wang introduced techniques to ensure that a finite set of random samples exactly matches the mean and covariance of the target distribution, drastically reducing variance in high-dimensional settings.
Geometric and Optimal Transport Perspectives
A sophisticated branch of this research explores the geometry of the feature space itself. Isaac Reid and Adrian Weller introduced Simplex Random Features (SimRFs), which move beyond simple orthogonal vectors to a "simplex" geometry. By ensuring vectors subtend obtuse angles, they achieve the lowest possible estimation error for Gaussian and softmax kernels.
More recently, Isaac Reid and Richard E. Turner have framed variance reduction as an Optimal Transport problem. This framework allows for "pairwise norm-coupling" to reduce noise. Interestingly, they also discovered a counter-intuitive phenomenon in Transformers: while variance reduction is usually the goal, maximizing variance through positive correlation can actually improve performance in certain attention mechanisms.
Stability and Positivity
For specific architectures like the Performer (a linear Transformer), the stability of the random features is paramount. Valerii Likhosherstov and Avinava Dubey developed Chefs’ Random Tables (CRTs), which provide the first unbiased kernel estimator that is both positive and bounded. This prevents the numerical "blow-ups" common in other methods, ensuring that the feature mapping reliably concentrates around the true kernel value.