mlsanityData to 7 Oct 2026

A general approximation lower bound in Lp norm, with applications to feed-forward neural networks

arXiv 2206.04360 ↗First posted 9 Jun 2022cs.LG math.ST stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the fundamental limits to the expressive power of neural networks. Given two sets F, G of real-valued functions, we first prove a general lower bound on how well functions in F can be approximated in Lp(μ) norm by functions in G, for any p ≥ 1 and any probability measure μ. The lower bound depends on the packing number of F, the range of F, and the fat-shattering dimension of G. We then instantiate this bound to the case where G corresponds to a piecewise-polynomial feed-forward neural network, and describe in details the application to two sets F: H"older balls and multivariate monotonic functions. Beside matching (known or new) upper bounds up to log factors, our lower bounds shed some light on the similarities or differences between approximation in Lp norm or in sup norm, solving an open question by DeVore et al. (2021). Our proof strategy differs from the sup norm case and uses a key probability result of Mendelson (2002).

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 13 of its 45 references that are in the map. First posted on arXiv 9 Jun 2022.

Builds on

13 of 45 references.

References · 13

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  3. 2016Benefits of depth in neural networkscited by 248
  4. 2019Universal Approximation with Deep Narrow Networkscited by 198
  5. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
  6. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  7. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
  8. 2019The phase diagram of approximation rates for deep neural networkscited by 86
  9. 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
  10. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  11. 2021Optimal learning of high-dimensional classification problems using deep neural networkscited by 9
  12. 2019Approximation in Lp(μ) with deep ReLU neural networkscited by 3
1 more
  1. 2021VC dimension of partially quantized neural networks in the overparametrized regimecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 2; 2025: 1; 2026: 4.

12 papers.

  1. 2024Operator Learning: Algorithms and Analysiscited by 84
  2. 2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 50
  3. 2023Operator learning with PCA-Net: upper and lower complexity boundscited by 44
  4. 2023Optimal rates of approximation by shallow ReLUk neural networks and applications to nonparametric regressioncited by 15
  5. 2024Operator Learning of Lipschitz Operators: An Information-Theoretic Perspectivecited by 9
  6. 2022Limitations on approximation by deep and shallow neural networkscited by 4
  7. 2026Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networkscited by 3
  8. 2025Expressive Power of Deep Networks on Manifolds: Simultaneous Approximationcited by 2
  9. 2026Sobolev Approximation of Deep ReLU Networks in Log-Barron Spacecited by 1
  10. 2023Neural networks: deep, shallow, or in between?cited by 0
  11. 2026Efficient Approximation to Analytic and Lp functions by Height-Augmented ReLU Networkscited by 0
  12. 2026Fractional Parabolic Partial Differential Equations in Anisotropic Spectral Barron Spaces: Regularity and Neural Approximationcited by 0