Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes
Authors: Christian Alexander Haase
Christoph Hertrich
Georg Loho
Venue: ICLR 2023 poster (2023)
Keywords: Rectified Linear Unit
Neural Network Expressivity
Neural Network Depth
Lattice Polytope
Normalized Volume

Abstract: We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that $\lceil\log_2(n)\rceil$ hidden layers are indeed necessary to compute the maximum of $n$ numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument on the normalized volume of faces of such polytopes.

Published as a conference paper at ICLR 2023
LOWER BOUNDS ON THE DEPTH OF INTEGRAL RELU NEURAL NETWORKS VIA LATTICE POLYTOPES
Christian Haase
Freie Universität Berlin, Germany haase@math. fu-ber Sebrlia peerrinn.c iininnn..
Christoph Hertrich
London School of Economics and Political Science, UK c. c.hertrichllss ac. uk
Georg Loho
University of Twente, Netherlands g. w..hhouuueente.n.
ABSTRACT
We prove that the of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that [Iog)(n)] hidden layers are indeed neces- sary to compute the maximum of n numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton poly- topes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument the normalized volume of faces of such polytopes.
INTRODUCTION
Classical results in the area of understanding the expressivity of neural networks are so-called uni- versal approximation theorems (Cybenko 1989 Hornik 1991). They state that shallow neural net- works are already capable of approximately representing every continuous function
bounded domain. However, order to gain a complete understanding what is going on modern neural networks, would also like answer the following question: what is the precise set of functions we can compute exactly with neural networks of certain depth? For instance, insights about exact representability have recently boosted our understanding of the computational complexity train neural networks in terms of both, algorithms (Arora et al. 20188] Khalife & Basu (2022) and hardness
results (Goel et al. 2021 Froese al. 2022 Bertschinger al. (0022).
Arguably, the most prominent activation function nowadays is the rectified linear wnit (ReLU) Glo- rot et al. 2011 Goodfellow et al. 2016). While its popularity is primarily fueled by intuition and empirical success, replacing previously used smooth activation functions like sigmoids with ReLUs has some interesting implications from mathematical perspective: suddenly methods from discrete geometry studying piecewise linear functions and polytopes play crucial role in understanding neural networks (Arora et al.) 2018: Zhhng al. 2018: Hertrich et al., 2021 supplementing the traditionally dominant analytical point of view.
fundamental result in this direction is by Arora et al. (2018), who show that a function is repre- sentable by a ReLU neural network if and only if it is continuous and piecewise linear (CPWL). Moreover, their proof implies that [logy(n + 1)] many hidden layers are sufficient to represent ev- ery CPWL function with n-dimensional input. A natural follow-up question is the following: is this logarithmic number of layers actually necessary or can shallower neural networks already represent all CPWL. functions?

---

