# On the Number of Linear Regions of Convolutional Neural Networks

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

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

- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition](https://mlsanity.com/paper/2102.01063/) (2021)
- [Neural Architecture Search for Spiking Neural Networks](https://mlsanity.com/paper/2201.10355/) (2022)
- [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)
- [AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search](https://mlsanity.com/paper/2403.19232/) (2024)
- [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)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Automated Deep Learning: Neural Architecture Search Is Not the End](https://mlsanity.com/paper/2112.09245/) (2021)
- [Are All Linear Regions Created Equal?](https://mlsanity.com/paper/2202.11749/) (2022)
- [SWAP-NAS: Sample-Wise Activation Patterns for Ultra-fast NAS](https://mlsanity.com/paper/2403.04161/) (2024)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/2102.13233/) (2021)
- [Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks](https://mlsanity.com/paper/2103.17174/) (2021)
- [Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics](https://mlsanity.com/paper/2108.11939/) (2021)
- [Piecewise Linear Neural Networks and Deep Learning](https://mlsanity.com/paper/2206.09149/) (2022)
- [Deep ReLU Networks Have Surprisingly Simple Polytopes](https://mlsanity.com/paper/2305.09145/) (2023)
- [MicroNAS: Zero-Shot Neural Architecture Search for MCUs](https://mlsanity.com/paper/2401.08996/) (2024)
- [L-SWAG: Layer-Sample Wise Activation with Gradients information for Zero-Shot NAS on Vision Transformers](https://mlsanity.com/paper/2505.07300/) (2025)
- [MONAS: Efficient Zero-Shot Neural Architecture Search for MCUs](https://mlsanity.com/paper/2408.15034/) (2024)
- [Neural networks behave as hash encoders: An empirical study](https://mlsanity.com/paper/2101.05490/) (2021)
- [A Rigorous Study Of The Deep Taylor Decomposition](https://mlsanity.com/paper/2211.08425/) (2022)
- [Revisiting Training-free NAS Metrics: An Efficient Training-based Method](https://mlsanity.com/paper/2211.08666/) (2022)
- [Training-free Neural Architecture Search through Variance of Knowledge of Deep Network Weights](https://mlsanity.com/paper/2502.04975/) (2025)
- [On Space Folds of ReLU Neural Networks](https://mlsanity.com/paper/2502.09954/) (2025)
- [Sparsity is Combinatorial Depth: Quantifying MoE Expressivity via Tropical Geometry](https://mlsanity.com/paper/2602.03204/) (2026)

## Abstract (arXiv)

One fundamental problem in deep learning is understanding the outstanding performance of deep Neural Networks (NNs) in practice. One explanation for the superiority of NNs is that they can realize a large class of complicated functions, i.e., they have powerful expressivity. The expressivity of a ReLU NN can be quantified by the maximal number of linear regions it can separate its input space into. In this paper, we provide several mathematical results needed for studying the linear regions of CNNs, and use them to derive the maximal and average numbers of linear regions for one-layer ReLU CNNs. Furthermore, we obtain upper and lower bounds for the number of linear regions of multi-layer ReLU CNNs. Our results suggest that deeper CNNs have more powerful expressivity than their shallow counterparts, while CNNs have more expressivity than fully-connected NNs per parameter.