# Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 66 references that are in the map.
- First posted on arXiv 16 Apr 2021.

## Builds on (most cited first, 25 of 25)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [How to Start Training: The Effect of Initialization and Architecture](https://mlsanity.com/paper/1803.01719/) (2018)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [The Geometry of Deep Networks: Power Diagram Subdivision](https://mlsanity.com/paper/1905.08443/) (2019)
- [On the Number of Linear Regions of Convolutional Neural Networks](https://mlsanity.com/paper/2006.00978/) (2020)
- [Empirical Studies on the Properties of Linear Regions in Deep Neural Networks](https://mlsanity.com/paper/2001.01072/) (2020)
- [A Tropical Approach to Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/1805.08749/) (2018)
- [Empirical Bounds on Linear Regions of Deep Rectifier Networks](https://mlsanity.com/paper/1810.03370/) (2018)
- [A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks](https://mlsanity.com/paper/1806.01918/) (2018)
- [A Sober Look at Neural Network Initializations](https://mlsanity.com/paper/1903.11482/) (2019)

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

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [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)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Polarity Sampling: Quality and Diversity Control of Pre-Trained Generative Networks via Singular Values](https://mlsanity.com/paper/2203.01993/) (2022)
- [On the Number of Regions of Piecewise Linear Neural Networks](https://mlsanity.com/paper/2206.08615/) (2022)
- [Algebra Unveils Deep Learning -- An Invitation to Neuroalgebraic Geometry](https://mlsanity.com/paper/2501.18915/) (2025)
- [Toward a Geometrical Understanding of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2205.06926/) (2022)
- [Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape](https://mlsanity.com/paper/2305.19510/) (2023)
- [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)
- [Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classification](https://mlsanity.com/paper/2306.08805/) (2023)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [Representing Piecewise Linear Functions by Functions with Small Arity](https://mlsanity.com/paper/2305.16933/) (2023)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks](https://mlsanity.com/paper/2306.15157/) (2023)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)
- [Understanding Nonlinear Implicit Bias via Region Counts in Input Space](https://mlsanity.com/paper/2505.11370/) (2025)
- [Robust stabilization of polytopic systems via fast and reliable neural network-based approximations](https://mlsanity.com/paper/2204.13209/) (2022)
- [A Computational Tropical Geometry Framework for Neural Networks](https://mlsanity.com/paper/2405.20174/) (2024)
- [Relu and softplus neural nets as zero-sum turn-based games](https://mlsanity.com/paper/2512.20582/) (2025)
- [On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions](https://mlsanity.com/paper/2603.03084/) (2026)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)

## Abstract (arXiv)

We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units. A rank-k maxout unit is a function computing the maximum of k linear functions. For networks with a single layer of maxout units, the linear regions correspond to the upper vertices of a Minkowski sum of polytopes. We obtain face counting formulas in terms of the intersection posets of tropical hypersurfaces or the number of upper faces of partial Minkowski sums, along with explicit sharp upper bounds for the number of regions for any input dimension, any number of units, and any ranks, in the cases with and without biases. Based on these results we also obtain asymptotically sharp upper bounds for networks with multiple layers.