mlsanityData to 14 Oct 2026

On the Depth of Monotone ReLU Neural Networks and ICNNs

arXiv 2505.06169 ↗First posted 9 May 2025cs.LG cs.DM cs.NEcited by 11

Not on the map. Why?

Abstract (arXiv)

We study two models of ReLU neural networks: monotone networks (ReLU^+) and input convex neural networks (ICNN). Our focus is on expressivity, mostly in terms of depth, and we prove the following lower bounds. For the maximum function MAXn computing the maximum of n real numbers, we show that ReLU^+ networks cannot compute MAXn, or even approximate it. We prove a sharp n lower bound on the ICNN depth complexity of MAXn. We also prove depth separations between ReLU networks and ICNNs; for every k, there is a depth-2 ReLU network of size O(k2) that cannot be simulated by a depth-k ICNN. The proofs are based on deep connections between neural networks and polyhedral geometry, and also use isoperimetric properties of triangulations.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 21 of its 41 references that are in the map. First posted on arXiv 9 May 2025.

Builds on

21 of 41 references.

References · 21

  1. 2016Input Convex Neural Networkscited by 414
  2. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  3. 2016Benefits of depth in neural networkscited by 250
  4. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  5. 2018Tropical Geometry of Deep Neural Networkscited by 95
  6. 2020Convex Potential Flows: Universal Probability Distributions with Optimal Transport and Convex Optimizationcited by 90
  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. 2017Depth Separation for Neural Networkscited by 46
  10. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  11. 2020Counterexample-Guided Learning of Monotonic Neural Networkscited by 34
  12. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
9 more
  1. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  2. 2020Input Convex Neural Networks for Building MPCcited by 17
  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. 2022Size and depth of monotone neural networks: interpolation and approximationcited by 10
  7. 2024Neural Networks and (Virtual) Extended Formulationscited by 9
  8. 2018Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomialscited by 6
  9. 2025Convexity in ReLU Neural Networks: beyond ICNNs?cited by 6

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. 2025Parameterized Hardness of Zonotope Containment and Neural Network Verificationcited by 5
  3. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  4. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 3
  5. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 2
  6. 2026SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functionscited by 1
  7. 2025Approximation Depth of Convex Polytopescited by 0
  8. 2025Maxout Polytopescited 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