mlsanityData to 7 Oct 2026

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

arXiv 2104.02746 ↗First posted 6 Apr 2021cs.LG math.FAcited by 30

Not on the map. Why?

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.

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

Builds on

22 of 59 references.

References · 22

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2014Going Deeper with Convolutionscited by 4,231
  4. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  5. 2017The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problemscited by 581
  6. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 331
  7. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  8. 2019Deep Learning for Symbolic Mathematicscited by 266
  9. 2017Recent Trends in Deep Learning Based Natural Language Processingcited by 262
  10. 2016Benefits of depth in neural networkscited by 248
  11. 2019Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networkscited by 195
  12. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
10 more
  1. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  2. 2019Deep neural network solution of the electronic Schr"odinger equationcited by 124
  3. 2019Deep Neural Network Approximation Theorycited by 92
  4. 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 90
  5. 2019A Theoretical Analysis of Deep Neural Networks and Parametric PDEscited by 74
  6. 2018A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equationscited by 55
  7. 2020The gap between theory and practice in function approximation with deep neural networkscited by 53
  8. 2019Approximation spaces of deep neural networkscited by 51
  9. 2018Analysis 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 Equationscited by 44
  10. 2020Neural network approximation and estimation of classifiers with classification boundary in a Barron classcited by 28

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 3; 2024: 6; 2025: 6; 2026: 6.

30 papers.

Sort:

  1. 2022Deep Learning Methods for Partial Differential Equations and Related Parameter Identification Problemscited by 34
  2. 2024Data Complexity Estimates for Operator Learningcited by 21
  3. 2024A Survey of Data-Efficient Graph Learningcited by 18
  4. 2021Optimal learning of high-dimensional classification problems using deep neural networkscited by 9
  5. 2022Approximation results for Gradient Descent trained Shallow Neural Networks in 1dcited by 7
  6. 2024Learning smooth functions in high dimensions: from sparse polynomials to deep neural networkscited by 7
  7. 2022Lp sampling numbers for the Fourier-analytic Barron spacecited by 6
  8. 2025Non-convergence to the optimal risk for Adam and stochastic gradient descent optimization in the training of deep neural networkscited by 6
  9. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  10. 2024Stable Learning Using Spiking Neural Networks Equipped With Affine Encoders and Decoderscited by 5
  11. 2025Theory-to-Practice Gap for Neural Networks and Neural Operatorscited by 4
  12. 2025Prediction error certification for PINNs: Theory, computation, and application to Stokes flowcited by 4
18 more
  1. 2022Deep learning approximations for non-local nonlinear PDEs with Neumann boundary conditionscited by 3
  2. 2022Deep neural networks can stably solve high-dimensional, noisy, non-linear inverse problemscited by 3
  3. 2023Approximation Results for Gradient Descent trained Neural Networkscited by 2
  4. 2024High-dimensional classification problems with Barron regular boundaries under margin conditionscited by 2
  5. 2025Time-Frequency Analysis for Neural Networkscited by 2
  6. 2026Lattice-based Deep Neural Networks: Regularity and Tailored Regularizationcited by 2
  7. 2021Sobolev-type embeddings for neural network approximation spacescited by 1
  8. 2023Algorithmically Designed Artificial Neural Networks (ADANNs): Higher order deep operator learning for parametric partial differential equationscited by 1
  9. 2023Sampling Complexity of Deep Approximation Spacescited by 1
  10. 2024Approximation and Gradient Descent Training with Neural Networkscited by 1
  11. 2025Leveraging time and parameters for nonlinear model reduction methodscited by 1
  12. 2026Limitations of Learning Tanh Neural Networks with Finite Precisioncited by 1
  13. 2022Constrained Few-Shot Learning: Human-Like Low Sample Complexity Learning and Non-Episodic Text Classificationcited by 0
  14. 2025Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networkscited by 0
  15. 2026Certified and accurate computation of function space norms of deep neural networkscited by 0
  16. 2026The Information-Theoretic Benefit of Shared Representations under Orthogonality Constraintscited by 0
  17. 2026Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networkscited by 0
  18. 2026Residual neural networks overcome the curse of dimensionality for semilinear heat equationscited by 0