Towards Lower Bounds on the Depth of ReLU Neural Networks
Year: 2022

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.

heading: 1 Introduction
text: A 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 one needs to solve the problem with high confidence (or equivalently, how much variance one has in one’s estimate). This is referred to as the bias-variance trade-off or the bias-complexity trade-off. Neural networks provide a way to turn this bias/complexity knob in a controlled manner that has been studied for decades going back to the idea of a 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, 1991, Anthony and Bartlett, 1999] show that even with a single hidden layer, i.e., when the depth of the architecture is the smallest possible value, one can essentially reduce the “bias” as much as one desires, by increasing the size of the network or the number of neurons used in the neural network. Nevertheless, it can be advantageous both theoretically and empirically to increase the depth because a substantial reduction in the size can be achieved; Telgarsky [2016a], Eldan and Shamir [2016], Arora et al. [2018] is a small sample of recent work in this direction. To get a better quantitative handle on these trade-offs,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
it is important to understand what classes of functions are exactly representable by neural networks with a certain architecture. The precise mathematical statements of 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 a mathematical perspective, one can ask the question if the class of functions represented by a single layer is a strict subset of the class of 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 a better understanding of the function classes exactly represented by different architectures will have implications not just for 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] := {1, 2, . . . , n} for the set of natural numbers up to n (without zero) and [n]0 := [n] ∪ {0} for the same set including zero. For any n ∈ N, let σ : Rn → Rn be the component-wise rectifier function
σ(x) = (max{0, x1},max{0, x2}, . . . ,max{0, xn}).
For any number of hidden layers k ∈ N, a (k + 1)-layer feedforward neural network with rectified linear units (ReLU NN or simply NN) is given by k affine transformations T (`) : Rn`−1 → Rn` , x 7→ A(`)x+ b(`), for ` ∈ [k], and a linear transformation T (k+1) : Rnk → Rnk+1 , x 7→ A(k+1)x. It is said to compute or represent the function f : Rn0 → Rnk+1 given by
f = T (k+1) ◦ σ ◦ T (k) ◦ σ ◦ · · · ◦ T (2) ◦ σ ◦ T (1). The matrices A(`) ∈ Rn`×n`−1 are called the weights and the vectors b(`) ∈ Rn` are the biases of the `-th layer. The number n` ∈ N is called the width of the `-th layer. The maximum width of all hidden layers max`∈[k] n` is called the width of the NN. Further, we say that the NN has depth k + 1 and size ∑k `=1 n`.
Often, NNs are represented as layered, directed, acyclic graphs where each dimension of each layer (including input layer ` = 0 and output layer ` = k + 1) is one vertex, weights are arc labels, and biases are node labels. Then, the vertices are called neurons.
For a given input x = x(0) ∈ Rn0 , let y(`) := T (`)(x(`−1)) ∈ Rn` be the activation vector and x(`) := σ(y`) ∈ Rn` the output vector of the `-th layer. Further, let y := y(k+1) = f(x) be the 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 `-th layer.
For k ∈ N, we define ReLUn(k) := {f : Rn → R | f can be represented by a (k + 1)-layer NN}, CPWLn := {f : Rn → R | f is continuous and piecewise linear}. By definition, a continuous function f : Rn → R is piecewise linear in case there is a finite set of polyhedra whose union is Rn, and f is affine linear over each such polyhedron. In order to analyze ReLUn(k), we use another function class defined as follows. We call a function g a p-term max function if it can be expressed as maximum of p affine terms, that is, g(x) = max{`1(x), . . . , `p(x)} where `i : Rn → R is affinely linear for i ∈ [p]. Based on that, we define
MAXn(p) := {f : Rn → R | f is a linear combination of p-term max functions}.
If the input dimension n is not important for the context, we sometimes drop the index and use ReLU(k) := ⋃ n∈N ReLUn(k) and MAX(p) := ⋃ n∈N MAXn(p) instead.
Since we deal with polyhedra a lot in this paper, we will use the standard notations convA and coneA for the convex and conic hulls of a set A ⊆ Rn. For an in-depth treatment of polyhedra and (mixed-integer) optimization, we refer to Schrijver [1986].

heading: 1.1 Our Contribution
text: It is not hard to see that any function expressed by a ReLU network is a continuous and piecewise linear (CPWL) function, because one is composing continuous piecewise linear functions together. Based on a result by Wang and Sun [2005], Arora et al. [2018] show that every CPWL function defined on Rn can be represented by a ReLU neural network with dlog2(n+ 1)e hidden layers. We wish to 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 ∈ N, let k∗ := dlog2(n+ 1)e. Then it holds that
ReLUn(0) ( ReLUn(1) ( · · · ( ReLUn(k∗ − 1) ( ReLUn(k∗) = CPWLn . (1)
Conjecture 1.1 claims that any additional layer up to 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.
Observe that in order to prove Conjecture 1.1, it suffices to find a single function f ∈ ReLUn(k∗) \ ReLUn(k∗ − 1) with n = 2k
∗−1 for all k∗ ∈ N. This also implies all remaining strict inclusions ReLUn(i− 1) ( ReLUn(i) for i < k∗ since ReLUn(i− 1) = ReLUn(i) directly implies that ReLUn(i− 1) = ReLUn(i′) for all i′ ≥ i− 1. 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 ∈ N, n = 2k, the function fn(x) = max{0, x1, . . . , xn} cannot be represented with k 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.1. For the other direction, one can argue that, if the specific (n+1)-term max function fn can be represented by k hidden layers, then every other (n+ 1)-term max function as well. The claim then follows via a result by [Wang and Sun, 2005] stating that any f ∈ CPWLn can be written as linear combination of (n+ 1)-term max functions. We provide a detailed argument in Appendix A.
It is known that Conjecture 1.2 holds for k = 1 [Mukherjee and Basu, 2017]. However, the conjecture remains open for k ≥ 2. In this paper, we present the following results as partial progress towards resolving this conjecture.
In Section 2, we resolve Conjecture 1.2 for k = 2, under a 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(2k) ⊆ ReLU(k) for all k ∈ N [Arora et al., 2018], that is, any 2k-term max function (and linear combinations thereof) can be expressed with k hidden layers. One might ask whether the converse is true as well, that is, whether the classes MAX(2k) and ReLU(k) are actually equal. This would not only provide a neat characterization of ReLU(k), but also prove Conjecture 1.2 without any additional assumption since one can show that max{0, x1, . . . , x2k} is not contained in MAX(2k).
In fact, this is true for k = 1, that is, a function is computable with one hidden layer if and only if it is a linear combination of 2-term max functions. However, in Section 3, we show that for k ≥ 2, the class ReLU(k) is a strict superset of MAX(2k). In this section, the key technical ingredient is the theory of polyhedral complexes associated with CPWL functions. This way, we provide important insights concerning the richness of the class ReLU(k).
So far, we have focused on understanding the smallest depth needed to express CPWL functions using neural networks with ReLU activations. In Section 4, we complement these results by upper bounds on the sizes of the networks needed for expressing arbitrary CPWL functions. In particular, Theorem 4.4 shows that any continuous piecewise linear function with p linear/affine pieces on Rn can be expressed by a network with depth at most O(log n) and width at most pO(n2). We arrive at this result by introducing a novel application of recently established interactions between neural networks and tropical geometry.

heading: 1.2 Related Work
text: Depth versus size. Soon after the original universal approximation theorems [Cybenko, 1989, Hornik, 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 to a 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, 2016a, Eldan and Shamir, 2016, Arora et al., 2018, Vardi et al., 2021]. See also Gribonval et al. [2021] for another perspective on 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 et al., 2014, Khalil et al., 2016, 2017, Kruber et al., 2017, Lodi and Zarpellon, 2017, Alvarez et al., 2017]; see also Bengio et al. [2020] for a recent survey. On the flip side, mixed-integer optimization techniques have been used to analyze function classes represented by neural networks [Serra et al., 2018, Anderson et al., 2020, Fischetti and Jo, 2017, Serra and Ramalingam, 2020, Serra et al., 2020]. In Section 2 below, we show another new use of mixed-integer optimization tools for understanding function classes represented by neural networks.
Design of training algorithms. We believe that a 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 a paper by Arora et al. [2018], an 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 [2019], Dey et al. [2020], Boob et al. [2020], Goel et al. [2021], Froese et al. [2021] for a similar lines of work.
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 to 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 and Maragos, 2018, Montúfar et al., 2021] and understanding decision boundaries [Alfarra et al., 2020]. In Section 4 we present a novel application of tropical concepts to understand neural networks. We refer to Maragos et al. [2021] for a recent survey of connections between machine learning and tropical geometry, as well as to the textbooks by Maclagan and Sturmfels [2015] and Joswig [2022] for in-depth introductions to tropical geometry and tropical combinatorics.

heading: 2 Conditional Lower Bounds on Depth via Mixed-Integer Programming
text: In this section, we provide a computer-aided proof that, under a natural, yet unproven assumption, the function f(x) := max{0, x1, x2, x3, x4} cannot be represented by a 3-layer NN. It is worth to note that, to the best of our knowledge, no CPWL function is known for which the non-existence of a 3-layer NN can be proven without additional assumption. For easier notation, we write x0 := 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 : Rn → Rm is called positively homogeneous if g(λx) = λg(x) for all λ ≥ 0. Definition 2.2. For an NN given by affine transformations T (`)(x) = A(`)x + b(`), we define the corresponding homogenized NN to be the NN given by T̃ (`)(x) = A(`)x 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 : Rn0 → Rnk+1 be the function computed by the original NN and g̃ the one computed by the homogenized NN. Further, for any 0 ≤ ` ≤ k, let g(`) = T (`+1) ◦σ ◦T (`) ◦ · · ·◦T (2) ◦σ ◦T (1) be the function computed by the sub-NN consisting of the first (` + 1)-layers and let g̃(`) be the function computed by the corresponding homogenized sub-NN. We first show by induction on ` that the norm of ‖g(`)(x)− g̃(`)(x)‖ is bounded by a global constant that only depends on the parameters of the NN but not on x.
For ` = 0, we obviously have ‖g(0)(x) − g̃(0)(x)‖ = ‖b(1)‖ =: C0, settling the induction base. For the induction step, let ` ≥ 1 and assume that ‖g(`−1)(x) − g̃(`−1)(x)‖ ≤ C`−1, where C`−1 only depends on the parameters of the NN. Since component-wise ReLU activation has Lipschitz constant 1, this implies ‖(σ ◦ g(`−1))(x)− (σ ◦ g̃(`−1))(x)‖ ≤ C`−1. Using any matrix norm that is compatible with the Euclidean vector norm, we obtain:
‖g(`)(x)− g̃(`)(x)‖ = ‖b(`+1) +A(`+1)((σ ◦ g(`−1))(x)− (σ ◦ g̃(`−1))(x))‖ ≤ ‖b(`+1)‖+ ‖A(`+1)‖ · C`−1 =: C`
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 is an x ∈ Rn0 with ‖g(x) − g̃(x)‖ = δ > 0. Let x′ := Ck+1δ x; then, by positive homogeneity, it follows that ‖g(x′)− g̃(x′)‖ = Ck + 1 > Ck, contradicting the property shown above. Thus, we have g = g̃.
Since f = max{0, x1, x2, x3, x4} 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 homogeneous. 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 at places where at least two of the five numbers x0 = 0, x1, x2, x3, and x4 are equal. Hence, if some neuron of an NN computing f introduces breakpoints at 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 Hij = {x ∈ R4 | xi = xj}, for 0 ≤ i < j ≤ 4, be ten hyperplanes in R4 and H = ⋃ 0≤i<j≤4Hij 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 5! = 120 possible orderings of the five numbers x0 = 0, x1, x2, x3, and x4. More precisely, for a permutation π of the five indices [4]0 = {0, 1, 2, 3, 4}, the corresponding region is the polyhedron
Cπ := {x ∈ R4 | xπ(0) ≤ xπ(1) ≤ xπ(2) ≤ xπ(3) ≤ xπ(4)}.
We say that a (positively homogeneous) CPWL function g is H-conforming, if it is linear within any of these regions of H , that is, if it only has breakpoints where the relative ordering of the five values x0 = 0, x1, x2, x3, x4 changes. Moreover, an NN is said to be H-conforming if the output of each neuron contained in the NN is H-conforming. Equivalently, this is the case if and only if all intermediate functions σ ◦ T (`) ◦ σ ◦ T (`−1) ◦ · · · ◦ σ ◦ T (1), ` ∈ [k], are H-conforming. Now our assumption can be formally phrased as follows. Assumption 2.4. If there exists a 3-layer NN computing f(x) = max{0, x1, x2, x3, x4}, then there also exists one that is H-conforming.
We use mixed-integer programming to prove the following theorem. Theorem 2.5. Under Assumption 2.4, there does not exist a 3-layer NN that computes the function f(x) = max{0, x1, x2, x3, x4}.
Proof (Outline). We first study some geometric properties of the hyperplane arrangement H . This will show that each of the 120 cells of H is a 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-conforming functions of type R4 → R is a 30-dimensional vector space and
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-conforming two-layer NNs is a 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, it remains the question whether the 14 dimensions producible with the first hidden layer can be combined in such a way that after applying a ReLU activation in the second hidden layer, we do not end up within the 29-dimensional subspace. We model this question as a mixed-interger program (MIP). Solving the MIP yields that we always end up within the 29-dimensional subspace, implying that f cannot be represented by a 3-layer NN. This provides a computational proof of Theorem 2.5. All details can be found in Appendix B.
3 Going Beyond 2k-Term Max Functions with k Layers
In this section we prove the following result: Theorem 3.1. For any k ≥ 2, the class ReLU(k) is a strict superset of MAX(2k).
In order to prove this theorem, we provide a specific function that is in ReLU(k) \MAX(2k) for any number of hidden layers k ≥ 2. The challenging part is to show that the function is in fact not contained in MAX(2k). Proposition 3.2. For any n ≥ 3, the function
f : Rn → R, f(x) = max{0, x1, x2, . . . , xn−3, max{xn−2, xn−1}+ max{0, xn}} (2) cannot be written as a linear combination of n-term max functions.
The above proposition means that it is not possible to write f(x) in the form
f(x) = p∑ i=1 λi max{`i1(x), . . . , `in(x)}
where p ∈ N, λ1, . . . , λp ∈ R, and `ij : Rn → R is an affine linear function for every i ∈ [p] and j ∈ [n]. (Note that max functions with less than n terms are also allowed, as some functions `ij may coincide.)
Before we prove Proposition 3.2, we show that it implies Theorem 3.1.
Proof of Theorem 3.1. For k ≥ 2, let n := 2k. By Proposition 3.2, function f defined in (2) is not contained in MAX(2k). It remains to show that it can be represented using a ReLU NN with k hidden layers. To see this, first observe that any of the n/2 = 2k−1 terms max{0, x1}, max{x2i, x2i+1} for i ∈ [n/2 − 2], and max{xn−2, xn−1} + max{0, xn} can be expressed by a one-hidden-layer NN since all these are (linear combinations of) 2-term max functions. Since f is the maximum of these 2k−1 terms, and since the maximum of 2k−1 numbers can be computed with k − 1 hidden layers [Arora et al., 2018], this implies that f is in ReLU(k).
In order to 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 a polyhedron in P is also in P , and for two polyhedra P,Q ∈ P , their intersection P ∩Q is a common face of P and Q (possibly the empty face). Given a polyhedral complex P in Rn and an integer m ∈ [n], we let Pm denote the collection of all m-dimensional polyhedra in P . For a convex CPWL function f , we define its underlying polyhedral complex as follows: it is the unique polyhedral complex covering Rn (i.e., each point in Rn 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 ∈ P , but not within any strict superset of a polyhedron in Pn. Exploiting properties of polyhedral complexes associated with CPWL functions, we prove the following proposition in Appendix C. Proposition 3.3. Let f0 : Rn → R be a convex CPWL function and let P0 be the underlying polyhedral complex. If there exists a hyperplane H ⊆ Rn such that the set
T := ⋃{ F ∈ Pn−10 ∣∣ F ⊆ H}
is nonempty and contains no line, then f0 cannot 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 in (2)) has the alternate representation
f(x) = max{0, x1, x2, . . . , xn−3, xn−2, xn−1, xn−2 + xn, xn−1 + xn} as a maximum of n+ 2 terms. Let P be its underlying polyhedral complex. Let the hyperplane H be defined by x1 = 0.
Observe that any facet in Pn−1 is a polyhedron defined by two of the n + 2 terms that are equal and at least as large as each of the remaining n terms. Hence, the only facet that could possibly be contained in H is
F := {x ∈ Rn | x1 = 0 ≥ x2, . . . , xn−3, xn−2, xn−1, xn−2 + xn, xn−1 + xn}.
Note that F is indeed an (n− 1)-dimensional facet in Pn−1, because, for example, the full neighborhood of (0,−1, . . . ,−1) ∈ Rn intersected with H is contained in F . Finally, we need to show that F is pointed, that is, it contains no line. A well-known fact from polyhedral theory says if there is any line in F with direction d ∈ Rn \ {0}, then d must satisfy the defining inequalities with equality. However, only the zero vector does this. Hence, F cannot contain a line.
Therefore, when applying Proposition 3.3 to f with underlying polyhedral complex P and hyperplane H , we have T = F , which is nonempty and contains no line. Hence, f cannot be written as linear combination of n-term maxima.

heading: 4 A Width Bound for NNs with Small Depth
text: While the arguments in Arora et al. [2018] show that CPWLn = ReLUn(dlog2(n + 1)e), 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 to 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 pO(n
2). This is closely related to works that bound the number of linear pieces of an NN as a function of the size [Montúfar et al., 2014, Pascanu et al., 2014, Raghu et al., 2017, Montúfar et al., 2021]. It can also be seen as a counterpart, in the context of exact representations, to quantitative universal approximation theorems that bound the number of neurons required to achieve a certain approximation guarantee; see, e.g., Barron [1993, 1994], Mhaskar [1993], Pinkus [1999], Mhaskar [1996], Mhaskar and Micchelli [1995].

heading: 4.1 The Convex Case
text: 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 a consequence of the following theorem about convex CPWL functions, for which we are going to provide a geometric proof later. Theorem 4.1. Let f(x) = max{aTi x + bi | i ∈ [p]} be a convex CPWL function defined on Rn. Then f can be written as
f(x) = ∑ S⊆[p], |S|≤n+1 cS max{aTi x+ bi | i ∈ S}
with coefficients cS ∈ Z, for S ⊆ [p], |S| ≤ n+ 1.
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 be written as a linear combination of (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 it possible to bound the total number of these (n+ 1)-term maxima and, therefore, the size of an NN representing f .
Theorem 4.2. Let f : Rn → R be a convex CPWL function with p affine pieces. Then f can be represented by a ReLU NN with depth dlog2(n+ 1)e+ 1 and width O(pn+1).
Proof. Since the number of possible subsets S ⊆ [p] with |S| ≤ n + 1 is bounded by pn+1, the theorem follows by Theorem 4.1 and the construction from Arora et al. [2018, Theorem 2.1].
Before we present the proof of Theorem 4.1, we show how we can generalize its consequences to the nonconvex case.

heading: 4.2 The General (Nonconvex) Case
text: It is a well-known fact that every CPWL function can be expressed as a difference of two convex CPWL functions, see, e.g., Wang [2004, 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 : Rn → R be a CPWL function with p affine pieces. Then, f can be written as f = g − h where both g and h are convex CPWL functions with at most p2n+1 pieces.
Proof. Suppose the p affine pieces of f are given by x 7→ aTi x + bi, i ∈ [p]. Define the function h(x) := ∑ 1≤i<j≤p max{aTi x+ bi, aTj x+ bj} and let g := f + h. Then, obviously, f = g − h. It 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 2 ) = p(p−1)2 < p 2 hyperplanes given by aTi x+ bi = a T j x+ bj , 1 ≤ i < j ≤ p. They divide Rn into at most ( p2
n
) + ( p2 n−1 ) + · · ·+ ( p2 0 ) ≤ p2n
regions (compare Edelsbrunner [1987, Theorem 1.3]) in each of which h is affine. In particular, h has at most p2n ≤ p2n+1 pieces. Next, we show that g = f + h is convex. Intuitively, this holds because each possible breaking hyperplane of f is made convex by adding h. To make this formal, note that by the definition of convexity, it suffices to show that g is convex along each affine line. For this purpose, consider an arbitrary line x(t) = ta+b, t ∈ R, given by a ∈ Rn and b ∈ R. Let f̃(t) := f(x(t)), g̃(t) := g(x(t)), and h̃(t) := h(x(t)). We need to show that g̃ : R→ R is a convex function. Observe that f̃ , g̃, and h̃ are clearly one-dimensional CPWL functions with the property g̃ = f̃ + h̃. Hence, it suffices to show that g̃ is convex locally around each of its breakpoints. Let t ∈ R be an arbitrary breakpoint of g̃. If f̃ is already convex locally around t, then the same holds for g̃ as well since h̃ inherits convexity from h. Now suppose that t is a nonconvex breakpoint of f̃ . Then there exist two distinct pieces of f , indexed by i, j ∈ [p] with i 6= j, such that f̃(t′) = min{aTi x(t′) + bi, aTj x(t′) + bj} for all t′ sufficiently close to t. By construction, h̃(t′) contains the summand max{aTi x(t′)+bi, aTj x(t′)+bj}. Thus, adding this summand to f̃ linearizes the nonconvex breakpoint of f̃ , while adding all the other summands preserves convexity. In total, g̃ is convex locally around t, which finishes the proof that g is a convex function.
Finally, observe that pieces of g = f + h are always intersections of pieces of f and h, for which we have only p · p2n = p2n+1 possibilities.
Having this, we may conclude the following.
Theorem 4.4. Let f : Rn → R be a CPWL function with p affine pieces. Then f can be represented by a ReLU NN with depth dlog2(n+ 1)e+ 1 and width O(p2n 2+3n+1).
Proof. Consider the decomposition f = g − h from Proposition 4.3. Using Theorem 4.2, we obtain that both g and h can be represented with the required depth dlog2(n + 1)e + 1 and with width O((p2n+1)n+1) = O(p2n2+3n+1). Thus, the same holds for f .

heading: 4.3 Extended Newton Polyhedra of Convex CPWL Functions
text: For our proof of Theorem 4.1, we use a correspondence of convex CPWL functions with certain polyhedra, which are known as (extended) Newton polyhedra in tropical geometry [Maclagan and Sturmfels, 2015]. 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 to formalize this correspondence, let CCPWLn ⊆ CPWLn be the set of convex CPWL functions of type Rn → R. For f(x) = max{aTi x + bi | i ∈ [p]} in CCPWLn, we define its so-called extended Newton polyhedron to be
N (f) := conv({(ai, bi) ∈ Rn × R | i ∈ [p]}) + cone({−en+1}) ⊆ Rn+1.
We denote the set of all possible extended Newton polyhedra in Rn+1 as Newtn. That is, Newtn is the set of (unbounded) polyhedra in Rn+1 that emerge from a polytope by adding the negative of the (n+ 1)-st unit vector −en+1 as an extreme ray. Hence, a set P ⊆ Rn+1 is an element of Newtn if and only if P can be written as P = conv({(ai, bi) ∈ Rn × R | i ∈ [p]}) + cone({−en+1}). Conversely, for a polyhedron P ∈ Newtn of this form, let F(P ) ∈ CCPWLn be the function defined by F(P )(x) = max{aTi x+ bi | i ∈ [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) ∈ Rn × R such that aTx+ b ≤ f(x) for all x ∈ Rn. This also explains why we add the extreme ray −en+1: decreasing b obviously maintains the property of aTx+ b being a lower bound on the function f .
We need the notion of the Minkowski sum of two polyhedra P and Q: it is given as the set P +Q = {p+ q | p ∈ P, q ∈ Q}. In fact, there is a one-to-one correspondence between elements of CCPWLn and Newtn, which is nicely compatible with some (functional and polyhedral) operations. This correspondence has been studied before in tropical geometry [Maclagan and Sturmfels, 2015, Joswig, 2022], convex geometry1 [Hiriart-Urruty and Lemaréchal, 1993], as well as neural network literature [Zhang 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 our work in the following proposition: Proposition 4.5. Let n ∈ N and f1, f2 ∈ CCPWLn. Then it holds that
(i) the functions N : CCPWLn → Newtn and F : Newtn → CCPWLn are well-defined, 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) N (max{f1, f2}) = conv(N (f1),N (f2)) := conv(N (f1) ∪N (f2)),
(iv) N (f1 + f2) = N (f1) +N (f2), where the + on the right-hand side is Minkowski addition.
An algebraic way of phrasing this proposition is as follows: N and F are isomorphisms between the semirings (CCPWLn,max,+) and (Newtn, conv,+).

heading: 4.4 Outline of the Proof of Theorem 4.1
text: 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 f with p ≥ n + 2. By Proposition 4.5, f corresponds to a polyhedron P ∈ Newtn with at least n + 2 vertices. Applying a classical result from discrete geometry known as Radon’s theorem allows us to carefully decompose P into a “signed”2 Minkowski sum of polyhedra in Newtn whose vertices are subsets of at most p− 1 out of the p vertices of P . Translating this back into the world of CPWL functions by Proposition 4.5 yields that f can be written as linear combination of p′-term maxima with p′ < p, where each of them involves a subset of
1N (f) is the negative of the epigraph of the convex conjugate of f . 2Some 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 at most n+ 1 terms.

heading: 4.5 Potential Approaches to Show Lower Bounds on the Width
text: In light of the upper width bounds shown in this section, a natural question to ask is whether also meaningful lower bounds can be achieved. This would mean constructing a family of CPWL functions with p pieces defined on Rn (with different values of p and n), for which we can prove that a large width is required to represent these functions with NNs of depth dlog2(n+ 1)e+ 1. A trivial and not very satisfying answer follows, e.g., from Raghu et al. [2017] or Serra et al. [2018]: for fixed input dimension n, they show that a function computed by an NN with k hidden layers and width w has at most O(wkn) pieces. For our setting, this means that an NN with logarithmic depth needs a width of at least O(p1/(n logn)) 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 on functions with very many pieces, which then, consequently, need many neurons to be represented (with small depth). However, since the lower bounds we 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 a tough task to argue why such functions should exist.
A different approach could leverage methods from complexity theory, in 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 6= 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, is an exciting question for further research.

heading: 5 Discussion of Future Research Directions
text: The most obvious and, at the same time, most exciting open research question is to prove or disprove Conjecture 1.1, or equivalently Conjecture 1.2. The first step could be to prove Assumption 2.4. The assumption is intuitive because every breakpoint introduced at other places needs to 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 a formal proof because it 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 Assumption 2.4. This might also be beneficial for generalizing our 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 ReLU(k). Another potential research goal is improving our upper bounds on the width from Section 4 and/or 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, 3. Understanding how the class ReLU(k) changes when a polynomial upper bound is imposed on the width of the NN; see related work by Vardi et al. [2021].
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 FA95502010341 and NSF Grant CCF2006587. Martin Skutella gratefully acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy — The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

Review summaries:
EDIT: After reading authors' responses, I decided to keep my score as is.  The 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).  The 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.  It 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)$.  The 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.   The 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.  Finally, 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}$.   

This paper studies the role of depth in exactly representing real functions by ReLU networks.  Unlike the common ML setting, the focus is on neural nets that are equal in every point to the target function.  Some partial results are given as well as a conjecture that networks of depth k+1 have strictly more expressivity than networks of depth k.  

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.

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.   Proposition 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.  Section 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)}$.

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.