# Complexity of Linear Regions in Deep Networks

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

## Key facts

- Cited by 167 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2019.

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

- [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)
- [Deep Model Reassembly](https://mlsanity.com/paper/2210.17409/) (2022)
- [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)
- [Neural Architecture Search for Spiking Neural Networks](https://mlsanity.com/paper/2201.10355/) (2022)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [Random Neural Networks in the Infinite Width Limit as Gaussian Processes](https://mlsanity.com/paper/2107.01562/) (2021)
- [Provable Repair of Deep Neural Networks](https://mlsanity.com/paper/2104.04413/) (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)
- [The Tunnel Effect: Building Data Representations in Deep Neural Networks](https://mlsanity.com/paper/2305.19753/) (2023)
- [Interpreting Neural Networks through the Polytope Lens](https://mlsanity.com/paper/2211.12312/) (2022)
- [SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundaries](https://mlsanity.com/paper/2302.12828/) (2023)
- [Do Sparse Autoencoders Capture Concept Manifolds?](https://mlsanity.com/paper/2604.28119/) (2026)
- [AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search](https://mlsanity.com/paper/2403.19232/) (2024)
- [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)
- [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)
- [Zero-Shot Neural Architecture Search: Challenges, Solutions, and Opportunities](https://mlsanity.com/paper/2307.01998/) (2023)
- [Quantitative CLTs in Deep Neural Networks](https://mlsanity.com/paper/2307.06092/) (2023)
- [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)
- [Deep ReLU Networks Preserve Expected Length](https://mlsanity.com/paper/2102.10492/) (2021)
- [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)

## Abstract (arXiv)

It is well-known that the expressivity of a neural network depends on its architecture, with deeper networks expressing more complex functions. In the case of networks that compute piecewise linear functions, such as those with ReLU activation, the number of distinct linear regions is a natural measure of expressivity. It is possible to construct networks with merely a single region, or for which the number of linear regions grows exponentially with depth; it is not clear where within this range most networks fall in practice, either before or after training. In this paper, we provide a mathematical framework to count the number of linear regions of a piecewise linear network and measure the volume of the boundaries between these regions. In particular, we prove that for networks at initialization, the average number of regions along any one-dimensional subspace grows linearly in the total number of neurons, far below the exponential upper bound. We also find that the average distance to the nearest region boundary at initialization scales like the inverse of the number of neurons. Our theory suggests that, even after training, the number of linear regions is far below exponential, an intuition that matches our empirical observations. We conclude that the practical expressivity of neural networks is likely far below that of the theoretical maximum, and that this gap can be quantified.