On the Power and Limitations of Random Features for Understanding Neural Networks

Gilad Yehudai, Ohad Shamir

Introduction

Deep neural networks consistently achieve remarkable success despite being heavily over-parameterized—possessing far more parameters than training examples. A prominent theoretical framework attempting to explain this phenomenon is the "lazy training" regime. In this regime, gradient descent barely alters the weights of a sufficiently large network from their random initializations. Instead, the network effectively operates as a linear predictor over a fixed set of random features.

While this perspective has yielded numerous positive theoretical results, Yehudai and Shamir investigate a critical question: Is the random features view sufficient to fully explain the expressive power and learning capabilities of neural networks? Specifically, if a simple model is known to be easily learnable by a real neural network, can a random feature model learn it just as efficiently?

The Random Features Hypothesis

The authors begin by formalizing the connection between lazy gradient descent in over-parameterized networks and linear models utilizing fixed random features. They provide a self-contained mathematical proof demonstrating that one-hidden-layer networks can successfully learn low-degree polynomials using the random features approach. This aligns with existing literature and validates the hypothesis for certain smooth functions, highlighting the "positive" explanatory power of the random features framework.

Methodology

To probe the limitations of this framework, the authors shift away from empirical datasets and rely on rigorous mathematical analysis over synthetic distributions. Specifically, they analyze standard Gaussian distributions in high-dimensional space ($\mathbb{R}^d$).

To construct their lower bound proofs, they introduce a "hard" periodic, sine-like function that is nearly uncorrelated with any fixed set of random features. Their target "ground truth" function is generated by the most fundamental building block of a neural network: a single ReLU neuron, defined as $y = [ \langle w^*, x \rangle + b^* ]_+$.

Key Findings

The study reveals a striking negative result. While random features excel at learning polynomials, they fail dramatically when tasked with approximating a single ReLU neuron.

  • Exponential Lower Bounds: The authors prove that for a random feature model to approximate a single ReLU neuron within a small error margin, the product of the number of features and the maximum weight magnitude must grow exponentially with the dimensionality, $\exp(\Omega(d))$.
  • The Efficiency Gap: In practice, standard gradient-based methods can learn a single ReLU neuron efficiently in polynomial time, $\text{poly}(d)$. The random features approach, however, requires exponential resources to achieve the same result.
  • Lazy vs. Active Learning: This massive efficiency gap proves that neural networks are not merely relying on "lazy" random feature learning. Instead, they must be actively updating their weights to perform representation learning—dynamically discovering specific features that match the data distribution rather than relying on the luck of random initialization.

Furthermore, the authors show that this limitation is universal: it applies even if the random features are generated by complex, multi-layer networks, provided their weights remain fixed near initialization.

Limitations and Implications

The authors note that their negative result relies on bounding the magnitude of the output weights. While they conjecture this constraint could be relaxed, it remains a practical consideration, as excessively large weights lead to numerical overflow in real-world systems.

Ultimately, this paper demonstrates that the random features theory is fundamentally incomplete. While it successfully explains how networks learn certain smooth functions, it fails to capture the essence of deep learning. The work underscores a crucial direction for future research: the community must develop theoretical frameworks that accurately model how weights move significantly during training to actively "carve out" useful representations from data.

Summary updated

Abstract

Recently, a spate of papers have provided positive theoretical results for training over-parameterized neural networks (where the network size is larger than what is needed to achieve low error). The key insight is that with sufficient over-parameterization, gradient-based methods will implicitly leave some components of the network relatively unchanged, so the optimization dynamics will behave as if those components are essentially fixed at their initial random values. In fact, fixing these \emph{explicitly} leads to the well-known approach of learning with random features (e.g. \citep{rahimi2008random,rahimi2009weighted}). In other words, these techniques imply that we can successfully learn with neural networks, whenever we can successfully learn with random features. In this paper, we formalize the link between existing results and random features, and argue that despite the impressive positive results, random feature approaches are also inherently limited in what they can explain. In particular, we prove that random features cannot be used to learn \emph{even a single ReLU neuron} (over standard Gaussian inputs in $\reals^d$ and $\text{poly}(d)$ weights), unless the network size (or magnitude of its weights) is exponentially large in $d$. Since a single neuron \emph{is} known to be learnable with gradient-based methods, we conclude that we are still far from a satisfying general explanation for the empirical success of neural networks. For completeness we also provide a simple self-contained proof, using a random features technique, that one-hidden-layer neural networks can learn low-degree polynomials.
BibTeX
@inproceedings{yehudai2019power,
  author = {Gilad Yehudai and Ohad Shamir},
  title = {{On the Power and Limitations of Random Features for Understanding Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=E5YJheix47T},
}
Figure