# Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 59 references that are in the map.
- First posted on arXiv 6 Apr 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problems](https://mlsanity.com/paper/1710.00211/) (2017)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Recent Trends in Deep Learning Based Natural Language Processing](https://mlsanity.com/paper/1708.02709/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networks](https://mlsanity.com/paper/1909.02487/) (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)
- [Deep neural network solution of the electronic Schr"odinger equation](https://mlsanity.com/paper/1909.08423/) (2019)
- [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)
- [A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations](https://mlsanity.com/paper/1809.02362/) (2018)
- [The gap between theory and practice in function approximation with deep neural networks](https://mlsanity.com/paper/2001.07523/) (2020)
- [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)
- [Neural network approximation and estimation of classifiers with classification boundary in a Barron class](https://mlsanity.com/paper/2011.09363/) (2020)

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

- [Deep Learning Methods for Partial Differential Equations and Related Parameter Identification Problems](https://mlsanity.com/paper/2212.03130/) (2022)
- [Data Complexity Estimates for Operator Learning](https://mlsanity.com/paper/2405.15992/) (2024)
- [A Survey of Data-Efficient Graph Learning](https://mlsanity.com/paper/2402.00447/) (2024)
- [Optimal learning of high-dimensional classification problems using deep neural networks](https://mlsanity.com/paper/2112.12555/) (2021)
- [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)
- [Lp sampling numbers for the Fourier-analytic Barron space](https://mlsanity.com/paper/2208.07605/) (2022)
- [Non-convergence to the optimal risk for Adam and stochastic gradient descent optimization in the training of deep neural networks](https://mlsanity.com/paper/2503.01660/) (2025)
- [Learning ReLU networks to high uniform accuracy is intractable](https://mlsanity.com/paper/2205.13531/) (2022)
- [Stable Learning Using Spiking Neural Networks Equipped With Affine Encoders and Decoders](https://mlsanity.com/paper/2404.04549/) (2024)
- [Theory-to-Practice Gap for Neural Networks and Neural Operators](https://mlsanity.com/paper/2503.18219/) (2025)
- [Prediction error certification for PINNs: Theory, computation, and application to Stokes flow](https://mlsanity.com/paper/2508.07994/) (2025)
- [Deep learning approximations for non-local nonlinear PDEs with Neumann boundary conditions](https://mlsanity.com/paper/2205.03672/) (2022)
- [Deep neural networks can stably solve high-dimensional, noisy, non-linear inverse problems](https://mlsanity.com/paper/2206.00934/) (2022)
- [Approximation Results for Gradient Descent trained Neural Networks](https://mlsanity.com/paper/2309.04860/) (2023)
- [High-dimensional classification problems with Barron regular boundaries under margin conditions](https://mlsanity.com/paper/2412.07312/) (2024)
- [Time-Frequency Analysis for Neural Networks](https://mlsanity.com/paper/2512.15992/) (2025)
- [Lattice-based Deep Neural Networks: Regularity and Tailored Regularization](https://mlsanity.com/paper/2603.02809/) (2026)
- [Sobolev-type embeddings for neural network approximation spaces](https://mlsanity.com/paper/2110.15304/) (2021)
- [Algorithmically Designed Artificial Neural Networks (ADANNs): Higher order deep operator learning for parametric partial differential equations](https://mlsanity.com/paper/2302.03286/) (2023)
- [Sampling Complexity of Deep Approximation Spaces](https://mlsanity.com/paper/2312.13379/) (2023)
- [Approximation and Gradient Descent Training with Neural Networks](https://mlsanity.com/paper/2405.11696/) (2024)
- [Leveraging time and parameters for nonlinear model reduction methods](https://mlsanity.com/paper/2501.03853/) (2025)
- [Limitations of Learning Tanh Neural Networks with Finite Precision](https://mlsanity.com/paper/2606.11104/) (2026)
- [Constrained Few-Shot Learning: Human-Like Low Sample Complexity Learning and Non-Episodic Text Classification](https://mlsanity.com/paper/2208.08089/) (2022)
- [Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks](https://mlsanity.com/paper/2507.04779/) (2025)
- [Certified and accurate computation of function space norms of deep neural networks](https://mlsanity.com/paper/2603.06431/) (2026)
- [The Information-Theoretic Benefit of Shared Representations under Orthogonality Constraints](https://mlsanity.com/paper/2606.16028/) (2026)
- [Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks](https://mlsanity.com/paper/2607.01266/) (2026)
- [Residual neural networks overcome the curse of dimensionality for semilinear heat equations](https://mlsanity.com/paper/2609.03626/) (2026)

## Abstract (arXiv)

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that approximation rates of a comparable order of convergence are (at least theoretically) achievable.