mlsanityData to 7 Oct 2026

On the Number of Regions of Piecewise Linear Neural Networks

arXiv 2206.08615 ↗First posted 17 Jun 2022cs.LG math.CO math.STcited by 21

Not on the map. Why?

Abstract (arXiv)

Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. Specifically, they partition the input domain into regions on which the mapping is affine. The number of these so-called linear regions offers a natural metric to characterize the expressiveness of CPWL NNs. The precise determination of this quantity is often out of reach in practice, and bounds have been proposed for specific architectures, including for ReLU and Maxout NNs. In this work, we generalize these bounds to NNs with arbitrary and possibly multivariate CPWL activation functions. We first provide upper and lower bounds on the maximal number of linear regions of a CPWL NN given its depth, width, and the number of linear regions of its activation functions. Our results rely on the combinatorial structure of convex partitions and confirm the distinctive role of depth which, on its own, is able to exponentially increase the number of regions. We then introduce a complementary stochastic framework to estimate the average number of linear regions produced by a CPWL NN. Under reasonable assumptions, the expected density of linear regions along any 1D path is bounded by the product of depth, width, and a measure of activation complexity (up to a scaling factor). This yields an identical role to the three sources of expressiveness: no exponential growth with depth is observed anymore.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 28 of its 44 references that are in the map. First posted on arXiv 17 Jun 2022.

Builds on

28 of 44 references.

References · 28

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  3. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  4. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  5. 2016On the Expressive Power of Deep Neural Networkscited by 302
  6. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  7. 2018Sorting out Lipschitz function approximationcited by 211
  8. 2013Maxout Networkscited by 186
  9. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  10. 2019Complexity of Linear Regions in Deep Networkscited by 166
  11. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  12. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
16 more
  1. 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
  2. 2020Training robust neural networks using Lipschitz boundscited by 98
  3. 2016Understanding and Improving Convolutional Neural Networks via Concatenated Rectified Linear Unitscited by 86
  4. 2016Deep vs. shallow networks : An approximation theory perspectivecited by 63
  5. 2014Learning Activation Functions to Improve Deep Neural Networkscited by 62
  6. 2018Mad Max: Affine Spline Insights into Deep Learningcited by 54
  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. 2021Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100cited by 47
  10. 2018A representer theorem for deep neural networkscited by 38
  11. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  12. 2020Approximating Lipschitz continuous functions with GroupSort neural networkscited by 27
  13. 2021Deep ReLU Networks Preserve Expected Lengthcited by 17
  14. 2018A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networkscited by 15
  15. 2021On the Expected Complexity of Maxout Networkscited by 15
  16. 2022Approximation of Lipschitz Functions using Deep Spline Neural Networkscited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 8; 2026: 7.

21 papers.

Sort:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2024On the Local Complexity of Linear Regions in Deep ReLU Networkscited by 9
  3. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  4. 2025Convexity in ReLU Neural Networks: beyond ICNNs?cited by 6
  5. 2023The Evolution of the Interplay Between Input Distributions and Linear Regions in Networkscited by 3
  6. 2024Spectral complexity of deep neural networkscited by 3
  7. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  8. 2025Fractal and Regular Geometry of Deep Neural Networkscited by 1
  9. 2025Certified Neural Approximations of Nonlinear Dynamicscited by 1
  10. 2026ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networkscited by 1
  11. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  12. 2026AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networkscited by 1
9 more
  1. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  2. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1
  3. 2024The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forestcited by 0
  4. 2025A Quotient Homology Theory of Representation in Neural Networkscited by 0
  5. 2025The Space Between: On Folding, Symmetries and Samplingcited by 0
  6. 2025ReLU Networks as Random Functions: Their Distribution in Probability Spacecited by 0
  7. 2025Critical Points of Random Neural Networkscited by 0
  8. 2026Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexitycited by 0
  9. 2026Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulascited by 0