mlsanityData to 14 Oct 2026

Bounding and Counting Linear Regions of Deep Neural Networks

arXiv 1711.02114 ↗First posted 6 Nov 2017cs.LG cs.AI cs.NEcited by 161

Not on the map. Why?

Abstract (arXiv)

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions, i.e. pieces, that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions on rectifier networks, which are exact for inputs of dimension one; (ii) a first upper bound for multi-layer maxout networks; and (iii) a first method to perform exact enumeration or counting of the number of regions by modeling the DNN with a mixed-integer linear formulation. These bounds come from leveraging the dimension of the space defining each linear region. The results also indicate that a deep rectifier network can only have more linear regions than every shallow counterpart with same number of neurons if that number exceeds the dimension of the input.

Key facts. Cited by 161 papers in the map (data through 14 Oct 2026). First posted on arXiv 6 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 31; 2022: 30; 2023: 27; 2024: 22; 2025: 27; 2026: 24.

161 papers.

Sort:

By area:

  1. 2021Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspectivecited by 169
  2. 2021CKConv: Continuous Kernel Convolution For Sequential Datacited by 120
  3. 2021Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognitioncited by 73
  4. 2021Model Complexity of Deep Learning: A Surveycited by 65
  5. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  6. 2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 51
  7. 2024Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learningcited by 42
  8. 2022The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networkscited by 41
  9. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  10. 2022Why neural networks find simple solutions: the many regularizers of geometric complexitycited by 39
  11. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  12. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
38 more
  1. 2026Do Sparse Autoencoders Capture Concept Manifolds?cited by 31
  2. 2022Improved Bounds on Neural Complexity for Representing Piecewise Linear Functionscited by 26
  3. 2021Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)cited by 25
  4. 2024The Real Tropical Geometry of Neural Networkscited by 24
  5. 2022Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networkscited by 22
  6. 2022On the Number of Regions of Piecewise Linear Neural Networkscited by 21
  7. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 21
  8. 2023Zero-Shot Neural Architecture Search: Challenges, Solutions, and Opportunitiescited by 21
  9. 2025Block-Recurrent Dynamics in Vision Transformerscited by 20
  10. 2021Scaling Up Exact Neural Network Compression by ReLU Stabilitycited by 19
  11. 2021GradSign: Model Performance Inference with Theoretical Insightscited by 19
  12. 2022Neur2SP: Neural Two-Stage Stochastic Programmingcited by 17
  13. 2021MAE-DET: Revisiting Maximum Entropy Principle in Zero-Shot NAS for Efficient Object Detectioncited by 16
  14. 2021On the Expected Complexity of Maxout Networkscited by 15
  15. 2021Convergence of Deep ReLU Networkscited by 15
  16. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  17. 2023Polyhedral Complex Extraction from ReLU Networks using Edge Subdivisioncited by 14
  18. 2021Sound and Complete Neural Network Repair with Minimality and Locality Guaranteescited by 13
  19. 2021Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verificationcited by 13
  20. 2022Are All Linear Regions Created Equal?cited by 13
  21. 2023TransNet: Transferable Neural Networks for Partial Differential Equationscited by 13
  22. 2024FairProof : Confidential and Certifiable Fairness for Neural Networkscited by 13
  23. 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 12
  24. 2021A Simple and Efficient Sampling-based Algorithm for General Reachability Analysiscited by 12
  25. 2022Effects of Data Geometry in Early Deep Learningcited by 12
  26. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  27. 2022Non-Linear Coordination Graphscited by 10
  28. 2023ReLU Neural Networks, Polyhedral Decompositions, and Persistent Homologcited by 10
  29. 2023Topological Expressivity of ReLU Neural Networkscited by 10
  30. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  31. 2022Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networkscited by 9
  32. 2024Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimallycited by 9
  33. 2024On the Local Complexity of Linear Regions in Deep ReLU Networkscited by 9
  34. 2022A coherence parameter characterizing generative compressed sensing with Fourier measurementscited by 8
  35. 2022Batch Normalization Explainedcited by 8
  36. 2022Curved Representation Space of Vision Transformerscited by 8
  37. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  38. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7

50 most cited of 161 All 161 (JSON)