# Optimal Approximation Rate of ReLU Networks in terms of Width and Depth

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

## Key facts

- Cited by 96 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 50 references that are in the map.
- First posted on arXiv 28 Feb 2021.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations](https://mlsanity.com/paper/1811.01558/) (2018)
- [The phase diagram of approximation rates for deep neural networks](https://mlsanity.com/paper/1906.09477/) (2019)
- [ResNet with one-neuron hidden layers is a Universal Approximator](https://mlsanity.com/paper/1806.10909/) (2018)
- [Deep Learning via Dynamical Systems: An Approximation Perspective](https://mlsanity.com/paper/1912.10382/) (2019)
- [A Priori Estimates of the Population Risk for Two-layer Neural Networks](https://mlsanity.com/paper/1810.06397/) (2018)
- [The loss surface of deep and wide neural networks](https://mlsanity.com/paper/1704.08045/) (2017)
- [Neural Network Approximation: Three Hidden Layers Are Enough](https://mlsanity.com/paper/2010.14075/) (2020)
- [Representation formulas and pointwise properties for Barron functions](https://mlsanity.com/paper/2006.05982/) (2020)
- [On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics](https://mlsanity.com/paper/2007.15623/) (2020)
- [Exponential Convergence of the Deep Neural Network Approximation for Analytic Functions](https://mlsanity.com/paper/1807.00297/) (2018)
- [Nonlinear Approximation via Compositions](https://mlsanity.com/paper/1902.10170/) (2019)
- [Elementary superexpressive activations](https://mlsanity.com/paper/2102.10911/) (2021)
- [Depth with Nonlinearity Creates No Bad Local Minima in ResNets](https://mlsanity.com/paper/1810.09038/) (2018)
- [A Priori Estimates of the Population Risk for Residual Networks](https://mlsanity.com/paper/1903.02154/) (2019)
- [Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python](https://mlsanity.com/paper/2006.15261/) (2020)
- [A priori estimates for classification problems using neural networks](https://mlsanity.com/paper/2009.13500/) (2020)
- [Make ℓ1 Regularization Effective in Training Sparse CNN](https://mlsanity.com/paper/1807.04222/) (2018)

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

- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Do language models plan ahead for future tokens?](https://mlsanity.com/paper/2404.00859/) (2024)
- [Deep Nonparametric Estimation of Operators between Infinite Dimensional Spaces](https://mlsanity.com/paper/2201.00217/) (2022)
- [Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons](https://mlsanity.com/paper/2107.02397/) (2021)
- [On the expressiveness and spectral bias of KANs](https://mlsanity.com/paper/2410.01803/) (2024)
- [Deep Network Approximation: Beyond ReLU to Diverse Activation Functions](https://mlsanity.com/paper/2307.06555/) (2023)
- [Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives](https://mlsanity.com/paper/2305.08466/) (2023)
- [Approximation Rate of the Transformer Architecture for Sequence Modeling](https://mlsanity.com/paper/2305.18475/) (2023)
- [Achieve the Minimum Width of Neural Networks for Universal Approximation](https://mlsanity.com/paper/2209.11395/) (2022)
- [How do noise tails impact on deep ReLU networks?](https://mlsanity.com/paper/2203.10418/) (2022)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [Localized Zeroth-Order Prompt Optimization](https://mlsanity.com/paper/2403.02993/) (2024)
- [Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysis](https://mlsanity.com/paper/2210.13300/) (2022)
- [Sample, estimate, aggregate: A recipe for causal discovery foundation models](https://mlsanity.com/paper/2402.01929/) (2024)
- [Neural Network Architecture Beyond Width and Depth](https://mlsanity.com/paper/2205.09459/) (2022)
- [Convergence of Deep ReLU Networks](https://mlsanity.com/paper/2107.12530/) (2021)
- [IAE-Net: Integral Autoencoders for Discretization-Invariant Learning](https://mlsanity.com/paper/2203.05142/) (2022)
- [Deep Neural Networks for Nonparametric Interaction Models with Diverging Dimension](https://mlsanity.com/paper/2302.05851/) (2023)
- [A Survey on Universal Approximation Theorems](https://mlsanity.com/paper/2407.12895/) (2024)
- [Convergence of Deep Convolutional Neural Networks](https://mlsanity.com/paper/2109.13542/) (2021)
- [On Deep Generative Models for Approximation and Estimation of Distributions on Manifolds](https://mlsanity.com/paper/2302.13183/) (2023)
- [On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theorem](https://mlsanity.com/paper/2308.05509/) (2023)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)
- [Solving PDEs on Unknown Manifolds with Machine Learning](https://mlsanity.com/paper/2106.06682/) (2021)
- [Deep Network Approximation in Terms of Intrinsic Parameters](https://mlsanity.com/paper/2111.07964/) (2021)
- [A general approximation lower bound in Lp norm, with applications to feed-forward neural networks](https://mlsanity.com/paper/2206.04360/) (2022)
- [Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits](https://mlsanity.com/paper/2310.07528/) (2023)
- [On the rates of convergence for learning with convolutional neural networks](https://mlsanity.com/paper/2403.16459/) (2024)
- [Deep Neural Network Approximation of Invariant Functions through Dynamical Systems](https://mlsanity.com/paper/2208.08707/) (2022)

## Abstract (arXiv)

This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved by construction that ReLU networks with width Obig(maxdlfloor N1/drfloor,, N+2big) and depth O(L) can approximate a H"older continuous function on [0,1]d with an approximation rate Obig(λ√d (N2L2ln N)-α/dbig), where α∈ (0,1] and λ>0 are H"older order and constant, respectively. Such a rate is optimal up to a constant in terms of width and depth separately, while existing results are only nearly optimal without the logarithmic factor in the approximation rate. More generally, for an arbitrary continuous function f on [0,1]d, the approximation rate becomes Obig(,√d,ωfbig( (N2L2ln N)-1/dbig),big), where ωf(·) is the modulus of continuity. We also extend our analysis to any continuous function f on a bounded set. Particularly, if ReLU networks with depth 31 and width O(N) are used to approximate one-dimensional Lipschitz continuous functions on [0,1] with a Lipschitz constant λ>0, the approximation rate in terms of the total number of parameters, W=O(N2), becomes O(tfracλWln W), which has not been discovered in the literature for fixed-depth ReLU networks.