# On the number of response regions of deep feed forward networks with piece-wise linear activations

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

## Key facts

- Cited by 94 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2013.

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

- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [PredRNN: A Recurrent Neural Network for Spatiotemporal Predictive Learning](https://mlsanity.com/paper/2103.09504/) (2021)
- [ATLAS: Learning to Optimally Memorize the Context at Test Time](https://mlsanity.com/paper/2505.23735/) (2025)
- [Discovering and Explaining the Representation Bottleneck of DNNs](https://mlsanity.com/paper/2111.06236/) (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)
- [Interpreting Neural Networks through the Polytope Lens](https://mlsanity.com/paper/2211.12312/) (2022)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)](https://mlsanity.com/paper/2106.13361/) (2021)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [An Embedding of ReLU Networks and an Analysis of their Identifiability](https://mlsanity.com/paper/2107.09370/) (2021)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [A Survey on Universal Approximation Theorems](https://mlsanity.com/paper/2407.12895/) (2024)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision](https://mlsanity.com/paper/2306.07212/) (2023)
- [TransNet: Transferable Neural Networks for Partial Differential Equations](https://mlsanity.com/paper/2301.11701/) (2023)
- [SWAP-NAS: Sample-Wise Activation Patterns for Ultra-fast NAS](https://mlsanity.com/paper/2403.04161/) (2024)
- [Non-Linear Coordination Graphs](https://mlsanity.com/paper/2211.08404/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Modeling Design and Control Problems Involving Neural Network Surrogates](https://mlsanity.com/paper/2111.10489/) (2021)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [On the Local Complexity of Linear Regions in Deep ReLU Networks](https://mlsanity.com/paper/2412.18283/) (2024)
- [Learning and Meshing from Deep Implicit Surface Networks Using an Efficient Implementation of Analytic Marching](https://mlsanity.com/paper/2106.10031/) (2021)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)

## Abstract (arXiv)

This paper explores the complexity of deep feedforward networks with linear pre-synaptic couplings and rectified linear activations. This is a contribution to the growing body of work contrasting the representational power of deep and shallow network architectures. In particular, we offer a framework for comparing deep and shallow models that belong to the family of piecewise linear functions based on computational geometry. We look at a deep rectifier multi-layer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime, when the number of inputs stays constant, if the shallow model has kn hidden units and n0 inputs, then the number of linear regions is O(kn0nn0). For a k layer model with n hidden units on each layer it is Omega(leftlfloor n/n0rightrfloork-1nn0). The number leftlfloorn/n0rightrfloork-1 grows faster than kn0 when n tends to infinity or when k tends to infinity and n ≥ 2n0. Additionally, even when k is small, if we restrict n to be 2n0, we can show that a deep model has considerably more linear regions that a shallow one. We consider this as a first step towards understanding the complexity of these models and specifically towards providing suitable mathematical tools for future analysis.