mlsanityData to 7 Oct 2026

Depth Separation for Neural Networks

arXiv 1702.08489 ↗First posted 27 Feb 2017cs.LG cs.CC stat.MLcited by 46

Not on the map. Why?

Abstract (arXiv)

Let f:mathbbSd-1× mathbbSd-1→mathbbS be a function of the form f(x,x') = g(langlex,x'rangle) for g:[-1,1]→ ℝ. We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate f whenever g cannot be approximated by a low degree polynomial. Moreover, for many g's, such as g(x)=sin(π d3x), the number of neurons must be 2Omegaleft(dlog(d)right). Furthermore, the result holds w.r.t. the uniform distribution on mathbbSd-1× mathbbSd-1. As many functions of the above form can be well approximated by poly-size depth three networks with poly-bounded weights, this establishes a separation between depth two and depth three networks w.r.t. the uniform distribution on mathbbSd-1× mathbbSd-1.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 7; 2023: 12; 2024: 7; 2025: 3; 2026: 5.

46 papers.

Sort:

By area:

  1. 2022Transformers Learn Shortcuts to Automatacited by 260
  2. 2023Representational Strengths and Limitations of Transformerscited by 132
  3. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  4. 2024Theoretical limitations of multi-layer Transformercited by 43
  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. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
  8. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  9. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  10. 2021Depth separation beyond radial functionscited by 18
  11. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 18
  12. 2021Deep ReLU Networks Preserve Expected Lengthcited by 17
34 more
  1. 2021Optimization-Based Separations for Neural Networkscited by 17
  2. 2021Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networkscited by 17
  3. 2023Minimum width for universal approximation using ReLU networks on compact domaincited by 17
  4. 2022The Role of Linear Layers in Nonlinear Interpolating Networkscited by 15
  5. 2021Layer Folding: Neural Network Depth Reduction using Activation Linearizationcited by 14
  6. 2023Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal Approximationcited by 13
  7. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  8. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  9. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10
  10. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  11. 2024Features are fate: a theory of transfer learning in high-dimensional regressioncited by 10
  12. 2023Depth Separation with Multilayer Mean-Field Networkscited by 8
  13. 2021Size and Depth Separation in Approximating Benign Functions with Neural Networkscited by 7
  14. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  15. 2022Intrinsic dimensionality and generalization properties of the R-norm inductive biascited by 5
  16. 2023Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Spacecited by 5
  17. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 5
  18. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  19. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  20. 2024Spectral complexity of deep neural networkscited by 3
  21. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  22. 2021Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theoremcited by 2
  23. 2022Towards Antisymmetric Neural Ansatz Separationcited by 2
  24. 2023A Minimal Control Family of Dynamical Systems for Universal Approximationcited by 2
  25. 2024Depth Separation in Norm-Bounded Infinite-Width Neural Networkscited by 2
  26. 2025Information-Theoretic Framework for Understanding Modern Machine-Learningcited by 2
  27. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 2
  28. 2023Expressivity of Shallow and Deep Neural Networks for Polynomial Approximationcited by 1
  29. 2024Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networkscited by 1
  30. 2021Depth and Feature Learning are Provably Beneficial for Neural Network Discriminatorscited by 0
  31. 2023Deep neural network approximation of composite functions without the curse of dimensionalitycited by 0
  32. 2024The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forestcited by 0
  33. 2026Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networkscited by 0
  34. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0