Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
Authors: Kuan-Lin Chen
Harinath Garudadri
Bhaskar D Rao
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep neural networks
rectified linear units
neural complexity
piecewise linear functions

Abstract: A deep neural network using rectified linear units represents a continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing a CPWL function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number of pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies a lower neural complexity because the number of distinct linear components is always not greater than the minimum number of pieces in a CPWL function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexities of any CPWL function are at most polynomial growth for low-dimensional inputs and factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.

Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
Kuan-Lin Chen
Harinath Garudadri
Department of Electrical and Computer Engineering University of California, San Diego La Jolla, CA 92093, USA kuc0290ucsd.c edu
Qualcomm Institute University of California, San Diego La Jolla, CA 92093, USA hgarudadr @ucsd. edu
Bhaskar Rao
Department of Electrical and Computer Engineering University of California, San Diego La Jolla, CA 92093, USA brao@ucsd. edu
Abstract
A deep neural network using rectified linear units represents continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing CPWI. function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required exactly represent any CPWL, function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies lower neural complexity because the number of distinct lincar components is always not greater than the minimum number of pieces in a CPWL. function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexities of any CPWI. function
most polynomial growth for low-dimensional inputs and factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.
Introduction
The rectified linear unit (ReLU) Fukushima 1980 Nair and Hinton 2010 activation has been by far the most widely used nonlinearity and successful building block deep neural networks (DNNs). Numerous architectures based ReLU DNNs have achieved remarkable performance or state-of-the-arr art accuracy in speech processing Zeiieer et al. [2013] Maas et al.) 2013), computer vision (Krizhevsky al.] 2012, (iimoyyan and Zisserman |2055] He al. 2016 medical image segmentation Ronneberger et 20155, game playing [Mnih et al. 2015 Silver et al. 2016), and
natural language processing Vaswani et al. 2017), just name few. Besides such unprecedented
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

