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

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

## Key facts

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

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [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)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [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 beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Optimal learning of high-dimensional classification problems using deep neural networks](https://mlsanity.com/paper/2112.12555/) (2021)
- [Approximation in Lp(μ) with deep ReLU neural networks](https://mlsanity.com/paper/1904.04789/) (2019)
- [VC dimension of partially quantized neural networks in the overparametrized regime](https://mlsanity.com/paper/2110.02456/) (2021)

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

- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Operator learning with PCA-Net: upper and lower complexity bounds](https://mlsanity.com/paper/2303.16317/) (2023)
- [Optimal rates of approximation by shallow ReLUk neural networks and applications to nonparametric regression](https://mlsanity.com/paper/2304.01561/) (2023)
- [Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective](https://mlsanity.com/paper/2406.18794/) (2024)
- [Limitations on approximation by deep and shallow neural networks](https://mlsanity.com/paper/2212.02223/) (2022)
- [Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networks](https://mlsanity.com/paper/2605.31152/) (2026)
- [Expressive Power of Deep Networks on Manifolds: Simultaneous Approximation](https://mlsanity.com/paper/2509.09362/) (2025)
- [Sobolev Approximation of Deep ReLU Networks in Log-Barron Space](https://mlsanity.com/paper/2601.01295/) (2026)
- [Neural networks: deep, shallow, or in between?](https://mlsanity.com/paper/2310.07190/) (2023)
- [Efficient Approximation to Analytic and Lp functions by Height-Augmented ReLU Networks](https://mlsanity.com/paper/2603.11128/) (2026)
- [Fractional Parabolic Partial Differential Equations in Anisotropic Spectral Barron Spaces: Regularity and Neural Approximation](https://mlsanity.com/paper/2607.27781/) (2026)

## 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).