Generalization Properties of Learning with Random Features

Alessandro Rudi, Raffaello Camoriano, Lorenzo Rosasco

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.

Introduction

Kernel methods, such as Kernel Ridge Regression (KRR), are powerful tools for non-parametric learning. However, they suffer from a significant "scalability wall," typically requiring $O(n^2)$ space and $O(n^3)$ time, which makes them unfeasible for massive datasets.

Random Features (RF) were introduced as a clever workaround. By mapping data into a lower-dimensional space using random basis functions, we can approximate complex kernels and solve the problem using fast, linear techniques. However, a lingering theoretical question remained: How many random features do we actually need to ensure we aren't sacrificing accuracy? Previous bounds suggested a linear scaling of $M = O(n)$ features, which offers limited computational relief. This work closes the gap between theory and practice by providing much sharper generalization bounds.

Theoretical Framework and Methods

The authors analyze Ridge Regression with Random Features within a statistical learning framework, leveraging advanced analytic and probabilistic tools. They decompose the excess risk into three primary components:

  1. Sample Error: Noise inherent in the finite data sample.
  2. Computational Error: The approximation error introduced by using $M$ random features instead of the full kernel.
  3. Approximation Error: How well the chosen kernel space fits the true target function.

By treating random features as a Monte Carlo approximation of an integral operator, the authors derive bounds that depend on the regularity of the target function and the capacity of the hypothesis space.

Key Insights: The "Square Root" Breakthrough

The most significant finding is the proof that for a standard learning rate of $O(1/\sqrt{n})$, only $M = O(\sqrt{n} \log n)$ random features are required. This is a massive improvement over the previously assumed $O(n)$, proving that random features can be exponentially more efficient than previously thought. This result identifies a "sweet spot" where computational costs can be drastically reduced without any loss in prediction accuracy.

Smarter Sampling for Faster Rates

While uniform sampling is sufficient for basic rates, the paper demonstrates that achieving "fast" learning rates (e.g., $O(1/n)$) in high-regularity problems requires more sophisticated sampling. The authors explore leverage scores—a problem-dependent sampling distribution that picks the random features most compatible with the specific data distribution.

Comparison of the exponent $c$ for the number of random features $M=n^c$ required for optimal generalization using uniform sampling (left) vs. leverage score sampling (right). Cooler colors indicate fewer features are needed.

As illustrated in the figure above, the exponent $c$ (where $M = n^c$) required to achieve optimal rates varies with the problem's regularity ($r$) and capacity ($\gamma$). Leverage score sampling (right) significantly expands the regime where a small number of features (lower $c$) is sufficient compared to uniform sampling (left).

Numerical Validation

The authors validate their theorems using synthetic numerical simulations, such as a spline kernel of varying orders. These simulations show that the theoretical predictions for the excess risk and the required $M$ align closely with empirical behavior, staying within one standard deviation across multiple repetitions. This confirms that the theoretical "square root" and fast-rate bounds are not just mathematical artifacts but reflect actual performance characteristics.

Limitations and Future Work

The current analysis is tailored to the squared loss (Ridge Regression). Extending these sharp bounds to other loss functions, such as Logistic Regression or Hinge Loss, remains an open challenge. Additionally, while leverage scores are theoretically superior, calculating them in practice can be expensive. Developing efficient, approximate numerical strategies for leverage score sampling is a key direction for future research to make these theoretical gains fully accessible in practical 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 Raffaello Camoriano 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