# Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 57 references that are in the map.
- First posted on arXiv 25 Nov 2022.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Solving high-dimensional partial differential equations using deep learning](https://mlsanity.com/paper/1707.02568/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [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)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Error bounds for approximations with deep ReLU neural networks in Ws,p norms](https://mlsanity.com/paper/1902.07896/) (2019)
- [The phase diagram of approximation rates for deep neural networks](https://mlsanity.com/paper/1906.09477/) (2019)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Neural Network Approximation of Refinable Functions](https://mlsanity.com/paper/2107.13191/) (2021)
- [A general approximation lower bound in Lp norm, with applications to feed-forward neural networks](https://mlsanity.com/paper/2206.04360/) (2022)

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

- [KAN: Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2404.19756/) (2024)
- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [On the expressiveness and spectral bias of KANs](https://mlsanity.com/paper/2410.01803/) (2024)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)
- [Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks](https://mlsanity.com/paper/2307.15285/) (2023)
- [Utility Theory of Synthetic Data Generation](https://mlsanity.com/paper/2305.10015/) (2023)
- [Weighted variation spaces and approximation by shallow ReLU networks](https://mlsanity.com/paper/2307.15772/) (2023)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Limitations on approximation by deep and shallow neural networks](https://mlsanity.com/paper/2212.02223/) (2022)
- [Spherical Analysis of Learning Nonlinear Functionals](https://mlsanity.com/paper/2410.01047/) (2024)
- [Higher Order Approximation Rates for ReLU CNNs in Korobov Spaces](https://mlsanity.com/paper/2501.11275/) (2025)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [On Universality Classes of Equivariant Networks](https://mlsanity.com/paper/2506.02293/) (2025)
- [A short tour of operator learning theory: Convergence rates, statistical limits, and open questions](https://mlsanity.com/paper/2603.00819/) (2026)
- [Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data](https://mlsanity.com/paper/2302.00834/) (2023)
- [A Statistical Framework for Data-dependent Retrieval-Augmented Models](https://mlsanity.com/paper/2408.15399/) (2024)
- [Some Super-approximation Rates of ReLU Neural Networks for Korobov Functions](https://mlsanity.com/paper/2507.10345/) (2025)
- [On Conditional Stochastic Interpolation for Generative Nonlinear Sufficient Dimension Reduction](https://mlsanity.com/paper/2512.18971/) (2025)
- [Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networks](https://mlsanity.com/paper/2605.31152/) (2026)
- [Deep Ridgelet Transform and Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machines](https://mlsanity.com/paper/2405.13682/) (2024)
- [Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks](https://mlsanity.com/paper/2409.06555/) (2024)
- [A convergent scheme for the Bayesian filtering problem based on the Fokker--Planck equation and deep splitting](https://mlsanity.com/paper/2409.14585/) (2024)
- [Nonlocal techniques for the analysis of deep ReLU neural network approximations](https://mlsanity.com/paper/2504.04847/) (2025)
- [Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions](https://mlsanity.com/paper/2508.16737/) (2025)
- [Expressive Power of Deep Networks on Manifolds: Simultaneous Approximation](https://mlsanity.com/paper/2509.09362/) (2025)
- [Sequence Modeling with Spectral Mean Flows](https://mlsanity.com/paper/2510.15366/) (2025)
- [Certifiable Boolean Reasoning Is Universal](https://mlsanity.com/paper/2602.05120/) (2026)
- [Approximation by non-symmetric networks for cross-domain learning](https://mlsanity.com/paper/2305.03890/) (2023)
- [Theoretical Insights into CycleGAN: Analyzing Approximation and Estimation Errors in Unpaired Data Generation](https://mlsanity.com/paper/2407.11678/) (2024)
- [DeepONet for Solving Nonlinear Partial Differential Equations with Physics-Informed Training](https://mlsanity.com/paper/2410.04344/) (2024)

## Abstract (arXiv)

Let Omega = [0,1]d be the unit cube in ℝd. We study the problem of how efficiently, in terms of the number of parameters, deep neural networks with the ReLU activation function can approximate functions in the Sobolev spaces Ws(Lq(Omega)) and Besov spaces Bsr(Lq(Omega)), with error measured in the Lp(Omega) norm. This problem is important when studying the application of neural networks in a variety of fields, including scientific computing and signal processing, and has previously been solved only when p=q=∞. Our contribution is to provide a complete solution for all 1≤ p,q≤ ∞ and s > 0 for which the corresponding Sobolev or Besov space compactly embeds into Lp. The key technical tool is a novel bit-extraction technique which gives an optimal encoding of sparse vectors. This enables us to obtain sharp upper bounds in the non-linear regime where p > q. We also provide a novel method for deriving Lp-approximation lower bounds based upon VC-dimension when p < ∞. Our results show that very deep ReLU networks significantly outperform classical methods of approximation in terms of the number of parameters, but that this comes at the cost of parameters which are not encodable.