On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth
This provides the first non-constant lower bound on depth for practically relevant ReLU networks, addressing a theoretical gap in understanding network expressiveness.
The paper tackles the problem of confirming that the expressive power of ReLU neural networks grows with depth by showing that for networks with rational weights, representing the function F_n requires at least ⌈log₃(n+1)⌉ hidden layers, and for N-ary fractions, it requires Ω(ln n / ln ln N) layers.
To confirm that the expressive power of ReLU neural networks grows with their depth, the function $F_n = \max \{0,x_1,\ldots,x_n\}$ has been considered in the literature. A conjecture by Hertrich, Basu, Di Summa, and Skutella [NeurIPS 2021] states that any ReLU network that exactly represents $F_n$ has at least $\lceil\log_2 (n+1)\rceil$ hidden layers. The conjecture has recently been confirmed for networks with integer weights by Haase, Hertrich, and Loho [ICLR 2023]. We follow up on this line of research and show that, within ReLU networks whose weights are decimal fractions, $F_n$ can only be represented by networks with at least $\lceil\log_3 (n+1)\rceil$ hidden layers. Moreover, if all weights are $N$-ary fractions, then $F_n$ can only be represented by networks with at least $Ω( \frac{\ln n}{\ln \ln N})$ layers. These results are a partial confirmation of the above conjecture for rational ReLU networks, and provide the first non-constant lower bound on the depth of practically relevant ReLU networks.