10th
Theorem and 3
Number of hidden neurons
1
Number of hidden neurons
1010
Hertrich
2021
1043
He et al.
2020
107
10
10a
10"
9-0-0-0
10
invariant to n
10a
5
10
15 20
1
5
10
15
20
Number of pieces g
Number of distinct lincar components k
Figure 1: Any CPWL function R + R with pieces or k distinct linear components can be exactly
represented by a ReLU network with at most hidden neurons. In Theorem [ andd 3 = when
q = 1 or k = 1. The bounds in Theorem [ the worst-case bounds in Theorem 3 Jare invariant to (4) is used to infer based on the depth and width given by Hertrich et al. [2021] The upper bounds
given by Theorem and 3 are substantially lower than existing bounds in the literature, implying that
any CPWL function can be exactly realized by a ReLU network at a much lower cost.
empirical success, ReLU DNNs also probably the most understandable nonlinear deep learning models due to their ability to be "un-rectified" (Hwang and Heinecke] 2019].
The ability to demystif' ReLU DNNs via "un-rectifying ReLUs" dates back seminal work by Pascaau et al.] in 2014 Because each of ReLUs a hidden layer divides the space of the preceding layer's output into two half spaces whose ReLU response is affine in one half space and exactly zero in the other, the layer of ReLUs can be replaced by an input- diagonal matrix whose diagonal elements are ones for firing ReLUs and zeros for non- non-firing firing ReLUs. Based on this rationale. Pascanu et al.) 2014) proved that a neural network using ReLUs divides the input space into many linear regions such that the network itself is affine function within every region. Two excellent visualizations are shown in Figure 2 in Haani and Rolnick] [019a] and [Hanin and Rolnick 2019b). At this point, it is quite evident that any ReL.U network exactly represents CPWL. function. Pascanu et al.] also proved that the maximum number of linear regions for any ReLU network with a single hidden layer is equivalent the number of connected components induced by arrangements of hyperplanes in general position where each hyperplane corresponds to a ReLU in the hidden layer. Such number can be computed a closed form by Zaslavsky's 's Theorem [Zalavskyy 1975). Furthermore, they showed that the maximum number of linear regions can be bounded from below by exponential growth in terms of the number of hidden layers, leading a conclusion that ReLU DNNs can generate more linear regions than their shallow counterparts. In the same year, Montúfar et al. improved such lower bound and gave the first upper bound for the maximum number of linear regions. These bounds and their assumptions were later improved by [Montáfar 2017 Raghu et al.)
2017 Arora et al. 2018 Serra et al. 2018 Hinz and van de Geer 2019], just to name a few. We refer readers Hinz)s doctoral thesis for thorough discussion on the upper bound of the number of linear regions. Because a CPWL function with more pieces can better approximate any given continuous function and ReLU DNN exactly represents a CPWL function [Arora al. 2018). ReLU DNN with more linear regions in general exhibits stronger expressivity. In summary, this "un-rectifying" perspective provides us a new angle to understand ReLU DNNs, and the results in some ways align with advances in approximation theory demonstrating the expressivity [
Despite these advancements in linear regions, the complexity of ReLU DNN that exactly represents a given CPWL. function remains largely unexplored. One can find that this question is the opposite direction of the above-mentionel line of research. Although Arora et al. (2018) proved that any CPWL function can be exactly represented by a ReLU DNN with a bounded depth, any estimates
'The approximation viewpoint is not the focus of this paper. The literature on approximation is vast and we refer readers to Vardi et al. 2021 Lu et al. 2017 Eldan and Shamir 2016 Telgarsky 2016 Hornik et al. 1989 Cybenko 1989) just a few.

---

regarding the width or number of neurons of such network were not given. The resources required for ReLU neural network exactly represent a CPWL function remained unknown He et al.) [2020) provided a bound to the complexity of a ReLUU network that realizes any given CPWL. function. They proved that the number of neurons is bounded from above by exponential growth in terms of the product between the number of pieces and the number of distinct linear components of given CPWL function. Such an exponential bound also grows linearly with the input dimension. Because the number of pieces is an upper bound of the number of distinct linear components for any CPWL function [arrlaa and Martínez, 1999 He et al. 2020), the bound grows exponentially with the quadratic number of pieces, which seems to imply that the cost for representing a CPWL function by a ReLU DNN is exceedingly high.
The most recent upper bound can be inferred from a recent work by Hertrich et al. [021] although
the number of hidden neurons was not directly given. [Hertrich et al. [021]] proved width bound in terms of the number of distinct linear components under the same depth used by AAroa et al. (2018) and He et al. 2020 In particular, they proved that the maximum width of ReLU network that represents any given CPWL function can be polynomially bounded from above in terms of the number of distinct linear components. However, the order of such a polynomial is quadratic function of the input dimension, which can be immensely large for small number of pieces linear components when the input dimension is large. This bound grows larger with the input dimension even though the underlying CPWL function is just one- mee-hidden-laye
ReLU network using only one ReLU (see Figure D for the difference between n = 1 and n = 2 when q = 2 or l = 2).
In this paper, we provide improved bounds showing that any CPWI. function can be represented by a ReL.U DNN whose neural complexity is bounded from above by functions with much slower growth (see Figure J. Our results imply that one can exactly realize any given CPWL function by ReLU network at a much lower cost. On the other hand, in addition to guaranteeing the existence of such a network, we also give a polynomial time algorithm to exactly find network satisfying our bounds. To the best of our knowledge, our results regarding the computational resource for a ReLU network, i.e., the number of hidden neurons, are the lowest upper bounds in the existing literature and the algorithm is the first tailored procedure to find a network representation from any given CPWL function. Key results and main contributions of this paper highlighted below.
1.1 Key results and contributions
Quadratic bounds. We prove that any CPWL function with q pieces can be represented by ReLU network whose number of hidden neurons is bounded from above by a quadratic function of q. We also give the corresponding upper bounds for the maximum width, i.e., the maximum number of neurons per hidden layer, and the number of layers for such a network. The maximum width is bounded from above by Ogq²) and the number of layers is bounded from above by logarithmic function of g, i.e., (loga q). These bounds are invariant to the impul dimension. For any affine function, the upper bounds for the maximum width and the number of hidden neurons are zero
Further improvements on neural complexity. When the number of distinct linear components k of any CPWL function is given along with the number of pieces q. the quadratic bounds Og²)) for the number of hidden neurons and the maximum width turn into bilinear bounds of k and q, i.e., (kg)) Such a change reduces the neural complexity because k < g, and q can be much larger than k. Still, these bounds independent of the input dimension.
Finding a network satisfying bilinear bounds. We establish a polynomial time algorithm that finds a ReLU network representing any given CPWL function. The network found by the algorithm satisfies the bilinear bounds on the number of hidden neurons and the maximum width, and the logarithmic bound on the number of layers. Note that such an algorithm also guarantees that one can always reverse-engincer at least one ReLU network from the function it computes. Compared to the general-purpose reverse-ent ceerrs-ennineriing algorithm proposed by Rolnick and Kording (2020), our algorithm specializes in the situation when pieces of CPWL function are given.
"The number of "affine pieces" used by Theorem 4.4 Hertrich et al. 2021 should be interpreted as the number of distinct linear components to best reflect the upper bound for the maximum width. Such an interpretation of "affine pieces" is different from the convention used by Pascanu et al. (2014). Montúfar et al. 2014), Arora et al. [2018) Hanin and Rolnick [2019a], and this work.
3

---

