mlsanityData to 7 Oct 2026

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

arXiv 2104.08135 ↗First posted 16 Apr 2021math.CO cs.DM cs.LGcited by 37

Not on the map. Why?

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.

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

Builds on

25 of 66 references.

References · 25

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  2. 2016Error bounds for approximations with deep ReLU networkscited by 567
  3. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  4. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  5. 2016On the Expressive Power of Deep Neural Networkscited by 302
  6. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  7. 2016Benefits of depth in neural networkscited by 248
  8. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  9. 2013Maxout Networkscited by 186
  10. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  11. 2019Complexity of Linear Regions in Deep Networkscited by 166
  12. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
13 more
  1. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  2. 2018How to Start Training: The Effect of Initialization and Architecturecited by 109
  3. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  4. 2018Tropical Geometry of Deep Neural Networkscited by 92
  5. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  6. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  7. 2019The Geometry of Deep Networks: Power Diagram Subdivisioncited by 53
  8. 2020On the Number of Linear Regions of Convolutional Neural Networkscited by 49
  9. 2020Empirical Studies on the Properties of Linear Regions in Deep Neural Networkscited by 36
  10. 2018A Tropical Approach to Neural Networks with Piecewise Linear Activationscited by 26
  11. 2018Empirical Bounds on Linear Regions of Deep Rectifier Networkscited by 23
  12. 2018A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networkscited by 15
  13. 2019A Sober Look at Neural Network Initializationscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 7; 2024: 6; 2025: 10; 2026: 5.

37 papers.

Sort:

  1. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  2. 2022The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networkscited by 41
  3. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  4. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  5. 2024The Real Tropical Geometry of Neural Networkscited by 23
  6. 2022Polarity Sampling: Quality and Diversity Control of Pre-Trained Generative Networks via Singular Valuescited by 21
  7. 2022On the Number of Regions of Piecewise Linear Neural Networkscited by 21
  8. 2025Algebra Unveils Deep Learning -- An Invitation to Neuroalgebraic Geometrycited by 21
  9. 2022Toward a Geometrical Understanding of Self-supervised Contrastive Learningcited by 17
  10. 2023Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscapecited by 16
  11. 2021On the Expected Complexity of Maxout Networkscited by 15
  12. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
25 more
  1. 2023Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classificationcited by 11
  2. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  3. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  4. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  5. 2024Neural Networks and (Virtual) Extended Formulationscited by 8
  6. 2023Representing Piecewise Linear Functions by Functions with Small Aritycited by 7
  7. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  8. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  9. 2025Constraining the outputs of ReLU neural networkscited by 3
  10. 2023Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networkscited by 2
  11. 2024Representing Piecewise-Linear Functions by Functions with Minimal Aritycited by 2
  12. 2025Understanding Nonlinear Implicit Bias via Region Counts in Input Spacecited by 2
  13. 2022Robust stabilization of polytopic systems via fast and reliable neural network-based approximationscited by 1
  14. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  15. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  16. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  17. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1
  18. 2022Enumeration of max-pooling responses with generalized permutohedracited by 0
  19. 2024Hyperplane Arrangements and Fixed Points in Iterated PWL Neural Networkscited by 0
  20. 2025The Space Between: On Folding, Symmetries and Samplingcited by 0
  21. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  22. 2025Maxout Polytopescited by 0
  23. 2025On the expressivity of sparse maxout networkscited by 0
  24. 2025Relu and softplus neural nets as zero-sum turn-based gamescited by 0
  25. 2026Laguerre Geometry for Interpreting Large Language Modelscited by 0