mlsanityData to 14 Oct 2026

Deep ReLU Networks Have Surprisingly Simple Polytopes

arXiv 2305.09145 ↗First posted 16 May 2023cs.LG cs.AI cs.CVcited by 5

Not on the map. Why?

Abstract (arXiv)

A ReLU network is a piecewise linear function over polytopes. Figuring out the properties of such polytopes is of fundamental importance for the research and development of neural networks. So far, either theoretical or empirical studies on polytopes only stay at the level of counting their number, which is far from a complete characterization. Here, we propose to study the shapes of polytopes via the number of faces of the polytope. Then, by computing and analyzing the histogram of faces across polytopes, we find that a ReLU network has relatively simple polytopes under both initialization and gradient descent, although these polytopes can be rather diverse and complicated by a specific design. This finding can be appreciated as a kind of generalized implicit bias, subjected to the intrinsic geometric constraint in space partition of a ReLU network. Next, we perform a combinatorial analysis to explain why adding depth does not generate a more complicated polytope by bounding the average number of faces of polytopes with the dimensionality. Our results concretely reveal what kind of simple functions a network learns and what will happen when a network goes deep. Also, by characterizing the shape of polytopes, the number of faces can be a novel leverage for other problems, textite.g., serving as a generic tool to explain the power of popular shortcut networks such as ResNet and analyzing the impact of different regularization strategies on a network's space partition.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 47 of its 59 references that are in the map. First posted on arXiv 16 May 2023.

Builds on

47 of 59 references.

References · 47

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  4. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  7. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  8. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  9. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  10. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  11. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  12. 2016Exponential expressivity in deep neural networks through transient chaoscited by 261
35 more
  1. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  2. 2019Towards Understanding the Spectral Bias of Deep Learningcited by 174
  3. 2021Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspectivecited by 169
  4. 2019Complexity of Linear Regions in Deep Networkscited by 167
  5. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  6. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 161
  7. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  8. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  9. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  10. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  11. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  12. 2015Representation Benefits of Deep Feedforward Networkscited by 86
  13. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
  14. 2019A Fine-Grained Spectral Perspective on Neural Networkscited by 68
  15. 2021Model Complexity of Deep Learning: A Surveycited by 65
  16. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  17. 2018Mad Max: Affine Spline Insights into Deep Learningcited by 55
  18. 2018Provable Robustness of ReLU networks via Maximization of Linear Regionscited by 51
  19. 2020On the Number of Linear Regions of Convolutional Neural Networkscited by 49
  20. 2020Empirical Studies on the Properties of Linear Regions in Deep Neural Networkscited by 36
  21. 2020Implicit Rank-Minimizing Autoencodercited by 35
  22. 2019Chart Auto-Encoders for Manifold Structured Datacited by 33
  23. 2022Training invariances and the low-rank phenomenon: beyond linear networkscited by 33
  24. 2018Exact and Consistent Interpretation for Piecewise Linear Neural Networks: A Closed Form Solutioncited by 32
  25. 2023SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundariescited by 31
  26. 2022Gradient Methods Provably Converge to Non-Robust Networkscited by 27
  27. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  28. 2022The Spectral Bias of Polynomial Neural Networkscited by 19
  29. 2022The Role of Linear Layers in Nonlinear Interpolating Networkscited by 16
  30. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  31. 2020Quasi-Equivalence of Width and Depth of Neural Networkscited by 7
  32. 2020Measuring Model Complexity of Neural Networks with Curve Activation Functionscited by 5
  33. 2020Hyperplane Arrangements of Trained ConvNets Are Biasedcited by 4
  34. 2021Unsupervised Representation Learning via Neural Activation Codingcited by 4
  35. 2018Nearly-tight bounds on linear regions of piecewise linear neural networkscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 1; 2026: 1.

5 papers.

  1. 2023Revisiting Long-term Time Series Forecasting: An Investigation on Linear Mappingcited by 11
  2. 2023On convex decision regions in deep network representationscited by 7
  3. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2
  4. 2025A Quotient Homology Theory of Representation in Neural Networkscited by 1
  5. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1