Improved bounds from perspective of linear components. When the number of pieces of CPWL function is unknown and only the number of linear components l is available, we prove that the number of hidden neurons and maximum width are bounded from above by factorial growth. More precisely, O (k- k!). The number of layers is bounded from above by linearithmic growth, or
Olg kt. However, when the input dimension n grows sufficiently slower than k. e.g.. O (Vk)
then bounds for the number of hidden neurons and maximum width reduce to polynomial growth functions of order 2n + 1: and the linearithmic growth reduces O (n log, k) for the depth.
A new approach to choosing the depth. Instead of scaling the depth of a ReLU network with the input dimension [Arora et al. 2018 He et al. 2020, |Hertrich et al. 202T, we reveal that constructing a ReLU network whose depth is scaled with the number of pieces of the given CPWL function is
more advantageous. Such scaling turns out to be the key to deriving better upper bounds. This insight is provided by the max-min representation of CPWL functions [Tarela et al.) [990]. The importance of this scaling on the depth ReLU networks has not been well recognized by existing bounds in the literature. We discuss implications of different representations in Section 4
2 Preliminaries
Notation and definitions used in this paper are set up and clarified in this section. The set (1,2, ,m3 is denoted by [m]] I [condilion] is an indicator function that gives 1 if the condition is true, and 0 otherwise. The CPWL function is defined by Definition beloo..
Definition 1. A Sunction p: Rn R is said be CPWL if there exists finite number of closed subsets of R,, say (Li [em)) such that (a) R = Uve(m) Ui (b) is affine on Us Vi E [m]
A family of closed convex subsets, say {x,) of convex regions, affine pieces or simply pieces for a CPWL function in this paper. Definition [ follows the definition of CPWL functions by OOvchnnikov (2002). Notice that there are different
iEfo]. ) satisfying Definition T is also referred to as family
definitions in the literature. For example,(Chie finite number of polyhedral regions. However, their definitions are essentially the same as Definition because any family of closed subsets satisfying Definition I can be decomposed into polyhedral regions. It is possible that some of the closed subsets satisfying Definition [ are non-convex even though the number of them reaches the minimum (see Figure 2 in [Wang and Sun
and Deng 1988) andoaa et al.) [2018] defined a
NPWLffunctinn
2005 ). The continuity is implied by Definition I due to the subsets being closed.
Because the goal of this paper is to bound the complexity of a ReLU DNN that exactly represents any given CPWL function, it is necessary to be able to measure the complexity of a CPWL function. The complexity of a CPWL function can be described using two different perspectives. One the number of pieces g, which is the number of closed convex subsets satisfying Definition | Because this number has a minimum and any finite number above the minimum can be a valid m Definition I the bounds become obviously loose when the number of pieces is not the minimum. Without loss of generality, we are interested in the number q when is the minimum. The other is the number of distinct linear components k. A linear component of CPWL function is defined in Definition 2
if there exists nonempty subset M C [m] such that f(x) = p(x), Vx E ULeM MM Us where (Ui (ue)s is family of the minimum number of closed subsets satisfying Definition
Definition 2. An affine function f is said to be a linear component of a CPWL.function
greater q or k gives CPWL function more degrees of freedom because a CPWL function allowed to use q + pieces or + 1 arbitrary linear components can represent any CPWL. function with pieces or & distinet linear components and still have the flexibility modify existing affine maps or increase the number of distinct affine maps of the CPWL function. Although increasing them both leads to a CPWL function with greater flexibility, the speed of upgrading degrees of freedom is different from each other. Note that CPWL function with g pieces can never have more than distinct linear components and CPWL function with i distinct linear components can easily have more than k minimum number of pieces. Such a difference in a 1 1-dimensional case can be clearly observed from Figure 1 in Tarela and Martínez [999]. Note that it is possible for two disjoint subsets from a minimum number of closed subsets satisfying Definition [ to share the same linear component. In other words, a linear component can be reused by multiple pieces. Hence, increasing gives faster growth than increasing q for the complexity and expressivity of CPWL functions.

---

We define the ReLU activation function in Definition The ReLU network defined in Definition a simple architecture which is usually referred as a ReLU multi-layer perceptron. Definition defines the corresponding number of hidden neurons, depth, and maximum width.
ounction a is defined as o(x) = max(0, The ReLU layer vector-valued rectified linear activation function σę is defined σx(xx) (0(x1) (
Definition 3. The rectified linear unit (ReLU) activation function
[[xx)] where x = _ T2
Definition 4. Let i be any positive integer. A function g: R + R& is said be an l-layer
ReLU network if there exist weights W, E R and b, E RR for i E [1] such that the
input-output relationship of the network satisfies g(x) hy(x) where hx(x) Wix + b and
h;(x) = Wook. (h,-1 (x)) + bi every i E [1] [L].
Definition 5. The sum Σi= kj and the maximum maxte]L-11 ka for L 1 are referred to as the number of hidden neurons and the maximum width of an L-layer ReLU network, respectively. Any 1-layer ReLU network is said to have O hidden neurons and a maximum width of O. An l-layer ReLU network is said to have depth and I hidden layers.
3 Upper bounds on neural complexity for representing CPWL functions
The correspondence between CPWL functions and ReLU networks was first clearly confirmed by Theorem 2.1 in [Arora et 2018 although a weaker version of the correspondence can be inferred from Proposition 4.1 in Goodfellow et al. 2013]. Arora et al. (2018) proved that every ReLU network Rd - IR exactly represents a CPWL function, and the converse is also true, i.e., every CPWL function can be exactly represented by a ReLU network. One of the key steps used by Arora al. 2018 to construct ReLU network from any given CPWL function relies on an important representation result by Wang and Sun [2005), stating that any CPWL function can be represented by a sum finite number of max-1--afiine functions [Magnani and Boyd 2009] whose signs may be flipped and 1) is bounded from above by + 1 where 7/ the number of affine functions in the -afffie function. The implication of using this representation is later discussed in Section 4.] and its max-n--ffiiee functions given therein. The bound 17 S n + 1 in the representation allowed Arora et al. 2018 to further prove that there exists a ReLU DNN with at most
logg(n + 1)]
hidden layers to exactly realize any given CPWL function. However, the computational resource required for ReLU network to exactly represent any CPWL function had not been available in the literature until the work by He al. 22020.
3.1 Upper bounds in prior work
He et al. 2020 proved that a CPWL function R" + R with pieces and linear components can be represented by ReLU network whose number of neurons given by
f o (n2ky- (n2ter Lo o (n22g)
if k 11,
(2)
if <
The number of hidden layers in such a ReLU DNN is also bounded from above by [log (n + 1)],
which is the same as the bound derived by Arora et al. [2018). One of their significant contributions in our view is that they utilize the number of pieces and linear components of a CPWL function to bound the complexity of the equivalent ReLU network. He et al. 2020 also proved the relationship
5 k!
(3)
for any CPWL function. Note that the bounds in the number of pieces and linear components were first mentioned by Tarela and Martínez [999] who developed the lattice representation of are amplified
CPWL functions. Asymptotically, the bounds in (2) for l >
and h < linearly with the input dimension n for any fixed k. Due to (3). they can be further bounded from
above by (n29* (m+ and O (2229' in terms of q and n. On the other hand, in terms
of & and n, they can be further bounded from above by O (n+ and (12
5

---

Because these bounds grow much faster than exponential growth, they seem to suggest that the cost of computing CPWL function via ReLU network is exceptionally high.
Hertrich et al. 2021 proved that any CPWI. function I + R with & distinct linear components can be represented by ReLU network whose maximum width is O (12n2+30t] under the same number of hidden layers [log2(1 + 1)]. Hence, the number of hidden neurons must be bounded from above by
o Note that we infer this bound by taking the product of the depth and the maximum width. Using
( (n2n² 1n22n+ +3++1 log2 (n + +)).
I q. the bound in (4) can be expressed terms q, leading to O q2n 22**+n++ +3n+++ log, (n + 1)) Such
a bound can grow slower than (n29") but it grows faster than O (124*) if the input dimension
n grows sufficiently faster than the number of pieces Also, O A22m² +3++1 loga (n + 1) grows
faster than O (n2 when the input dimension grows sufficiently faster than the number of distinct linear components
3.2 Improved upper bounds
We show that any CPWL function can be represented by a ReLU network whose number hidden neurons is bounded by much slower growth functions. We state main results in Theorem 2 and 3 and focus on their impact in this subsection. Each one of them is tailored to a specific complexity measure of the CPWL function. Their proof sketches deferred to Section 4.22 We first focus on the case when the number of linear components is unknown and the complexity the CPWL is only measured by the number of pieces q-
Theorem 1. Any CPWL,functionn p: R" + R with q pieces be represented by a ReLU network whose number of layers I, maximum width w, and number of hidden neurons h satisfy
$ [log2 47 +
(5)
3q
w S [g > 1]
9.
(6)
2
and
h < (3 (3-2) 20 a 27 + [log q1 -3) -3) 9+ 3- 2
[log2 q1
Furthermore, Algorithm D finds such network poly (n, q, L) time where L the number of bits required to represent every entry of the rational matrix A; in the polyhedron representation {x E R. Axx < b;} of the piece X; for every E [g].
Algorithm 1 Find a ReLU network that computes a given continuous piecewise linear function Input: A CPWL. function p with pieces (Xi of Th satisfying Definition |
Output: A ReLU network g computing gxx) p(x), Vx E IR". fi, f2. ..... f& < run Algorithm to to find all distinct linear components of
2: for i = 1, 2, ... do
3:
A, +- 0
4:
for 1,2... k do
5:
if fx) ((x))p(ee pxx), Vx E X, then
6:
A; + A.U
7:
end end for
8:
9:
U; f- run Algorithm with {mmemee using the minimum type
10: end for
11: V + rum Algorithm with U1. U2
Combine ReLU networks in parallel
12: u < run Algorithm with { {[s]
82 8q H sm mElg]
using the maximum type
13: < run Algorithm with and
> Find ReLU network for the composition u o

---

The proof of Theorem T is deferred to Appendix [B.4 in the supplementary material. Algorithm
and 4 used by Algorithm aare deferred to Oppeeddi_[iim the supplementary material and
will be discussed soon after the discussion on bounds. Because 2 [log, < 2g. the upper bound in
(7) can be further bounded from above by 6u² + 2 flog2 q] q + 37 - [log2 9 3, leading to the asymptotic bound h = Og4²). Obviousl, = O (log2 v) and w = =O(²)) Since the bound given by
Theorem 5.2 in He et al. [2020] can be lower bounded by O (n22?² it grows exponentially faster than our bound of h given in Theorem] [ On the other hand, the upper bound given by (4) at least polynomially larger than our bound of f and the order of this polynomial grows quadratically with the input dimension n. Note that such a polynomial becomes an exponential function when the growth in is not slower than q. Such differences are illustrated by the figure the left-hand side of Figure I The bounds in Theorem T are independent of the input dimension n. Hence, one can realize any given CPWL function using a relatively small ReLU network even though is huge.
In terms of the maximum width, the upper bound given by 6 at least polynomially smaller than the one given by Hertrich et al. [202T]. In contrast to the bound for the number of layers in [Arora jet al., 2018 He et al. 2020 Hertrich et al. 202 that grows logarithmically with the input dimension n, our bound in Theorem grows logarithmically with the number of pieces q. Therefore, the ReLU network found by Algorithm iin general becomes deeper when the CPWL becomes more complex for a fixed input dimension. On the other hand, the network remains the same depth even for an arbitrarily larger n as long as q is fixed. Taking an affine function for example. a 1-layer ReLU However, the bound given by [Arora et al. 2018 He et al. 2020 Hertrich et al. [021] keeps increasing the depth for a larger n.
network with 0 hidden neurons is the solution given by Theorem [
We briefly explain algorithms used by Algorithm] 1 Algorithm 2 finds a ReLU network that computes Algorithm
a max-affine or min-affine function [Magnani and Boyd] 2009 2009
[3 coneatenates two given ReLU networks in parallel and returns another ReLU network computing the concatenation of two outputs. Algorithm 4 finds a ReLU network that represents a composition of two given ReLU networks. These algorithms are basic manipulations of ReLU networks. Algorithm iis polynomial time algorithm, following from the proof of Theorem
[
Table [ in Appendix C in the supplementary
material gives a complexity analysis for Algorithm
Notice that Algorithm dooes not need to be given any linear components or completely know the CPWL function because every distinct linear component can be found by Algorithm 6, which only needs to be given a closed c-ball in the interior of every piece of CPWL function p and observe the output of when feeding an input. Algorithm solves a system of linear equations for every piece of p to find the corresponding linear component. Every system of linear equations here has a unique solution because the interior of each of the pieces is nonempty. The nonemptyness is guaranteed by Lemma
12 aa in Appendix A in the supplementary material.
The 5th step of Algorithm| can be executed by checking the optimization result of the following linear programming problem
minimize [xxx)p(x))
subject to x X.
The condition in the 5th step can only be true when the optimal value is nonnegative. Because every piece of is given to Algorithm [] the piece X; is available for the linear program as a system of linear inequalities. The objective function is also available since p is affine on X, and all distinct linear components are available from Algorithm 6 The corresponding linear component of on X; can be found by first feeding at most n + 1 affinely independent points from the closed e-ball to p and every candidate linear component, and then matching their output values.
The ellipsoid method [Khachiyan| 1979]. the interior-point method (Karmarkar 1984]. and the path-following method [Renegar| 1988) are polynomial time algorithms for the linear programming problem using rational numbers on the Turing machine model of computation. These algorithms are also known to be weakly polynomial time algorithms. The strongly polynomial time algorithm requested by Smale's 9th problem [Smale] 1998), i.e., the linear programming problem, still an open question. Given that we run the 5th step of Algorithm [T by solving the linear programming problem in { Algorithm is a weakly polynomial time algorithm. The question of whether it is a strongly polynomial time algorithm is not known. The dependency on the number of bits I. in the time complexity of Algorithm [ directly comes from using (8) to execute the 5th step. practice, linear programming problems can be solved very reliably and efficiently [Boyd and Vandenberghe
7

---

10
10
101
Upper bound of
10:3
Upper bound of
10
Upper bound of
1013
10
10a
10P
10
109
10P
10
10
10
3
10
6
9
10
2
7
10
Figure 2: Left: The upper bound of / in Theorem grows much slower when grows sufficiently slower than leading to a much better upper bound compared to the worst-case asymptotic bound O [k- k!) in Theorem when is sufficiently larger. Middle: the bound in (4) inferred from Hertrich et al. 2021
Right: Theorem 5.2 in [H et al. 2020
2004]. We provide an implementation of Algorithm and measure its run time on a computer for different numbers of pieces and input dimensions in Appendix D in the supplementary material.
discusses the case when the number linear components and pieces are both known. Theorem 2. Any CPWL function p: R + R with k linear components and q pieces be represented by a ReLU network whose number of layers maximum width w, and number of hidden
Theorem 2
neurons satisfy S [log2 q) [log2 k] 1, w 1411 1
3k
q, and
h < (3 20g 8 + Togz k
logz a1 2 logz kl - 33
+ 3
(9)
Farthermore, Algorithm finds such network in poly (n, ki q, L) time where L is the number of bits required to represent every entry of the rational matrix A; in the polyhedron representation (x E R.
Axx x < b,} of the piece N, for every [g].
The proof of Theorem 2 is deferred to Appendix B.3 in the supplementary material. The bounds in Theorem are in general tighter and always no worse than those Theorem Tecause is never less than & but can be much larger than k. Asymptotically, / = Ologg 9). w = (kk)), and Okg)). The bound given by Theorem 5.2 in He al. 20200) increases exponentially faster than the bound of in Theorem 2
When the number of linear components is the only complexity measure of the CPWL function, resort to Theorem B below.
Theorem 3. Any CPWL function p: __ + IR with & linear components can be represented by ReLU network whase number of layers I maximum width w, and number of hidden neurons satisfy
1 S
[ogg ((n,k) ]m] [log2 k1 + 1, S T [ 1x>11
3k
((n,k) and
(3 [looo 1. + [logz k] - -3) Φ(n, k) + logo p(n,)) floga k7 -
h <
(10)
where
s(n, k) min
Σ ==
2
k!
(11)
The proof of Theorem is deferred to Appendix B.5 in the supplementary material. Because p(n, k) < kt. the worst-case asymptotic bounds for I, w and are 0 log, k). w 0 (k- k!), < 22", so the asymptotic
and h O (k k!), respectively. However, it holds that En (k2++1), and O (m2++1 when grows sufficiently slower
bounds are O (n log, k), than k. For example, n o VT In this case, w and are bounded from above by a polynomial
of order 2c + 1 for some constant c, which grows slower than factorial growth. Such an advantage for small is illustrated by the figure the left-hand side of Figure 2
Since the bound given by Theorem 5.2 in He al., 2020 can be bounded from below by O (n22-kt). it at the minimum grows exponentially larger than the upper bound of h in Theorem 3 Even for

---

small n, the relative order of growth is gigantic. The figure on the right-hand side of Figure 2 illustrates such a large difference. For k = 5, n2 7.92 10 when n = 1, while our bound of h is at most 3615 for any n. The difference is extremely large even though k is small under n 1.
The middle plot in Figure 2 shows that (4) increases much faster when n becomes larger. For l =
k222433+ log2 (n + 1) = 8.20 x 10 when n = 10, while our bound of h is at most 95 for any n. The upper bound of h in Theorem is much better than { for any and k.
Lemma 1. Let Pn, k. be the set of all CPWL.fuctionn with exactly distinct linear components such that p: _ + R. Vp E Pn,k. Let (p,)(p) be the collection of all families of closed convex subsets satisfying Definition 7 for any E Pa,k- Then, 1s S min Q S ((n, k).
The proof of Lemma is deferred to Appendix B.1 in the supplementary material. Clearly, ((n,, k) is a better upper bound of compared to the bound 4 S k! given by He et al. (2020). When grows sufficiently slower than k, the bound c(n, k) can be exponentially smaller than k!.
3.3 Limitations
Although these new bounds are significantly better than previous results, it is still possible to find a ReLU network whose hidden neurons are fewer than the bounds in Theorem 2 to exactly represent a given CPWL function. A tight bound for the case when n was first given by Theorem 2.2 in Arora et al., 2018). However, it seems more difficult to bound the size of network from below for n > 1. To the best our knowledge, we are not aware of any tight bounds in the literature for the size of the ReLU network representing general CPWL function using an arbitrary input dimension.
4 Representations of CPWL functions have different implications on depth
We reveal implications of using different representations of CPWL functions and their impact on constructing ReLU networks. We first discuss the popular representation used by prior work and the implicit constraint imposed by such a representation.
4.1 Constrained depth
Arora et al. 20088 He et al. 2020 and Hertrich et al. [202T] proved the same bound for the number of layers, relying on the following representation of CPWL. function
p(x)
Jy max f((x
(12)
.EN())
j=1
where o, E (+1,- -1} and n7) is subset of [J] such that |n(i)| S n + 1 for all j E [J]. That is, a sum of a finite number of max-n-affine functions whose signs may be flipped. (12) was established by Theorem in [Wang and Sun 2005] which is essentially the same as Theorem in [Wang] 2004] that emphasizes the difference between two convex piecewise linear functions. This result was also used by Goodffllow et al. (2013) to prove Proposition 4.1 in the maxout network paper.
The depth given by (1) does not scale with the complexity of CPWL function. This feature directly comes from using a Rel.U network to realize each of max-i)-affine functions in (12) and concatenating all of them together. Because the size of r)(j) is bounded from above by n + 1, the depth can be made to depend solely on n. Such a treatment seems to be the only way if one considers a CPWL function represented by (12) As result, the ReLU network is forced to use depth constrained by the input dimension to represent the given CPWL function, which in turn requires more hidden neurons. Because we do not use (2), our networks are not limited by such an implication.
4.2 Proof sketch for the unconstrained depth
We give a proof sketch in this subsection for our main results. By using a different representation, the depth of ReLU network is able to be scaled with the complexity measure, i.c., the number of pieces, of any given CPWL function to accommodate the high expressivity.
By Theorem 4.2 in (Tarela and Martinez 1999], any CPWL function p can be represented as
p(x)
max min f((x) XEQIEA(A (EA(())
(13)

---

for all x E R" where (A) = fie [R]] f(() 2 p(x), VX E 2} is the set of indices of linear components that have values greater than or equal to p(x) for all x E X, and Q is any family of closed convex subsets of K" satisfying Definition ! We have used f2. f& to denote the distinct linear components of p. Notice that Theorem 4.2 in [Tarela and Martínez 1999| was first stated by Theorem in [Tarela et al. 1990]. Both are essentially the same, but Theorem 4.2 in Taaela and Martínez, 1999 emphasizes the convexity of each of the regions in the domain. Both theorems are also fundamentally equivalent to Theorem 2.1 in [Ovchinnikov, 2002]. Notice that one of the concluding remarks in [Ovchinnikov] 2002] pointed out that the convexity of the input space is an essential assumption. The entire space I satisfies such an assumption. In addition, Ovchinnikov pointed out that the max-min representation also holds for vector-valued CPWI. functions. Hence, it possible to generalize our bounds to vector-valued CPWI. functions.
Using the representation in (13) and Lemma 2 below, we are able to prove Theorem by bounding the size of Q and A (X). Theorem and 3 can be proved by applying Lemmal I to Theorem 2 Note that the size [2] in 13 is the key for the depth of a ReLU network to be able to scale with q.
Lemma 2. Let m. be any positive integer. Define 1m)) and the following sequence for any positive integer k,
[log, m] + 1, w(m)
[m > 1] 2
0,
if k =
rlk)
3k 2
+
2
if k is even,
(14)
+
3(k-1)
k+1 2
if k + and is odd.
2
Then, there exists an 1mm)-layer ReLU network g: R² + R with r(m) hidden neurons and maximum width of wmm) such that computes the extremum of fx(x,, fx.x),....,.
i.e., g(x) max f((x) or g(x) (m) fi(x) for all x E Rh" under any m scalar-valued affine functions fI, 12, fm.. Furthermore, Algorithm 2 finds such network in poly(m, n)) time.
The proof of Lemma is deferred to Appendix B.2 in the supplementary material. One can also view 1(m), w(m), and r (m) as upper bounds for the number of layers, maximum width, and the number of hidden neurons. Because r(m) < 6m 3 by Lemma 6. the bound for the number of hidden neurons r rmm) is tighter than the bound 8m - given by Lemma D.3 in [Arora et al. 2018 or Lemma 5.4 in (He et al. 2020) (these two lemmas are essentially the same). The bound for the number of layers remains the same as the one given by Lemma D.3 in [Arora et al. 2018). By combining 2
Lemma with Lemma Lemma and Lemma
can easily perform the same job computing the extremum of multiple scalar-valued ReLU networks as Lemma D.3 does in [Arora et al. 2018
Lemma
6 3
and g are given in Appendix A in the supplementary material.
5 Broader impact
Our results guarantee that any CPWL function can be exactly computed by a ReLU neural network at more manageable cost. This assurance is crucial because CPWI. functions are important tools in many applications. Such an assurance also relates DNNs closer to CPWL functions and allows researchers and engineers to understand the expressivity of DNNs from differrntt perspective. We focus on simple ReLU networks (ReLU multi-layer perceptrons) in this paper, but it may be possible to derive bounds for other activation functions and advanced neural network architectures such as maxout networks [Goodfellow et al. 2013), residual networks (He et al. 2016). densely connected networks (Huang et al.]] 2017]. and other nonlinear networks (Chen al. [202]]. by making some (possibly mild) assumptions. Our contributions advance the fundamental understanding of the link between ReLU networks and CPWL. functions.
Acknowledgments and disclosure of funding
We would like to thank the anonymous reviewers for their constructive comments, Tai-Hsuan Chung for answering our mathematical questions, and Christoph Hertrich for his thoughtful comments on the time complexity of Algorithm [ and for clarifying Theorem 4.4 in [Hertrich et al. 202T]. This work was supported in part by NSF under Grant CCF-2225617, Grant CCF-2124929, and Grant 118-1838897, part by NIH/NIDCD under Grant DCIDC433666 and in part by KIBM Innovative Research Grant Award.
10

---

References
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Kian-Lin Chen, Ching- Huing-Hualue Lee, Harinath Garudadri, and Bhaskar D. Rao. ResNEsts and DenseNEsts: Block-based DNN models with improved representation guarantees. In Advances in Neural Information Processing Systems, pages 3413-3424, 2021.
Leon O. Chua and An-Chang Deng. Canonical piecewise- representation. IEEE Transactions on Circuits and Systems, 35(1): 101-111, 1988.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics Control, Signals and Systems, 2(4):303-314, 1989.
Ronen Eldan and Ohad Shamir: The power of depth for feedforward neural networks. In Conference on Learning Theory, pages 907-940. PMLR, 2016.
Kunihiko Fukushima. Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics, 36(4):193-202, 1980.
lan Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks. In International Conference Machine Learning, pages 1319-1327. PMLR, 2013.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pages 2596-2604. PMLR, 2019a.
Boris Hanin and David Rolnick. Deep ReLU networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, 2019b.
Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng. ReLU deep neural networks and linear finite elements. Journal of Computational Mathematics, 38(3):502-527, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference Computer Vision and Pattern Recognition, pages 770-778. IEEE, 2016.
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of ReLU neural networks. In Advances in Neural Information Processing Systems, 2021.
pages
Peter Hinz. An analysis of the piece-wise affine structure of ReLU feed-forrrrr neural networks. PhD thesis, ETH Zurich, 2021.
Peter Hinz and Sara van de Geer. A framework for the construction of upper bounds on the number of affine linear regions of relu feed-forward neural networks. IEEE Transactions on Information Theory, 65(11):7304 7324,, 2019.
Kurt Horiik Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Newral Networks, 2(5):359-366, 1989.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Conference on Computer Vision and Pattern Recognition, pages 4700-4708. IEEE, 2017.
Wen-Liang Hwang and Andreas Heinecke. Un-rectifying non-linear networks for signal representa- tion. IEEE Transactions on Signal Processing, 68: 196-210, 2019.
Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pages 302-311, 1984. Revised version: Combinatorica 4:373-395, 1984.
11

---

Leonid Genrikhovich Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk, 2496991093-1096, 1979. Translated in Soviet Mathematics Doklady 20(1):191-194, 1979.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, pages 1097-1105, 2012.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Advances in Neural Information Processing Systems, 2017.
Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural network acoustic models. In International Conference on Machine Learning, 2013.
Alessandro Magnani and Stephen P. Boyd. Convex piecewise-linens fitting. Optimization and Engineering, 10(1):1-17, 2009.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):52-533, 2015.
Guido Montúfar. Notes on the number of linear regions of deep neural networks. In International Conference on Sampling Theory and Applications, 2017.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances Neural Information Processing Systems, pages 2924-2932, 2014.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In International Conference on Machine Learning, pages 807-814, 2010.
Sergei Ovchinnikov. Max-min representation of piecewise linear functions. Contributions to Algebra and Geometry, 43(1 :927-302, 2002.
Razvan Pascanu, Guido Montúfar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. International Conference on Learning Representations, 2014.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning, pages 2847-2854. PMLR, 2017.
James Renegar. A polynomial time algorithm, based on Newton's 's method, for linear programming. Mathematical Programming, 40(1):59-93, 1988.
time
David Rolnick and Konrad Kording. Reverse-engincering deep ReLU networks. In International Conference on Machine Learning, pages 8178-8888 8187. PMLR, 2020.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional networks for biomedical image segmentation. In International Conference on Medical Image Computing and Computer Assisted Intervention, pages 234-241. Springer, 2015.
Thiago Serra, Christian Tjandraatmadja. and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pages 4558 4566. PMLR, 2018.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
12

---

Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer, 20(2): 7-15, 1998.
M. Tarela and M. V. Martínez. Region configurations for realizability of lattice piecewise- linea models. Mathematical and Computer Modelling, 30(11-12)117 1999.
J. M. Tarela, E. Alonso, and M. V. Martínez. A representation method for PWI. functions oriented to parallel processing. Mathematical and Computer Modelling, 13(10):75-83, 1990.
Matus Telgarsky. Benefits of depth neural networks. In Conference on Learning Theory, pages 1517-1539. PMLR, 2016.
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in approximating benign functions with neural networks. In Conference on Learning Theory, pages 4195-4223. PMLR, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Information Processing Systems, 2017.
Stephen A. Vavasis and Yinyu Ye. A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programmingg 74(1):79-120, 1996.
Shuning Wang. General constructive representations continuous piecewise-lineal functions. JEEE Transactions Circuits and Systems I: Regular Pupers, 51(9): 119):1889-1896 189--899, 2004.
Shuning Wang and Xusheng Sun. Generalization of hinging hyperplanes. IEEE Transactions Information Theory, 51(12):442544311 2005.
Thomas Zaslavsky. Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes, volume 154, American Mathematical Society, 1975.
Matthew D. Zeiler, Marc' Aurelio Ranzato, Rajat Monga, Min Mao, Kun Yang. Quoe V. Le, Patrick Nguyen, Alan Senior, Vincent Vanhoucke, Jeffrey Dean, and Geoffrey E. Hinton. On rectified linear units for speech processing. In International Conference on Acoustics, Speech and Signal Processing, pages 3517-3521. IEEE, 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] The main claims are summarized in Section 1.1
(b) Did you describe the limitations of your work? [Yes] See Section 3.3
(c) Did you discuss any potential negative societal impacts of your work? [No] This is theoretical paper and we are not aware of any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All definitions and assumptions stated or referenced before the results.
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix B in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "f_wDlbG3OC7", "reviewer": "Reviewer_WJTP", "summary": "In this paper the authors provide bounds for approximating a continuous piecewise linear function by a ReLU function. \n\nWhen compared to previous work, the bounds provided by the authors are tighter. Furthermore, the bounds provided by the authors only depend upon the total number of linear components in the CPWL (unlike previous work). This helps when the growth in the number of dimensions is faster than the number of linear components. The authors are able to do this because they make use of a different representation of a CPWL function (as mentioned in equation 13). \n\nThe authors also provide an algorithm for finding a ReLU network that computes the given a CPWL. However, this algorithm requires one to know how many linear components are present in the function beforehand, and uses the fact that the final function is a combination of smaller ReLU function approximating the linear components.", "questions": "I think giving a sketch of what Algorithms 2, 3 and 4 do in the main text—even if it is just a sketch will improve the readability of the paper. ", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and motivated and provides a rigorous proof for improving of bounds for approximating CPWL functions with neural network. The authors have done an amazing job at motivating and explaining their results as well as placing their work with the related work (which is very well explained). I really enjoyed reading the paper. \n\nA possible drawback is that Algorithm 1 assumes that the number of linear components in the function is known beforehand. Is there a way that this assumption could be relaxed in a way? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ae1S7CQgPdW", "reviewer": "Reviewer_LuVg", "summary": "The paper focuses on neural networks with ReLU activations. For these networks, the paper proposes bounds on the number of neurons needed to represent continuous piecewise linear functions (CPWL). These bounds are derived in terms of the number of linear pieces and the number of distinct linear components of the CPWL. In contrast to prior work, which proposed exponential bounds, the paper shows that quadratic bounds in the number of pieces are enough.", "questions": "**For the rebuttal**\n* Can Algorithm 1 be used in practice? What is the computational complexity of the algorithm?\n\n**Questions**\n* L11: Why is the invariance wrt the input dimension more important than the quadratic bounds?\n* L100: “q is always not less than k” -> $k \\leq q$\n", "limitations": "Theoretical work, no direct negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* The paper significantly improves previous bounds, which enables much more accurate estimates of the number of neurons needed.\n\n### Weaknesses\n* It is unclear whether Algorithm 1 can be used in practice. Also, the run time and the computational complexity of the algorithm are unclear.\n**Clarity**\n* Definition 4: ReLU network should be called ReLU-Multi Layer Perceptron. A general ReLU network is a network with only ReLU activations. A ResNet can also be a ReLU network. Hence, in the Broader impact chapter, it’s confusing that the text says “We focus on ReLU networks in this paper, but it is possible to derive bounds with similar asymptotic growth rates for other neural network architectures such as … residual networks …, densely connected networks …\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4bMck8ZCeIT", "reviewer": "Reviewer_snmk", "summary": "Summary. The authors study the representation of continuous piecewise linear (CPWL) functions using neural networks with ReLU activations. They showed that, for Any CPWL function with q pieces or k linear components, it can be represented by a ReLU network\nwith certain layers l, maximum width w, and the number of hidden neurons h. The bounds in this paper are much better than in previous papers. The algorithm for constructing such networks is also given.", "questions": "It would be interesting to extend the results to more general network architectures.", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The related works are adequately cited. The novelty of this paper is high. The results on the sharp bound of number of hidden neurons needed to representing CPWL functions in this paper, will certainly help us have a better understating of representation power of 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 the machine learning immunity. \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.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept