# Sampling Complexity of Deep Approximation Spaces

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 30 references that are in the map.
- First posted on arXiv 20 Dec 2023.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Solving high-dimensional partial differential equations using deep learning](https://mlsanity.com/paper/1707.02568/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [A unified deep artificial neural network approach to partial differential equations in complex geometries](https://mlsanity.com/paper/1711.06464/) (2017)
- [Deep Neural Network Approximation Theory](https://mlsanity.com/paper/1901.02220/) (2019)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [A Theoretical Analysis of Deep Neural Networks and Parametric PDEs](https://mlsanity.com/paper/1904.00377/) (2019)
- [Approximation spaces of deep neural networks](https://mlsanity.com/paper/1905.01208/) (2019)
- [Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations](https://mlsanity.com/paper/1809.03062/) (2018)
- [Solving the Kolmogorov PDE by means of deep learning](https://mlsanity.com/paper/1806.00421/) (2018)
- [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)
- [Deep neural network approximation for high-dimensional elliptic PDEs with boundary conditions](https://mlsanity.com/paper/2007.05384/) (2020)
- [Neural Networks Trained to Solve Differential Equations Learn General Representations](https://mlsanity.com/paper/1807.00042/) (2018)
- [Deep Neural Network Framework Based on Backward Stochastic Differential Equations for Pricing and Hedging American Options in High Dimensions](https://mlsanity.com/paper/1909.11532/) (2019)
- [Approximations with deep neural networks in Sobolev time-space](https://mlsanity.com/paper/2101.06115/) (2020)
- [Uniform error estimates for artificial neural network approximations for heat equations](https://mlsanity.com/paper/1911.09647/) (2019)
- [Deep Neural Networks for Rotation-Invariance Approximation and Learning](https://mlsanity.com/paper/1904.01814/) (2019)
- [Construction of neural networks for realization of localized deep learning](https://mlsanity.com/paper/1803.03503/) (2018)
- [Space-time error estimates for deep neural network approximations for differential equations](https://mlsanity.com/paper/1908.03833/) (2019)
- [Space-Time Approximation with Shallow Neural Networks in Fourier Lebesgue spaces](https://mlsanity.com/paper/2312.08461/) (2023)

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

- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)

## Abstract (arXiv)

While it is well-known that neural networks enjoy excellent approximation capabilities, it remains a big challenge to compute such approximations from point samples. Based on tools from Information-based complexity, recent work by Grohs and Voigtlaender [Journal of the FoCM (2023)] developed a rigorous framework for assessing this so-called "theory-to-practice gap". More precisely, in that work it is shown that there exist functions that can be approximated by neural networks with ReLU activation function at an arbitrary rate while requiring an exponentially growing (in the input dimension) number of samples for their numerical computation. The present study extends these findings by showing analogous results for the ReQU activation function.