mlsanityData to 7 Oct 2026

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

arXiv 2211.14400 ↗First posted 25 Nov 2022stat.ML cs.LG cs.NAcited by 50

Not on the map. Why?

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.

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

Builds on

19 of 57 references.

References · 19

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2017Solving high-dimensional partial differential equations using deep learningcited by 549
  3. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  4. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  6. 2016Benefits of depth in neural networkscited by 248
  7. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
  8. 2019Complexity of Linear Regions in Deep Networkscited by 166
  9. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  10. 2020Deep Network Approximation for Smooth Functionscited by 163
  11. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  12. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
7 more
  1. 2019Error bounds for approximations with deep ReLU neural networks in Ws,p normscited by 95
  2. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
  3. 2019The phase diagram of approximation rates for deep neural networkscited by 86
  4. 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
  5. 2016Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ℓ1 and ℓ0 Controlscited by 84
  6. 2021Neural Network Approximation of Refinable Functionscited by 15
  7. 2022A general approximation lower bound in Lp norm, with applications to feed-forward neural networkscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 12; 2025: 12; 2026: 19.

50 papers.

Sort:

By area:

  1. 2024KAN: Kolmogorov-Arnold Networkscited by 634
  2. 2024Operator Learning: Algorithms and Analysiscited by 84
  3. 2024On the expressiveness and spectral bias of KANscited by 36
  4. 2024On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networkscited by 13
  5. 2023Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networkscited by 11
  6. 2023Utility Theory of Synthetic Data Generationcited by 8
  7. 2023Weighted variation spaces and approximation by shallow ReLU networkscited by 7
  8. 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
  9. 2022Limitations on approximation by deep and shallow neural networkscited by 4
  10. 2025Higher Order Approximation Rates for ReLU CNNs in Korobov Spacescited by 4
  11. 2025Approximation Bounds for Transformer Networks with Application to Regressioncited by 4
  12. 2025On Universality Classes of Equivariant Networkscited by 4
38 more
  1. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  2. 2024Spherical Analysis of Learning Nonlinear Functionalscited by 3
  3. 2025Some Super-approximation Rates of ReLU Neural Networks for Korobov Functionscited by 3
  4. 2026Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networkscited by 3
  5. 2024Deep Ridgelet Transform and Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machinescited by 2
  6. 2024A Statistical Framework for Data-dependent Retrieval-Augmented Modelscited by 2
  7. 2024Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networkscited by 2
  8. 2024A convergent scheme for the Bayesian filtering problem based on the Fokker--Planck equation and deep splittingcited by 2
  9. 2025Nonlocal techniques for the analysis of deep ReLU neural network approximationscited by 2
  10. 2025Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributionscited by 2
  11. 2025Expressive Power of Deep Networks on Manifolds: Simultaneous Approximationcited by 2
  12. 2025Sequence Modeling with Spectral Mean Flowscited by 2
  13. 2025On Conditional Stochastic Interpolation for Generative Nonlinear Sufficient Dimension Reductioncited by 2
  14. 2026A short tour of operator learning theory: Convergence rates, statistical limits, and open questionscited by 2
  15. 2023Approximation by non-symmetric networks for cross-domain learningcited by 1
  16. 2024Theoretical Insights into CycleGAN: Analyzing Approximation and Estimation Errors in Unpaired Data Generationcited by 1
  17. 2024DeepONet for Solving Nonlinear Partial Differential Equations with Physics-Informed Trainingcited by 1
  18. 2025Autonomous-Flow-Based Generationcited by 1
  19. 2026RPWithPrior: Label Differential Privacy in Regressioncited by 1
  20. 2026Certifiable Boolean Reasoning Is Universalcited by 1
  21. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  22. 2026Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networkscited by 1
  23. 2023Neural networks: deep, shallow, or in between?cited by 0
  24. 2024How Can Deep Neural Networks Fail Even With Global Optima?cited by 0
  25. 2025Why and When Deep is Better than Shallow: Implementation-Agnostic State-Transition Model of Deep Learningcited by 0
  26. 2026SAQNN: Spectral Adaptive Quantum Neural Network as a Universal Approximatorcited by 0
  27. 2026Memorization capacity of deep ReLU neural networks characterized by width and depthcited by 0
  28. 2026Efficient Approximation to Analytic and Lp functions by Height-Augmented ReLU Networkscited by 0
  29. 2026Approximation Theory for Neural Networks: Old and Newcited by 0
  30. 2026Neural Flow Operators can Approximate any Operator: Abstract Frameworks and Universal Approximationscited by 0
  31. 2026Black-Box Assisted Regression: Phase Transitions and Minimax Optimalitycited by 0
  32. 2026Harvesting AI Computation at the Edge via Generic Approximationcited by 0
  33. 2026Approximation of Analytic Functions by ReLU Neural Networks with Adjustable Depth and Widthcited by 0
  34. 2026Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity Viewcited by 0
  35. 2026Approximating Smooth Functionals with ReLU Networkscited by 0
  36. 2026Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networkscited by 0
  37. 2026Neural Approximation by Function Composition: Rigidity and Doubly Exponential Convergencecited by 0
  38. 2026Minimax rates for learning spectral Barron functions by deep ReLU neural networkscited by 0