On the Depth of Monotone ReLU Neural Networks and ICNNs
Abstract
We study two models of neural networks: monotone networks () and input convex neural networks (). 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 . For the maximum function computing the maximum of real numbers, we show that networks cannot compute , or even approximate it. We prove a sharp lower bound of on the depth complexity of . We also prove depth separations between networks and s; for every , there is a depth- network of size that cannot be simulated by a depth- . 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
ReLU Neural Networks
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
See all 136 papers