On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth

Response to Review

Dear Reviewer eki2, thank you very much for your comments. Our contribution is classified as AI theory, and in this regard we hope that it holds theoretical significance in making progress towards resolving an interesting conjecture. However, we understand that numerical computations on a computer are ultimately only approximations of the exact operations on the rationals (or the reals), and the quality of approximation is among the key concerns in practice. Let us briefly give our take on why we think that exact representability (or rather: non-representability) results like ours are interesting for practitioners. Exact formulas are often applied in numerical and approximation contexts. Following this, possibility results (providing exact representations) are complemented naturally by impossibility results, which clarify when exact representations do not exist. Both aspects are significant and commonly studied together. It makes a difference whether there is an exact representation that one aims to approximate (say a limit of a sequence of solutions of slightly perturbed problems) or not. The former obviously makes error estimation much easier, while the latter can spell trouble in numerical practice. Indeed, https://arxiv.org/pdf/2203.01016 analyses the downsides when approximating the max function with fewer than logarithmic layers, and concludes that computational complexity of such approximations will be troublesome. Next to these general arguments, there is an area of research within AI that is closely related to rational-weight NNs: In order to save space needed to store a NN and boost the calculation speed when evaluating a given input, techniques for compressing the weights of the NN, known under the name *quantization*, have been deployed in AI and are currently widely used in practice (e.g., within the PyTorch package https://pytorch.org/tutorials/recipes/quantization.html), see https://arxiv.org/pdf/2103.13630 for a survey on quantization. In the case of so-called *uniform quantization* (which is most common) weights are essentially restricted to rationals with a fixed denominator, the point being that floating point arithmetic can be replaced with much faster INT8-operations (for example). We added a short reference on quantization to the paper as additional motivation. With our contribution we help to understand the impact of depth on the expressive power of quantized networks. If you feel the above arguments address you concerns, we would be glad if you consider raising your score. Moreover, any suggestions on how to better motivate our approach in the manuscript are of course appreciated. Concerning the mentioned weaknesses: While we build on [Haase et al, 2023], we aim to make interesting and non-trivial improvements. Extending from arguments modulo 2 to modulo any prime $p$ may seem straightforward in hindsight but actually involves nuanced insights. Furthermore, we apply the theory of mixed volumes, which generalizes and systematizes a key argument. This also suggests that mixed volume theory could be instrumental in fully resolving Conjecture 1. Indeed, [Haase et al, 2023] raised several open problems, some of which could be resolved by our new techniques. For instance, the case of $2 \cdot F_n$ could not be investigated by [Haase et al, 2023], whereas we obtain a logarithmic bound for $2 \cdot F_n$, which is optimal up to a constant factor. Moreover, we can handle classes of rational numbers, for which the results of [Haase et al, 2023] were not applicable. Concerning the specific questions raised: - Theorem 1 serves as a starting point, highlighting the importance of prime factors of $N$ in our way of establishing lower bounds. Theorem 4 follows from this and its statement avoids number-theoretic specifics, instead addressing order-of-magnitude considerations in terms of $n$ and $N$. - Conjecture 1 claims that there is a gain in expressivity all the way up to $\log n$ layers, where saturation occurs. In the statement of this conjecture, it is easy to overlook its dependence on the weight domain. While the conjecture is stated over real numbers, other choices are possible, such as the field of rationals, real algebraic numbers, the ring of integers [Haase et al, 2023], or the ring of $N$-ary fractions, as used in our work. In all cases it has been shown previously that $F_n$ is one of the functions that are the hardest to represent exactly: If we can represent $F_n$, we can represent any function that is at all representable by a ReLU network. Thus one may replace $F_n$ by ``all functions representable by a ReLU network" in Theorems 2 and 4 (though we find the current formulation clearer). This impact of our results on expressiveness of neural networks is summarized in Corollary 17.

Response to the Follow-up questions

