mlsanityData to 14 Oct 2026

Better Neural Network Expressivity: Subdividing the Simplex

arXiv 2505.14338 ↗First posted 20 May 2025cs.LG cs.DM cs.NEcited by 12

Not on the map. Why?

Abstract (arXiv)

This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that lceil log2(n+1) rceil hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on ℝn. Hertrich, Basu, Di Summa, and Skutella (NeurIPS'21 / SIDMA'23) conjectured that this result is optimal in the sense that there are CPWL functions on ℝn, like the maximum function, that require this depth. We disprove the conjecture and show that lceillog3(n-1)rceil+1 hidden layers are sufficient to compute all CPWL functions on ℝn. A key step in the proof is that ReLU neural networks with two hidden layers can exactly represent the maximum function of five inputs. More generally, we show that lceillog3(n-2)rceil+1 hidden layers are sufficient to compute the maximum of n≥ 4 numbers. Our constructions almost match the lceillog3(n)rceil lower bound of Averkov, Hojny, and Merkert (ICLR'25) in the special case of ReLU networks with weights that are decimal fractions. The constructions have a geometric interpretation via polyhedral subdivisions of the simplex into ``easier'' polytopes.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 25 of its 47 references that are in the map. First posted on arXiv 20 May 2025.

Builds on

25 of 47 references.

References · 25

  1. 2016Input Convex Neural Networkscited by 414
  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. 2018Optimal Control Via Neural Networks: A Convex Approachcited by 85
  8. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  9. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  10. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  11. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  12. 2024More Asymmetry Yields Faster Matrix Multiplicationcited by 27
13 more
  1. 2022Improved Bounds on Neural Complexity for Representing Piecewise Linear Functionscited by 26
  2. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 21
  3. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  4. 2020Input Convex Neural Networks for Building MPCcited by 17
  5. 2017Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensorcited by 13
  6. 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
  7. 2024On Minimal Depth in Neural Networkscited by 11
  8. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  9. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  10. 2023Topological Expressivity of ReLU Neural Networkscited by 10
  11. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  12. 2024Neural Networks and (Virtual) Extended Formulationscited by 9
  13. 2018Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomialscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 8.

12 papers.

  1. 2026Most ReLU Networks Admit Identifiable Parameterscited by 6
  2. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  3. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 3
  4. 2025Toric geometry of ReLU neural networkscited by 2
  5. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 2
  6. 2026Representing MAX functions using two-hidden-layer ReLU networkscited by 1
  7. 2025Maxout Polytopescited by 0
  8. 2025On the expressivity of sparse maxout networkscited by 0
  9. 2026A simplex-based measure of symmetrycited 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
  12. 2026A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numberscited by 0