mlsanityData to 7 Oct 2026

Towards Lower Bounds on the Depth of ReLU Neural Networks

arXiv 2105.14835 ↗First posted 31 May 2021cs.LG cs.DM cs.NEcited by 55

Not on the map. Why?

Abstract (arXiv)

We contribute to a better understanding of the class of functions that can be represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning any function. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). As a by-product of our investigations, we settle an old conjecture about piecewise linear functions by Wang and Sun (2005) in the affirmative. We also present upper bounds on the sizes of neural networks required to represent functions with logarithmic depth.

Key facts. Cited by 55 papers in the map (data through 7 Oct 2026). Builds on 34 of its 72 references that are in the map. First posted on arXiv 31 May 2021.

Builds on

34 of 72 references.

References · 34

  1. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  2. 2016Error bounds for approximations with deep ReLU networkscited by 567
  3. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  5. 2016On the Expressive Power of Deep Neural Networkscited by 302
  6. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  7. 2016Benefits of depth in neural networkscited by 248
  8. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  9. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  10. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 120
  11. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  12. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
22 more
  1. 2018Tropical Geometry of Deep Neural Networkscited by 92
  2. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  3. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  4. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  5. 2019Approximation spaces of deep neural networkscited by 51
  6. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  7. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  8. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  9. 2020Lossless Compression of Deep Neural Networkscited by 34
  10. 2018A Tropical Approach to Neural Networks with Piecewise Linear Activationscited by 26
  11. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  12. 2017Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Studycited by 25
  13. 2020On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspectivecited by 25
  14. 2018Complexity of Training ReLU Neural Networkcited by 23
  15. 2018Empirical Bounds on Linear Regions of Deep Rectifier Networkscited by 23
  16. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  17. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  18. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 20
  19. 2018Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regionscited by 17
  20. 2020Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Sizecited by 16
  21. 2018Principled Deep Neural Network Training through Linear Programmingcited by 13
  22. 2021A Note on the Representation Power of GHHscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 11; 2024: 10; 2025: 17; 2026: 11.

55 papers.

Sort:

  1. 2022Transformers Learn Shortcuts to Automatacited by 260
  2. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  3. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  4. 2022Improved Bounds on Neural Complexity for Representing Piecewise Linear Functionscited by 26
  5. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  6. 2024The Real Tropical Geometry of Neural Networkscited by 23
  7. 2024On the Complexity of Neural Computation in Superpositioncited by 21
  8. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  9. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  10. 2024Activation degree thresholds and expressiveness of polynomial neural networkscited by 14
  11. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  12. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
38 more
  1. 2023Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classificationcited by 11
  2. 2024On Minimal Depth in Neural Networkscited by 11
  3. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  4. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  5. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
  6. 2023Topological Expressivity of ReLU Neural Networkscited by 9
  7. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  8. 2024Neural Networks and (Virtual) Extended Formulationscited by 8
  9. 2023Representing Piecewise Linear Functions by Functions with Small Aritycited by 7
  10. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  11. 2025Convexity in ReLU Neural Networks: beyond ICNNs?cited by 6
  12. 2023Deep ReLU Networks Have Surprisingly Simple Polytopescited by 5
  13. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  14. 2023Exploring the Complexity of Deep Neural Networks through Functional Equivalencecited by 4
  15. 2025Parameterized Hardness of Zonotope Containment and Neural Network Verificationcited by 4
  16. 2022Training Thinner and Deeper Neural Networks: Jumpstart Regularizationcited by 3
  17. 2025Constraining the outputs of ReLU neural networkscited by 3
  18. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  19. 2023Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networkscited by 2
  20. 2024Complexity of Injectivity and Verification of ReLU Neural Networkscited by 2
  21. 2024Representing Piecewise-Linear Functions by Functions with Minimal Aritycited by 2
  22. 2025Toric geometry of ReLU neural networkscited by 2
  23. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  24. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 2
  25. 2023Data Topology-Dependent Upper Bounds of Neural Network Widthscited by 1
  26. 2024The Topos of Transformer Networkscited by 1
  27. 2025Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2cited by 1
  28. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 1
  29. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  30. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  31. 2026AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networkscited by 1
  32. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  33. 2022Enumeration of max-pooling responses with generalized permutohedracited by 0
  34. 2024Two-hidden-layer ReLU neural networks and finite elementscited by 0
  35. 2025Positivity sets of hinge functionscited by 0
  36. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  37. 2025Approximation Depth of Convex Polytopescited by 0
  38. 2025Maxout Polytopescited by 0

50 most cited of 55 All 55 (JSON)