# Deep ReLU Networks Have Surprisingly Simple Polytopes

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 59 references that are in the map.
- First posted on arXiv 16 May 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [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)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [A Fine-Grained Spectral Perspective on Neural Networks](https://mlsanity.com/paper/1907.10599/) (2019)
- [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)
- [Mad Max: Affine Spline Insights into Deep Learning](https://mlsanity.com/paper/1805.06576/) (2018)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)

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

- [Revisiting Long-term Time Series Forecasting: An Investigation on Linear Mapping](https://mlsanity.com/paper/2305.10721/) (2023)
- [On convex decision regions in deep network representations](https://mlsanity.com/paper/2305.17154/) (2023)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [A Quotient Homology Theory of Representation in Neural Networks](https://mlsanity.com/paper/2502.01360/) (2025)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)

## Abstract (arXiv)

A ReLU network is a piecewise linear function over polytopes. Figuring out the properties of such polytopes is of fundamental importance for the research and development of neural networks. So far, either theoretical or empirical studies on polytopes only stay at the level of counting their number, which is far from a complete characterization. Here, we propose to study the shapes of polytopes via the number of faces of the polytope. Then, by computing and analyzing the histogram of faces across polytopes, we find that a ReLU network has relatively simple polytopes under both initialization and gradient descent, although these polytopes can be rather diverse and complicated by a specific design. This finding can be appreciated as a kind of generalized implicit bias, subjected to the intrinsic geometric constraint in space partition of a ReLU network. Next, we perform a combinatorial analysis to explain why adding depth does not generate a more complicated polytope by bounding the average number of faces of polytopes with the dimensionality. Our results concretely reveal what kind of simple functions a network learns and what will happen when a network goes deep. Also, by characterizing the shape of polytopes, the number of faces can be a novel leverage for other problems, textite.g., serving as a generic tool to explain the power of popular shortcut networks such as ResNet and analyzing the impact of different regularization strategies on a network's space partition.