# The universal approximation power of finite-width deep ReLU networks

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [State Space Models are Provably Comparable to Transformers in Dynamic Token Selection](https://mlsanity.com/paper/2405.19036/) (2024)
- [Finding Everything within Random Binary Networks](https://mlsanity.com/paper/2110.08996/) (2021)
- [Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training](https://mlsanity.com/paper/2311.18022/) (2023)
- [Seeking Interpretability and Explainability in Binary Activated Neural Networks](https://mlsanity.com/paper/2209.03450/) (2022)
- [Deep ReLU networks and high-order finite element methods II: Chebyshev emulation](https://mlsanity.com/paper/2310.07261/) (2023)
- [Approximating Langevin Monte Carlo with ResNet-like Neural Network architectures](https://mlsanity.com/paper/2311.03242/) (2023)
- [Do stable neural networks exist for classification problems? -- A new view on stability in AI](https://mlsanity.com/paper/2401.07874/) (2024)
- [Data Topology-Dependent Upper Bounds of Neural Network Widths](https://mlsanity.com/paper/2305.16375/) (2023)
- [Training Neural Networks Using Reproducing Kernel Space Interpolation and Model Reduction](https://mlsanity.com/paper/2308.16754/) (2023)
- [Deep Neural Variation Spaces: A Unifying Perspective on Depth and Complexity](https://mlsanity.com/paper/2607.05546/) (2026)
- [Minimax rates for learning spectral Barron functions by deep ReLU neural networks](https://mlsanity.com/paper/2609.39020/) (2026)

## Abstract (arXiv)

We show that finite-width deep ReLU neural networks yield rate-distortion optimal approximation (B"olcskei et al., 2018) of polynomials, windowed sinusoidal functions, one-dimensional oscillatory textures, and the Weierstrass function, a fractal function which is continuous but nowhere differentiable. Together with their recently established universal approximation property of affine function systems (B"olcskei et al., 2018), this shows that deep neural networks approximate vastly different signal structures generated by the affine group, the Weyl-Heisenberg group, or through warping, and even certain fractals, all with approximation error decaying exponentially in the number of neurons. We also prove that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.