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

Gilad Yehudai, Ohad Shamir

Here is a summary of the paper tailored for a technically literate audience:

TL;DR

Recent theoretical work suggests that over-parameterized neural networks succeed because they behave like linear models over fixed, randomly initialized features (often called the "lazy training" regime). This paper mathematically proves that this "random features" explanation is fundamentally incomplete: it cannot efficiently explain the learning of even a single ReLU neuron without requiring an exponentially large network.

What Problem Does This Paper Address?

Despite the massive practical success of deep learning, our theoretical understanding of why over-parameterized neural networks generalize so well remains incomplete. Recently, a popular wave of theoretical papers provided a compelling explanation: if a network is wide enough, its inner weights barely change during gradient descent. Therefore, the network effectively acts as a linear classifier operating over a fixed set of "random features" determined at initialization.

Because linear models are convex and easy to analyze, this perspective yielded many positive mathematical proofs about neural network convergence. However, the authors of this paper ask a critical question: Does the random features approach actually capture the true power of neural networks? Or does it ignore the crucial element of representation learning—the network's ability to adapt its internal features to the data?

Methods

This is a purely theoretical machine learning paper. The authors use mathematical analysis, specifically focusing on $L^2$ function spaces weighted by Gaussian measures, Legendre polynomials, and concentration of measure inequalities.

The paper is structured in two main parts:

  1. A Positive Proof: For completeness, they first provide a self-contained proof showing that over-parameterized, one-hidden-layer networks can successfully learn low-degree polynomials using standard Stochastic Gradient Descent (SGD), acting purely as random features.
  2. A Negative Proof (The Core Contribution): They construct a mathematically rigorous worst-case scenario. They define a simple target function—a single ReLU neuron with standard Gaussian inputs—and prove lower bounds on the network size and weight magnitudes required to approximate this target using any fixed random features.

Datasets

Not discussed in the paper. As a theoretical work, the authors analyze expected loss over synthetic data distributions, specifically standard Gaussian distributions in $\mathbb{R}^d$.

Key Insights and Ideas

  • The "Lazy Training" Illusion: Treating neural networks as random feature generators makes the math highly tractable, but it strips away the very mechanism that makes deep learning powerful. If weights don't move much, the network isn't learning representations; it's just doing kernel regression.
  • The Single Neuron Test: A single ReLU neuron is a trivial function. We know empirically (and theoretically) that standard gradient descent can easily learn a single target neuron. Therefore, any valid "theory of deep learning" must be able to explain this basic fact.
  • The Exponential Wall: The authors prove that random features are remarkably bad at approximating a single ReLU neuron. If you restrict a network to act as a random feature model, learning a single neuron requires either an exponentially large number of neurons or exponentially massive weights.
  • Polynomials vs. ReLUs: The random features approach is great at explaining how networks learn low-degree polynomials. However, low-degree polynomials are terrible at approximating a single ReLU neuron with large weights, which explains the disconnect.

Key Results

  • Positive Result: An over-parameterized network trained with SGD can learn a polynomial of degree $k$ in $d$ dimensions, requiring a network size that scales polynomially with $d^k$.
  • Main Negative Result: Suppose you want to approximate a single target ReLU neuron $y = [\langle w^*, x \rangle + b^*]_+$ (where $x \in \mathbb{R}^d$ is a standard Gaussian and the target weight norm is $\|w^*\| = d^3$). To achieve a small constant error (e.g., $\le 1/50$) using a random features model $N(x) = \sum_{i=1}^r u_i f_i(x)$, the product of the number of features $r$ and the maximum weight magnitude $\max |u_i|$ must be at least $\exp(\Omega(d))$.
  • This negative result holds even if the random features $f_i$ are complex, multi-layer neural networks of any depth, as long as they are fixed at their random initialization.

Limitations and Future Work

  • Weight Magnitude Restriction: The main negative theorem relies on bounding the maximum magnitude of the linear weights ($\max_i |u_i|$). The authors conjecture that the exponential lower bound holds even without this restriction, leaving the proof for future work.
  • Input Distribution: The negative results are proven specifically for standard Gaussian input distributions. However, the fact that the random features approach fails on such a simple, well-behaved distribution only strengthens the authors' argument that the theory is fundamentally insufficient to explain real-world deep learning.

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 explicitly leads to the well-known approach of learning with random features. 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 first review these techniques, providing a simple and self-contained analysis for one-hidden-layer networks. We then argue that despite the impressive positive results, random feature approaches are also inherently limited in what they can explain. In particular, we rigorously show that random features cannot be used to learn even a single ReLU neuron with standard Gaussian inputs, unless the network size (or magnitude of the weights) is exponentially large. Since a single neuron is learnable with gradient-based methods, we conclude that we are still far from a satisfying general explanation for the empirical success of neural networks.
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