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