# Optimal Approximation with Sparsely Connected Deep Neural Networks

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

## Key facts

- Cited by 91 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2017.

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

- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons](https://mlsanity.com/paper/2107.02397/) (2021)
- [Deep Learning Methods for Partial Differential Equations and Related Parameter Identification Problems](https://mlsanity.com/paper/2212.03130/) (2022)
- [Deep Network Approximation: Beyond ReLU to Diverse Activation Functions](https://mlsanity.com/paper/2307.06555/) (2023)
- [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)
- [Sumformer: Universal Approximation for Efficient Transformers](https://mlsanity.com/paper/2307.02301/) (2023)
- [Fully Learnable Deep Wavelet Transform for Unsupervised Monitoring of High-Frequency Time Series](https://mlsanity.com/paper/2105.00899/) (2021)
- [A Deep Learning approach to Reduced Order Modelling of Parameter Dependent Partial Differential Equations](https://mlsanity.com/paper/2103.06183/) (2021)
- [Consistent Sparse Deep Learning: Theory and Computation](https://mlsanity.com/paper/2102.13229/) (2021)
- [Theory of Deep Convolutional Neural Networks III: Approximating Radial Functions](https://mlsanity.com/paper/2107.00896/) (2021)
- [Approximation bounds for norm constrained neural networks with applications to regression and GANs](https://mlsanity.com/paper/2201.09418/) (2022)
- [Neural and spectral operator surrogates: unified construction and expression rate bounds](https://mlsanity.com/paper/2207.04950/) (2022)
- [Global universal approximation of functional input maps on weighted spaces](https://mlsanity.com/paper/2306.03303/) (2023)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Neural Network Architecture Beyond Width and Depth](https://mlsanity.com/paper/2205.09459/) (2022)
- [Wasserstein Generative Adversarial Uncertainty Quantification in Physics-Informed Neural Networks](https://mlsanity.com/paper/2108.13054/) (2021)
- [Universal Approximation Theorem and error bounds for quantum neural networks and quantum reservoirs](https://mlsanity.com/paper/2307.12904/) (2023)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [Universal approximation property of Banach space-valued random feature models including random neural networks](https://mlsanity.com/paper/2312.08410/) (2023)
- [Deep Network Approximation in Terms of Intrinsic Parameters](https://mlsanity.com/paper/2111.07964/) (2021)
- [Rates of Approximation by ReLU Shallow Neural Networks](https://mlsanity.com/paper/2307.12461/) (2023)
- [Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective](https://mlsanity.com/paper/2406.18794/) (2024)
- [Chaotic Hedging with Iterated Integrals and Neural Networks](https://mlsanity.com/paper/2209.10166/) (2022)
- [Deep Neural Network Approximation of Invariant Functions through Dynamical Systems](https://mlsanity.com/paper/2208.08707/) (2022)
- [Learning Ability of Interpolating Deep Convolutional Neural Networks](https://mlsanity.com/paper/2210.14184/) (2022)
- [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)
- [Sparse Deep Learning: A New Framework Immune to Local Traps and Miscalibration](https://mlsanity.com/paper/2110.00653/) (2021)
- [Weighted variation spaces and approximation by shallow ReLU networks](https://mlsanity.com/paper/2307.15772/) (2023)

## Abstract (arXiv)

We derive fundamental lower bounds on the connectivity and the memory requirements of deep neural networks guaranteeing uniform approximation rates for arbitrary function classes in L2(mathbb Rd). In other words, we establish a connection between the complexity of a function class and the complexity of deep neural networks approximating functions from this class to within a prescribed accuracy. Additionally, we prove that our lower bounds are achievable for a broad family of function classes. Specifically, all function classes that are optimally approximated by a general class of representation systems---so-called affine systems---can be approximated by deep neural networks with minimal connectivity and memory requirements. Affine systems encompass a wealth of representation systems from applied harmonic analysis such as wavelets, ridgelets, curvelets, shearlets, α-shearlets, and more generally α-molecules. Our central result elucidates a remarkable universality property of neural networks and shows that they achieve the optimum approximation properties of all affine systems combined. As a specific example, we consider the class of α-1-cartoon-like functions, which is approximated optimally by α-shearlets. We also explain how our results can be extended to the case of functions on low-dimensional immersed manifolds. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm generates deep neural networks providing close-to-optimal approximation rates. Moreover, these results indicate that stochastic gradient descent can actually learn approximations that are sparse in the representation systems optimally sparsifying the function class the network is trained on.