mlsanityData to 14 Oct 2026

Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

arXiv 1610.09887 ↗First posted 31 Oct 2016cs.LG cs.NE stat.MLcited by 59

Not on the map. Why?

Abstract (arXiv)

We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-linear functions which are radial with respect to the L1 norm; and smooth non-linear functions. We also show that these gaps can be observed experimentally: Increasing the depth indeed allows better learning than increasing width, when training neural networks to learn an indicator of a unit ball.

Key facts. Cited by 59 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 17; 2022: 8; 2023: 14; 2024: 11; 2025: 4; 2026: 5.

59 papers.

Sort:

By area:

  1. 2022Is Out-of-Distribution Detection Learnable?cited by 109
  2. 2021Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networkscited by 74
  3. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  4. 2024Theoretical limitations of multi-layer Transformercited by 45
  5. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  6. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  7. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  8. 2021Theory of Deep Convolutional Neural Networks III: Approximating Radial Functionscited by 22
  9. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  10. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 19
  11. 2021Depth separation beyond radial functionscited by 18
  12. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
38 more
  1. 2021Optimization-Based Separations for Neural Networkscited by 17
  2. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  3. 2021Layer Folding: Neural Network Depth Reduction using Activation Linearizationcited by 14
  4. 2024On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networkscited by 13
  5. 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 12
  6. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  7. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10
  8. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  9. 2023Depth Separation with Multilayer Mean-Field Networkscited by 9
  10. 2026Inverse Depth Scaling From Most Layers Being Similarcited by 9
  11. 2021What Do Deep Nets Learn? Class-wise Patterns Revealed in the Input Spacecited by 8
  12. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  13. 2023Quantifying Privacy Risks of Prompts in Visual Prompt Learningcited by 8
  14. 2021Size and Depth Separation in Approximating Benign Functions with Neural Networkscited by 7
  15. 2021Meta Internal Learningcited by 7
  16. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 6
  17. 2021Quantitative approximation results for complex-valued neural networkscited by 5
  18. 2022Intrinsic dimensionality and generalization properties of the R-norm inductive biascited by 5
  19. 2022On the Privacy Risks of Cell-Based NAS Architecturescited by 5
  20. 2023Error convergence and engineering-guided hyperparameter search of PINNs: towards optimized I-FENN performancecited by 5
  21. 2023Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Spacecited by 5
  22. 2024On the Benefits of Rank in Attention Layerscited by 5
  23. 2023Deep Convolutional Neural Networks with Zero-Padding: Feature Extraction and Learningcited by 4
  24. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  25. 2021Theoretical Exploration of Flexible Transmitter Modelcited by 3
  26. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  27. 2024Depth Separation in Norm-Bounded Infinite-Width Neural Networkscited by 3
  28. 2024Spectral complexity of deep neural networkscited by 3
  29. 2024Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Modelscited by 3
  30. 2024On the Expressive Power of Tree-Structured Probabilistic Circuitscited by 3
  31. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  32. 2024A Theoretical Study of Neural Network Expressive Power via Manifold Topologycited by 2
  33. 2023Expressivity of Shallow and Deep Neural Networks for Polynomial Approximationcited by 1
  34. 2023Securing Neural Networks with Knapsack Optimizationcited by 1
  35. 2023Data Topology-Dependent Upper Bounds of Neural Network Widthscited by 1
  36. 2023From Alexnet to Transformers: Measuring the Non-linearity of Deep Neural Networks with Affine Optimal Transportcited by 1
  37. 2024Hybrid Quantum-inspired Resnet and Densenet for Pattern Recognitioncited by 1
  38. 2021Bayesian Deep Learning Hyperparameter Search for Robust Function Mapping to Polynomials with Noisecited by 0

50 most cited of 59 All 59 (JSON)