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

arXiv: https://arxiv.org/abs/1904.00687 · HTML: https://mlsanity.com/paper/1904.00687/

## Key facts

- Cited by 103 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2019.

## Built on by (most cited first, 30 of 103)

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Understanding neural networks with reproducing kernel Banach spaces](https://mlsanity.com/paper/2109.09710/) (2021)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers](https://mlsanity.com/paper/2102.07346/) (2021)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks](https://mlsanity.com/paper/2306.04073/) (2023)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Properties of the After Kernel](https://mlsanity.com/paper/2105.10585/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Sparse Neural Additive Model: Interpretable Deep Learning with Feature Selection via Group Sparsity](https://mlsanity.com/paper/2202.12482/) (2022)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Learning sparse features can lead to overfitting in neural networks](https://mlsanity.com/paper/2206.12314/) (2022)
- [Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks](https://mlsanity.com/paper/2104.03093/) (2021)
- [The Limitations of Large Width in Neural Networks: A Deep Gaussian Process Perspective](https://mlsanity.com/paper/2106.06529/) (2021)
- [Operator Learning Using Random Features: A Tool for Scientific Computing](https://mlsanity.com/paper/2408.06526/) (2024)
- [Understanding Deflation Process in Over-parametrized Tensor Decomposition](https://mlsanity.com/paper/2106.06573/) (2021)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)

## Abstract (arXiv)

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.