# Deep Neural Network Approximation Theory

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

## Key facts

- Cited by 93 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2019.

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

- [Scientific Machine Learning through Physics-Informed Neural Networks: Where we are and What's next](https://mlsanity.com/paper/2201.05624/) (2022)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [Exponential Convergence of Deep Operator Networks for Elliptic Partial Differential Equations](https://mlsanity.com/paper/2112.08125/) (2021)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [Nonlinear Reconstruction for Operator Learning of PDEs with Discontinuities](https://mlsanity.com/paper/2210.01074/) (2022)
- [Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysis](https://mlsanity.com/paper/2210.13300/) (2022)
- [Variational Physics Informed Neural Networks: the role of quadratures and test functions](https://mlsanity.com/paper/2109.02035/) (2021)
- [Neural Network Approximation of Refinable Functions](https://mlsanity.com/paper/2107.13191/) (2021)
- [A Simple Single-Scale Vision Transformer for Object Localization and Instance Segmentation](https://mlsanity.com/paper/2112.09747/) (2021)
- [Adaptive deep learning for nonlinear time series models](https://mlsanity.com/paper/2207.02546/) (2022)
- [Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective](https://mlsanity.com/paper/2406.18794/) (2024)
- [A practical existence theorem for reduced order models based on convolutional autoencoders](https://mlsanity.com/paper/2402.00435/) (2024)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Approximation speed of quantized vs. unquantized ReLU neural networks and beyond](https://mlsanity.com/paper/2205.11874/) (2022)
- [Data-driven reduced order models using invariant foliations, manifolds and autoencoders](https://mlsanity.com/paper/2206.12269/) (2022)
- [Approximation results for Gradient Descent trained Shallow Neural Networks in 1d](https://mlsanity.com/paper/2209.08399/) (2022)
- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)
- [Solving The Quantum Many-Body Hamiltonian Learning Problem with Neural Differential Equations](https://mlsanity.com/paper/2408.08639/) (2024)
- [Calibrating multi-dimensional complex ODE from noisy data via deep neural networks](https://mlsanity.com/paper/2106.03591/) (2021)
- [Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries](https://mlsanity.com/paper/2310.15003/) (2023)
- [Understanding the Difficulty of Solving Cauchy Problems with PINNs](https://mlsanity.com/paper/2405.02561/) (2024)
- [Quantitative approximation results for complex-valued neural networks](https://mlsanity.com/paper/2102.13092/) (2021)
- [Deep neural network approximation for high-dimensional parabolic Hamilton-Jacobi-Bellman equations](https://mlsanity.com/paper/2103.05744/) (2021)
- [High-Dimensional Distribution Generation Through Deep Neural Networks](https://mlsanity.com/paper/2107.12466/) (2021)
- [Learning ReLU networks to high uniform accuracy is intractable](https://mlsanity.com/paper/2205.13531/) (2022)
- [Residual Multi-Fidelity Neural Network Computing](https://mlsanity.com/paper/2310.03572/) (2023)
- [Orthogonal Representation Learning for Estimating Causal Quantities](https://mlsanity.com/paper/2502.04274/) (2025)
- [Metric Entropy Limits on Recurrent Neural Network Learning of Linear Dynamical Systems](https://mlsanity.com/paper/2105.02556/) (2021)
- [Unlabeled Data Help: Minimax Analysis and Adversarial Robustness](https://mlsanity.com/paper/2202.06996/) (2022)
- [Approximation Power of Deep Neural Networks: an explanatory mathematical survey](https://mlsanity.com/paper/2207.09511/) (2022)

## Abstract (arXiv)

This paper develops fundamental limits of deep neural network learning by characterizing what is possible if no constraints are imposed on the learning algorithm and on the amount of training data. Concretely, we consider Kolmogorov-optimal approximation through deep neural networks with the guiding theme being a relation between the complexity of the function (class) to be approximated and the complexity of the approximating network in terms of connectivity and memory requirements for storing the network topology and the associated quantized weights. The theory we develop establishes that deep networks are Kolmogorov-optimal approximants for markedly different function classes, such as unit balls in Besov spaces and modulation spaces. In addition, deep networks provide exponential approximation accuracy - i.e., the approximation error decays exponentially in the number of nonzero weights in the network - of the multiplication operation, polynomials, sinusoidal functions, and certain smooth functions. Moreover, this holds true even for one-dimensional oscillatory textures and the Weierstrass function - a fractal function, neither of which has previously known methods achieving exponential approximation accuracy. We also show that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.