# Enumeration of max-pooling responses with generalized permutohedra

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 44 references that are in the map.
- First posted on arXiv 29 Sep 2022.

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

- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [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)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [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)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [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)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [A Tropical Approach to Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/1805.08749/) (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 geometric approach for the upper bound theorem for Minkowski sums of convex polytopes](https://mlsanity.com/paper/1502.02265/) (2015)

## Abstract (arXiv)

We investigate the combinatorics of max-pooling layers, which are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates, and which are commonly used in convolutional neural networks. We obtain results on the number of linearity regions of these functions by equivalently counting the number of vertices of certain Minkowski sums of simplices. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride, and for the number of vertices in a special case of 2D max-pooling.