Published as a conference paper at ICLR 2023
Hertrich et al. (2021) conjecture that the former alternative is true. More precisely, if ReLU,, (k) de- notes the set of CPWL functions defined on IR" and computable with & hidden layers, the conjecture can be formulated as follows:
Conjecture Hertriih et al. (2021)) ReLU,. - 1) & (e)UU,(k) for all S [logz(n + 1)].
Note that ReLC,, (1oog2 1)1) is the entire set of CPWL functions defined on IR" by the result of Arora et al. (2018).
While Hertrich et al. 2021 provide some evidence for their conjecture, it remains open for every Even more drastically, there is not single CPWL function known for
input dimension n which one can prove that two hidden layers are not sufficient to represent it. Even for function as simple as max (0, 31, 22, v3, na),
unknown whether two hidden layers are sufficient.
In fact, max (0, 21, T2, Fy, Ta is not just an arbitrary example. Based result by Wang & Sun (2005), (Hertrich et al. (202T) show that their conjecture is equivalent to the following statement.
Conjecture 2 (Hertrich et al. (2021).. For = 2", the function max Z1...., Zn is not contained in (k)
This reformulation gives rise to interesting interpretations in terms of two elements commonly used in practical neural network architectures: max-pooling and maxout. Max-pooling units used be- tween (ReLJU or other) layers and simply output the maximum of several inputs (that is, "pool" them together). They do not contain trainable parameters themselves. In contrast, maxout networks are an alternative to (and in fact a generalization of) ReLU networks. Each neuron in a maxout network outputs the maximum of several (trainable) affine combinations of the outputs in the previous layer, in contrast to comparing single affine combination with zero as in the ReLU case.
Thus, the conjecture would imply that one needs in fact logarithmically many ReLU layers to replace max maxx-pooiigg unit or a maxout layer, being a theoretical justification that these elements are indeed more powerful than pure ReLU networks.
1.1 OUR RESULTS
In this paper we prove that the conjecture by Hertrich et al. (2021) is true for all E N under the additional assumption that weights the neural network are restricted be integral. In other words, if ReL.Ug n the set of functions defined on IR representable with hidden layers and only integer weights, we show the following.
Theorem 3. For n = 2k, the function max 20, ,I, J is not contained in (e)
Proving Theorem is main contribution. The overall strategy is highlighted in Section 1.2 We put all puzzle pieces together and provide a formal proof Section
The arguments in Hertrich et al. [22TT) can be adapted to show that the equivalence between the two conjectures is also valid in the integer case. Thus, we obtain that adding more layers to an integral neural network indeed increases the set of representable functions up to a logarithmic number of layers. A formal proof can be found in Section 4
Corollary 4. ReLU - 1) ç (k)) for all S [logz(n + 1)].
To the best of our knowledge, our result is the first non-constant (namely logarithmic) lower bound on the depth of ReLU neural networks without any restriction on the width. Without the integrality assumption, the best known lower bound remains two hidden layers Mukherjee & Basu 2017 which is already valid for the simple function max(0. 21. 22)-
While the integrality assumption is rather implausible for practical neural network applications where weights are usually tuned by gradient descent, from a perspective of analyzing the theoretical expressivity, the assumption is arguably plausible. To see this, suppose ReLU network represents Then every fractional weight must either cancel out or add up to some integers with other fractional weights, because every linear piece in the final function has only integer coefficients. Hence, it makes sense to assume that no fractional weights exist in the first place. However, unfortunately, this intuition cannot casily be turned into proof because it might happen that combinations fractional weights yield integer coefficients which could not be achieved without fractional weights.
the function max(0, .1...., ).
2

---

Published as a conference paper at ICLR 2023
1.2 OUTLINE OF THE ARGUMENT
The first ingredient of our proof is to apply previous work about connections between neural net- works and tropical geometry, initiated by Zhang et al. (2018). Every CPWL function can be decom- posed as a difference of two convex CPWL functions. Convex CPWL. functions admit a neat duality to certain polytopes, known as Newton polytopes in tropical geometry. Given any neural network, this duality makes it possible to construct a pair of Newton polytopes which uniquely determines the CPWI, function represented by the neural network. These Newton polytopes are constructed, layer by layer, from points by alternatingly taking Minkowski sums and convex hulls. The number of alternations corresponds to the depth of the neural network. Thus, analyzing the set of func- tions representable by neural networks with a certain depth is equivalent to understanding which polytopes can be constructed in this manner with a certain number of alternations (Theorem S
Having translated the problem into the world of polytopes, the second ingredient is to gain better understanding of the two operations involved in the construction of these polytopes: Minkowski sums and convex hulls. We show for each of the two operations that the result can be subdivided into polytopes of easier structure: For the Minkowski sum of two polytopes, each cell in the subdivision is an affine product of faces of the original polytopes, that is, polytope which is affinely equivalent to a Cartesian product (Proposition 2). For the convex hull of two polytopes, each cell is a join of two faces of the original polytopes. that is, convex hull of two faces whose affine hulls are skew each other, which means that they do not intersect and do not have parallel directions (Proposition IO].
Finally, with these subdivisions at hand, our third ingredient the volume of these polytopes. Thanks to our integrality assumption, all coordinates of all vertices of the relevant polytopes are integral, that is, these polytopes are lattice polytopes. For lattice polytopes, one can define the so-called normalized volume (Section 2.3). This is scaled version of the Euclidean volume with scaling factor depending on the affine hull of the polytope. is integral for all lattice polytopes. Using the previously obtained subdivisions, we show that the normalized volume of a face of dimension at least 2 of a polytope corresponding to a neural net- work with most & hidden layers has always even normalized volume (Theorem [6]. This implies that not all lattice polytopes can be constructed this way. Using again the tropical geometry inspired duality between polytopes and functions (Theorem [8, we translate this result back to the world of CPWL. functions computed by neural networks and obtain that hidden layers are not sufficient to compute max (0, Fi,.... T2t J. proving Theorem
constructed in such a way that
1.3 BEYOND INTEGRAL WEIGHTS
Given the integrality assumption, a natural thought is whether one can simply generalize our results to rational weights by multiplying all weights of the neural network with the common denomina- tor. Unfortunately this does not work. Our proof excludes that an integral ReLU network with k hidden layers can compute max 21, ..... Jz+ but it does not exclude the possibility to compute 2 max (0, ......, I2 }or with integral weights. In particular, dividing the weights of the output layer by two might result half-integral neural network computing max (0, .1...., Z224.
,
In order to tackle the conjecture in full generality, that for arbitrary weights, arguing via the parity of volumes seems not to be sufficient. The parity argument is inherently discrete and suffers from the previously described issue. Nevertheless, we are convinced that the techniques of this paper do in fact pave the way towards resolving the conjecture in full generality. constructed in Section 3 are valid for arbitrary polytopes and not only for lattice polytopes. Hence, is conceivable that one can replace the parity of normalized volumes with a different invariant which, applied to the subdivisions, yields a general depth-separation for the non-integer case.
particular, the subdivisions
1.4 FURTHER RELATIONS TO PREVIOUS WORK
Similar to our integrality assumption, also Hertrich et al. 2021) use an additional assumption and prove their conjecture in a special case for so-called H -oonforming neural networks. Let us note that the two assumptions are incomparable; there are H H-conforming networks with non-integral weights as well as integral neural networks which are not H H-cofforming.
Our results are related to (but conceptually different from) so-called trade-off results between depth and width, showing that slight decrease of depth can exponentially increase the required width to
3

---

Published as a conference paper at ICLR 2023
maintain the same (exact approximate) expressive power. Tel Telgarsky (2015 2016) proved the first
results of this type and Eldan & Shamir (2016) even proved an exponential separation between two and three layers. Lots of other improvements and related results have been established (Arora al.
2018
Daniely 2017: Hanin 2019 Hanin & Sellke| 2017; Liang & Srikant 2017 Nguyen et al,
2018
Raghu al. 2017 Safran & Shamir 2017] Safran al. 2019; Vardi et al. 2021; Yarotsky
2017
In contrast, we focus on exact representations, where we show an even more drastic trade-off:
decreasing the depth from logarithmic sublogarithmic yields that no finite width is sufficient all
any more.
The duality between CPWL functions computed by neural networks and Newton polytopes inspired by tropical geometry has been used in several other works about neural networks before (Maragos
al. et al. 2018) to count and bound the number of linear pieces (Charisopoulos & Maragos 2018
2021), for example to analyze the shape of decision boundaries (Alfarra et al. 2020; Zhang
Hertrich et al. 2021 Montúfar et 2022).
PRELIMINARIES
We write [n] = 21, nn for the of natural numbers up (without zero).
2.1 RELU NEURAL NETWORKS
For any n E N, let a: R" > R2" be the womponent-wise rectifier function
(x) (max x max(0, #2)...., max x.,)).
For any number of hidden layers & E N. (k + 1l-ley feedforward neural network with rectified linear units (ReLU neural network) is given by k + 1 affine transformations T(";; IR - R a + A + bl0), for E [k 1]. is said to compute or represent the function f: 1R + R22+1
given by
f T o T oo....
(2) TT()
The matrices (()) E R are called the weights and the vectors b(() E Th are the biases of the f-th layer. The number ny hidden layers maxte[M] ng is called the width of the neural network. Further, we say that the neural network has depth ls + 1 and size Σe= T4g.
called the width of the f-th layer. The maximum width of all
Often, neural networks represented layered, directed, acyclic graphs where each dimension of each layer (including input layer = 0 and output layer f= k + 1) is one vertex, weights are labels, and biases are node labels. The vertices of this graph are called neurons. Each neuron computes an affine transformation of the outputs of their predecessors, applies the ReLU function on top of that, and outputs the result.
2.2 POLYTOPES LATTICES
We give a brief overview of necessary notions for polytopes and lattices and refer to (Schrijver 1986
Ch. 4,7-9) for further reading. For two arbitrary sets X, Y C IR" one can define their Minkowski sum X ++Y Y {I + x E X, E YJ. By Span(X) we denote the usual linear hull of the set X, that is, the smallest linear subspace containing X. The affine hull Aff( is the smallest affine subspace containing X. Finally, with set X we associate linear space Lin(X) Span {i 2. E X), which is Aff(X) shifted to the origin. Note that Lin(X) is usually a strict subspace of Span(X), unless A Aff(X) contains the origin, in which case all three notions coincide.
For a set X C IR", its convex hull
{
conv(X) = Σ A,s [s| SCC finite, A 2 0 for all E S, >
LEE
SES
A polytope is the convex hull of a finite set V C R". Given polytope P C IR", a face of P is a set of the form arg min {c x x P] for some R"; face of polytope is again a polytope. The dimension dim(P) P) of P is the dimension of Tin(P) By convention, we also call the empty set
4

---

Published as a conference paper at ICLR 2023
Figure 1:
A regular subdivision: the quadrilateral in 2 is subdivided into six full-dimensional cells which arise as projections of lower faces of the convex hull of the lifted points in R2.
face of of dimension 1. face of dimension 0 is a vertex and a face of dimension dim(P) is facet. If all vertices belong to Q", call P rational; even more, P is lattice polytope if all its vertices are integral, that means they lie Z"
An important example of (lattice) polytope is the simplex A conv (0, c1, ......, en S R" spanned by the origin and all standard basis vectors.
Finally, we define (regular polyhedral) subdivisions of polytope. Let C R be polytope and let P RR be its image under the projection proj IR*+1 - R forgetting the last coordinate. A lower face of P is a set of minimizers with respect to a linear objective (c .1) E IR" x R. The projection of the lower faces of P to P C R" forms subdivision of P. that is, a collection of polytopes which intersect in common faces and cover An example of subdivision of polytope in the plane is given in Figure
lattice a subset of RD of the form
L | 2 Z²}
for some matrix B E RR with linearly independent columns. In this case, we call the columns ((1), ((P) B a lattice basis. Every element in L can be written uniquely as a linear combination of ((1)) ...., b(r) with integer coefficients. choice of lattice basis identifies L with Z".
The classic example of lattice is n itself. In this paper, we will only work with lattices that arise as
(ar E Z" A x x== 0}
for some A E Q that is, the intersection nn with rational subspace R...
For example, the vectors (i) (2) form basis of IR2 vector space, but they do not form lattice basis of g2, Instead, they generate the smaller lattice {ar g divides æı x22. Choosing two bases for the same lattice yields a change of bases matrix with integral entries whose inverse is also integral. It must therefore have determinant #1.
We will mainly deal with affine lattices, that is, sets of the form K = L + v where L C 12n is lattice and E R". Then, bp....,b b, E K form an affine lattice basis if 61 bo ..., b, is (linear) lattice basis of the linear lattice = K K parallel to L, that is, every element of K is unique affine combination of bo,...,b, b, with integral coefficients.
2.3 NORMALIZED VOLUME
The main tool in our proof is the normalized volume of faces of (Newton) polytopes. We measure the volume (possibly lower dimensional) rational polytope P C gn inside its affine hull Af) For this, we choose lattice basis of Lin(P) 2n inside the linear space Lin(P) parallel to Aff(P). Since P is a rational polytope, this lattice basis gives rise to a linear transform from Lin(P) onto R" (r dim P) by mapping the lattice basis vectors to the standard unit vectors. Now, the normalized volume Vol(P) of r! times the Euclidean volume of its image under this transformation. The scaling factor r! is chosen so that, for each > 1, the normalized volume of the simplex AB is one.

---

Published as a conference paper at ICLR 2023
4
P
x
2
Figure Some lattice segments and lattice polygons with their normalized volumes. Note that the normalized volume a lattice poly- tope differs from its Euclidean volume it is measured with respect to the induced lattice in its affine hull.
Figure The normalized volume of an affine product of P and Q can be calculated as the volume of the Cartesian product times the inte- gral absolute value of the determinant of the linear map sending P x Q (left) to P + Q (right): Vol(P + Q) = (111) |det [-11 212) Vol(P) Vol(Q).
2
The fact that any two lattice bases differ by integral matrix with integral inverse (and hence de- terminant 1:1) ensures that this well defined. For full-dimensional polytopes, this yields just scaled version of the Euclidean volume. But for dimenssinaii polytopes. our normalization with respect to the lattice differs from the Euclidean normalization (cf. Figure 2 For us. the cru- cial property that every lattice polytope has integral volume (see, c.g., (Beck & Robins 2007 $3.5.$5.4).. This will allow us to argue using divisibility properties of volumes.
We give visualizations of the following fundamental statements and defer the actual proofs to the appendix.
Lemma 5. Let P.Q C R be two lattice polytopes with ddi(() and dim(Q). If we have dim(P Q) dimm P) + dim(Q) then
+
Vol(P) Vol(Q) divides Vol(P +
If P and Q fulfill the assumptions of Lemma then call P affine product of P and Q- This is equivalent to the definition given in the introduction; we visualize the Cartesian product P x Q for comparison in Figure
Lemma 6. Let P.Q C. R" be two lattice polytopes with = dim(P) and j = dim(Q). If dim(conv (UQ)) = dim(p) dim(Q) then
Vol(P) Vol(Q) divides Vol(conv(PUUC)
If P and Q fulfill the assumptions of Lemma 6 then call conv U Q) the join of P and Q compare Figure This definition is equivalent with the one given in the introduction.
2.4 NEWTON POLYTOPES AND NEURAL NETWORKS
The first ingredient to prove our main result to use previously discovered duality between CPWL. functions and polytopes inspired by tropical geometry in order to translate the problem into the world of polytopes.
As first step, let observe that we may restrict ourselves neural networks without biases. For this, we say a function g: R + m is positively homogeneous if it satisfies g(xx) = >g(x) for all A 0.
Lemma (Hertrich et al. 2021). If neural network represents a positively homogeneous funccitooo then the same neural network with all bias parameters b(D) set to zero represents exactly the same function.
Since max Ti.... Zzz} is positively homogeneous, this implies that focus neural networks without biases in order to prove Theorem Functions computed by such neural networks always positively homogeneous.

---

Published as a conference paper at ICLR 2023
P
*
Figure 4: The normalized volume of join of P and Q can be calculated as the product of the normalized volumes P and Q times the integral absolute value the determinant the linear map sending Px (left) conv (PUQ) (right): Vol(conv (PUQ)) det 2
.Vol(P). Vol(Q).
where P x Q denotes an embedding of P and Q in orthogonal subspaces with distance 1.
Let f be a positively homogeneous, convex CPWL function. Convexity implies that we can write f the maximum of its linear pieces, that is, f(x) max(a] xrr x,..,, æ). The Newton polytope Py corresponding to f is defined as the convex hull of the coefficient vectors, that is, Pj convia ap). - It turns out that the two basic operations + and max (applied pointwise) on functions translate nicely to Minkowski sum and convex hull for the corresponding Newton poly- topes: Ps+g Pj- + Pg and max = conv { Py U Pg). compare Zhang et al. (2018). Since alternation of affine transformations (that is, weighted sums) and
a neural network is basically maxima computations, this motivates the following definition of classes Pa of polytopes which intu- itively correspond to integral neural networks with k hidden layers. Note that the class Ps: contains polytopes of different dimensions.
We begin with Po, the set of lattice points. For l 2 define
Pk++ {conv(Q U Q2) Q1, Q2 E Ph)
(I)
Pk+1 {Q: + Qe Q Q....., Qe Pk+1)
The correspondence of P: to a neural network with hidden layers can made formal by the following. The difference in the theorem accounts for the fact that f is not necessarily convex, and even if it is, intermediate functions computed by the neural network might be non-convex.
Theorem 8. A positively homogeneous CPWL function f can be represented by integral k- hayden-layer neural network if and only if = - for two convex, positively homogeneous CPWL functions g and h with pg. Pa. E Pk-
A proof of the same theorem for the non-intee non-integral case can be found in Hertrich (2022 Thm. 3.35). A careful inspection of the proof therein reveals that it carries over to the integral case. For the sake of completeness, we provide a proof in the appendix.
SUBDIVIDING MINKOWSKI SUMS AND CONVEX HULLS
The purpose of this section develop the main geometric tool of our proof: subdividing Minkowski sums and unions into affine products and joins, respectively. More precisely, we show the following two statements. They are valid for general polytopes and not only for lattice polytopes.
Proposition 9. For two polytopes P and Q in R", there exists a subdivision of P + Q such that each full-dimensional cell is an affine product of a face of P and a face of Q.
Proposition 10. For two polytopes P and Q in R there exists subdivision of conv (PUQ) such that each full fill-dimensional cell a join of a face of P and face of Q.
The strategy to prove these statements is to lift the polytopes P and Q by dimension to R*+1 in a generic way, perform the respective operation (Minkowski sum or convex hull) in this space, and obtain the subdivision by projecting the lower faces of the resulting polytope in Ra+1 back to R
7

---

Published as a conference paper at ICLR 2023
More precisely, given E R and B E R, we define
ood = (p. PE and Qa (19 q B) g Q
Note that the projections jr (P0) (PO) and pr (Q onto the first n coordinates result in P and Q. respectively. Moreover, we obtain subdivisions of P+Q and conv PUQ) } by projecting down the lower faces of pa Q and conv oo UQ* respectively, the first n coordinates. remains to show that the parameters can be chosen so that the subdivisions have the desired properties.
To this end, we introduce the following notation for faces of the respective polytopes. For each E I (0), let
Fo arg min {(c,, 1)x 2 po] and G arg min {(c ,1)z E Qn
well
Fe = arg min E P} and G. = arg min argmin x
Observe that F. proj n²] (P2) and G. projjn (G%..).
With this, we can finally specify what we mean by "choosing a and generically". means that the linear and affine hulls of Fe and Ge intersect little as possible.
Lemma 11. One can choose and 3 such that Lin Fg nTi G. (0) and Aff F AAT G D for every c E R2 {0).
Using the lemma about generic choices of and we have the tool prove the existence of the desired subdivisions. The actual proofs are given in the appendix.
4 USING NORMALIZED VOLUME TO PROVE DEPTH LOWER BOUNDS
In this section we complete our proof by applying parity argument on the normalized volume of cells in the subdivisions constructed in the previous section.
Let Q be the set of lattice polytopes P with the following property: for every face F of P with dim(F) (F) 2 2 we have that Vol F) even. Note that the class Qx contains polytopes of different dimensions and, in particular, all lattice polytopes of dimension smaller than 2
Our plan to prove Theorem 3 is follows. We first show that the classes Qs are closed under Minkowski addition and that taking unions of convex hulls of polytopes in Qx always gives poly- tope in Q++1. Using this, induction guarantees that Pa S Qs. We then show that adding the simplex A to polytope in Q. gives a polytope which is never contained in 2x. Combining this separation result with Ps S Q₁ and Theorem X allows us to prove Theorem 3 The general intuition behind most of the proofs in this section is to use the subdivisions constructed in the previous section and argue about the volume of each cell in subdivision separately, using the lemmas of Section 2.3
4.1 CLOSEDNESS OF Q
Proposition 12. For P,Q E Qs, we have that P Q E Qt-
The proof of Proposition 12 based on the following lemma.
Lemma 13. If = dim (P + Q) 2 2*, then Vol( P + Q) is even.
By Proposition 9 it follows that P + Q can subdivided such that each full- dimensional cell C in the subdivision is affine product of faces F and G of P and Q. re- spectively. Let i == dim(F) and j == dim(G), then d = i + j. By Lemma 3 it follows that Vol(C) = z (9) Vol(F) Vol(G) for some z E Z. We argue now that this quantity is always even. If either contained in Qx- Otherwise, d = i + 2 but i,j < 2* In this case, (9) is always even, which is a direct consequence of Lucas' theorem (Lucas) 1878). In any case, for every cell C' in the subdivision, Vol(C) is even. Therefore, also the total volume of P + Q is even.
Proof of Lemma 13
is at least 2* then Vol(F') or Vol(G)) is even, respectively, because P and Q
8

---

Published as a conference paper at ICLR 2023
Proof of Proposition 12 To prove the proposition, we need to ensure that not only P+ Q, but every face of P + Q with dimension at least 2 has even normalized volume. If F is such face, then, by basic properties of the Minkowski sum, is the Minkowski sum of two faces P' and Q' of P and Q, respectively. Since 2: is closed under taking faces, it follows that P' E Q Hence, applying Lemma 13 to P' and Q', it follows that F has even volume. Doing for all faces F with dimension at least 2n completes the proof.
Proposition 14. For P.Q. E Qk we have that conv(PUQ) E 2x+1.
Again, the heart of the proof lies in the following lemma.
Lemma 15. If d = dim(conv( U Q)) 2 2*+1, then Vol(conv(PUU Q)) is even.
We defer the proofs of Lemma 15 and Proposition 14 and to the Appendix as they are analogous to
those of Proposition 12 and Lemma 13 building on the respective claims for convex hulls (Lemma and Proposition T0 instead of Minkowski sums.
Theorem 16. For all l E N it is true that Ps C 2+.
Proof. We prove this statement by induction on k. The class Po contains only points, so no polytope
Po has a face dimension at least 2 = Therefore, it trivially follows that Po C Qo. settling
the induction start. The induction step follows by applying Proposition 12 and Proposition 14 to the definition ① of the classes Pk.
4.2 THE ODD ONE OUT
The final ingredient for Theorem is to show how Ag breaks the structure of Qs. Proposition 17. If P E Qk is polytope in R² with 2 then P + AB & Qk.
P and Q Aß. we obtain that P AB be subdivided such that each full-dimensional cell C' is an affine product of a face F of P and face G of AÑ
Proof. Applying Proposition
As in the proof of Lemma 13 follows that all these cells have even volume, with one exception: if dim F' = 0 and dim G = 2 Revisiting the proof of Proposition 9 shows that there exists exactly one such cell C' in the subdivision. This cell is translated version of AB, so it has volume Vol(C)= 1.
Since all cells the subdivision have even volume except for one cell with odd volume, we obtain that Vol P + AT) is odd. Hence, P + Ag cannot be contained in Q:-
Theorem 3. For n = 2 the function max (0, x Inn } is not contained in (k)
Proof. Suppose for the sake of contradiction that there is neural network with integer weights
and & hidden layers computing fx) = max(0, 21, J. Since the Newton polytope of f is Pj Ag. Theorem 8 yields the existence of two polytopes P, Q Pa in R" with P + A Q.
By Theorem 16 we obtain P.Q E Qt- This a contradiction to Proposition 17
From this we conclude that the set of functions representable with integral ReLU neural networks strictly increases when adding more layers.
Corollary 4. R 1) Ç. ReLU (k) for all k < [log2 (n + 1)].
Proof. Note that & < [log2 + 1)] implies 2 < Let R" R be the function f(x) max(0, F1. . -1 }. By Theorem 3 we get & RcLU - 1). In contrast, it is not difficult
to see that l 1 hidden layers with integer weights are sufficient to compute max(x1,... Iza- } compare for example Zhang et al. [
Hertrich (2022). Appending single ReLU neuron the output of this network implies f (el.UU(k)).
n

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Christian Haase has been supported by the German Science Foundation (DFG) under grant HA 4383/8-1.
Christoph Hertrich is supported by the European Research Council (ERC) under the European Union's ' Horizon 2020 research and innovation programme (grant agreement ScalcOpt-757481)
REFERENCES
Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the de- cision boundaries of deep neural networks: tropical geometry perspective. arXiv:2002.08838, 2020.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), 2018.
Matthias Beck and Sinai Robins. Computing the continuous discretely. Undergraduate Texts in Mathematics. Springer, New York, 2007. ISBN 978-0-387-29113--0 0-387-29139-3. Integer- point enumeration in polyhedra.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is 3IR-complete. arXiv:2204.01368 2022.
Vasileios Charisopoulos and Petros Maragos. A tropical approach to neural networks with piecewise linear activations. urXiv:/85.00877 2018.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 244):303-314, 1989.
Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory, pp. 690- 696. PMLR, 2017.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. Conference Learning Theory (COLT), 2016.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Re- search, 74:1775-1790 2022.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In International Conference Artificial Intelligence and Statistics (AISTATS), 2011.
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training depth-2 ReLU networks. In 12th Innovations in Theoretical Computer Science Confer- ence (ITCS), 2021.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: 7/ 7/www.co www.deeplearningboo... org
Boris Hanin. Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics, 7(10):992, 2019.
Boris Hanin and Mark Sellke, Approximating continuous functions by ReL.U nets of minimal width. 1rX1::7110.11278. 2017.
Christoph Hertrich. Facets of neural network complexity. Doctoral thesis. Technische Universität Berlin, Berlin, 2022. URL StLhhtt::// //t: doi. ooooi.org// org/ 10. 14299429/// http//ppposooeee1133333
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of ReLU neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
10

---

Published as a conference paper at ICLR 2023
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Sammy Khalife and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. In International Conference on Integer Programming and Combinatorial Optimiza- fion, pp. 347-360. Springer, 2022.
Shiyu Liang and Rayadurgam Srikant. Why deep neural networks for function approximation? In International Conference Learning Representations (ICLR), 2017.
Edouard Lucas. Théorie des fonctions numériques simplement périodiques. American Journal of Mathematics, pp. 289-321, 1878.
Petros Maragos, Vasileios Charisopoulos, and Emmanouil Theodosis. Tropical geometry and ma- chine learning. Proceedings of the IEEE, 10965):78--755, 2021.
Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6 (4):618-649, 2022.
Anirbit Mukherjee and Amitabh Basu, Lower bounds over boolean inputs for deep neural networks with ReLU gates. 1r 2017.
Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. Neural networks should be wide enough to learn disconnected decision regions. International Conference on Machine Learning (ICML), 2018
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning (ICML), 2017.
Itay Safran and Ohad Shamir. Depth-width tradeoff's in approximating natural functions with neural networks. In International Conference on Machine Learning (ICML), 2017.
Itay Safran, Ronen Eldan, and Ohad Shamir. Depth separations in neural networks: what is actually being separated? In Conference on Learning Theory, pp. 2664-2666660 2666. PMLR, 2019.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.
Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv: 2015.
Matus Telgarsky. Benefits of depth in neural networks. In Conference Learning Theeor (COLT), 2016.
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in ap- proximating benign functions with neural networks. In Conference on Learning Theory, pp- 4195 4293. PMLR, 2021.
Shuning Wang and Xusheng Sun. Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, 51(12):4425 4431, 2005.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In International Conference Machine Learning (ICML), 2018.
11

---

Published as a conference paper at ICLR 2023
A ADDITIONAL PROOFS
Lemma 5. Let P.Q C I= be two lattice polytopes with i = dim(P) and j dim(Q). If we have
dim(P' + +Q) dim(P) + dim(Q) then
+ 1
Vol(P)- Vol(Q) divides Vol(P + +Q).
Proof. The assumption dim P +Q) = dim(() dim is equivalent to Lin(P)nLin(Q) {0} so that there an affine bijection f: Aff Aff(Q) - Aff(P + Q) mapping lattice points to
lattice points. Thus, the volume of P+Q equals the volume of PxQ times the (integral) determinant of f (cf. Fig. 3
Multiplicativity of Lebesgue measures together with our normalization yields
Vol(P x Q)
Vol(P)
Vol(Q)
(i j)!
i!
Lemma 6. Let P.Q C. Rn be two lattice polytopes with dim(P) and j dim(Q). If Con(covv(PUQQ) = dim(P) dim(Q) then
Vol(P) Vol(Q) divides Vol(conv(PUQQ)
Proof. This essentially the same proof, just replace the product P x Q by the join
P*Q := conv (P {0} x {0} (0) x xx c X X" X
(CF. Fig.
Theorem 8. positively homogeneous CPWL function f can represented by an integral k-- hidden-layer neural network if and only if foror two convex, positively homogeneous CPWL functions and ht with Pg. Pr. E PA.
Proof. We use induction on k. The statement is clear for A 0 because both properties apply precisely to linear functions with integral coefficients. settling the induction start.
For the induction step, assume that the equivalence is true up to k hidden layers for some k 2 1. We show that is true for hidden layers, too.
First, focus on the forward direction, that is, suppose can be represented by an integral k-hidden- layer neural network. Using Zhang et al. 22018 Lemma 6.2), the difference (tropical quotient) of two tropical polynomials and h. Moreover, by the same lemma, Pg and Pv, arise weighted Minkowski sums of convex hulls of pairs of Newton polytopes associated with (A: - 11--1--dideenllyerr neural networks. By the induction hypothesis, these polytopes are contained in PA-1- By (1) this implies that Pg and Pa are contained Pk. where the fact that the weights of the neural network are integers ensures that the resulting polytopes are lattice polytopes. This completes the first direction.
For the converse, suppose that can be written as g - with Pg. Ph E Pk. Using Hertrich (0022 Prop. 3.34) and (I). this implies that and h can be written sums of maxima of pairs of convex CPWL functions with Newton polytopes in Px-1- By induction, these functions can be expressed with (A= ---iideenllayer neural networks. The additional maxima and operations to obtain and can be realized with a single additional hidden layer (compare Hertrich (2022) Prop. 2.2)). The fact that Px contains only lattice polytopes ensures that the resulting neural network has only integral weights. Since and h can be expressed with & hidden layers, the same holds true for f. O
Lemma 11. One can choose and 3 such that Lin F. Lin G. (0) and AfT F NAI G 0 for every c E R (0).
Proof. We will show that the set of parameters a and 3 for which these conditions are not satisfied measune-zero set.
12

---

Published as a conference paper at ICLR 2023
Let us first focus on the first statement. Suppose there is direction c E R" \ {0} such that Lin Fe n Lin G. 2 {0) is a subspace of dimension at least one. By the definitions of F. and Ge we obtain CE [LinFF) as well as + a E (Lin G.) / This implies a E (Lin
+ (Lin G.) G.)+, which is a subspace of dimension at most n - 1, and thus a measure-zero set. Hence, choosing a such that it is not contained in (Lin F n Lin G)- for all pairs of faces F and G with Lin n Lin G 2 {0} guarantees that the first condition holds.
(Lin P
For the second statement, we choose a satisfying the first statement and observe that for all e E RE \\ {0} we have Lin F. n Lin G. = {0). This implies |Afl P. n Aff Gel < 1 and hence Aff FO A GZ S 1. Suppose there is a direction c E R"A {0) for which Aff F nAff Go = follows that = y a aar + B. Hence, choosing B such that 0 az for all pairs of lower faces o'r of pd and Ga. of Qa. with Aff F n Aff Ga. = {(x, y)} guarantees that the second condition holds.
((,,)) S R" x R. By the choice of our lifting function from R" to R'+1,
Proposition 9. For two polytopes P and Q in R., there exists a subdivision of P + Q such that each full-dimensional cell is an affine product of a face of P and a face of Q.
Proof. Without loss of generality, we can assume that P+Q is full-dimensional. Choose a and according to Lemmal and consider the subdivision induced by projecting down the lower faces of po + Qa. Let be a cell of dimension face C of oo + Qa. minimizing a direction (c 1) E R" x R. follows from basic properties
the subdivision originating as a projection of a lower
of the Minkowski sum that Ö = F + G and thus C' = Fe + Ge. By Lemma 11 it follows that dim F. + dim Ge 2 dim C n. Hence, C' is an affine product of Fe and Ge.
Proposition 10. For two polytopes P and Q in R", there exists subdivision of conv (PUQ) such that each full full-dimensional cell a join of a face of P and a face of
Proof. Without loss of generality, we assume that conv PUQ) is full-dimensional. Choose and B according to Lemma I1 and consider the subdivision induced by projecting down the lower faces of conv projection of lower face Ö of po U UQa.... minimizing direction (c .1) R" R. If contains only vertices from either pe or Qa.3. then C' is a face of either P or Q and we are done. Otherwise, it follows that Ö = c J G...) and thus C conv F. U G.). By Lemma 11 it follows that dim C = dim Č dim Fo + -dim G + 1 = dim F. + dim G. + 1. Hence, C a join of F. and Ge-
Qa.3 3 Let C be cell of dimension n in the subdivision originating as
Proposition 14. For P,QE E Qs we have that (P E Q++1- Lemma 15. If (ii(coon(PUUQ)) > 2k+1, then (PU Q)) is even.
Proof of Lemma 15 By Proposition 10 it follows that c U Q} can be subdivided such that each full-dimensional cell C is a join of a face F of P and a face G of Q. Let i dim(F) and j dim (G), then d = i + +1 1. By Lemma we get that Vol(C) 2 Vol(F) Vol(G) for some 2 E Since d is at least 2 either or j be even because P and Q are contained in QR. Therefore also Vol(C) is even. Doing so for all cells in the subdivision implies that Vol(conv (P I Q)) is even.
least 2 Therefore, either Vol(F) or Vol(G) must
Proof of Proposition 14 Again, to prove the proposition, we need to ensure that not only the convex hull conv (U) has even normalized volume, but each of its faces of dimension at least 2 If F such a face, let H/ be hyperplane containing F. Observe that F' is the convex hull of all vertices of either P or Q that lie within H. In particular, F conv P' U Q'), where p and Q' are the (possibly empty) faces of P and Q defined via the hyperplane H, respectively. Since Q, is closed under taking faces, it follows that P' Q' E Qt. Hence, applying Lemma 15 P and Q' yields that F has even volume, Doing so for all faces F with dimension at least 2 completes the proof.
O
13


Reviews:
[{"review_id": "vHoDmVjFcu", "reviewer": "Reviewer_TovE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In (Arora et al. 2018), it was shown that $\\lceil \\log(n+1) \\rceil$-depth was sufficient for representing $n-dim$ CPWL functions. Is this necessary? Authors say yes, under the assumptions that weights are integral. That is, there exists functions that cannot be represented by depth less than $\\log(n+1)$, under the conditions that the weights are integral. To show this they exploit the fact that the weights are integral and the hard function is $\\text{max}[0,x_1,x_2,\\ldots,x_n]$, where $n=2^k$ and this is not expressible by a ReLU with integral weights and depth $k \\leq \\log(n)$.", "summary_of_the_review": "Overall, I think it is a good attempt at a big open question w.r.t the depth separation results, but I feel there are some questions as mentioned above, that requires some explanation and probably a bit more work.", "strength_and_weaknesses": "Strengths:\n\n It is an open problem to characterize the necessity of $\\lceil \\log(n+1) \\rceil$-depth for dimensions $n \\geq 4$ and also to get depth separations in high-dimensions, that are not constant depth, such as depth 3 vs depth 2 as shown in many works such as (Eldan and Shamir 2016, Daniely 2017, Safran et al.2019). This work tries to address this problem and gives a partial resolution and increased evidence for this. It does this by providing connections to the high-dimensional convex geometry of lattices. \n\nWeakness:\nThe main weakness is that of the integrality assumption. Now as the author points out that this is impractical in training and that perhaps new techniques are needed to deal with real-valued weights. The main issue is that the separation is argued by saying that a ReLU network of a depth smaller than this threshold does not exactly represent the hard function that is provided. However, results such as (Telgarsky, 2016) focus on L1-inapproximability by networks whose depths are $o(threshold-depth)$ and that have polynomial width. Could the authors clarify if allowed for real-valued weights, if they could still get separation on depths that are say $o(\\log(n+1))$ and show a stronger inapproximability result, rather than the exact representation of the function? Could the authors comment if ReLU(k), where $k=\\log(n)$ and allowed for real-valued weights can still provide an arbitrarily good approximation of the hard function?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "sfubfOdMsH", "reviewer": "Reviewer_U42b", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper \"Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes\" derives a theoretical result and proves that log_2(n) hidden layers are necessary to compute the maximum of n input numbers. This is achieved by building on previous theoretical work that links neural networks to tropical geometry, and uses this connection to link neural networks with integer weights to lattice polytopes. Employing subdivisions of these polytopes, Minkowski sums and convex hulls, allows to construct all polytopes corresponding to a neural network of a given depth. Further, by looking at the normalized volume, it shown that not all lattice polytopes can be constructed that way, which implies a lower-bound on the depth of neural network (log_2(n)) to calculate the maximum of n numbers - matching the previously known upper bound.", "summary_of_the_review": "The paper provides a novel theoretical insight into neural networks, and a proof construction that is well laid out. ", "strength_and_weaknesses": "Strengths.\n- the paper gives a thorough and long introduction into the preliminaries (until mid of p.7); this is great to give a more self-contained presentation of the topic.\n- the paper proposes a novel theoretical insight into neural networks\n- limitations of the study are clearly stated\n\nWeaknesses - only minor things:\n- as the authors state clearly in the paper the analysis is limited to the case of integer-valued neural networks. It is unclear how to extend the analysis to the general case, but the methods provided might be instructive towards this target.\n- p.4. in conv(X): it should probably read 'lambda_i \\geq 0 \\forall i'?\n- the structure of the paper doesn't conform to typical ICLR papers, in particular, a Conclusion section is missing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lzhzG3oGUXO", "reviewer": "Reviewer_iGLm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to provide a non-constant lower bound on the depth of ReLU neural networks without any restriction on the width. Mostly, the authors prove that the conjecture by Hertrich et al. (2021) is true for all n ∈ N with an additional assumption on the weighs of the network to be integer numbers.", "summary_of_the_review": "Although I found the general concept of finding a logarithmic lower bound for the ReLU networks interesting and of value, there are several concerns needs to be addressed before publication.", "strength_and_weaknesses": "This general topic is appropriate for the machine learning community and the manuscript’s proofs are well-written. I found the general concept of finding a logarithmic lower bound for the ReLU networks interesting and of value, since finding a lower bound for this seems to be the first and the ReLU networks are the most frequently used activation function in the world right now. While I did find this work interesting, there are several concerns to be addressed before further consideration.\n\n1-\tRegarding Theorem 3’s proof, I could not find any precise justification for the used reasoning. It will be better to propose a more systematic procedure for the proof of this theorem and give a more detailed explanation of how “The arguments in Hertrich et al. (2021) can be adapted to show that the equivalence between the two conjectures is also valid in the integer case”\n\n2-\t“Translating this result back to the world of CPWL functions computed by neural networks, we obtain that k hidden layers are not sufficent” clause used in the manuscript needs more discussion about how they assumed it. Also, it has a typo. (Sufficient)\n\n3-\tThe “FURTHER RELATED WORK” section is just naming some papers without a brief description. It would be better if for some cases the author gives a brief description in manuscript.\n\n4-\tIt would be better if the author adds the proof of Theorem 8 to the appendix, since the paper should be self completed.\n\n5-\tThe theorem 12 proof is better to be more accurate and complete.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "09jhiQ_wLIL", "reviewer": "Reviewer_dCJW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the depth requirements for exactly representing the maximum of $n$ inputs using networks with integer weights. They show that $\\lceil \\log_2 n \\rceil$ depth is necessary. Note that the simple binary tree construction that computes maximum of two inputs at a time achieves this depth. For this class of integer weight NNs this shows a depth separation result for all depths less than $\\lceil \\log_2 n \\rceil$. The lower bound sheds light on the importance of using max pooling layers to remove depth dependence.", "summary_of_the_review": "Overall, I found the problem studied in the paper and the results mathematically interesting. I think they are a nice addition to the rich literature of representation results known for neural networks despite the limitation of exact representability. Therefore, I vote to accept the paper. I encourage the authors to improve the writing.", "strength_and_weaknesses": "**Strengths**: \n- The paper takes a good step towards understanding the depth separation of exact function computation for ReLU networks. Unlike approximation results where one non-linear layer suffices for approximating functions, the question of exact representation is not so straightforward. Though the paper does not solve the question in its generality, understanding even the integer weight constraint is useful, and hopefully helpful for the general setting.\n- Showing separation for max of linear functions is insightful since it suggests that adding max-pooling layers (which are popular in practice) might be a computationally useful operation.\n\n**Weaknesses**: \n- Despite being mathematically interesting, exact representability is not the most interesting from the point of learning in-distribution. Approximate approximation suffices for that.\n- There is no mention of width of the network. As has been seen in Telgarsky 2015, width and depth do have their interesting trade-offs.\n- The overall writing of the paper is not very friendly to readers without a tropical geometry background.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster