# Bounding and Counting Linear Regions of Deep Neural Networks

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

## Key facts

- Cited by 161 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2017.

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

- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [CKConv: Continuous Kernel Convolution For Sequential Data](https://mlsanity.com/paper/2102.02611/) (2021)
- [Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition](https://mlsanity.com/paper/2102.01063/) (2021)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (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)
- [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)
- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (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)
- [Do Sparse Autoencoders Capture Concept Manifolds?](https://mlsanity.com/paper/2604.28119/) (2026)
- [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)
- [Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks](https://mlsanity.com/paper/2207.07696/) (2022)
- [On the Number of Regions of Piecewise Linear Neural Networks](https://mlsanity.com/paper/2206.08615/) (2022)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Zero-Shot Neural Architecture Search: Challenges, Solutions, and Opportunities](https://mlsanity.com/paper/2307.01998/) (2023)
- [Block-Recurrent Dynamics in Vision Transformers](https://mlsanity.com/paper/2512.19941/) (2025)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [GradSign: Model Performance Inference with Theoretical Insights](https://mlsanity.com/paper/2110.08616/) (2021)
- [Neur2SP: Neural Two-Stage Stochastic Programming](https://mlsanity.com/paper/2205.12006/) (2022)
- [MAE-DET: Revisiting Maximum Entropy Principle in Zero-Shot NAS for Efficient Object Detection](https://mlsanity.com/paper/2111.13336/) (2021)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Convergence of Deep ReLU Networks](https://mlsanity.com/paper/2107.12530/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision](https://mlsanity.com/paper/2306.07212/) (2023)
- [Sound and Complete Neural Network Repair with Minimality and Locality Guarantees](https://mlsanity.com/paper/2110.07682/) (2021)

## Abstract (arXiv)

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions, i.e. pieces, that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions on rectifier networks, which are exact for inputs of dimension one; (ii) a first upper bound for multi-layer maxout networks; and (iii) a first method to perform exact enumeration or counting of the number of regions by modeling the DNN with a mixed-integer linear formulation. These bounds come from leveraging the dimension of the space defining each linear region. The results also indicate that a deep rectifier network can only have more linear regions than every shallow counterpart with same number of neurons if that number exceeds the dimension of the input.