Kernel methods are the "gold standard" for non-linear learning, but they suffer from a classic scaling problem: as your dataset grows to $N$ points, the cost of computing the kernel matrix grows at $O(N^2)$, and solving the system grows at $O(N^3)$.
Random Fourier Features (RFF) were introduced to break this bottleneck. By mapping data into a randomized, finite-dimensional feature space of size $M$, we can use linear solvers to approximate kernel machines. For years, the conventional wisdom was that to maintain the accuracy of the full kernel, you needed a number of features $M$ roughly equal to the number of data points $N$.
However, a surge of theoretical work has revealed a much more optimistic reality: you can achieve optimal statistical performance with significantly fewer features—often scaling as $O(\sqrt{N})$.
The Approximation-Generalization Balance
To understand why sublinear scaling works, we have to look at the two sources of error in a model:
- Statistical Risk: The error inherent in having only a finite number of data points $N$.
- Approximation Error: The error introduced by using $M$ random features instead of the infinite-dimensional kernel.
In Towards a Unified Analysis of Random Fourier Features, Zhu Li, Dino Sejdinovic, and colleagues argue that we don't need a "perfect" approximation of the kernel. We only need the approximation error to be smaller than the statistical risk.
If the kernel's eigenvalues decay quickly (which is true for common kernels like the Gaussian RBF), the most important information is concentrated in a small subspace. Once $M$ is large enough to capture this subspace, adding more features provides diminishing returns because the model's accuracy is already limited by the amount of data $N$, not the quality of the approximation.
Deterministic Equivalents and Scaling Laws
How do we know exactly how many features are "enough"? Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz addressed this in Dimension-free deterministic equivalents and scaling laws for random feature regression.
They derived "deterministic equivalents"—closed-form expressions that predict the test error based solely on the eigenvalues of the feature map. This framework proves that the optimal number of features depends on the "effective dimension" of the task. In many practical scenarios, this allows practitioners to drastically reduce $M$ without sacrificing generalization, effectively decoupling the computational cost from the raw size of the dataset.
Sharper Bounds for Classification and Operators
This sublinear trend holds across different tasks. In Sharp Analysis of Random Fourier Features in Classification, researchers showed that for classification, $O(\sqrt{N} \log N)$ features are sufficient for minimax optimality. This represents a massive memory saving, moving from linear to sublinear complexity.
Even in more complex settings, like infinite-dimensional operator learning, the pattern persists. Samuel Lanthaler and Nicholas H. Nelsen demonstrated in Error Bounds for Learning with Vector-Valued Random Features that by using a direct risk analysis, one can eliminate the logarithmic overhead typically found in older bounds, confirming that $M \approx \sqrt{N}$ is a fundamental scaling law for vector-valued regression.
Beyond Uniform Sampling
If the goal is to minimize $M$, how we choose our random features matters. Standard RFF uses simple Monte Carlo sampling from the Fourier transform of the kernel. However, not all frequencies are equally important.
- Ridge Leverage Scores: Zhu Li and Dino Oglic proposed data-dependent sampling based on "ridge leverage scores." By oversampling the features that are most representative of the actual data distribution, they achieve even tighter approximations with fewer features.
- Quasi-Monte Carlo: Yian Huang explored Randomized Quasi-Monte Carlo Features, which use low-discrepancy sequences to cover the frequency space more evenly than pure randomness. This approach further accelerates the convergence of the approximation error, allowing for even smaller feature sets.
Why It Matters
The shift from $M=N$ to $M=\sqrt{N}$ is not just a theoretical curiosity; it changes the feasibility of kernel methods for massive data. As surveyed by Fanghui Liu in Random Features for Kernel Approximation, these insights bridge the gap between classical kernels and modern neural networks. By understanding that we only need a sublinear number of features to reach the statistical limit of our data, we can build models that are both theoretically grounded and computationally efficient enough for millions of samples.