On the Depth of Monotone ReLU Neural Networks and ICNNs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908356519657472 |
|---|---|
| author | Bakaev, Egor Brunck, Florestan Hertrich, Christoph Reichman, Daniel Yehudayoff, Amir |
| author_facet | Bakaev, Egor Brunck, Florestan Hertrich, Christoph Reichman, Daniel Yehudayoff, Amir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06169 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Depth of Monotone ReLU Neural Networks and ICNNs Bakaev, Egor Brunck, Florestan Hertrich, Christoph Reichman, Daniel Yehudayoff, Amir Machine Learning Discrete Mathematics Neural and Evolutionary Computing Combinatorics 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. |
| title | On the Depth of Monotone ReLU Neural Networks and ICNNs |
| topic | Machine Learning Discrete Mathematics Neural and Evolutionary Computing Combinatorics |
| url | https://arxiv.org/abs/2505.06169 |