# On the Approximation Power of Two-Layer Networks of Random ReLUs

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 42 references that are in the map.
- First posted on arXiv 3 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Neural tangent kernels, transportation mappings, and universal approximation](https://mlsanity.com/paper/1910.06956/) (2019)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)

## Built on by (most cited first, 29 of 29)

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [On the Generalization Properties of Diffusion Models](https://mlsanity.com/paper/2311.01797/) (2023)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [The Expressive Power of Tuning Only the Normalization Layers](https://mlsanity.com/paper/2302.07937/) (2023)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable](https://mlsanity.com/paper/2205.11716/) (2022)
- [Cauchy Random Features for Operator Learning in Sobolev Space](https://mlsanity.com/paper/2503.00300/) (2025)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [Approximation with Random Shallow ReLU Networks with Applications to Model Reference Adaptive Control](https://mlsanity.com/paper/2403.17142/) (2024)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)
- [Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem](https://mlsanity.com/paper/2110.10295/) (2021)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)
- [Inference on Time Series Nonparametric Conditional Moment Restrictions Using General Sieves](https://mlsanity.com/paper/2301.00092/) (2022)
- [Efficient uniform approximation using Random Vector Functional Link networks](https://mlsanity.com/paper/2306.17501/) (2023)
- [ScoreFusion: Fusing Score-based Generative Models via Kullback-Leibler Barycenters](https://mlsanity.com/paper/2406.19619/) (2024)
- [Function Approximation with Randomly Initialized Neural Networks for Approximate Model Reference Adaptive Control](https://mlsanity.com/paper/2303.16251/) (2023)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2410.09771/) (2024)
- [Dimension lower bounds for linear approaches to function approximation](https://mlsanity.com/paper/2508.13346/) (2025)
- [A Neural Network Algorithm for KL Divergence Estimation with Quantitative Error Bounds](https://mlsanity.com/paper/2510.05386/) (2025)
- [Structured vs. Unstructured Pruning: An Exponential Gap](https://mlsanity.com/paper/2603.02234/) (2026)
- [Explicit integral representations and quantitative bounds for two-layer ReLU networks](https://mlsanity.com/paper/2604.23260/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## Abstract (arXiv)

This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upper- and lower-bounds for L2-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms. Our positive results employ tools from harmonic analysis and ridgelet representation theory, while our lower-bounds are based on (robust versions of) dimensionality arguments.