Generalization Properties of Learning with Random Features

Alessandro Rudi, Lorenzo Rosasco

Executive Summary

This paper demonstrates that random features are significantly more efficient for machine learning than previously believed. While earlier research suggested that matching the performance of exact kernel methods required a number of random features proportional to the dataset size ($M \approx n$), this work proves that $O(\sqrt{n} \log n)$ features are actually sufficient to achieve optimal generalization. This theoretical breakthrough offers a massive computational speedup for large-scale learning without sacrificing predictive accuracy.

The Scalability Bottleneck in Kernel Methods

Kernel methods, such as Kernel Ridge Regression (KRR), are considered a gold standard for non-parametric learning due to their ability to model complex, non-linear relationships. However, they suffer from a major scalability bottleneck. To process $n$ data points, exact kernel methods typically require $O(n^2)$ memory and $O(n^3)$ computational time, rendering them impractical for modern, large-scale datasets.

"Random Features" (RF) were introduced to circumvent this issue by approximating the kernel with a finite-dimensional map. By utilizing $M$ random features, the computational complexity drops to $O(nM^2 + M^3)$. The central question for researchers has been: How large must $M$ be to ensure no loss in prediction accuracy?

Previous influential theoretical bounds suggested that $M$ needed to be proportional to $n$, which largely defeats the purpose of the approximation. This paper aims to close the gap between this theoretical pessimism and the widespread empirical success of random features.

Methodology

Rather than solely evaluating how well random features approximate the kernel function—a common approach in earlier literature—the authors analyze Ridge Regression with Random Features within a statistical learning framework. They focus on how well the resulting model generalizes to unseen data.

Key technical components of their analysis include:

  • Integral Representation: The assumption that the kernel can be expressed as an expectation over a random function (e.g., Random Fourier Features).
  • Effective Dimension ($\mathcal{N}(\lambda)$): A metric capturing the "size" or complexity of the Reproducing Kernel Hilbert Space (RKHS) relative to the underlying data distribution.
  • Source Condition: An assumption regarding the smoothness or regularity of the true target function being learned.
  • Problem-Dependent Sampling: An exploration of feature sampling distributions that account for the data (inspired by "leverage scores"), rather than relying solely on uniform random sampling.

To validate their mathematical proofs, the authors employ synthetic numerical simulations using a spline kernel on a uniform marginal distribution, comparing theoretical error bounds and required features ($M$) against actual simulations.

Key Insights and Results

"Less is More" via Regularization

A primary insight of the paper is that perfect kernel approximation is unnecessary for an optimal predictor. Because the learning process inherently involves regularization ($\lambda$), this regularization effectively "masks" the errors in the kernel approximation, allowing for a substantially smaller $M$.

The $\sqrt{n}$ Threshold

For the standard learning rate of $O(1/\sqrt{n})$, the authors prove that only $O(\sqrt{n} \log n)$ features are needed. This represents a quadratic improvement in the required number of features compared to previous theoretical results. Specifically, with $M = O(\sqrt{n} \log n)$ and $\lambda = n^{-1/2}$, the random feature estimator achieves the same $O(1/\sqrt{n})$ error as the computationally expensive full kernel ridge regression.

Massive Computational Gains

This theoretical result translates directly into practical efficiency. It implies that practitioners can reduce computational time from $O(n^3)$ to $O(n^2)$ and memory requirements from $O(n^2)$ to $O(n\sqrt{n})$ without any degradation in statistical performance.

Fast Rates and Leverage Scores

The paper also demonstrates that if a problem is "easy" (i.e., the target function is highly smooth), faster convergence rates (such as $O(1/n)$) are achievable. While this might require more features under uniform sampling, the authors show that sampling features according to a "compatibility condition"—essentially prioritizing features most relevant to the data distribution—can achieve these fast rates with significantly fewer features, sometimes even a constant number independent of $n$.

Limitations and Future Work

  • Loss Function Dependency: The current analysis is specific to the squared loss used in ridge regression. While the authors hypothesize that the results might extend to other loss functions (like Hinge loss for Support Vector Machines), the existing proofs rely heavily on the linear algebraic structure of least squares.
  • Practical Sampling: The highly efficient "problem-dependent sampling" requires prior knowledge of the data distribution or the computation of leverage scores. Developing efficient, data-driven methods to estimate these scores for random features remains a critical area for future research.
  • Optimization Dynamics: The paper focuses strictly on the statistical properties of the solution rather than the optimization path (e.g., Stochastic Gradient Descent). Combining these generalization bounds with an analysis of iterative solvers would provide a more comprehensive guide for real-world applications.

Summary updated

Abstract

We study the generalization properties of ridge regression with random features in the statistical learning framework. We show for the first time that $O(1/\sqrt{n})$ learning bounds can be achieved with only $O(\sqrt{n}\log n)$ random features rather than $O({n})$ as suggested by previous results. Further, we prove faster learning rates and show that they might require more random features, unless they are sampled according to a possibly problem dependent distribution. Our results shed light on the statistical computational trade-offs in large scale kernelized learning, showing the potential effectiveness of random features in reducing the computational complexity while keeping optimal generalization properties.
BibTeX
@inproceedings{rudi2017generalization,
  author = {Alessandro Rudi and Lorenzo Rosasco},
  title = {{Generalization Properties of Learning with Random Features}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=HkNvEDWuZH},
}
Figure