cs.LGMay 9, 2025

On the Depth of Monotone ReLU Neural Networks and ICNNs

Authors: Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, Amir Yehudayoff

Abstract

We study two models of ReLU\mathsf{ReLU} neural networks: monotone networks (ReLU+\mathsf{ReLU}^+) and input convex neural networks (ICNN\mathsf{ICNN}). Our focus is on expressivity, mostly in terms of depth, and our motivation is to gain a better understanding of the depth required to exactly represent functions using neural networks with ReLU activations, a subject that has received a lot of attention lately. We prove several lower bounds on the depth required to represent functions by monotone ReLU networks and ICNN\mathsf{ICNN}. For the maximum function MAXn\mathsf{MAX}_n computing the maximum of nn real numbers, we show that ReLU+\mathsf{ReLU}^+ networks cannot compute MAXn\mathsf{MAX}_n, or even approximate it. We prove a sharp lower bound of n−1n-1 on the ICNN\mathsf{ICNN} depth complexity of MAXn\mathsf{MAX}_n. We also prove depth separations between ReLU\mathsf{ReLU} networks and ICNN\mathsf{ICNN}s; for every kk, there is a depth-22 ReLU\mathsf{ReLU} network of size O(k2)O(k^2) that cannot be simulated by a depth-kk ICNN\mathsf{ICNN}. The proofs are based on deep connections between neural networks and polyhedral geometry, and also use isoperimetric properties of triangulations.

Figures & tables

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Aug 24, 2026

Every Layer Counts: An Exponential L2L_2 Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all k≥2k\geq2, we construct a globally [0,1][0,1]-valued, 11-Lipschitz function realized by a depth-(k+1)(k+1) network of width O(d4)\mathcal{O}(d^4), whereas any depth-kk network with unrestricted weights and width at most 2d2d(k−1)\frac{2^d}{2d(k-1)} has squared L2L_2 error at least 1/241/24 under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least 33. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case k=2k=2 gives a compactly supported separation between depths 33 and 22 with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally [0,1][0,1]-valued and O(d)\mathcal{O}(\sqrt d)-Lipschitz and maps the unit hypercube onto [0,1][0,1]. It is computed by a polynomial-width depth-44 network, whereas any depth-33 network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.
Jul 22, 2026

Shallower ReLU Network Representations via Exact Linear Algebra

We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that max⁡n(x)=max⁡{x1,…,xn}\max_n(x)=\max\{x_1,\ldots,x_n\} is exactly representable with two hidden layers for every n≤12n\leq 12. Previously, this was only known up to n≤5n\leq5 [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we obtain a finite system of linear equations over Q\mathbb{Q} such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into deeper networks. This yields an exact ReLU representation of max⁡n\max_n with at most ⌈log⁡6(n/2)⌉+1\lceil \log_6(n/2) \rceil+1 hidden layers. Consequently, every continuous piecewise-linear function on Rd\mathbb{R}^d admits an exact representation with at most ⌈log⁡6((d+1)/2)⌉+1\lceil\log_6((d+1)/2)\rceil+1 hidden layers; in particular, two hidden layers suffice for d≤11d\leq 11. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.
Oct 3, 2026

A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers

Exactly computing the maximum function is a standard test case for studying depth in ReLU networks. Two hidden layers are known to suffice for up to twelve inputs through computer-assisted constructions. For six real inputs, we give an explicit hexagon identity whose local structure yields a self-contained analytical proof of this depth bound. The identity was found by computer-assisted search; we prove it through explicit cancellations that can be checked entirely by hand, without executing a verification program. The identity also yields an explicit network with hidden widths 1717 and 4141, zero biases, and rational weights.