# Representation Benefits of Deep Feedforward Networks

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

## Key facts

- Cited by 86 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2015.

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

- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learning](https://mlsanity.com/paper/2406.06158/) (2024)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [The Tunnel Effect: Building Data Representations in Deep Neural Networks](https://mlsanity.com/paper/2305.19753/) (2023)
- [Selective Network Linearization for Efficient Private Inference](https://mlsanity.com/paper/2202.02340/) (2022)
- [Do Sparse Autoencoders Capture Concept Manifolds?](https://mlsanity.com/paper/2604.28119/) (2026)
- [Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)](https://mlsanity.com/paper/2106.13361/) (2021)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [Block-Recurrent Dynamics in Vision Transformers](https://mlsanity.com/paper/2512.19941/) (2025)
- [Deep ReLU Networks Preserve Expected Length](https://mlsanity.com/paper/2102.10492/) (2021)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Neural Network Approximation of Refinable Functions](https://mlsanity.com/paper/2107.13191/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision](https://mlsanity.com/paper/2306.07212/) (2023)
- [On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theorem](https://mlsanity.com/paper/2308.05509/) (2023)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL](https://mlsanity.com/paper/2209.09845/) (2022)
- [Effects of Data Geometry in Early Deep Learning](https://mlsanity.com/paper/2301.00008/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [Expressivity and Approximation Properties of Deep Neural Networks with ReLUk Activation](https://mlsanity.com/paper/2312.16483/) (2023)
- [Curved Representation Space of Vision Transformers](https://mlsanity.com/paper/2210.05742/) (2022)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [Deep Neural Networks and Finite Elements of Any Order on Arbitrary Dimensions](https://mlsanity.com/paper/2312.14276/) (2023)

## Abstract (arXiv)

This note provides a family of classification problems, indexed by a positive integer k, where all shallow networks with fewer than exponentially (in k) many nodes exhibit error at least 1/6, whereas a deep network with 2 nodes in each of 2k layers achieves zero error, as does a recurrent network with 3 distinct nodes iterated k times. The proof is elementary, and the networks are standard feedforward networks with ReLU (Rectified Linear Unit) nonlinearities.