Towards Lower Bounds on the Depth of ReLU Neural Networks
Authors: Christoph Hertrich
Amitabh Basu
Marco Di Summa
Martin Skutella
Venue: NeurIPS 2021 Poster (2021)
Keywords: ReLU Neural Networks
Expressivity
Depth Bounds
Polyhedral Methods
Mixed-Integer Optimization

Abstract: We contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). This problem has potential impact on algorithmic and statistical aspects because of the insight it provides into the class of functions represented by neural hypothesis classes. However, to the best of our knowledge, this question has not been investigated in the neural network literature. We also present upper bounds on the sizes of neural networks required to represent functions in these neural hypothesis classes.

Towards Lower Bounds on the Depth of ReLU Neural Networks
Christoph Hertrich
Amitabh Basu Johns Hopkins University Baltimore, USA basu. amittaa@@hhaaa. edu
Technische Universität Berlin
Berlin, Germany christoph. herthierrrrcrr www.rich@osttee.oooooooooo www.ichhppes...oom
Marco Di Summa Università degli Studi di Padova Padua, Italy disumma@math. unipd. it
Martin Skutella
Technische Universität Berlin
Berlin, Germany
martin. werriiiskuttela@tu--bboe de
Abstract
We contribute to better understanding of the class of functions that represented by neural network with ReLU activations and given architecture. Using tech- niques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide mathematical counterbalance the universal approximation theorems which suggest that single hidden layer sufficient for learning tasks. In particular, investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). This problem has potential impact algorithmic and statistical aspects because of the insight provides into the class functions represented by neural hypothesis classes. However, to the best of our knowledge, this question has not been investigated in the neural network literature. We also present upper bounds on the sizes of neural networks required represent functions in these neural hypothesis classes.
1 Introduction
core problem in machine learning or statistical pattern recognition is the estimation of an unknown data distribution with access to i.i.d. samples from the distribution. It is well-known that there is a tension between how much prior information one has about the data distribution and how many samples needs solve the problem with high confidence (or equivalently, how much variance one has one's estimate). This is referred to as the variance trade-off or the bias-complexity trade-off. Neural networks provide way turn this bias/complexity knob in controlled manner that has been studied for decades going back to the idea of perceptron by Rosenblatt [1958). This is done by modifying the architecture of a neural network class of functions, which has two parameters: depth and size. As one increases these parameters, the class of functions becomes more expressive. In terms of the bias-variance trade-off, the "bias" decreases as the class of functions becomes more expressive, but the "variance" or "complexity" increases.
So-called universal approximation theorems [Cybenko] 1989 Hornik [991 Anthhny and Bartlett 1999] show that even with a single hidden layer, i.e., when the depth of the architecture is the smallest possible value, size of the network or the number of neurons used in the neural network. Nevertheless, it can be advantageous both theoretically and empirically increase the depth because substantial reduction in the size can be achieved; Telgarsky [2016a], [Elan and Shamir (2016), Arora et al. (2018) is small sample of recent work in this direction. To get better quantitative handle on these trade-ofis.
essentially reduce the "bias" much
desires, by increasing the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

it is important to understand what classes of functions are exactly representable by neural networks with certain architecture. The precise mathematical statements universal approximation theorems show that single layer networks can approximate arbitrarily well any continuous function (under some additional mild hypotheses). While this suggests that single layer networks are good enough from a learning perspective, from mathematical perspective, one can ask the question if the class of functions represented by a single layer is a strict subset the class function represented by two or more hidden layers. On the question of size, one can ask for precise bounds on the size of the network of a given depth to represent a certain class of functions. We believe that better understanding of just for
the function classes exactly represented by different architectures will have implications mathematical foundations, but also algorithmic and statistical learning aspects of neural networks. The task of searching for the "best" function in that class can only benefit from a better understanding of the nature of functions in that class. A motivating question behind the results in this paper is to understand the hierarchy of function classes exactly represented by neural networks of increasing depth.
We now introduce more precise notation and terminology to set the stage for our investigations.
Notation. We write [n] and [n30 == [n] U {0} for the same set including zero. For any n E N, let a:: R² - R" be the component-wis rectifier function
n for the of natural numbers up to (without zero)
a(z) (ma 21), max max xn,).
For any mumber of hidden layers & N. (A + 1l-layer feedforward neural network with rectified linear units (ReLU NN or simply NN) is given by l affine transformations T((;; R= + 1R A + b(t), for é E [k], and a linear transformation T(++1); R + R + ( It said to compute or represent the function f: R - _ given by
f = T o o ((k) o o (2) ooo7()
The matrices 100) E R are called the weights and the vectors ((() E TR are the biases of the f-th layer. The number ny E N is called the width of the l-th layer. The maximum width of all hidden layers maXxe(K] ny is called the width of the NN. Further, we say that the NN has depth k + and size Een
Often, NNs are represented as layered, directed, acyclic graphs where each dimension of each layer (including input layer = and output layer 8 k + 1) is one vertex, weights are are labels, and biases are node labels. Then, the vertices are called neurons.
(0) E R"o, let g T( (xx((1)) R be the activation vector and (,(() = (vy²) E Ra the outpul vector of the f-th layer. Further, let y (8+11) f(x:) be the
For given input
output of the NN. We also say that the i-th component of each of these vectors is the activation or the
output of the i-th neuron in the b-th layer.
For E N, we define
(k)U,(k) = (f: R² + IR f can be represented by a (k + 1)ylayer NN),
CPWL, = (f: R" - R f is continuous and piecewise linear).
By definition, continuous function f: R" - R is piecewise linear in case there is finite set of polyhedra whose union is IR"", and f is affine lincar over each such polyhedron.
In order to analyze ReLU,,k) we use another function class defined as follows. We call function 9 a p-term max function if it can be expressed as maximum of p affine terms, that is, g(z) = max (f)...,,,, define
{x(r)} where e; IR" + R is affinely linear for E [p]. Based on that, we
MAX, (p) = {f: R + f is a linear combination of p-term max functions).
If the input dimension is not important for the context, we sometimes drop the index and use ReLU(A) = Unex ReLU,(,) and MAX = Unex MAX,, instead.
Since we deal with polyhedra a lot in this paper, we will use the standard notations conv A and cone for the convex and conic hulls of set C R". For an in-depth treatment of polyhedra and (mixed-integer) optimization, we refer to Schrijver 1986].

---

1.1 Our Contribution
is not hard to see that any function expressed by ReLU network continuous and piecewise linear (CPWL) function, because one is composing continuous piecewise linear functions together. Based on result by [Wang and Sun [2005], Arora al. [2018] show that every CPWL function defined on IR" can be represented by a ReL.U neural network with [1ogz(1 + 1)] hidden layers. We wish understand whether one can do better. We believe it is not possible to do better and we pose the following conjecture to better understand the importance of depth in neural networks.
Conjecture 1.1. For any n E N, let k* = [log2(n (n + 1)]- Then it holds that
(cLU,,(0) & ReLU,, _ .... (eLU,, 1) & ReLU,((k) = CPWL,, (1)
Conjecture 1.1 claims that any additional layer up k" hidden layers strictly increases the set of representable functions. This would imply that the construction by [Arora et al. (2018) Theorem 2.1] is actually depth-minimal.
suffices to find a single function I ReLU,, (k*) \, ReLU,, (k. 1) with 2= for all kt N. This also implies all remaining strict inclusions ReLU,,
Observe that in order prove Conjecture 1.1.
ç ReLU,, for k- since ReLU,, - 1) = (cLU,, directly implies that (t 1) ReLU,, (i') for all 2
In fact, there is a canonical candidate for such a function, allowing us to reformulate the conjecture as follows.
Conjecture 1.2. For any k E N, n = 2*, the function fn(x) = max(0, æ1...., .n cannot be reprexented with hidden layers.
Proposition 1.3. Conjecture 1.1 and Conjecture 1.2 are equivalent.
Proof (Sketch). We argued above that Conjecture 1.2 implies Conjecture 1.I For the other direction, one can argue that, if the specific (n + T--term max function fn can be represented by hidden layers. then every other (n -ter max function well. The claim then follows via a result by [Wang] and Sun (205)) stating that any f E CPWL,, can be written as linear combination of (n + 1) 1)-term max functions. We provide detailed argument in Appendix A
It is known that Conjectre 1.2 holds for k = Muukherjee and Basu 2017]. However, the conjecture remains open for l: 2 2. In this paper, we present the following results partial progress towards resolving this conjecture.
In Section 2]
resolve Conjecture 1.2 for A 2, under natural assumption on the breakpoints of the function represented by any intermediate neuron. We achieve this result by leveraging techniques from mixed-integer programming to analyze the set of functions computable by certain NNs.
It is not hard to see that MAX(2*) S RcLU(k) for all max function (and linear combinations thereof) can be expressed with & hidden layers. One might ask whether the converse true as well, that is, whether the classes MAX(2*) and ReLU(k) are actually equal. This would not only provide neat characterization of Re).U(k)) but also prove Conjecture 1.2 without any additional assumption since one can show that max (0, Z22 is contained in (2).
[Arora et al., 2018), that is, any 2 -term
In fact, this is true for lo = 1, that is, function is computable with one hidden layer if and only if a linear combination of 2-term max funetions. However, in /Secciiion 3 we show that for k > 2, the class (cLU(() is a strict superset of MAX(2*). In this section, the key technical ingredient the theory of polyhedral complexes associated with CPWL functions. This way, provide important insights concerning the richness of the class (kL.(kk..
So far, we have focused understanding the smallest depth needed express CPWL. functions using neural networks with ReLU activations. In In[Section 4| we complement these results by upper bounds on the sizes of the networks needed for expressing arbitrary CPWL functions. particular, Theorem shows that any continuous piecewise linear function with linear/aftine pieces on IR" can be expressed by network with depth at most Ollog n.) and width at most p(n)), We arrive this result by introducing a novel application of recently established interactions between neural networks and tropical geometry.
3

---

1.2
Related Work
Depth versus size. Soon after the original universal upproximation theorems [ybbenko 1989
Hormik 1991], concrete bounds were obtained on the number of neurons needed in the hidden layer to achieve a certain level of accuracy. The literature on this is vast and we refer small
representative sample here [Barron 1993 1994 Mhaskar 1993 Pinkus 1999 Mhaskar 1996
Mhaskar and Micchelli 1995]. More recently, work has focused on how deeper networks can have exponentially or super exponentially smaller size compared to shallower networks (Telgarsky 2016
Eldan and Shamir 2016 Arora et al., 2018 Vardi et al., 2021] See also Gribonval et al. [2021] for another perspective the relationship between expressivity and architecture, and the references therein. We reiterate that the list of references above is far from complete.
Mixed-integer optimization and machine learning. Over the past decade, a growing body of work has emerged that explores the interplay between mixed-integer optimization and machine learning. On the one hand, researchers have attempted to improve mixed-integer optimization algorithms by
exploiting novel techniques from machine learning [Bonami et al. 2018 Gasse et al.) 2019 He
ct al.
2014 Khalil et al. 2016 2017 Kruber et al. 2017 Lodi and Zarpellon
[ et al.
2017 see also Bengio et al. 2020 for a recent survey, On the flip side, mixed-integee integer optimization
techniques have been used to analyze function classes represented by neural networks [Serra et al.
Anderson et al.] 2020 Fischetti and Jo 2017 SSeraa and Ramalingam 2020, Serra et al. 2020
In Sectionn 2 below, we show another new of mixed-integer optimization tools for understanding function classes represented by neural networks.
Design of training algorithms. We believe that better understanding of the function classes represented exactly by a neural architecture also has benefits in terms of understanding the complexity of the training problem. For instance, in paper by Arora al. [2018). J. understanding of single layer ReLU networks enables the design of a globally optimal algorithm for solving the empirical risk minimization (ERM) problem, that runs in polynomial time in the number of data points in fixed
dimension. See also Goel et al. 2017 2018
Goel and Klivans (019). Dey et al. [2020] Boob et al. Froese al. 202 for a similar lines of work.
2020
Goel et al. 2021
Neural Networks and Tropical Geometry. A recent stream of research involves the interplay between neural networks and tropical geometry. The piecewise linear functions computed by neural networks can be seen as (tropical quotients of) tropical polynomials. Linear regions of these functions correspond vertices of so-called Newton polytopes associated with these tropical polynomials. Applications of this correspondence include bounding the number of linear regions of a neural network
(Zhang et al., 2018 Charisopoulos los and Maragos 2018 Montúfar et al. 202T and understanding
decision boundaries [Alfarra et al. [2020] In Section 4 we present novel application of tropical concepts to understand neural networks, We refer Maragos et al. [022]] for recent survey of
connections between machine learning and tropical geometry, as well as to the textbooks by Maclagan
and Sturmfels (0055 and Joswig 2022 for in-depth introductions to tropical geometry and tropical combinatorics.
2 Conditional Lower Bounds on Depth via Mixed-Integer Programming
In this section, we provide a computer-aided proof that, under a natural, yet unproven assumption, the function fx) = max(0, (0, 21. X2, Iy, xt} cannot be represented by 3-layer NN. It is worth to note that, to the best of our knowledge, no CPWL function known for which the non-existence of 3-layer NN can be proven without additional assumption. For easier notation, we write vo == 0.
We first prove that we may restrict ourselves to NNs without biases. This holds true independent of our assumption, which we introduce afterwards.
Definition 2.1. A function g: R - R.m is called positively homogeneous g(xx) >g(x)) for all A 2 0.
Definition 2.2. For an NN given by affine transformations (() = A00xx + b(O,, we define the corresponding homogenized NN to be the NN given by ('( = A with all biases set to zero
Proposition 2.3. If an NN computes a positively homogeneous function, then the corresponding homogenized NN computes the same function.

---

Proof. Let g: R - I be the function computed by the original NN and I the one computed by the homogenized NN. Further, for any 0 < & k, let g T((-1) og or((( o...o T o o be the function computed by the sub-NN consisting of the first (e + llllyyers and let g(t) be the function computed by the corresponding homogenized sub-NN. We first show by induction on l that the norm of (lgg0 of the NN but not on æ.
g)) is bounded by global constant that only depends the parameters
For é == O, we obviously have (z) (2)) || = Co. settling the induction base. For the induction step, let 2 1 and assume that 1) - -g I Cz-1, where C2-1 only depends on the parameters of the NN. Since component-win ReLU activation has Lipschitz constant 1, this implies ([ o (
(a (x)=l s Ca-1. Using any matrix norm that is compatible with the Fuclidean vector norm, we obtain:
l19 (z) g0 (=)]l [bb(e-1) ( ((o (l (x) (a ((r-11>()))
S ||b(e-1|| + || Ct-1 CC
Since the right-hand side only depends on NN parameters, the induction is completed.
Finally, we show that g = g. For the sake of contradiction, suppose that there an x E R with [[)( - ((x)]
> Let x' == Cxt+ x; then, by positive homogeneity, it follows that
[lg(x') - g(x')ll C2 + +>> Ck. contradicting the property shown above. Thus, we have g = 9. O
Since / max (0, 2 x2, 33, va } is positively homogeneous, Proposition 2.3 implies that, if there is a 3-layer NN computing f. then there also is one that has no biases. Therefore, in the remainder of this section, we only consider NNs without biases and assume implicitly that all considered CPWL. functions are positively homogencous. In particular, any piece of such a CPWL function is linear and not only affine linear.
Observe that, for function f. the only points of non differentiability (a.k.a. breakpoints) are places where at least two of the five numbers Zo = 0, 21. 22, Iz, and Z4 are equal. Hence, if some neuron of an NN computing f introduces breakpoints other places, these breakpoints must be canceled out by other neurons. Therefore, it is a natural assumption that such breakpoints are not introduced at all in the first place.
To make this assumption formal, let Hig = {ar E TR | =;= x2), for 0 S < S 4, be ten hyperplanes 2² and H = Unsiezga Hi be the corresponding hyperplane arrangement. The regions or cells of H are defined to be the closures of the connected components of R4 H. It is easy to see that these regions are in one-to-one correspondence to the = 120 possible orderings of the five numbers To = 0, 11 I2, I3. and Z4. More precisely, for permutation of the five indices [4]o = (0, 1, 2, 3, 4). the corresponding region is the polyhedron
C = far E R (0) S Tn(1) S Tx(2) I (3) S. {
We say that (positively homogeneous) CPWL function g is H -coooform,ng, if linear within any of these regions of H, that is, if it only has breakpoints where the relative ordering of the five values Tn = 0, x1. Ø2, 33, 2A changes. Moreover, an NN is said to be H -oooffrrn if the output of each neuron contained in the NN is H H-conforming. Equivalently, this is the case if and only if all intermediate functions a T() o ((f-1) o o.... o T(1, l E [k)]. are H-conforming. Now our assumption can be formally phrased as follows.
Assumption 2.4. If there exists 3-layer NN computing f(x) max 22, 23, Lnh. then there also exists one that is H H-conforming.
We use mixed-integer programming to prove the following theorem.
Theorem 2.5. Under (nnde(AAssupption 2.4 there does not exist a 3-layer NN that computes the function f() = (0, 11, Ø2, Ø3, F.
Proof ( (Outline). We first study some geometric properties the hyperplane arrangement H. This will show that each of the 120 cells of H is simplicial polyhedral cone spanned by 4 extreme rays. In total, there are 30 such rays (because rays are used multiple times to span different cones). This implies that the set of H H-conforming functions of type IR - IR is 30-dimensional vector space and
5

---

each function is uniquely determined by its values on the 30 rays. We then use linear algebra to show that the space of functions generated by H- -oonformnng two-layer NNs is 14-dimensional subspace. Moreover, with two hidden layers, at least 29 of the 30 dimensions can be generated and f is not contained in this 29-dimensional subspace. So, remains the question whether the 14 dimensions producible with the first hidden layer can be combined in such a way that after applying ReLU activation in the second hidden layer, we do not end up within the 29-dimensional subspace. We model this question as mixed-intergen program (MIP). Solving the MIP yields that always end up within the 29-dimensional subspace, implying that f cannot be represented by a 3-layer NN. This All details can be found in Appendix B
provides a computational proof of Theorem 2.5
3 Going Beyond 2 -TeTerm Max Functions with l Layers
In this section we prove the following result:
Theorem 3.1. For any k 2 2, the class ReLU(() is strict superset of MAX(2*).
In order to prove this theorem, we provide a specific function that is (eLU(E) \ MAX(2*) for any number of hidden layers 2. The challenging part is show that the function is in fact not contained in M2X(
Proposition 3.2. For any n 2 the function
f: IR R, f(x) (0, $2, Fn-33 max max((an-2 ( In + max xx
(2)
cannot be written as a linear combination of n-term max functions.
The above proposition means that it is not possible to write far) in the form
((x)
Σ d max (nx)) (x)
where p E N, A1...., Ap E R. and lij Rd + R is an affine linear function for every E [p] and [n). (Note that max functions with less than n. terms also allowed, some functions Esj may coincide.)
Before we prove Proposition 3.2) we show that implies Theorem 3.1
Proof of Theorem 3.7 For 2 2, let n = 2* By Proposition 3.2 function f defined in (2) is not contained in MAX(2"). It remains to show that it can be represented using ReLU NN with & hidden layers. To see this, first observe that any of the n 24-1 terms max(0, }. max max(22;; #2 } for i E [n/2 2], and max(#n-2, Fn-1 + max(0, (0, .n. can be expressed by hidddddee--lyerr NN since all these are (linear combinations of) 2-term max functions. Since f is the maximum of these 26-1 terms, and since the maximum of 2 numbers can be computed with 1 hidden layers
Arora et al. 2018), this implies that f is in ReLUU(k).
In order prove Proposition 3.2 we need the concept of polyhedral complexes. A polyhedral
complex P is a finite set of polyhedra such that each face of polyhedron in P is also in P. and for two polyhedra P. Q P. their intersection P n Q is a common face P and Q (possibly the empty face). Given polyhedral complex P in R" and an integer m [n]] we let pm denote the collection of all m--iimnnsional polyhedra in P.
For convex CPWL function f. we define its underlying polyhedral complex as follows: it is the unique polyhedral complex covering R" (i.e., each point in IH" belongs to some polyhedron in P) whose n-dimensional polyhedra coincide with the domains of the (maximal) affine pieces of f. In particular, f is affinely linear within each P E P. but not within any strict superset a polyhedron in Pn..
Exploiting properties of polyhedral complexes associated with CPWL functions, we prove the following proposition in inlAppendix C
Proposition 3.3. Let fo: R" + be a convex CPWL function and let Po be the underlying polyhedral complex. If there exists hyperplane H S RR" such that the set
T T= U(F FFCH)

---

is nonempry and contains no line, then fu cannor be expressed as a linear combination of n-term maxima of affine linear functions.
This allows us to prove Proposition 3.2
Proof of Proposition 3.2 Observe that f (defined (2) has the alternate representation
f(x) = max 22, ..... In- 33, 2n-2; 2n-1, In-2 + In: 2n-1 + Zn
maximum of n + terms. Let P be its underlying polyhedral complex. Let the hyperplane H be defined by I1 = 0.
Observe that any facet in pa-1 is polyhedron defined by two of the terms that equal and at least as large as each the remaining n terms. Hence, the only facet that could possibly be contained in H is
= {x ERR
21 = 0 2 22 2n-3, 2n-2, In-1; Zn-2 + Eni In-1 + Fn
Note that F is indeed an (n- 1) dimeeniional facet in p because, for example, the full neighbor- hood of (0.-1......
E E² intersected with H is contained in F.
Finally, we need to show that is pointed, that is, contains no line. A well-known fact from polyhedral theory says if there is any line in F with direction d E R" {0), then must satisfy the defining inequalities with equality. However, only the zero vector does this. Hence, F cannot contain line.
Therefore, when applying Proposition 3.3 to f with underlying polyhedral complex P and hyper- plane H, we have T = F. which is nonempty and contains no line. Hence, cannot be written as linear combination of n n-term maxima.
Width Bound for NNs with Small Depth
While the arguments in Arora et al. 2018 show that CPWL,, = ReLU,, ([ooz + 1)7). they do not provide any bound on the width of the NN required to represent any particular continuous piecewise linear function. The purpose of this section is prove that for fixed dimension n, the required width for exact, depth-minimal representation of a CPWL function can be polynomially bounded in the number p of affine pieces; in particular ((x)), This is closely related to works that bound the number of linear pieces of NN function of the size [Montúfar al.) 2014 Pascanu et al. 2014 4, Raghu et al.] 2017 Montúfar et al. 2021]. It can also be seen as a counterpart, in the context exact representations, to quantitative universal approximation theorems that bound the number of neurons required to achieve certain approximation guarantee; see, e.g., Barron [1993 Mhaskar
1994],
1993.. Pinkus
1999). Mhaskar (1996), Mhaskar and Micchelli (1955).
4.1 The Convex Case
We first derive our result for the case of convex CPWL functions and then use this to also prove the general nonconvex case. Our width bound is consequence of the following theorem about convex CPWL functions, for which we are going to provide a geometric proof later.
Theorem 4.1. Let (xx = max (a x + b, E [p]} be a convex CPWL function defined on IR... Then can be written
fxx)
Σ
cs max((a biEiS
SCIP. 18
with coefficients es E for S S [p]. IS| 11
For the convex case, this yields a stronger version of the theorem by Wang and Sun (2005) stating that any (not necessarily convex) CPWL function can written as a linear combination (n + 1)-term maxima. Theorem 4.1 is stronger in the sense that it guarantees that all pieces of the (n + 1)-term maxima must be pieces of the original function, making possible bound the total number of these (n + 1)- term maxima and, therefore, the size of an NN representing f.
7

---

Theorem 4.2. Let f: R - R be a convex CPWL function with affine pieces. Then f can be represented by a ReLU NN with depth [log2(n 1)] and width O(p*+1).
is bounded by p*+1 the theorem follows by Theorem 4.1 and the construction from Arora et al. [0018] Theorem 2.1].
Proof. Since the number of possible subsets S _ [p] with |S| S
Before we present the proof of Theorem 4.1 nonconvex case.
show how we can generalize its consequences the
4.2 The General (Nonconvex) Case
It is well-known fact that every CPWL function can be expressed difference of two convex CPWL. functions, see, e.g., Wang| [004] Theorem 1]. This allows us to derive the general case from the convex case. What we need, however, is to bound the number of affine pieces of the two convex CPWL functions in terms of the number of pieces of the original function. Therefore, we consider a specific decomposition for which such bounds can easily be achieved.
Proposition 4.3. Let f: R" R be a CPWL function with p affine pieces. Then, f can be written as f = g - h where both and h are convex CPWL,fuctionn with most 2 pieces.
Proof. Suppose the affine pieces of f are given by x ++ a. x + bi, i E [p]. Define the function h(x) = Eisiejsp max(uç x + b;, az x + bj} and let g = f h. Then, obviously, f = - h. remains to show that both g and h are convex CPWL functions with at most p2n+1 pieces.
The convexity of h is clear by definition. Consider the
p(p-1) < p² hyperplanes given by af b; = oa bb, jijj < p. They divide R" into at most (2) + +..)) +... (6)
S p
regions (compare Edelsbrunner 1987 Theorem 1.3)) in each of which h is affine. In particular, has most 2
p a pieces.
Next, we show that g = f h is convex. Intuitively, this holds because each possible breaking hyperplane of is made convex by adding h. To make this formal, note that by the definition of convexity, suffices to show that is convex along each affine line. For this purpose, consider an arbitrary line xtt) = ta + b, E R. given by a E R" and E R. Let f(t) = f(x(t)). g() = ((x())), and i((t) = (t)))). We need to show that ÿ: R + IR is a convex function. Observe that f. g. and are clearly one me--imensional CPWL functions with the property = f h. Hence, it suffices to show that ý is convex locally around each of breakpoints. Let & E R an arbitrary breakpoint of g. If f already convex locally around f. then the same holds for ğ as well since h inherits convexity from h. Now suppose that a nonconvex breakpoint of f. Then there exist two distinct pieces of f. indexed by i. j E [p] with + j. such that f(t') min min(a? (t')) + b, az x(t)) sufficiently close to By construction, h(t') contains the summand max(a; (t')) + +b, a x(t'')) +by}. Thus, adding this summand to linearizes the nonconvex breakpoint of f, while adding all the other summands preserves convexity. In total, ğ is convex locally around I, which finishes the proof that g a convex function.
) by} for all t'
Finally, observe that pieces of g f + h are always intersections of pieces of f and h, for which we have only p pmn 21+ possibilities.
Having this, may conclude the following.
Theorem 4.4. Let f: R² + R be a CPnnfinctiin with p affine pieces. Then can be represented by a ReLU NN with depth [log (n + 1)1 + and width Og +3n+1). +(=+1)+3++1)
Proof. Consider the decomposition = g from Proposition 4.3 Using Theorem 4.2, obtain that both g and h can be represented with the required depth [loga (n + 1)] + 1 and with width (1 Op2"n +3n+1). (32211) Thus, the same holds for f.

---

4.3 Extended Newton Polyhedra of Convex CPWL Functions
For our proof of Theorem 4.1 we use correspondence of convex CPWL functions with certain polyhedra, which are known as (extended) Newton polyhedra in tropical geometry [Maclagan and Sturmfels 2013]. These relations between tropical geometry and neural networks have previously been applied to investigate expressivity of NNs; compare our references in the introduction.
In order formalize this correspondence, let CCPWT.,, C CPWT., be the set of convex CPWL. functions of type Iº' + IR. For f(x) = max(a? + 6; i E [p]} in CCPWL2, we define its so-called extended Newton polyhedron be
N(f) == conv([(a,, b,) E ER x R ie pI)) + cone(1-ent11) CR**!
We denote the set of all possible extended Newton polyhedra in R=+1 as Newt,, That is, Newt,, is the set of (unbounded) polyhedra in IR n+1 that emerge from a polytope by adding the negative of
the (n + 1) -stt unit vector -cn+1 an extreme ray. Hence, set P C R=+ is an element of Newt,,
and only if can be written as = conv( bi) R x i E [p]}) + cone({ }).
Conversely, for polyhedron P E Newt,, of this form, let F(P) E CCPWL, be the function defined by (x) = max x + b, E [p]].
There is an intuitive way of thinking about the extended Newton polyhedron P of a convex CPWL function f: it consists of all hyperplane coefficients (a, b) E R" x R such that a x + S f(x) for all æ E R". This also explains why we add the extreme ray - decreasing b obviously maintains the property of a x + being a lower bound on the function f.
We need the notion of the Minkowski sum of two polyhedra and Q: it is given as the set P P+G Q {p (p+9 p P, q Q). In fact, there a one-to-one correspondence between elements of CCPWL,, Wn and Newt,, which is nicely compatible with some (functional and polyhedral) operations. This correspondence has been studied before in tropical geometry MMaclagan and Sturmfels 2015 Joswig 2022] convex [ geometry [Hiriart-Urii Urruty and Lemaréchal 1993]. well as neural network literature [hang et al.
2018, Charisopoulos and Maragos] 2018 Alfarra et al. 2020 Montúfar et al. 2021]. We summarize
the key findings of this correspondence relevant to work in the following proposition:
Proposition 4.5. Let N and f1, f2 CCPWL,,. Then it holds that
(i) the functions N CCPWL, + Newt, and F: Newt, + CCPWL, are well-defindd that is, their output is independent from the representation of the input by pieces or vertices, respectively,
(ii) N and F are bijections and inverse to each other.
(iii) (mmax (1,, conv(NV(i), = (onv(N((i) (N2(
(iv) N(1 + f2) = W({) + N(22), where the + on the right-hand side is Minkowski addition.
An algebraic way of phrasing this proposition is follows: N and F are isomorphisms between the semirings (CCPWL,, max, +) and (Newtn, conv, +).
4.4 Outline of the Proof of Theorem 4.1
We prove Theorem 4.1 in full detail in Appendix D The rough idea is as follows.
Suppose we have a p-term max function with p 2 n + 2. By Proposition 4.5) f corresponds to polyhedron P E Newt, with at least n + 2 vertices. Applying a classical result from discrete geometry known Radon's 's theorem allows us carefully decompose
into a "signed" " Minkowski sum of polyhedra in Newt,, whose vertices are subsets of at most p - out of the vertices of P. Translating this back into the world of CPWL functions by [Proposition 4.3] yields that f can be written as linear combination of p p'-term maxima with p' < where each of them involves a subset of
W(() is the negative of the epigraph of the convex conjugate of "Some polyhedra may occur with "negative" coefficents in that sum, meaning that they are actually added to P instead of the other polyhedra. The corresponding CPWL functions will then have negative coefficients in the linear combination representing f.

---

the p affine terms of f. We can then obtain Theorem 4.1 by iterating until every occurring maximum expression involves most n terms.
4.5 Potential Approaches to Show Lower Bounds on the Width
In light of the upper width bounds shown in this section, natural question to ask is whether also meaningful lower bounds can be achieved. This would mean constructing family of CPWL functions with p pieces defined on I" (with different values of p and r2), for which we can prove that large width required to represent these functions with NNs of depth [log2 (n + 1)7+11
trivial and not very satisfying answer follows, c.g., from Raghu et al. [2017] or SSerra et al. (0188) for fixed input dimension n, they show that function computed by an NN with & hidden layers and width w has at most O () pieces. For our setting, this means that an NN with logarithmic depth
needs a width of at least (p ((pp/(nlogw)) (mllog)) to represent a function with p pieces. This is, of course, very far away from our upper bounds.
Similar upper bounds on the number of pieces have been proven by many other authors and are often used to show depth-width tradeoffs [Montúfar et al. 2014 2021 Pascanu et al., 2014| Telgarsky 2016b Arora et al., 2018). However, there is a good reason why all these results only give rise to very trivial lower bounds for our setting: the focus is always functions with very many pieces, which then, consequently, need many neurons to be represented (with small depth). However, since the lower bounds strive for depend on the number of pieces, we would need to construct a family of functions with comparably few pieces that still need very many neurons to be represented. In general, it seems to be tough task argue why such functions should exist.
different approach could leverage methods from complexity theory, particular from circuit complexity. Neural networks are basically arithmetic circuits with very special operations allowed. In fact, they can be seen as a tropical variant of arithmetic circuits. Showing circuit lower bounds is a notoriously difficult task in complexity theory, but maybe some conditional result (based on common conjectures similar to P # NP) could be established.
We think that the question whether our bounds are tight, or whether at least some non-trivial lower bounds on the width for NNs with logarithmic depth can be shown, an exciting question for further research.
Discussion of Future Research Directions
The most obvious and, at the same time, most exciting open research question is to prove disprove Conjecture I.I] or equivalently [onjecture 1.2 The first step could be to prove Assumption 2.4] The assumption is intuitive because every breakpoint introduced at other places needs be canceled out later. Therefore, it is natural to assume that these breakpoints do not have to be introduced in the first place. However, this intuition does not seem to be enough for formal proof because could occur that additional breakpoints in intermediate steps, which are canceled out later, also influence the behavior of the function at other places where we allow breakpoints in the end.
Another step towards resolving our conjecture may be to find an alternative proof of Theorem 2.5 not using Assumpissnpoion 2.4 This might also be beneficial for generalizing techniques to more hidden layers, since, while theoretically possible, a direct generalization is infeasible due to computational limitations.
In light of our results from Section 3. it would be desirable to provide a complete characterization of the functions contained in RA). Another potential research goal is improving upper bounds on the width from Section 4 andd/o proving matching lower bounds as discussed in /Section 4.5
Some more interesting research directions are the following: 1. Establishing or strengthening our results for special classes of NNs like recurrent neural networks (RNNs) or convolutional neural networks (CNNs), 2. Using exact representation results to show more drastic depth-width tradeoffs compared to existing results in the literature, Understanding how the class (eI.U(k) changes when polynomial upper bound is imposed the width of the NN; see related work by Vardi et al. [2021]
10

---

Acknowledgments and Disclosure of Funding
Christoph Hertrich gratefully acknowledges funding by DFG-GRK 2434 "Facets of Complexity". Amitabh Basu gratefully acknowledges support from AFOSR Grant FA95502010344 and NSF Grant CCF2006587. Martin Skutella gratefully acknowledges funding by the Deutsche Forschungsgemeinn schaft (DFG, German Research Foundation) under Germany's Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).
References
M. Alfarra, A. Bibi, H. Hammoud, M. Gaafar, and B. Ghanem. On the decision boundaries of deep neural networks: A tropical geometry perspective. arXiv preprini urXiv:2002.08838 2020.
A. M. Alvarez, Q. Louveaux, and L. Wehenkel. A machine learning-bast based approximation of strong branching. INFORMS Journal Computing, 19 2017.
R. Anderson, Huchette, Ma, C. Tjandraatmadja, and J. P. Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming, pages 1-37, 2020.
M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018.
R. Bagnara, P. M. Hill, and E. Zaffanella. The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Science of Computer Programming. 72(1-2):3-22 2008.
A. R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Trunsactions on Information theory, 39(3):330-94, 1993.
A. R. Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14-1):15--133, 1994.
Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: method- ological tour d' l'horizon. European Journal of Operational Research, 2020.
P. Bonami, A. Lodi, and G. Zarpellon. Learning classification of mixed-integer quadratic pro- gramming problems. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 595-604. Springer, 595-ne..Springer, 2018.
D. Boob, S. Dey, and G. Lan. Complexity of training relu neural network. Discrete Optimization, page 100620, 2020.
V. Charisopoulos and P. Maragos. tropical approach to neural networks with piecewise linear activations. arXiv preprint arXiv: 1805.08999 2018.
G. Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
S. Dey, G. Wang, and Y. Xie. Approximation algorithms for training one-node relu neural networks. IEEE Transactions on Signal Processing, 68:6696-6706, 2020.
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Science & Business Media, 1987.
R. Eldan and O. Shamir. The power of depth for feedforward neural networks. 29th Annual Conference Learning Theory, pages 907-940, 2016.
M. Fischetti and J. Jo. Deep neural networks as 0-1 mixed integer linear programs: feasibility study. arXiv preprint
2017. 2017.

---

V. Froese, C. Hertrich, and R. Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. arXiv preprint (XXi::2155006675 2021.
M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks, arXiv preprint arXiv: 01669, 2019.
S. Goel and A. R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, pages 1470-1499, PMLR, 2019.
S. Goel, V. Kanade, A. Klivans, and Thaler. Reliably learning the relu in polynomial time. In Conference Learning Theory, pages 1004-1042. PMLR, 2017.
Goel, A. Klivans, and R. Meka. Learning one convolutional layer with overlapping patches. In International Conference Machine Learning, pages 1793-1791. PMLR, 2018.
Goel, A. R. Klivans, P. Manurangsi, and Reichman. Tight hardness results for training depth-2 ReLU networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS '21), volume 185 of LIPIcs, pages 22:1-22:14 Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021.
R. Gribonval, G. Kutyniok, Nielsen, and Voigtlaender. Approximation spaces of deep neural networks. Constructive Approximation, pages 1-109, 2021.
Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2021. URL http::/www.ggrrt/ com
H. He, H. Daume III, and J. M. Eisner. Learning search in branch and bound algorithms. Advances in neural information processing systems, 27:3293- -3301, 2014.
J.-B. Striart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms II, volume 306 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag Berlin, 1993. ISBN 3-540-56852-2.
K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
M. Joswig. Essentials of tropical combinatorics. Graduate Studies Mathematics. American Mathe- matical Society, Providence, RI, 2022. URL httLhtttt///aaa hwtp::///.aaemaaa.....aamm math. ww--eruin.dccc iun-berlin.dd//jjovie etc/index. html
To appear.
E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
E. B. Khalil, B. Dilkina, G. L. Nemhauser, S. Ahmed, and Y. Shao. Learning to run heuristics in tree search. In IJCAI, pages 659-666, 2017.
M. Kruber, M. E. Lübbecke, and A. Parmentier. Learning when to use a decomposition. In International Conference on Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 202-210. Springer, 2017.
A. Lodi and G. Zarpellon. On learning and branching: a survey. Top, 25(2):207-236, 2017.
D. Maclagan and B. Sturmfels. Introduction to tropical geometry, volume 161 of Graduate Studies in Mathematics. American Mathematical Soc., 2015.
Maragos, Charisopoulos, and E. Theodosis. Tropical geometry and machine learning. Proceed- ings of the IEEE, 109(5):72--755 2021.
H. Mhaskar. Approximation of real functions using neural networks. Proc. Intl. Conf. Comp. Math., New Delhi, India, World Scientific Press, pages 267-278. World Scientific, 1993.
H. N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural computation, 8(1):164-177, 1996.
12

---

H. N. Mhaskar and C. A. Micchelli. Degree of approximation by neural and translation networks with a single hidden layer. Advances in applied mathematics, 16(2):151-183, 1995.
G. Montúfar, Y. Ren, and Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. arXiv preprint arXiv:2 35, 2021.
G. F. Montúfar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, e Advances in Neural Information Processing Systems 27, pages 2924 2932. 2014.
A. Mukherjee and Basu. Lower bounds over boolean inputs for deep neural networks with relu gates. arXiv preprint 1rXiv:1711.000
2017.
R. Pascanu, G. Montúfar, and Y. Bengio. On the number of inference regions of deep feed forward net- works with piece-wiig wise linear activations. In International Conference on Learning Representations, 2014.
A. Pinkus. Approximation theory of the mlp model. Acta Numerica 1999: Volume 8, 8:143-195. 1999.
M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, and S. Dickstein. On the expressive power of deep neural networks. In International Conference Machine Learning, pages 2847-2854, 2017.
Rosenblatt. The perceptron: probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.
T. Serra and S. Ramalingam. Empirical bounds on linear regions of deep rectifier networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5628-5635, 2020.
T. Serra, C. Tjandraatmadja, and S. Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pages 4558 48666.66...6 PMLR, 2018.
T. Serra, A. Kumar, and S. Ramalingam. Lossless compression of deep neural networks. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 417-430. Springer, 2020.
M. Telgarsky. benefits of depth in neural networks. In 29th Annual Conference on Learning Theory, pages 1517-1539, 2016a.
M. Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory, pages 2016b
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.0), 2020. https://vvee stttp::/www.ssggmmahh org.
G. Vardi, D. Reichman, T. Pitassi, and O. Shamir. Size and depth separation in approximating benign functions with neural networks. arXiv:2102.00314, 2021.
S. Wang. General constructive representations for continuous piecewise-linear functions. IEEE Transactions Circuits and Systems I: Regular Papers, 51(9): (990):888919990 889-1896, 2004.
S. Wang and X. Sun. Generalization of hinging hyperplanes. IEEE Transactions Information Theory, 5 (1(1)):44254444 4431, 2005.
L. Zhang, G. Naitzat, and L.-H. Lim. Tropical geometry of deep neural networks, In International Conference Machine Learning, pages 5819-5827, 2018.
13


Reviews:
[{"review_id": "vsU9XC1SBFL", "reviewer": "Reviewer_gadk", "summary": "The authors study the class of functions that can be represented by a fully connected neural network with ReLU activations. First, They conjectured that for any $k\\in\\mathbb{N}$, $n=2^k$, the function $f_n(x)=\\max\\{0,x_1,\\dots,x_n\\}$ cannot be represented by a fully connected network with $k$ hidden layers, and prove this conjecture for $k=2$ under some mild assumption. Second, they proved the class of functions that can be represented by a $(k + 1)$-layer NN is strictly larger than the class of functions that are linear combinations of $2^k$-term max functions. Finally, they provided a bound on the width of the NN required to represent continuous piecewise linear functions. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The related works are adequately cited. The novelty of this paper is high. The three main results in this paper, as mentioned in the above summary part,  will certainly help us have a better understating of deep neural networks from a theoretical way. I have checked the technique parts and find that the proofs are solid. I think this is a significant contribution to deep learning immunity. My only concern is that, the proof of Conjecture 1.2 for $k=2$ case, relies on Assumption 2.4, which is not quite elegant. It will be interesting to prove Conjecture 1.2 for $k=2$ case without any further assumptions.\n\nQuality: This paper is technically sound.\n\nClarity: This paper is clearly written and well organized. I find it easy to follow.\n\nSignificance: I think the results in this paper is significant, as explained above.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "nt_vgvy_CNv", "reviewer": "Reviewer_oew5", "summary": "It is known from the universal approximation theorem that ReLU networks with one hidden layer can approximate any continuous function on compact sets arbitrarily well. Instead of approximations, this paper investigates  the set of functions that can precisely be described by a network of certain depth. For a given input dimension D, a ReLU network with L=ceil[ log2(D+1) ] (or more) hidden layers (and arbitrary width) can describe the entire set of piecewise continuous functions. Here, new insight is provided for networks with having between 1 and L layers. In particular, under an unproven assumption, the paper shows that L is a strict lower limit for the depth and that adding layers to a network strictly increases the set of describable functions. This is achieved by studying a natural candidate function to require a larger number of hidden layers. The candidate function suggests a conjecture on a nice description of ReLU network functions of finite depth, which is shown to not hold true. Finally, the paper derives a bound on the width and depth of networks that can describe any piecewise linear function with fixed number of linear pieces.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is very well-written and the arguments are carefully put together. All proofs are described in detail.  This theoretical paper is mostly interesting from a mathematical viewpoint. With universal approximation at hand, one could argue that a better understanding of the precise description of the set of ReLU functions does not add much from a practical point of view. However, as the authors point out, a better understanding could also be useful for algorithmic advances. \n\nI found the story of the paper intriguing. The conjecture on the lower limit in depth that is necessary to describe all continuous piecewise linear functions on a D-dimensional input space is reduced to proving that the candidate function max{0,x1,x2,,..,xD} cannot be described with less than ceil[ log2(D+1) ] many hidden layers. This statement seems at first like a fairly easy statement to prove or disprove, but appears to be actually quite difficult. Starting from the candidate function, there is natural hope to conjecture that a ReLU network with L hidden layers can only describe linear combinations of maxima of 2^L terms and no more, but this is shown to be false, which adds to the story that the description of ReLU network functions of a certain depth is complicated. \n\nAs a result, the paper does not present a complete story by fully characterizing the functions implemented by ReLU networks of fixed depth. \n\nThe following describes the progress made in more detail and discusses its limitations:\n\n(i) The conjecture on the tightness of the known lower bound on necessary depth to describe all piecewise linear functions on a D-dimensional input space holds true for networks with two hidden layers, but only under an unproven assumption. That is, the result is limited to three-layer networks and is even incomplete in that case.\n\n(ii) There are maxima of D+1 terms that can be described by a network of depth less than L=ceil[ log2(D+1) ]. This result is interesting, but oneit also disproves a conjecture that was first mentioned in this same paper and which did not previously appear important.\n\n(iii) A bound on the order of depth and width necessary to exactly describe any continuous piecewise linear function with p linear pieces, saying that the required width is polynomial in p with exponent defined by the input dimension. This is a only a small improvement to previously known results.\n\nThe main weakness of the paper is that it misses to describe the complications that need to be overcome to extend these limited results. For example, what are the problems to prove the necessary (unproven) assumption for the result in (i)? If it is a natural assumption that should be believed to (probably) hold true for ReLU networks, then why is difficult to show that it does indeed hold? A discussion of the difficulty to prove this critical assumption would make it easier to appreciate the partial result. Similarly, what are the problems of extending the proof to layers with more than two hidden layers?\n\nA strength of the paper is that the proofs of the partial results use nontrivial methods and require a good understanding on the geometrical setting of linear regions. The proof of statement (i) from above is based on mixed integer programming (MIP) with a nontrivial setup of the MIP problem. This part of the paper also introduces so-called H-conforming functions, which form a natural subset of piecewise continuous functions for the study of ReLU networks and this viewpoint could be interesting outside the study in question. The proofs to (ii) and (iii) use theoretical insight on piecewise continuous functions and their associated polyhedra of linear pieces. These proof ideas and techniques provide some insight on their own. \n\nTaken together, the paper presents an intriguing, theoretically interesting question, but only resolves it partially without explaining well why the partial progress is substantial. Since the ideas involved in setting up the statements and proofs are quite interesting by themselves, I tend to support the acceptance of the paper.\n\n\n*****\n Two small suggestions for potential minor improvement in the presentation:\n\n- Line 66: Better: \"By definition, a continuous function is piecewise linear in case ...“ \n- Line 96: The sketch of the proof only states half the arguments necessary for the proof. It would just cost a single line or maybe two to state the other half: If the specific n+1 term maximum function can be written with k layers, then all n+1-term maximum functions can.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is carefully put together and describes the assumptions of all statements clearly.  As argues in the main part of the review, the paper would benefit from describing the limitations of the used tools to extend the result and to go beyond the partial results reported in the study.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "VOqDTwmRQNE", "reviewer": "Reviewer_zAhu", "summary": "This paper studies the role of depth in exactly representing real functions by ReLU networks. \nUnlike the common ML setting, the focus is on neural nets that are equal in every point to the target function. \nSome partial results are given as well as a conjecture that networks of depth k+1 have strictly more expressivity than networks of depth k.  ", "questions": "", "limitations": "", "rating": 7, "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": "Pros: \nIt is an interesting question to study expressivity in the interpolation setting where pointwise equality is required. The main conjecture (that depth k+1 is strictly larger than depth k) is of interest and the partial results serve as a good intro to the kind of polyhedral theory that is likely to be involved in these problems. The paper is generally well written and conveys the questions well (although some improvements are possible: see below). I agree with the authors that  finding connections between well develop fields such as polyhedral combinatorics and integer programing to neural networks could yield interesting insights. \n\nCons: \nThe requirement for equality in all points is very strong and less useful in machine learning. One issue is that it is easy to come up with simple functions that cannot be represented in this model by a finite network. In general, it is easy to obtain strong lower bounds by considering functions with a very large number of linear regions and using the ideas of Montufar et al (2014). See also\n\"Size and Depth Separation in Approximating Benign Functions with Neural Networks\" by Vardi et al (2021). Therefore lower bounds in this model may be less informative with respect to the power or limitations of neural networks. \nIt would be good if the authors could further justify their representational assumption from a machine learning perspective. Perhaps it is related to memorization and interpolation in neural networks. \n\nThe authors do not impose any bounds on the width or size of the networks. It might be of interest to consider what happens if one restricts the size of the ReLU networks to be polynomial: arguably networks used in practice have strong limitation on their size. It could be that such a restriction makes the questions raised in this paper more difficult: see Vardi et al. \n\nWith respect to the width bound in section 4 it would be nice to have also some kind of a lower bound, or at least an estimate of what the right answer should be. \n\nI've found the first two paragraphs not very informative reiterating common knowledge that does not seem to be very related to the body of the paper. Perhaps the authors could stress more their novel contribution in the first two paragraphs. \n\nNote after rebuttal: I think the paper studies an interesting question and introduces new techniques that might yield interesting insights. \nI thereby change my review to accept. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "FgVt6Vp89Zf", "reviewer": "Reviewer_YGav", "summary": "This paper considers the problem of characterizing exact representations for ReLU networks of a given depth, but any width. It was previously shown that the functions represented by ReLU networks of depth logarithmic in dimension is exactly equal to the set of all continuous piecewise linear functions. This work provides some results which suggest that this result is tight. That is, a depth logarithmic in dimension is necessary to exactly represent all piecewise linear functions. \n\nProposition 1.3 simplifies this conjecture by giving a simple equivalent condition in terms of representing max(0,x_1,\\dots,x_n) and proves the conjecture up to dimension 4 under the assumption 2.4 which is unproven. In section 3 it is shown that the set of functions representable by a depth k network is a strict super set of Max(2^k) - i.e, set of all functions which can written as a linear combination of max of 2^k affine functions. This provides further evidence in support of the conjecture. \nSection 4 then extends the results of Arora et. al 2018 to provide an upper bound on the width required for a relu network to exactly represent affine function with p pieces. This bound is $p^{O(n^2)}$.", "questions": "", "limitations": "", "rating": 5, "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": "Disclaimer: I am not an expert on tropical geometry and related topics.\n\nI would first note that this paper is about exact representations. The closure of $\\mathsf{ReLU}_n(k)$ with respect to uniform convergence over compacts contains the space of all continuous functions by universal approximation property. This work is about not taking the closure and considering the exact representations. I acknowledge that this is indeed a hard problem. \n\nThe scope of the work seems to be very limited. It is not clear why having exact representation is ever useful in practical machine learning. The authors do mention the learning algorithm by Arora et. al 2018, which I believe they should expand on. The results seem a bit weak. The main result in Section 2 which proves the conjecture only upto dimension 4,  conditioned on an unproven assumption. The bounds in Section 4 are super exponential in dimension, which seems very intractable from a computation perspective. It would be great to see some discussions about lower bounds for the width. Practically speaking, if indeed this is tight, what is the use of exact representations at all?\n\nThe paper is very well written but I am skeptical about the relevance of this work in a venue like NeurIPS.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think a bit more effort needs to be put in to highlight the exact limitations of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "1vaOCXZgOjD", "reviewer": "Reviewer_Umtt", "summary": "EDIT: After reading authors' responses, I decided to keep my score as is.\n\nThe paper studies the problem of exact representation of continuous functions via neural networks with the ReLU activation. The literature on the approximation power of neural nets is large, however the paper here delves into the less studied question of whether the class of *exactly* representable functions strictly increases when adding more layers (with no restrictions on size).\n\nThe authors want to understand the function classes exactly represented by different architectures and a step towards this direction is to analayze the class of functions captured by a depth-d neural net (without width constraints) and how this class of functions changes as we get to depth-d+1 neural nets.\n\nIt is obvious that ReLU nets will output continuous piecewise linear functions (CPWL for short) and a non-trivial fact from previous works is that $\\log(n+1)$ hidden layers suffice to represent *any* CPWL in n dimensions, via a ReLU net. Let d is a parameter for the depth and and ReLU(d) is all functions representable exactly via ReLU nets of depth at most d. The paper tries to understand ReLU(d) as d goes from 0 to $\\log(n+1)$.\n\nThe authors put forth two equivalent conjectures about the relations between the class of functions ReLU(d) for different d. Conjecture 1.1 states that every additional layer will indeed be substantial in terms of the representational capabilities of ReLU nets up to $d\\le \\log(n+1)$ of course, at which point all CPWL are representable. The authors reformulate this with Conjecture 1.2 that is a simple statement about max functions. \n\nThe authors then show a special case of Conj. 1.2 that corresponds to showing that the max function on 5 variables cannot be representted with 2 or 3 hidden layers, with the caveat that they need a certain assumption on the breakpoints of the function represented by any intermediate neuron. Along the same lines,  the authors show that the class ReLU(k) contains more functions than just taking the max on $2^k+1$ variables. To achieve this they use the theory of polyhedral complexes associated with CPWL functions.\n\nFinally, the authors find upper bounds on the sizes of the networks needed for expressing arbitrary CPWL functions with p linear pieces, as given in Theorem 4.4, which basically involves depth O(logn) nets with width growing as $p^{n^2}$.\n\n\n", "questions": "", "limitations": "", "rating": 5, "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": "I like the overall theme of understanding the exact representation capabilities of neural networks, escaping the traditional approximation theory viewpoint. As most of the traditional approximation theory results, rely on large widths to approximately construct step functions to approximate a given function, all these techniques cannot work here and new ideas are necessary.\n\nThe main ideas in the paper involve how to relate the max functions with output of ReLU nets. Both conjectures provided in the introduction are very plausible (equivalent of course as the authors show) and the authors take some small first steps towards understanding them.\n\nOne of the main results is that \"there does not exist a 3-layer NN\" to compute max on 5 variables. One quick observation here however is that following the notaion in Conj. 1.2 I think there is a shift by +1 that is not correct (is k=2 or k=3 for the statement?). One annoying thing with this result is that it involves a somewhat technical condition on the breakpoints of intermediate neurons which I can't see how to prove. Furthermore, I believe the result is useful but not very surprising. It basically means that computing the maximum between inputs somehow requires a lot of depth in some sense. \n\nThe next result is about ReLU(k) being a superset of the class of max functions on $2^k$ variables. To establish this they use a specific construction involving max functions and compositions between max functions that can be written as a ReLU net but not as a max function on several terms. Although the proof is somewhat complicated, still the result seems not as surprising.\n\nThe perhaps more interesting part has to do with Section 4 where the authors derive upper bounds for the size of the net to be able to represent CPWL functions.\n\nOverall, the motivation of the work is interesting from a theoretical point of view, however the results presented are quite weak. Section 2 relied on a technical assumption and only proves a very special case of the (plausible) conjecture 1.1, Section 3 is a comparison between very special class of functions. Section 4 has some interesting techniques. I like that the authors have identified the relation to max functions and have built several ways to analyze the exact representation capabilities of NN, however I believe more and stronger results are necessary to make this a solid contribution.\n\nQuestions/Future directions to the authors:\n- Could most of these results also be stated for recurrent neural networks? As far as I know several important approximation theory results (e.g., Telgarsky's \"Benefits of depth in neural networks\") can also be viewed for RNNs instead of feedforward nets, and having the analogous theory for RNNs would be interesting, and can strengthen the overall message of your paper.\n- To get the separations for the different depth levels and also to separate ReLU(k) from MAX(2^k), the authors identify the max function as a \"source of complexity\" in some sense. In particular Proposition 3.2 relies on max of max functions. Why not taking this to the extreme? Specifically, is there another way of using repeated compositions of max functions with themselves in order to get a \"sufficiently complicated\" function? Notice that works that have exploited this repeated compositions trick include the seminal paper by Telgarsky and also follow-ups that extended Telgarsky's results to much broader family of functions using characterizations from dynamical systems (e.g., \"Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem\"). The \"source of complexity\" in that case came from oscillations in the input, and not max alternations between the inputs as in your case. \n- Another interesting direction would be to get also tradeoffs for the depth/width or other aspects of the architecture needed to exactly represent certain functions. This again will be a counterpoint to many existing approximation theory results that derive depth/width tradeoffs instead of just approximability results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers recommend accept and two reviewers recommend weak reject. A main criticism is the unclear significance of the partial results and the unclear relevance to practical machine learning. After weighing the discussion and evaluating the submission, I agree with the positive reviewers that the problem formulation, the approach and the tools presented are sufficiently interesting and relevant to the theoretical understanding of neural networks. Hence I am recommending accept. I ask the authors to add the details promised in the discussion in the final version of the paper and to take the reviewers suggestions carefully into consideration when preparing it. 
Decision: Accept (Poster)