Dear Reviewer eki2, thank you for your reply. We appreciate that you take the time to further discuss your concerns with us, and we are happy to provide additional comments on your follow-up question. We agree that in practice one would not work with arbitrary $N$-ary fractions, but impose a bound on the denominator. However, we would like to stress that if, in the case of bounded denominators, a common denominator $N$ of the weights is established, then all the weights are $N$-ary fractions with one place, as $1/N$ is written as $0{.}1$ in the $N$-ary system (see lines 77-78). In our paper, $N$ is arbitrary, but neither the base $N$ nor the actual denominators $N^t$ for some $t \in \mathbb{N}$ need to grow to infinity for any of our main results to hold (so neither $N$ nor $t$ need to be large). Although Theorem 4 involves a constant $C$ that is not further specified (which makes the theorem look asymptotic in nature), it still yields meaningful bounds for small values of $N$, while a value for $C$ could be traced down through the proof of Theorem 4. Note, however, that Theorem 4 involves estimates, so Theorem 2 will give a stronger bound in general. To give a concrete example, consider a network that includes max-pooling applied to, say, a 20x20 window of an image. Suppose we want to know how many layers would be needed to express such an operation ($F_{400}$) in a classical ReLU-network with weight denominators $N = 10$ (i.e., using one-place decimal fractions) if we did not explicitly use a max-pooling layer. Clearing denominators leads to the problem of modeling $10^{k+1} F_{400}$ by an integer-weight ReLU-network with $k$ hidden layers. For this case, results of [Haase et al. (2023)] do not provide any non-trivial bound on the depth. ([Haase et al. (2023)] explicitly mention that their results on $F_{n}$ do not exclude a sub-logarithmic integer-weight representation even for $2 \cdot F_{n}$.) From Theorem 2, however, we obtain the lower bound $\left \lceil{\log_3(400)}\right \rceil = 6$ for the number of hidden layers; if Conjecture 1 was proven, we could update that number to 9. Of course, it would also be interesting to investigate representability if we restrict the *numerator* as well. Since we wanted to stay close to Conjecture 1, we did not investigate this further and think it would go beyond the scope of this article.

Response to Review

Dear Reviewer ojAS, thank you very much for your comments and your very positive assessment. Concerning the mentioned weaknesses: - We added brief definitions of the mentioned notions and added an argument why SU is closed under Minkowski addition, in the main part of the article where these concepts are introduced. The binomial formula for the mixed volumes is now proven in the appendix. - Thank you for pointing us to this very interesting reference. We do not expect that a depth-separation result similar to the one in our paper also holds for approximation, as [Safran et al., 2024] recently showed that $\max \{0,x_1,\ldots,x_n\}$ can be approximated arbitrarily well by $\text{ReLU}^{\mathbb{Z}}_n(2)$-networks of width $n(n + 1)$ https://arxiv.org/abs/2307.09212. We would have to look at bit closer at the details in both papers to see whether this result just rules out a non-approximability result for depth $\ge 4$ and small weights. In any case, we added the paper you suggested to our literature overview ([Safran et al., 2024] was already included). Concerning the specific questions raised: - We do not see a similarly intuitive complexity measure here. To provide an intuition, it might be worth looking at the case $k=1$ of just one hidden layer. This case covers the support functions of zonotopes, which are sums of finitely many segments. But, zonotopes can be decomposed into hyperparallelepipeds, all having the normalized volume divisible by $n!$. So, we know that the volume of the zonotope is divisible by $n!$. If $n$ is a prime power $p^t$, then $n!$ is divisible by $p$. So, the volume of the zonotopes is divisible by $p$, no matter how complex the zonotope is. - Our modular invariant does not directly capture the width-complexity of the underlying network, but rather it accumulates the contribution of the neurons in one single quantity (an element of $\mathbb{Z}_p$), from which the number of neurons cannot be read off directly but which still allows to carry out separation by the depth. - Allowing residual connections will not affect the result, since when we only consider expressiveness and there is no limit on the width, such connections can be simulated with classical ReLU networks.

Response to Review

Dear Reviewer oyU3, thank you very much for your comments and your very positive feedback. We fully agree with your assessment that our proof relies on the strategy of [Haase et al, 2023], while the main new ingredient is using the theory of mixed volumes for proving Proposition 11. We are happy to read that you share our hopes that this idea might inspire further results that eventually lead to the resolution of the conjecture for more general weight domains. Regarding your question, we are unsure whether we understand it correctly. If you are asking for a lower bounds on the denominator of the weights needed to represent the max function with a given (small) number $k$ of layers, such a bound can be obtained from Theorem 4, by solving for $N$. Or are you asking for a result that would say if the max function can be represented with rational weights then it can also be represented with weights using denominators $\leq$ a certain constant and the same number of layers (i.e., is there an upper bound on the denominators that we may assume without loss of generality)? This would then indeed imply a non-constant lower bound on the depth for arbitrary rational weights. This looks like an interesting line of attack for Conjecture 1, but some new ideas would have to be generated to follow this path. Our results could be seen as a step in this direction, showing that allowing larger denominators can potentially only increase expressiveness if this also increases the number of primes dividing the denominator. Does that answer your question? Regarding the minor issues, we have corrected the statement (formerly) in line 151 and rephrased the sentence in the conclusion as suggested. Thank you.

