# Benefits of depth in neural networks

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

## Key facts

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

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

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Anti-Oversmoothing in Deep Vision Transformers via the Fourier Domain Analysis: From Theory to Practice](https://mlsanity.com/paper/2203.05962/) (2022)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [SpookyNet: Learning Force Fields with Electronic Degrees of Freedom and Nonlocal Effects](https://mlsanity.com/paper/2105.00304/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Prompt Waywardness: The Curious Case of Discretized Interpretation of Continuous Prompts](https://mlsanity.com/paper/2112.08348/) (2021)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [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)
- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Much Ado About Noising: Dispelling the Myths of Generative Robotic Control](https://mlsanity.com/paper/2512.01809/) (2025)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [ExSpliNet: An interpretable and expressive spline-based neural network](https://mlsanity.com/paper/2205.01510/) (2022)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [On the Existence of Universal Lottery Tickets](https://mlsanity.com/paper/2111.11146/) (2021)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [A Primer on Bayesian Neural Networks: Review and Debates](https://mlsanity.com/paper/2309.16314/) (2023)
- [SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models](https://mlsanity.com/paper/2106.00553/) (2021)
- [Achieve the Minimum Width of Neural Networks for Universal Approximation](https://mlsanity.com/paper/2209.11395/) (2022)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [On the statistical complexity of quantum circuits](https://mlsanity.com/paper/2101.06154/) (2021)
- [Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)](https://mlsanity.com/paper/2106.13361/) (2021)
- [How do noise tails impact on deep ReLU networks?](https://mlsanity.com/paper/2203.10418/) (2022)

## Abstract (arXiv)

For any positive integer k, there exist neural networks with Theta(k3) layers, Theta(1) nodes per layer, and Theta(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large --- they must possess Omega(2k) nodes. This result is proved here for a class of nodes termed "semi-algebraic gates" which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Omega(2k3) total tree nodes are required).