# On the Expected Complexity of Maxout Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 67 references that are in the map.
- First posted on arXiv 1 Jul 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (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)
- [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)
- [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)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [On the Number of Linear Regions of Convolutional Neural Networks](https://mlsanity.com/paper/2006.00978/) (2020)
- [Gradient Dynamics of Shallow Univariate ReLU Networks](https://mlsanity.com/paper/1906.07842/) (2019)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Empirical Studies on the Properties of Linear Regions in Deep Neural Networks](https://mlsanity.com/paper/2001.01072/) (2020)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (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)
- [Towards Robust, Locally Linear Deep Networks](https://mlsanity.com/paper/1907.03207/) (2019)
- [Deep ReLU Networks Preserve Expected Length](https://mlsanity.com/paper/2102.10492/) (2021)
- [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)
- [Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks](https://mlsanity.com/paper/2103.17174/) (2021)
- [A Sober Look at Neural Network Initializations](https://mlsanity.com/paper/1903.11482/) (2019)
- [A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions](https://mlsanity.com/paper/2012.04428/) (2020)

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

- [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)
- [On the Number of Regions of Piecewise Linear Neural Networks](https://mlsanity.com/paper/2206.08615/) (2022)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [On the Local Complexity of Linear Regions in Deep ReLU Networks](https://mlsanity.com/paper/2412.18283/) (2024)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [Expected Gradients of Maxout Networks and Consequences to Parameter Initialization](https://mlsanity.com/paper/2301.06956/) (2023)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks](https://mlsanity.com/paper/2605.06218/) (2026)
- [Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks](https://mlsanity.com/paper/2605.06300/) (2026)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [A Rigorous, Tractable Measure of Model Complexity](https://mlsanity.com/paper/2605.21167/) (2026)
- [Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity](https://mlsanity.com/paper/2606.21687/) (2026)

## Abstract (arXiv)

Learning with neural networks relies on the complexity of the representable functions, but more importantly, the particular assignment of typical parameters to functions of different complexity. Taking the number of activation regions as a complexity measure, recent works have shown that the practical complexity of deep ReLU networks is often far from the theoretical maximum. In this work, we show that this phenomenon also occurs in networks with maxout (multi-argument) activation functions and when considering the decision boundaries in classification tasks. We also show that the parameter space has a multitude of full-dimensional regions with widely different complexity, and obtain nontrivial lower bounds on the expected complexity. Finally, we investigate different parameter initialization procedures and show that they can increase the speed of convergence in training.