# On the Depth of Monotone ReLU Neural Networks and ICNNs

arXiv: https://arxiv.org/abs/2505.06169 · HTML: https://mlsanity.com/paper/2505.06169/

## 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 (most cited first, 21 of 21)

- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Convex Potential Flows: Universal Probability Distributions with Optimal Transport and Convex Optimization](https://mlsanity.com/paper/2012.05942/) (2020)
- [Optimal Control Via Neural Networks: A Convex Approach](https://mlsanity.com/paper/1805.11835/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Counterexample-Guided Learning of Monotonic Neural Networks](https://mlsanity.com/paper/2006.08852/) (2020)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Input Convex Neural Networks for Building MPC](https://mlsanity.com/paper/2011.13227/) (2020)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Size and depth of monotone neural networks: interpolation and approximation](https://mlsanity.com/paper/2207.05275/) (2022)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials](https://mlsanity.com/paper/1802.09121/) (2018)
- [Convexity in ReLU Neural Networks: beyond ICNNs?](https://mlsanity.com/paper/2501.03017/) (2025)

## Built on by (most cited first, 11 of 11)

- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)
- [Shallower ReLU Network Representations via Exact Linear Algebra](https://mlsanity.com/paper/2607.21651/) (2026)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions](https://mlsanity.com/paper/2604.22355/) (2026)
- [Approximation Depth of Convex Polytopes](https://mlsanity.com/paper/2507.07779/) (2025)
- [Maxout Polytopes](https://mlsanity.com/paper/2509.21286/) (2025)
- [A simplex-based measure of symmetry](https://mlsanity.com/paper/2607.03815/) (2026)
- [Tropical Circuits with Scalar Multiplication Gates](https://mlsanity.com/paper/2607.11540/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## 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.