Response to Review

Dear Reviewer 1gfZ, thank you very much for your comments. We are pleased to see that you support acceptance of our work. Concerning the mentioned weaknesses: - Conjecture 1 is the strongest version among the possible variants of the conjecture for subrings or subfields of $\mathbb{R}$ as the underlying domain of weights. So, if Conjecture 1 (which is about real-valued weights) is true, the version with rational weights would be settled as a consequence. We thus see Conjecture 1 as the main conjecture. Nevertheless, the role of the domain for the weights is somewhat hidden in its formulation, and understanding the role of the domain could be a way to resolving it and its rational-weight version. We therefore have added Question 18 to the conclusions section of the paper, which essentially asks if there is any subfield of $\mathbb{R}$ for which Conjecture 1 would have a different answer. - As correctly pointed out, our proof follows the same high-level strategy as in [Haase et al, 2023]. The main new ingredient in our proof to strengthen their result is to make use of the theory of mixed volumes. This allows us to reveal that the divisor 2 used by [Haase et al, 2023] can be generalized to a prime number, which in hindsight might seem reasonable although its derivation requires to find the right tool, namely mixed volume theory. We believe that the idea to apply mixed volumes was non-trivial and could pave the way for making further progress towards resolving Conjecture 1, in particular, because we have only used a tiny part of the theory of mixed volumes. Our approach also allows to streamline some steps in the proof strategy. We therefore believe that our contribution is more than just incremental. Concerning the specific questions raised: - If $f$ is expressible by $k$ layers but not $k-1$ layers, the width necessary to represent $f$ can be arbitrarily large. Take $f = h_P$ to be the support function of a $2^k$-dimensional polytope $P \subseteq \mathbb{R}^n$ with $t$ vertices. Then $f$ admits a representation with $k$ layers. Since $P$ has $t$ vertices, the space $\mathbb{R}^n$ is decomposed into $t$ regions on which $f$ is piecewise linear. Since literature contains width bounds $b(n,k,w)$ on the number of regions of linearity that depend on the input size $n$, the depth $k$ and the width $w$, we see that when $t$ is chosen to be large enough to exceed $b(n,k,w)$, the function $f$ won't be representable with width $w$. We are currently not aware of any approaches that would use $\mathbb{Z}_p$ or mixed volumes to lower-bound the width, but it seems likely there are obstructions from discrete geometry that would help to cope with the width as well. While not within the scope of the current paper, this could be an interesting question for future research. - As the leaky ReLU activation function can be represented as the difference of two ReLU activation functions (and vice versa for a fixed slope for negative values), the expressive power of the network will not change in this case. Thus any statements on the expressive power under arbitrary width will transfer from one setting to the other. Consequently, the role of $\max \{0,x_1,\ldots,x_n\}$ will also remain the same. A similar argument can be made for activation functions with more than two linear pieces.

Response to Review

Dear Reviewer eDpF, thank you very much for your comments and your positive assessment of our work. Concerning the mentioned weaknesses: Indeed, our paper relies on [Haase et al, 2023]. However, by using the theory of mixed volumes we were able to strengthen their result. We believe that this new ingredient was non-trivial and could pave the way for making further progress towards resolving Conjecture 1. Our approach also allows to streamline some steps in the proof strategy. Concerning the specific question raised: If one fixes the domain to be a field, such as the field of rational numbers, an analogous approach would be to find a linear function that separates the vector subspace of functions representable by $k$ layers from the larger space of functions representable by $k+1$ layers. On this level of detail, the approach could be similar, since our contribution uses a homomorphism of Abelian groups, acting onto $\mathbb{Z}_p$, for the purpose of separation. We believe that such a ``separation-based'' approach, which we follow, could be helpful for both the rational and the (original) real case. Since we believe that the question raised by you is important, we elaborate more on this in our update of the conclusions section. In the rational case, combinatorial invariants like divisibility of normalized volumes might play a crucial role further on and we hope that the theory of mixed volumes (only a tiny part of which we use in our contribution) will be a useful tool. However, the specific invariant given in Proposition 11 may not be enough for proving a stronger result and one has to look deeper into the combinatorics of the corresponding polytopes.