Kernel methods are powerful tools for capturing non-linear relationships, but they suffer from a "curse of kernelization": their computational cost typically scales quadratically or cubically with the number of data points $n$. To bypass this, researchers use Random Features (RF) to map data into a finite-dimensional space where the inner product approximates the original kernel. This transformation turns complex non-linear problems into efficient linear ones. However, this efficiency introduces a fundamental trade-off: using too few features leads to high approximation error, while using too many negates the computational benefits.
The Geometry of Approximation Error
The core intuition behind random features, popularized by Rahimi et al., is that a shift-invariant kernel can be viewed as the expectation of a product of random basis functions. By sampling $M$ such functions, we create a Monte Carlo approximation of the kernel.
As noted by Stuart et al., the approximation error in these models typically scales at a rate proportional to $1/\sqrt{M}$. This creates a predictable but punishing relationship: to halve the error, one must quadruple the number of features. In high-dimensional spaces or for complex kernels, this requirement can lead to a massive memory footprint, as the storage cost remains proportional to $M$ (Lopez-Paz et al.).
Breaking the Linear Scaling Myth
For years, theoretical bounds suggested that to maintain the statistical optimality of the original kernel method, the number of features $M$ had to scale linearly with the number of data points $n$. If $M \approx n$, the computational advantage of the approximation vanishes.
However, Rudi et al. provided a breakthrough by proving that $M = O(\sqrt{n} \log n)$ features are actually sufficient to achieve optimal generalization. This means that as datasets grow, the relative number of features required actually decreases. This finding is echoed in the context of dimensionality reduction; Ullah et al. demonstrated that $\tilde{O}(\sqrt{n})$ features are sufficient for Kernel PCA to achieve optimal statistical rates, making non-linear dimensionality reduction viable for massive streaming datasets.
Reducing Variance through Structure
Since the approximation error stems from the variance of Monte Carlo sampling, researchers have sought ways to make each random feature "work harder." Standard Random Fourier Features (RFF) use independent Gaussian projections, which often result in redundant samples that cluster together, leaving other parts of the spectral space empty.
Yu et al. introduced Orthogonal Random Features (ORF) to solve this. By forcing the random projection vectors to be orthogonal rather than independent, they ensure a more uniform "covering" of the kernel's spectral distribution. This structural tweak significantly reduces the approximation variance, allowing for higher fidelity with fewer features. To further optimize speed, the authors proposed Structured ORF (SORF), which uses fast Walsh-Hadamard transforms to reduce the projection time from $O(d^2)$ to $O(d \log d)$. Similarly, Feng explored signed circulant matrices to achieve log-linear computation time, though they noted a trade-off where structured matrices can sometimes increase variance compared to unstructured ones.
Data-Dependent and Adaptive Features
A major source of inefficiency in traditional random features is that they are "data-blind"—the features are sampled from a fixed distribution (like a Gaussian) regardless of the actual data distribution. This often necessitates a very high $M$ to capture the relevant signal.
To address this, Chen et al. proposed Training-Efficient Feature Maps (TEFM), which combine random features with data-dependent subspace embeddings to achieve high precision with fewer components. Taking this further, Le et al. introduced Reparameterized Random Features (RRF), which allow the parameters of the kernel itself (such as the Gaussian width) to be learned via stochastic gradient descent alongside the model weights. By adapting the feature distribution to the data, these methods break the rigid trade-off between dimensionality and accuracy, enabling compact models that maintain high expressive power (Li et al.).
Implicit Regularization and Resource Allocation
The choice of $M$ does not just affect speed; it also changes the model's behavior. Carratino et al. argued that the number of features acts as an implicit regularizer. In this view, the trade-off is not just between "fast and slow" but between different ways of preventing overfitting.
In modern architectures like Transformers, this trade-off is being applied layer-by-layer. Nishikawa et al. demonstrated that by measuring the "degrees of freedom" in different layers, one can adaptively allocate more features to complex layers and fewer to simple ones. This granular approach to the dimensionality trade-off allows for the distillation of heavy softmax attention into efficient linear attention without the accuracy loss typically associated with low-rank approximations.