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

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

    Aug 24, 2026Itay SafranShallow Neural NetworksReLU Neural Networks

  2. Shallower ReLU Network Representations via Exact Linear Algebra

    Jul 22, 2026Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7Shallow Neural NetworksReLU Neural Networks