NeurIPS 2026Deep learning theorySpotlightCopenhagen U Copenhagen U Technology Nuremberg Worcester Polytechnic Institute Technion - Israel institue of Te

On the Depth of Monotone ReLU Neural Networks and ICNNs

Monotone ReLU networks cannot compute or approximate maximum, ICNNs need depth n for it, and depth-k ICNNs cannot simulate some depth-2 ReLU networks.

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

Published 2026Sydney Poster Session 1 · Tue, Dec 8, 10:00 AM–1:00 PM local time · Hall 1-4arXiv ↗OpenReview ↗

72%

OverallHighly rated

OverallHighly ratedVote to see the scoreThe exact score shows once you've voted, so every vote is your own call. The first half of each home page shelf shows its scores.

Readers

–

Only vote on papers you've read. Sign in with GitHub to vote.

AI panel8/20reviewers recommend it

lenient 1/5

medium 4/10

strict 3/5

AI panel?Vote to see what the 20 AI reviewers said

Abstract

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 MAX$_n$ computing the maximum of $n$ real numbers, we show that ReLU$^+$ networks cannot compute MAX$_n$, or even approximate it. We prove a sharp $n$ lower bound on the ICNN depth complexity of MAX$_n$. We also prove depth separations between ReLU networks and ICNNs; for every $k$, there is a depth-2 ReLU network of size $O(k^2)$ 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.