# Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

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

## Key facts

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

## Built on by (most cited first, 30 of 59)

- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networks](https://mlsanity.com/paper/2110.03825/) (2021)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Theory of Deep Convolutional Neural Networks III: Approximating Radial Functions](https://mlsanity.com/paper/2107.00896/) (2021)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (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)
- [Inverse Depth Scaling From Most Layers Being Similar](https://mlsanity.com/paper/2602.05970/) (2026)
- [What Do Deep Nets Learn? Class-wise Patterns Revealed in the Input Space](https://mlsanity.com/paper/2101.06898/) (2021)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Quantifying Privacy Risks of Prompts in Visual Prompt Learning](https://mlsanity.com/paper/2310.11970/) (2023)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Meta Internal Learning](https://mlsanity.com/paper/2110.02900/) (2021)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Quantitative approximation results for complex-valued neural networks](https://mlsanity.com/paper/2102.13092/) (2021)
- [Intrinsic dimensionality and generalization properties of the R-norm inductive bias](https://mlsanity.com/paper/2206.05317/) (2022)

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