mlsanityData to 7 Oct 2026

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

arXiv 2102.02336 ↗First posted 3 Feb 2021cs.LG cs.NE stat.MLcited by 29

Not on the map. Why?

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.

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

Builds on

12 of 42 references.

References · 12

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  3. 2016Benefits of depth in neural networkscited by 248
  4. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  5. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  6. 2016Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ℓ1 and ℓ0 Controlscited by 84
  7. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  8. 2017Depth Separation for Neural Networkscited by 46
  9. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  10. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  11. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  12. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 7; 2024: 5; 2025: 4; 2026: 5.

29 papers.

Sort:

By area:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  2. 2023The Expressive Power of Low-Rank Adaptationcited by 100
  3. 2021Quantum machine learning beyond kernel methodscited by 91
  4. 2023On the Generalization Properties of Diffusion Modelscited by 67
  5. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  6. 2021Neural Active Learning with Performance Guaranteescited by 22
  7. 2021Optimization-Based Separations for Neural Networkscited by 17
  8. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 17
  9. 2021The Separation Capacity of Random Neural Networkscited by 14
  10. 2023The Expressive Power of Tuning Only the Normalization Layerscited by 13
  11. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  12. 2022Randomly Initialized One-Layer Neural Networks Make Data Linearly Separablecited by 5
17 more
  1. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  2. 2024Approximation with Random Shallow ReLU Networks with Applications to Model Reference Adaptive Controlcited by 4
  3. 2025Cauchy Random Features for Operator Learning in Sobolev Spacecited by 3
  4. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  5. 2021Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theoremcited by 2
  6. 2025Learning and Testing Convex Functionscited by 2
  7. 2022Inference on Time Series Nonparametric Conditional Moment Restrictions Using General Sievescited by 1
  8. 2023Efficient uniform approximation using Random Vector Functional Link networkscited by 1
  9. 2024ScoreFusion: Fusing Score-based Generative Models via Kullback-Leibler Barycenterscited by 1
  10. 2023Function Approximation with Randomly Initialized Neural Networks for Approximate Model Reference Adaptive Controlcited by 0
  11. 2024EUGens: Efficient, Unified, and General Dense Layerscited by 0
  12. 2025Dimension lower bounds for linear approaches to function approximationcited by 0
  13. 2025A Neural Network Algorithm for KL Divergence Estimation with Quantitative Error Boundscited by 0
  14. 2026EUGens: Efficient, Unified, and General Dense Layerscited by 0
  15. 2026Structured vs. Unstructured Pruning: An Exponential Gapcited by 0
  16. 2026Explicit integral representations and quantitative bounds for two-layer ReLU networkscited by 0
  17. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0