# Depth separation beyond radial functions

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

## 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 (most cited first, 30 of 33)

- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [The power of deeper networks for expressing natural functions](https://mlsanity.com/paper/1705.05502/) (2017)
- [Expressivity of Deep Neural Networks](https://mlsanity.com/paper/2007.04759/) (2020)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Is Deeper Better only when Shallow is Good?](https://mlsanity.com/paper/1903.03488/) (2019)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Neural Networks with Small Weights and Depth-Separation Barriers](https://mlsanity.com/paper/2006.00625/) (2020)
- [Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem](https://mlsanity.com/paper/1912.04378/) (2019)
- [Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth](https://mlsanity.com/paper/2006.04048/) (2020)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)

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

- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)
- [Exponential Separations in Symmetric Neural Networks](https://mlsanity.com/paper/2206.01266/) (2022)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [Spectral complexity of deep neural networks](https://mlsanity.com/paper/2405.09541/) (2024)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)
- [Depth Separation in Norm-Bounded Infinite-Width Neural Networks](https://mlsanity.com/paper/2402.08808/) (2024)
- [Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics](https://mlsanity.com/paper/2106.05739/) (2021)
- [Expressivity of Shallow and Deep Neural Networks for Polynomial Approximation](https://mlsanity.com/paper/2303.03544/) (2023)
- [Depth and Feature Learning are Provably Beneficial for Neural Network Discriminators](https://mlsanity.com/paper/2112.13867/) (2021)
- [Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks](https://mlsanity.com/paper/2607.25200/) (2026)
- [The Barron-Lipschitz Energy Gap and Depth Separation Phenomena in Scientific Machine Learning](https://mlsanity.com/paper/2607.25905/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## 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.