# A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [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)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [On the Number of Regions of Piecewise Linear Neural Networks](https://mlsanity.com/paper/2206.08615/) (2022)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks](https://mlsanity.com/paper/2103.17174/) (2021)
- [Deep ReLU networks and high-order finite element methods II: Chebyshev emulation](https://mlsanity.com/paper/2310.07261/) (2023)
- [Sparsity is Combinatorial Depth: Quantifying MoE Expressivity via Tropical Geometry](https://mlsanity.com/paper/2602.03204/) (2026)
- [Dual Graphs of Polyhedral Decompositions for the Detection of Adversarial Attacks](https://mlsanity.com/paper/2211.13305/) (2022)
- [Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2](https://mlsanity.com/paper/2503.13001/) (2025)
- [On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions](https://mlsanity.com/paper/2603.03084/) (2026)
- [Enumeration of max-pooling responses with generalized permutohedra](https://mlsanity.com/paper/2209.14978/) (2022)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)

## Abstract (arXiv)

We present a framework to derive upper bounds on the number of regions that feed-forward neural networks with ReLU activation functions are affine linear on. It is based on an inductive analysis that keeps track of the number of such regions per dimensionality of their images within the layers. More precisely, the information about the number regions per dimensionality is pushed through the layers starting with one region of the input dimension of the neural network and using a recursion based on an analysis of how many regions per output dimensionality a subsequent layer with a certain width can induce on an input region with a given dimensionality. The final bound on the number of regions depends on the number and widths of the layers of the neural network and on some additional parameters that were used for the recursion. It is stated in terms of the L1-norm of the last column of a product of matrices and provides a unifying treatment of several previously known bounds: Depending on the choice of the recursion parameters that determine these matrices, it is possible to obtain the bounds from Mont'ufar (2014), (2017) and Serra et. al. (2017) as special cases. For the latter, which is the strongest of these bounds, the formulation in terms of matrices provides new insight. In particular, by using explicit formulas for a Jordan-like decomposition of the involved matrices, we achieve new tighter results for the asymptotic setting, where the number of layers of the same fixed width tends to infinity.