mlsanityData to 14 Oct 2026

Depth-Bounds for Neural Networks via the Braid Arrangement

arXiv 2502.09324 ↗First posted 13 Feb 2025cs.LG cs.DM cs.NEcited by 11

Not on the map. Why?

Abstract (arXiv)

We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on ℝd. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove a non-constant lower bound of Omega(loglog d) hidden layers required to exactly represent the maximum of d numbers. Additionally, under our assumption, we provide a combinatorial proof that 3 hidden layers are necessary to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 26 of its 45 references that are in the map. First posted on arXiv 13 Feb 2025.

Builds on

26 of 45 references.

References · 26

  1. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  2. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  3. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  4. 2016Benefits of depth in neural networkscited by 250
  5. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  6. 2018Tropical Geometry of Deep Neural Networkscited by 95
  7. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  8. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  9. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  10. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  11. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  12. 2019Analyzing Deep Neural Networks with Symbolic Propagation: Towards Higher Precision and Faster Verificationcited by 28
14 more
  1. 2024The Real Tropical Geometry of Neural Networkscited by 24
  2. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  3. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  4. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 21
  5. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  6. 2020Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Sizecited by 16
  7. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  8. 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 12
  9. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  10. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  11. 2024On Minimal Depth in Neural Networkscited by 11
  12. 2023Topological Expressivity of ReLU Neural Networkscited by 10
  13. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  14. 2024Neural Networks and (Virtual) Extended Formulationscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 6.

11 papers.

  1. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 12
  2. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  3. 2026Most ReLU Networks Admit Identifiable Parameterscited by 6
  4. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  5. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 3
  6. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 2
  7. 2026Representing MAX functions using two-hidden-layer ReLU networkscited by 1
  8. 2025Maxout Polytopescited by 0
  9. 2025On the expressivity of sparse maxout networkscited by 0
  10. 2026Tropical Circuits with Scalar Multiplication Gatescited by 0
  11. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0