mlsanityData to 7 Oct 2026

Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes

arXiv 2302.12553 ↗First posted 24 Feb 2023cs.LG cs.DM cs.NEcited by 36

Not on the map. Why?

Abstract (arXiv)

We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that lceillog2(n)rceil hidden layers are indeed necessary to compute the maximum of n numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument on the normalized volume of faces of such polytopes.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). Builds on 22 of its 35 references that are in the map. First posted on arXiv 24 Feb 2023.

Builds on

22 of 35 references.

References · 22

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2016On the Expressive Power of Deep Neural Networkscited by 302
  3. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  4. 2016Benefits of depth in neural networkscited by 248
  5. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  6. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 120
  7. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  8. 2018Tropical Geometry of Deep Neural Networkscited by 92
  9. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  10. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  11. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  12. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
10 more
  1. 2017Depth Separation for Neural Networkscited by 46
  2. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  3. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  4. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  5. 2018A Tropical Approach to Neural Networks with Piecewise Linear Activationscited by 26
  6. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  7. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 20
  8. 2018Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regionscited by 17
  9. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  10. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 7; 2025: 12; 2026: 13.

36 papers.

Sort:

  1. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  2. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  3. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  4. 2024On Minimal Depth in Neural Networkscited by 11
  5. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  6. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  7. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
  8. 2023Topological Expressivity of ReLU Neural Networkscited by 9
  9. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  10. 2024Neural Networks and (Virtual) Extended Formulationscited by 8
  11. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  12. 2025Constraining the outputs of ReLU neural networkscited by 3
24 more
  1. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  2. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2
  3. 2024Representing Piecewise-Linear Functions by Functions with Minimal Aritycited by 2
  4. 2025Toric geometry of ReLU neural networkscited by 2
  5. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  6. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 2
  7. 2023Neural Polytopescited by 1
  8. 2024Extracting Formulae in Many-Valued Logic from Deep Neural Networkscited by 1
  9. 2025Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2cited by 1
  10. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited 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
  13. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  14. 2024Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantizationcited by 0
  15. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  16. 2025Approximation Depth of Convex Polytopescited by 0
  17. 2025Maxout Polytopescited by 0
  18. 2025On the expressivity of sparse maxout networkscited by 0
  19. 2026Hidden Monotonicity: Explaining Deep Neural Networks via their DC Decompositioncited by 0
  20. 2026Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexitycited by 0
  21. 2026A simplex-based measure of symmetrycited by 0
  22. 2026Tropical Circuits with Scalar Multiplication Gatescited by 0
  23. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0
  24. 2026Representing MAX functions using two-hidden-layer ReLU networkscited by 0