mlsanityData to 7 Oct 2026

On the Number of Linear Regions of Convolutional Neural Networks

arXiv 2006.00978 ↗First posted 1 Jun 2020cs.LG stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

One fundamental problem in deep learning is understanding the outstanding performance of deep Neural Networks (NNs) in practice. One explanation for the superiority of NNs is that they can realize a large class of complicated functions, i.e., they have powerful expressivity. The expressivity of a ReLU NN can be quantified by the maximal number of linear regions it can separate its input space into. In this paper, we provide several mathematical results needed for studying the linear regions of CNNs, and use them to derive the maximal and average numbers of linear regions for one-layer ReLU CNNs. Furthermore, we obtain upper and lower bounds for the number of linear regions of multi-layer ReLU CNNs. Our results suggest that deeper CNNs have more powerful expressivity than their shallow counterparts, while CNNs have more expressivity than fully-connected NNs per parameter.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

49 papers.

Sort:

By area:

  1. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  2. 2021Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspectivecited by 168
  3. 2021Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognitioncited by 71
  4. 2022Neural Architecture Search for Spiking Neural Networkscited by 52
  5. 2022The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networkscited by 41
  6. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  7. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  8. 2024AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Searchcited by 25
  9. 2022On the Number of Regions of Piecewise Linear Neural Networkscited by 21
  10. 2023Zero-Shot Neural Architecture Search: Challenges, Solutions, and Opportunitiescited by 21
  11. 2021On the Expected Complexity of Maxout Networkscited by 15
  12. 2021Automated Deep Learning: Neural Architecture Search Is Not the Endcited by 13
37 more
  1. 2022Are All Linear Regions Created Equal?cited by 13
  2. 2024SWAP-NAS: Sample-Wise Activation Patterns for Ultra-fast NAScited by 11
  3. 2022Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networkscited by 9
  4. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  5. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7
  6. 2021Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networkscited by 7
  7. 2021Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metricscited by 7
  8. 2022Piecewise Linear Neural Networks and Deep Learningcited by 7
  9. 2023Deep ReLU Networks Have Surprisingly Simple Polytopescited by 5
  10. 2024MicroNAS: Zero-Shot Neural Architecture Search for MCUscited by 5
  11. 2025L-SWAG: Layer-Sample Wise Activation with Gradients information for Zero-Shot NAS on Vision Transformerscited by 5
  12. 2024MONAS: Efficient Zero-Shot Neural Architecture Search for MCUscited by 4
  13. 2021Neural networks behave as hash encoders: An empirical studycited by 3
  14. 2022A Rigorous Study Of The Deep Taylor Decompositioncited by 3
  15. 2022Revisiting Training-free NAS Metrics: An Efficient Training-based Methodcited by 3
  16. 2025On Space Folds of ReLU Neural Networkscited by 3
  17. 2026Sparsity is Combinatorial Depth: Quantifying MoE Expressivity via Tropical Geometrycited by 3
  18. 2025Training-free Neural Architecture Search through Variance of Knowledge of Deep Network Weightscited by 2
  19. 2021Generating Attribution Maps with Disentangled Masked Backpropagationcited by 1
  20. 2022On the Feasibility and Generality of Patch-based Adversarial Attacks on Semantic Segmentation Problemscited by 1
  21. 2022On the Relationship Between Adversarial Robustness and Decision Region in Deep Neural Networkscited by 1
  22. 2023Why do CNNs excel at feature extraction? A mathematical explanationcited by 1
  23. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  24. 2024NASH: Neural Architecture and Accelerator Search for Multiplication-Reduced Hybrid Modelscited by 1
  25. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  26. 2026Geometric Capacity of Transformers: A Tropical Geometry Perspectivecited by 1
  27. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  28. 2022Enumeration of max-pooling responses with generalized permutohedracited by 0
  29. 2023Efficacy of Neural Prediction-Based Zero-Shot NAScited by 0
  30. 2024Hard Work Does Not Always Pay Off: Poisoning Attacks on Neural Architecture Searchcited by 0
  31. 2024Hyperplane Arrangements and Fixed Points in Iterated PWL Neural Networkscited by 0
  32. 2024Unlearning-based Neural Interpretationscited by 0
  33. 2025Variation Matters: from Mitigating to Embracing Zero-Shot NAS Ranking Function Variationcited by 0
  34. 2025The Space Between: On Folding, Symmetries and Samplingcited by 0
  35. 2026Zero-Shot Neural Network Evaluation with Sample-Wise Activation Patternscited by 0
  36. 2026Laguerre Geometry for Interpreting Large Language Modelscited by 0
  37. 2026Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulascited by 0