mlsanityData to 7 Oct 2026

Depth separation beyond radial functions

arXiv 2102.01621 ↗First posted 2 Feb 2021cs.LG cs.NE stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

High-dimensional depth separation results for neural networks show that certain functions can be efficiently approximated by two-hidden-layer networks but not by one-hidden-layer ones in high-dimensions d. Existing results of this type mainly focus on functions with an underlying radial or one-dimensional structure, which are usually not encountered in practice. The first contribution of this paper is to extend such results to a more general class of functions, namely functions with piece-wise oscillatory structure, by building on the proof strategy of (Eldan and Shamir, 2016). We complement these results by showing that, if the domain radius and the rate of oscillation of the objective function are constant, then approximation by one-hidden-layer networks holds at a poly(d) rate for any fixed error threshold. A common theme in the proofs of depth-separation results is the fact that one-hidden-layer networks fail to approximate high-energy functions whose Fourier representation is spread in the domain. On the other hand, existing approximation results of a function by one-hidden-layer neural networks rely on the function having a sparse Fourier representation. The choice of the domain also represents a source of gaps between upper and lower approximation bounds. Focusing on a fixed approximation domain, namely the sphere mathbbSd-1 in dimension d, we provide a characterisation of both functions which are efficiently approximable by one-hidden-layer networks and of functions which are provably not, in terms of their Fourier expansion.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 33 of its 51 references that are in the map. First posted on arXiv 2 Feb 2021.

Builds on

33 of 51 references.

References · 33

  1. 2018On the Spectral Bias of Neural Networkscited by 1,321
  2. 2016Error bounds for approximations with deep ReLU networkscited by 567
  3. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  4. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  5. 2016On the Expressive Power of Deep Neural Networkscited by 302
  6. 2016Exponential expressivity in deep neural networks through transient chaoscited by 260
  7. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  8. 2016Benefits of depth in neural networkscited by 248
  9. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  10. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
  11. 2019Complexity of Linear Regions in Deep Networkscited by 166
  12. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
21 more
  1. 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
  2. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 113
  3. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  4. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  5. 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 90
  6. 2016Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ℓ1 and ℓ0 Controlscited by 84
  7. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  8. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  9. 2017Depth Separation for Neural Networkscited by 46
  10. 2017The power of deeper networks for expressing natural functionscited by 35
  11. 2020Expressivity of Deep Neural Networkscited by 31
  12. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  13. 2019Is Deeper Better only when Shallow is Good?cited by 24
  14. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  15. 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
  16. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  17. 2020Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depthcited by 13
  18. 2021Size and Depth Separation in Approximating Benign Functions with Neural Networkscited by 7
  19. 2020Depth-Width Trade-offs for Neural Networks via Topological Entropycited by 6
  20. 2020Depth separation for reduced deep networks in nonlinear model reduction: Distilling shock waves in nonlinear hyperbolic problemscited by 3
  21. 2019Efficient Deep Learning of GMMscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 4; 2024: 3; 2025: 0; 2026: 5.

18 papers.

Sort:

  1. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  2. 2021Optimization-Based Separations for Neural Networkscited by 17
  3. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  4. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10
  5. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  6. 2023Depth Separation with Multilayer Mean-Field Networkscited by 8
  7. 2023Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Spacecited by 5
  8. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 5
  9. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  10. 2024Spectral complexity of deep neural networkscited by 3
  11. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  12. 2024Depth Separation in Norm-Bounded Infinite-Width Neural Networkscited by 2
6 more
  1. 2021Separation Results between Fixed-Kernel and Feature-Learning Probability Metricscited by 1
  2. 2023Expressivity of Shallow and Deep Neural Networks for Polynomial Approximationcited by 1
  3. 2021Depth and Feature Learning are Provably Beneficial for Neural Network Discriminatorscited by 0
  4. 2026Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networkscited by 0
  5. 2026The Barron-Lipschitz Energy Gap and Depth Separation Phenomena in Scientific Machine Learningcited by 0
  6. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0