Preprint version

B OUNDING AND C OUNTING L INEAR R EGIONS
D EEP N EURAL N ETWORKS

arXiv:1711.02114v2 [cs.LG] 6 Jan 2018

Thiago Serra & Christian Tjandraatmadja
Tepper School of Business
Carnegie Mellon University
tserra@cmu.edu, ctjandra@andrew.cmu.edu

OF

Srikumar Ramalingam
School of Computing
The University of Utah
srikumar@cs.utah.edu

A BSTRACT
In this paper, we study the representational power of deep neural networks (DNN)
that belong to the family of piecewise-linear (PWL) functions, based on PWL
activation units such as rectifier or maxout. We investigate the complexity of
such networks by studying the number of linear regions of the PWL function.
Typically, a PWL function from a DNN can be seen as a large family of linear
functions acting on millions of such regions. We directly build upon the work
of Montúfar et al. (2014), Montúfar (2017), and Raghu et al. (2017) by refining the
upper and lower bounds on the number of linear regions for rectified and maxout
networks. In addition to achieving tighter bounds, we also develop a novel method
to perform exact enumeration or counting of the number of linear regions with a
mixed-integer linear formulation that maps the input space to output. We use this
new capability to visualize how the number of linear regions change while training
DNNs.

1

I NTRODUCTION

We have witnessed an unprecedented success of deep learning algorithms in computer vision,
speech, and other domains (Krizhevsky et al., 2012; Ciresan et al., 2012; Goodfellow et al., 2013;
Hinton et al., 2012). While the popular deep learning architectures such as AlexNet (Krizhevsky
et al., 2012), GoogleNet (Szegedy et al., 2015), and residual networks (He et al., 2016) have shown
record beating performance on various image recognition tasks, empirical results still govern the
design of network architecture in terms of depth and activation functions. Two important practical
considerations that are part of most successful architectures are greater depth and the use of PWL
activation functions such as rectified linear units (ReLUs). Due to the large gap between theory
and practice, many researchers have been looking at the theoretical modeling of the representational
power of DNNs (Cybenko, 1989; Anthony & Bartlett, 1999; Pascanu et al., 2014; Montúfar et al.,
2014; Bianchini & Scarselli, 2014; Eldan & Shamir, 2016; Telgarsky, 2015; Mhaskar et al., 2016;
Raghu et al., 2017; Montúfar, 2017).
Any continuous function can be approximated to arbitrary accuracy using a single hidden layer
of sigmoid activation functions (Cybenko, 1989). This does not imply that shallow networks are
sufficient to model all problems in practice. Typically, shallow networks require exponentially more
number of neurons to model functions that can be modeled using much fewer activation functions in
deeper ones (Delalleau & Bengio, 2011). There have been a wide variety of activation functions such
as threshold (f (z) = (z > 0)), logistic (f (z) = 1/(1 + exp(−e))), hyperbolic tangent (f (z) =
tanh(z)), rectified linear units (ReLUs f (z) = max{0, z}), and maxouts (f (z1 , z2 , . . . , zk ) =
max{z1 , z2 , . . . , zk }). The activation functions offer different modeling capabilities. For example,
sigmoid networks are shown to be more expressive than similar-sized threshold networks (Maass
et al., 1994). It was recently shown that ReLUs are more expressive than similar-sized threshold
networks by deriving transformations from one network to another (Pan & Srikumar, 2016).
The complexity of neural networks belonging to the family of PWL functions can be analyzed by
looking at how the network can partition the input space to an exponential number of linear response
regions (Pascanu et al., 2014; Montúfar et al., 2014). The basic idea of a PWL function is simple:
we can divide the input space into several regions and we have individual linear functions for each
1

Preprint version

of these regions. Functions partitioning the input space to a larger number of linear regions are
considered to be more complex ones, or in other words, possess better representational power. In the
case of ReLUs, it was shown that deep networks separate their input space into exponentially more
linear response regions than their shallow counterparts despite using the same number of activation
functions (Pascanu et al., 2014). The results were later extended and improved (Montúfar et al.,
2014; Raghu et al., 2017; Montúfar, 2017; Arora et al., 2016). In particular, Montúfar et al. (2014)
shows both upper and lower bounds on the maximal number of linear regions for a ReLU DNN
and a single layer maxout network, and a lower bound for a maxout DNN. Furthermore, Raghu
et al. (2017) and Montúfar (2017) improve the upper bound for a ReLU DNN. This upper bound
asymptotically matches the lower bound from Montúfar et al. (2014) when the number of layers
and input dimension are constant and all layers have the same width. Finally, Arora et al. (2016)
improves the lower bound by providing a family of ReLU DNN S with an exponential number of
regions given fixed size and depth.
In this work, we directly improve on the results of Montúfar et al. (Pascanu et al., 2014; Montúfar
et al., 2014; Montúfar, 2017) and Raghu et al. (Raghu et al., 2017) in better understanding the
representational power of DNNs employing PWL activation functions.

2

N OTATIONS AND BACKGROUND

We will only consider feedforward neural networks in this paper. Let us assume that the network
has n0 input variables given by x = {x1 , x2 , . . . , xn0 }, and m output variables given by y =
{y1 , y2 , . . . , ym }. Each hidden layer l = {1, 2, . . . , L} has nl hidden neurons whose activations are
given by hl = {hl1 , hl2 , . . . , hlnl }. Let W l be the nl × nl−1 matrix where each row corresponds to
the weights of a neuron of layer l. Let bl be the bias vector used to obtain the activation functions
of neurons in layer l. Based on the ReLU(x) = max{0, x} activation function, the activations of
the hidden neurons and the outputs are given below:
h1

=

max{0, W 1 x + b1 }

l

h

=

max{0, W l hl−1 + bl }

y

=

W L+1 hL

As considered in Pascanu et al. (2014), the output layer is a linear layer that computes the linear
combination of the activations from the previous layer without any ReLUs.
We can treat the DNN as a piecewise linear (PWL) function F : Rn0 → Rm that maps the input x
in Rn0 to y in Rm . This paper primarily deals with investigating the bounds on the linear regions of
this PWL function. There are two subtly different definitions for linear regions in the literature and
we will formally define them.
Definition 1. Given a PWL function F : Rn0 → Rm , a linear region is defined as a maximal
connected subset of the input space Rn0 , on which F is linear (Pascanu et al., 2014; Montúfar
et al., 2014).
Activation Pattern: Let us consider an input vector x = {x1 , x2 , . . . , xn0 }. For every layer l we
define an activation set S l ⊆ {1, 2, . . . , nl } such that e ∈ S l if and only if the ReLU e is active,
that is, hle > 0. We aggregate these activation sets into a set S = (S 1 , . . . , S l ), which we call an
activation pattern. Note that we may consider activation patterns up to a layer l ≤ L. Activation
patterns were previously defined in terms of strings (Raghu et al., 2017; Montúfar, 2017).
We say that an input x corresponds to an activation pattern S in a DNN if feeding x to the DNN
results in the activations in S.
Definition 2. Given a PWL function F : Rn0 → Rm represented by a DNN, a linear region is the
set of input vectors x that corresponds to an activation pattern S in the DNN.
We prefer to look at linear regions as activation patterns and we interchangeably refer to S as an
activation pattern or a region. Definitions 1 and 2 are essentially the same, except in a few degenerate
cases. There could be scenarios where two different activation patterns may correspond to two
adjacent regions with the same linear function. In this case, Definition 1 will produce only one
linear region whereas Definition 2 will yield two linear regions. This has no effect on the bounds
that we derive in this paper.
2

Preprint version

In Fig. 1(a) we show a simple ReLU DNN with two inputs {x1 , x2 } and 3 hidden layers.

Figure 1: (a) Simple DNN with two inputs and three hidden layers with 2 activation units each. (b),
(c), and (d) Visualization of the hyperplanes from the first, second, and third hidden layers respectively partitioning the input space into several linear regions. The arrows indicate the directions
in which the corresponding neurons are activated. (e), (f), and (g) Visualization of the hyperplanes
from the first, second, and third hidden layers in the space given by the outputs of their respective
previous layers.
The activation units {a, b, c, d, e, f } in the hidden layers can be thought of as hyperplanes that each
divide the space in two. On one side of the hyperplane, the unit outputs a positive value. For all
points on the other side of the hyperplane including itself, the unit outputs 0.
One may wonder: into how many regions do n hyperplanes split a space? Zaslavsky (1975)
 shows
Pd
that an arrangement of n hyperplanes divides a d-dimensional space into at most s=0 ns regions,
a bound that is attained when they are in general position. The term general position basically
means that a small perturbation of the hyperplanes does not change the number of regions. This
corresponds to the exact maximal number of regions of a single layer DNN with n ReLUs and input
dimension d.
In Figs. 1(b)–(g), we provide a visualization of how ReLUs partition the input space. Figs. 1(e),
(f), and (g) show the hyperplanes corresponding to the ReLUs at layers l = 1, 2, and 3 respectively.
Figs. 1(b), (c), and (d) consider these same hyperplanes in the input
 space
 x. In Fig. 1(b), as per
Zaslavsky (1975), the 2D input space is partitioned into 4 regions ( 20 + 21 + 22 = 4). In Figs. 1(c)
and (d), we add the hyperplanes from the second and third layers respectively, which are affected
by the transformations applied in the earlier hidden layers. The regions are further partitioned as we
consider additional layers.
Fig. 1 also highlights that activation boundaries behave like hyperplanes when inside a region and
may bend whenever they intersect with a boundary from a previous layer. This has also been pointed
out by Raghu et al. (2017). In particular, they cannot appear twice in the same region as they are
defined by a single hyperplane if we fix the region. Moreover, these boundaries do not need to be
connected, as illustrated in Fig. 2.
Main Contributions
We summarize the main contributions of this paper below:
• We achieve tighter upper and lower bounds on the maximal number of linear regions of
the PWL function corresponding to a DNN that employs ReLUs. As a special case, we
3

Preprint version

Figure 2: (a) A network with one input x1 and three activation units a, b, and c. (b) We show the
hyperplanes x1 = 0 and −x1 + 1 = 0 corresponding to the two activation units in the first hidden
layer. In other words, the activation units are given by ha = max{0, x1 } and hb = max{0, −x1 +
1}. (c) The activation unit in the third layer is given by hc = max{0, 4ha + 2hb − 3}. (d) The
activation boundary for neuron c is disconnected.

present the exact maximal number of regions when the input dimension is one. We additionally provide the first upper bound on the number of linear regions for multi-layer
maxout networks (See Sections 3 and 4).
• We show for ReLUs that the exact maximal number of linear regions of shallow networks
is larger than that of deep networks if the input dimension exceeds the number of neurons.
This result is particularly interesting, since it cannot be inferred from the bounds derived in
prior work.
• We use a mixed-integer linear formulation to show that exact counting of the linear regions
is indeed possible. For the first time, we show the exact counting of the number of linear
regions for several small-sized DNNs during the training process. This new capability
can be used to evaluate the tightness of the bounds and potentially analyze the correlation
between validation accuracy and the number of linear regions. It also provides new insights
as to how the linear regions vary during the training process (See Section 5 and 6).

3

T IGHTER BOUNDS FOR RECTIFIER NETWORKS

Montúfar et al. (2014) derive an upper bound of 2N for N hidden units, which can be obtained by
mapping linear regions to activation patterns. Raghu et al. (2017) improves this result by deriving
an asymptotic upper bound of O(nLn0 ) to the maximal number of regions, assuming nl = n for
QL Pdl nl 
all layers l and n0 = O(1). Montúfar (2017) further tightens the upper bound to l=1 j=0
j ,
where dl = min{n0 , n1 , . . . , nl }.
Q
P

L−1
n0
nL
n0
Moreover, Montúfar et al. (2014) prove a lower bound of
bn
/n
c
when
l
0
l=1
j=0 j
n ≥ n0 , or asymptotically
Ω((n/n0 )(L−1)n0 nn0 ). Arora et al. (2016) present a lower bound of
Pn0 −1 m−1 L−1
2 j=0
w
where 2m = n1 and w = nl for all l = 2, . . . , L. By choosing m and w
j
appropriately, this lower bound is Ω(sn0 ) where s is the total size of the network. We derive both
upper and lower bounds that improve upon these previous results.
3.1

A N UPPER BOUND ON THE NUMBER OF LINEAR REGIONS

In this section, we prove the following upper bound on the number of regions.
4

Preprint version

Theorem 1. Consider a deep rectifier network with L layers, nl rectified linear units at each layer
l, and an input of dimension n0 . The maximal number of regions of this neural network is at most
L  
X
Y
nl
jl
(j1 ,...,jL )∈J l=1

where J = {(j1 , . . . , jL ) ∈ ZL : 0 ≤ jl ≤ min{n0 , n1 − j1 , . . . , nl−1 − jl−1 , nl } ∀l = 1, . . . , L}.
This bound is tight when L = 1.
Note that this is a stronger upper bound than the one that appeared in Montúfar (2017), which can
be derived from this bound by relaxing the terms nl − jl to nl and factoring the expression. When
n0 = O(1) and all layers have the same width n, this expression has the same best known asymptotic
bound O(nLn0 ) first presented in Raghu et al. (2017).
Two insights can be extracted from the above expression:
1. Bottleneck effect. The bound is sensitive to the positioning of layers that are small relative
to the others, a property we call the bottleneck effect. If we subtract a neuron from one
of two layers with the same width, choosing the one closer to the input layer will lead to
a larger (or equal) decrease in the bound. This occurs because each index jl is essentially
limited by the widths of the current and previous layers, n0 , n1 , . . . , nl . In other words,
smaller widths in the first few layers of the network imply a bottleneck on the bound.
In particular for a 2-layer network, we show in Appendix A that if the input dimension is
sufficiently large to not create its own bottleneck, then moving a neuron from the first layer
to the second layer strictly decreases the bound, as it tightens a bottleneck.
Figure 3a illustrates this behavior. For the solid line, we keep the total size of the network
the same but shift from a small-to-large network (i.e., smaller width near the input layer
and larger width near the output layer) to a large-to-small network in terms of width. We
see that the bound monotonically increases as we reduce the bottleneck. If we add a layer
of constant width at the end, represented by the dashed line, the bound decreases when the
layers before the last become too small and create a bottleneck for the last layer.
While this is a property of the upper bound rather than one of the exact maximal number
of regions, we observe in Section 6 that empirical results for the number of regions of a
trained network exhibit a behavior that resembles the bound as the width of the layers vary.
2. Deep vs shallow for large input dimensions. In several applications such as imaging, the
input dimension can be very large. Montúfar et al. (2014) show that if the input dimension
n0 is constant, then the number of regions of deep networks is asymptotically larger than
that of shallow (single-layer) networks. We complement this picture by establishing that
if the input dimension is large, then shallow networks can attain more regions than deep
networks.
More precisely, we compare a deep network with L layers of equal width n and a shallow
network with one layer of width Ln. In Appendix A, we show using Theorem 1 that if
the input dimension n0 exceeds the size of the network Ln, then the ratio between the
exact maximal number of regions of the deep and of the shallow network goes to zero as L
approaches infinity.
We also show in Appendix A that in a 2-layer network, if the input dimension n0 is larger
than both widths n1 and n2 , then turning it into a shallow network with a layer of n1 + n2
ReLUs increases the exact maximal number of regions.
Figure 3b illustrates this behavior. As we increase the number of layers while keeping
the total size of the network constant, the bound plateaus at a value lower than the exact
maximal number of regions for shallow networks. Moreover, the number of layers that
yields the highest bound decreases as we increase the input dimension n0 .
It is important to note that this property cannot be inferred from previous upper bounds
derived in prior work, since they are at least 2N when n0 ≥ max{n1 , . . . , nL }, where N
is the total number of neurons.
We remark that asymptotically both deep and shallow networks can attain exponentially
many regions when the input dimension is at least n (see Appendix B).
5

Preprint version

·1018
1x60
2x30
3x20
4x15
5x12
6x10

1
Bound

Bound

10

23

1016

0.5

Five parameterized layers
Extra layer with 16 neurons

109
−5

0

5

0

5

10

k

15

20

25

30
n0

35

40

45

50

55

60

(b)

(a)

Figure 3: Bounds from Theorem 1: (a) is in semilog scale, has input dimension n0 = 32, and the
width of the first five layers is 16 − 2k, 16 − k, 16, 16 + k, 16 + 2k; (b) is in linear scale, evenly
distributes 60 neurons in 1 to 6 layers (the single-layer case is exact), and the input dimension varies.
We now build towards the proof of Theorem 1. For a given activation set S l and a matrix W with
nl rows, let σS l (W ) be the operation that zeroes out the rows of W that are inactive according
to S l . This represents the effect of the ReLUs. For a region S at layer l − 1, define W̄Sl :=
W l σS l−1 (W l−1 ) · · · σS 1 (W 1 ).
Each region S at layer l − 1 may be partitioned by a set of hyperplanes defined by the neurons of
layer l. When viewed in the input space, these hyperplanes are the rows of W̄Sl x + b = 0 for some b.
To verify this, note that, if we recursively substitute out the hidden variables hl−1 , . . . , h1 from the
original hyperplane W l hl−1 + bl = 0 following S, the resulting weight matrix applied to x is W̄Sl .
Finally, we define the dimension of a region S at layer l − 1 as dim(S) :=
rank(σS l−1 (W l−1 ) · · · σS 1 (W 1 )). This can be interpreted as the dimension of the space corresponding to S that W l effectively partitions.
The proof of Theorem 1 focuses on the dimension of each region S. A key observation is that once
it falls to a certain value, the regions contained in S cannot recover to a higher dimension.
Zaslavsky (1975) showed that the maximal number of regions in Rd induced by an arrangement of m
Pd
hyperplanes is at most j=0 m
j . Moreover, this value is attained if and only if the hyperplanes are
in general position. The lemma below tightens this bound for a special case where the hyperplanes
may not be in general position.
Lemma 2. Consider m hyperplanes in Rd defined by the rows of W x + b = 0. Then the number of
Prank(W ) m
regions induced by the hyperplanes is at most j=0
j .
The proof is given in Appendix C. Its key idea is that it suffices to count regions within the row
space of W . The next lemma brings Lemma 2 into our context.
Lemma 3. The number of regions induced by the nl neurons at layer l within a certain region S is
Pmin{n ,dim(S)} nl 
at most j=0 l
j .
Proof. The hyperplanes in a region S of the input space are given by the rows of W̄Sl x +
b = 0 for some b.
By the definition of W̄Sl , the rank of W̄Sl is upper bounded
l
by min{rank(W ), rank(σS l−1 (W l−1 ) · · · σS 1 (W 1 ))} = min{rank(W l ), dim(S)}. That is,
rank(W̄Sl ) ≤ min{nl , dim(S)}. Applying Lemma 2 yields the result.
In the next lemma, we show that the dimension of a region S can be bounded recursively in terms
of the dimension of the region containing S and the number of activated neurons defining S.
Lemma 4. Let S be a region at layer l and S 0 be the region at layer l − 1 that contains it. Then
dim(S) ≤ min{|S l |, dim(S 0 )}.
Proof. dim(S) = rank(σS l (W l ) · · · σS 1 (W 1 )) ≤ min{rank(σS l (W l )), rank(σS l−1 (W l−1 ) · · ·
σS 1 (W 1 )) ≤ min{|S l |, dim(S 0 )}. The last inequality comes from the fact that the zeroed out rows
do not count towards the rank of the matrix.
6

Preprint version

In the remainder of the proof of Theorem 1, we combine Lemmas 3 and 4 to construct a recurrence
R(l, d) that bounds the number of regions within a given region of dimension d. Simplifying this
recurrence yields the expression in Theorem 1. We formalize this idea and complete the proof of
Theorem 1 in Appendix D.
As a side note, Theorem 1 can be further tightened if the weight matrices are known to have small
Pmin{rank(W l ),dim(S)} nl 
rank. The bound from Lemma 3 can be rewritten as j=0
j if we do not relax
rank(W l ) to nl in the proof. The term rank(W l ) follows through the proof of Theorem 1 and the
index set J in the theorem becomes {(j1 , . . . , jL ) ∈ ZL : 0 ≤ jl ≤ min{n0 , n1 − j1 , . . . , nl−1 −
jl−1 , rank(W l )} ∀l ≥ 1}.
A key insight from Lemmas 3 and 4 is that the dimensions of the regions are non-increasing as we
move through the layers partitioning it. In other words, if at any layer the dimension of a region
becomes small, then that region will not be able to be further partitioned into a large number of
regions. For instance, if the dimension of a region falls to zero, then that region will never be further
partitioned. This suggests that if we want to have many regions, we need to keep dimensions high.
We use this idea in the next section to construct a DNN with many regions.
3.2

T HE CASE OF DIMENSION ONE

If the input dimension n0 is equal to 1 and nl = n for all layers l, the upper bound presented in the
previous section reduces to (n + 1)L . On the other hand, the lower bound given by Montúfar et al.
(2014) becomes nL−1 (n + 1). It is then natural to ask: are either of these bounds tight? The answer
is that the upper bound is tight in the case of n0 = 1, assuming there are sufficiently many neurons.
Theorem 5. Consider a deep rectifier network with L layers, nl ≥ 3 rectified linear units at each
layer l, and an input of dimension 1. The maximal number of regions of this neural network is
QL
exactly l=1 (nl + 1).
The expression above is a simplified form of the upper bound from Theorem 1 in the case n0 = 1.
The proof of this theorem in Appendix E has a construction with n + 1 regions that replicate themselves as we add layers, instead of n as in Montúfar et al. (2014). That is motivated by an insight
from the previous section: in order to obtain more regions, we want the dimension of every region
to be as large as possible. When n0 = 1, we want all regions to have dimension one. This intuition
leads to a new construction with one additional region that can be replicated with other strategies.
3.3

A LOWER BOUND ON THE MAXIMAL NUMBER OF LINEAR REGIONS

Both the lower bound from Montúfar et al. (2014) and from Arora et al. (2016) can be slightly
improved, since their approaches are based on extending a 1-dimensional construction similar to the
one in Section 3.2. We do both since they are not directly comparable: the former bound is in terms
of the number of neurons in each layer and the latter is in terms of the total size of the network.
Theorem 6. The maximal number of linear regions induced by a rectifier network with n0 input
units and L hidden layers with nl ≥ 3n0 for all l is lower bounded by
 n0 ! X

n0 
L−1
Y  nl 
nL
+1
.
n0
j
j=0
l=1

The proof of this theorem is in Appendix F. For comparison, the differences between the lower
bound theorem (Theorem 5) from Montúfar et al. (2014) and the above theorem is the replacement
of the condition nl ≥ n0 by the more restrictive nl ≥ 3n0 , and of bnl /n0 c by bnl /n0 c + 1.
Theorem 7. For any values of m ≥ 1 and w ≥ 2, there exists a rectifier
network with n0 input units
Pn0 −1 m−1
and L hidden layers of size 2m + w(L − 1) that has 2 j=0
(w
+ 1)L−1 linear regions.
j
The proof of this theorem is in Appendix G. The differences between Theorem 2.11(i) from Arora
et al. (2016) and the above theorem is the replacement of w by w + 1. They construct a 2m-width
layer with many regions and use a one-dimensional construction for the remaining layers.
7

Preprint version

4

A N UPPER BOUND ON THE NUMBER OF LINEAR REGIONS FOR MAXOUT
NETWORKS

We now consider a deep neural network composed of maxout units. Given weights Wjl for j =
1, . . . , k, the output of a rank-k maxout layer l is given by
hl

=

max{W1l hl−1 + bl1 , . . . , Wkl hl−1 + blk }

In terms of bounding number of regions, a major difference between the next result for maxout units
and the previous one for ReLUs is that reductions in dimensionality due to inactive neurons with
zeroed output become a particular case now. Nevertheless, using techniques similar to the ones from
Section 3.1, the following theorem can be shown (see Appendix H for the proof).
Theorem 8. Consider a deep neural network with L layers, nl rank-k maxout units at each layer l,
and an input of dimension n0 . The maximal number of regions of this neural network is at most
dl  k(k−1) 
L X
Y
nl
2
j
j=0
l=1

where dl = min{n0 , n1 , . . . , nl }.
Asymptotically, if nl = n for all l = 1, . . . , L, n ≥ n0 , and n0 = O(1), then the maximal number
of regions is at most O((k 2 n)Ln0 ).

5

E XACT COUNTING OF LINEAR REGIONS

If the input space x ∈ Rn0 is bounded by minimum and maximum values along each dimension,
or else if x corresponds to a polytope more generally, then we can define a mixed-integer linear
formulation mapping polyhedral regions of x to the output space y ∈ Rm . The assumption that x is
bounded and polyhedral is natural in most applications, where each value xi has known lower and
upper bounds (e.g., the value can vary from 0 to 1 for image pixels). Among other things, we can
use this formulation to count the number of linear regions.
In the formulation that follows, we use continuous variables to represent the input x, which we
can also denote as h0 , the output of each neuron i in layer l as hli , and the output y as hL+1 .
To simplify the representation, we lift this formulation to a space that also contains the output of
a complementary set of neurons, each of which is active when the corresponding neuron is not.
l
Namely, for each neuron i in layer l we also have a variable hi := max{0, −Wil hl−1 − bli }. We use
binary variables of the form zil to denote if each neuron i in layer l is active or else if the complement
of such neuron is. Finally, we assume M to be a sufficiently large constant.
For a given neuron i in layer l, the following set of constraints maps the input to the output:
l

l

l

Wil hl−1 + bli = hli − hi , hli ≤ M zil , hi ≤ M (1 − zil ), hli ≥ 0, hi ≥ 0, zil ∈ {0, 1}
|wil hl−1
j

bli |

(1)

l−1

Theorem 9. Provided that
+
≤ M for any possible value of h , a formulation with
the set of constraints (1) for each neuron of a rectifier network is such that a feasible solution with a
fixed value for x yields the output y of the neural network.
The proof for the statement above is given in Appendix I. More details on the procedure for exact
counting are in Appendix J. In addition, we show the theory for unrestricted inputs and a mixedinteger formulation for maxout networks in Appendices K and L, respectively.
These results have important consequences. First, they allow us to tap into the literature of mixedinteger representability (Jeroslow, 1987) and disjunctive programming (Balas, 1979) to understand
what can be modeled on rectifier networks with a finite number of neurons and layers. To the best
of our knowledge, that has not been discussed before. Second, they imply that we can use mixedinteger optimization solvers to analyze the (x, y) mapping of a trained neural network. For example,
Cheng et al. (2017) use another mixed-integer formulation to generate adversarial examples of a
DNN. That is technically feasible due to the linear proportion between the size of the neural network
and that of the mixed-integer formulation. Compared to Cheng et al. (2017), we show in Appendix I
that formulation (1) can be implemented with further refinements on the value of the M constants.
8

Preprint version

6

E XPERIMENTS

We perform two different experiments for region counting using small-sized networks with ReLU
activation units on the MNIST benchmark dataset (LeCun et al., 1998). In the first experiment, we
generate rectifier networks with 1 to 4 hidden layers having 10 neurons each, with final test error
between 6 and 8%. The training was carried out for 20 epochs or training steps, and we count
the number of linear regions during each training step. For those networks, we count the number
of linear regions within 0 ≤ x ≤ 1 in which a single neuron is active in the output layer, hence
partitioning these regions in terms of the digits that they classify. In Fig. 4, we show how the number
of regions classifying each digit progresses during training. Some digits have zero linear regions in
the beginning, which explains why they begin later in the plot. The total number of such regions
per training step is presented in Fig. 5(a) and error measures are found in Appendix M. Overall, we
observe that the number of linear regions jumps orders of magnitude are varies more widely for each
added layer. Furthermore, there is an initial jump in the number of linear regions classifying each
digit that seems proportional to the number of layers.

108

108

(1x10)

108

(2x10)

108

(3x10)

106

106

106

106

104

104

104

104

102

102

102

102

100

100
0

5

10

15

20

100
0

5

10

15

20

(4x10)

100
0

5

10

15

20

0

5

10

15

20

1010

1010

4x10
3x10
2x10
1x10

108

108
Linear regions

Linear regions with single output neuron

Figure 4: Total number of regions classifying each digit (different colors for 0-9) of MNIST alone as
training progresses, each plot corresponding to a different number of hidden layers.

106
104

106
104
Bound from Montúfar et al. (2014)
Bound from Montúfar (2017)
Bound from Theorem 1
Exact count of sample networks

102

102

100

100
0

5

(a)

10

15

20

1;21;10

Training step

6;16;10

(b)

11;11;10

16;6;10

21;1;10

Neurons on each layer

Figure 5: (a) Total number of linear regions classifying a single digit of MNIST as training progresses, each plot corresponding to a different number of hidden layers. (b) Comparison of upper
bounds from Montúfar et al. (2014), Montúfar (2017), and from Theorem 1 with the total number of
linear regions of a network with two hidden layers totaling 22 neurons.

In the second experiment, we train rectifier networks with two hidden layers summing up to 22
neurons. We train a network for each width configuration under the same conditions as above, with
the test error in half of them ranging from 5 to 6%. In this case, we count all linear regions within
0 ≤ x ≤ 1, hence not restricting by activation in output layer as before. The number of linear regions
of these networks are plotted in Fig. 5(b), along with the upper bound from Theorem 1 and the upper
bounds from Montúfar et al. (2014) and Montúfar (2017). Error measures of both experiments can
be found in Appendix M and runtimes for counting the linear regions in Appendix N.
9

Preprint version

7

D ISCUSSION

The representational power of a DNN can be studied by observing the number of linear regions of
the PWL function that the DNN represents. In this work, we improve on the upper and lower bounds
on the linear regions for rectified networks derived in prior work (Montúfar et al., 2014; Raghu et al.,
2017; Montúfar, 2017; Arora et al., 2016) and introduce a first upper bound for multi-layer maxout
networks. We obtain several valuable insights from our extensions.
Our ReLU upper bound indicates that small widths in early layers cause a bottleneck effect on the
number of regions. If we reduce the width of an early layer, the dimensions of the linear regions become irrecoverably smaller throughout the network and the regions will not be able to be partitioned
as much. Moreover, the dimensions of the linear regions are not only driven by width, but also
the number of activated ReLUs corresponding to the region. This intuition allowed us to create a
1-dimensional construction with the maximal number of regions by eliminating a zero-dimensional
bottleneck. An unexpected and useful consequence of our result is that shallow networks can attain
more linear regions when the input dimensions exceed the number of neurons of the DNN.
In addition to achieving tighter bounds, we use a mixed-integer linear formulation that maps the
input space to the output to show the exact counting of the number of linear regions for several
small-sized DNNs during the training process. In the first experiment, we observed that the number
of linear regions correctly classifying each digit of the MNIST benchmark increases and vary in
proportion to the depth of the network during the first training epochs. In the second experiment, we
count the total number of linear regions as we vary the width of two layers with a fixed number of
neurons, and we experimentally validate the bottleneck effect by observing that the results follow a
similar pattern to the upper bound that we show.
Our current results suggest new avenues for future research. First, we believe that the study of linear
regions may eventually lead to insights in how to design better DNNs in practice, for example by
further validating the bottleneck effect found in this study. Other properties of the bounds may turn
into actionable insights if confirmed as these bounds get sufficiently close to the actual number of
regions. For example, the plots in Appendix O show that there are particular network depths that
maximize our ReLU upper bound for a given input dimension and number of neurons. In a sense,
the number of neurons is a proxy to the computational resources available. We also believe that
analyzing the shape of the linear regions is a promising idea for future work, which could provide
further insight in how to design DNNs. Another important line of research is to understand the exact
relation between the number of linear regions and accuracy, which may also involve the potential
for overfitting. We conjecture that the network training is not likely to generalize well if there are
so many regions that each point can be singled out in a different region, in particular if regions with
similar labels are unlikely to be compositionally related. Second, applying exact counting to larger
networks would depend on more efficient algorithms or on using approximations instead. In any
case, the exact counting at a smaller scale can assess the quality of the current bounds and possibly
derive insights for tighter bounds in future work, hence leading to insights that could be scaled up.

R EFERENCES
M. Anthony and P. Bartlett. Neural network learning: Theoretical foundations. 1999.
R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified
linear units. CoRR, abs/1611.01491, 2016.
E. Balas. Disjunctive programming. Annals of Discrete Mathematics, (5):3–51, 1979.
E. Balas, S. Ceria, and G. Cornuéjols. A lift-and-project cutting plane algorithm for mixed 0–1
programs. Mathematical Programming, 58:295–324, 1993.
M. Bianchini and F. Scarselli. On the complexity of neural network classifiers: A comparison
between shallow and deep architectures. IEEE Transactions on Neural Networks and Learning
Systems, 2014.
J. D. Camm, A. S. Raturi, and S. Tsubakitani. Cutting big M down to size. Interfaces, 20(5):61–66,
1990.
10

Preprint version

C.-H. Cheng, G. Nührenberg, and H. Ruess. Maximum resilience of artificial neural networks. In
D. D’Souza and K. Narayan Kumar (eds.), Proceedings of ATVA, pp. 251–268, 2017.
D. Ciresan, U. Meier, J. Masci, and J. Schmidhuber. Multi column deep neural network for traffic
sign classification. Neural Networks, 32:333–338, 2012.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control,
Signals and Systems, 2(4):303–314, 1989.
E. Danna, M. Fenelon, Z. Gu, and R. Wunderling. Generating multiple solutions for mixed integer
programming problems. In M. Fischetti and D. P. Williamson (eds.), Proceedings of IPCO, pp.
280–294. Springer, 2007.
O. Delalleau and Y. Bengio. Shallow vs. deep sum-product networks. In NIPS, 2011.
R. Eldan and O. Shamir. The power of depth for feedforward neural networks. In Conference on
Learning Theory, pp. 907–940, 2016.
J.B.J. Fourier. Solution dune question particuliére du calcul des inégalités. Nouveau Bulletin des
Sciences par la Société Philomatique de Paris, pp. 317–319, 1826.
I.J. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, and Y. Bengio. Maxout networks. In
ICML, 2013.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
G. Hinton, L. Deng, G.E. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen,
T. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal Processing Magazine, 2012.
R.G. Jeroslow. Representability in mixed integer programming, I: Characterization results. Discrete
Applied Mathematics, 17(3):223 – 243, 1987.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional
neural networks. In NIPS, 2012.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
W. Maass, G. Schnitger, and E.D. Sontag. A comparison of the computational power of sigmoid
and boolean threshold circuits. Theoretical Advances in Neural Computation and Learning, pp.
127–151, 1994.
H. Mhaskar, Q. Liao, and T. A. Poggio. Learning real and boolean functions: When is deep better
than shallow. CoRR, abs/1603.00988, 2016.
G. Montúfar. Notes on the number of linear regions of deep neural networks. In SampTA, 2017.
G. Montúfar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural
networks. In NIPS, 2014.
X. Pan and V. Srikumar. Expressiveness of rectifier networks. In ICML, 2016.
R. Pascanu, G. Montúfar, and Y. Bengio. On the number of response regions of deep feedforward
networks with piecewise linear activations. In ICLR, 2014.
M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, and J. Sohl-Dickstein. On the expressive power of
deep neural networks. In ICML, 2017.
J. Stirling. Methodus Differentialis sive Tractatus de Summatione et Interpolatione Serierum Infinitarum. G. Strahan, London, 1730.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In CVPR, 2015.
M. Telgarsky. Representation benefits of deep feedforward networks. CoRR, abs/1509.08101, 2015.
T. Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. American Mathematical Society, 1975.
11

Preprint version

Appendices
Most of the proofs for theorems and lemmas associated with the upper and lower bounds on the
linear regions are provided below. The theory for mixed-integer formulation for exact counting in
the case of maxouts and unrestricted inputs are also provided below.

A

A NALYSIS OF THE BOUND FROM T HEOREM 1

In this section, we present properties of the upper bound for the number of regions of a rectifier
network from Theorem 1. Denote the bound by B(n0 , n1 , . . . , nL ), where n0 is the input dimension
and n1 , . . . , nL are the widths of layers 1 through L of the network. That is,
L  
X
Y
nl
B(n0 , n1 , . . . , nL ) :=
jl
(j1 ,...,jL )∈J l=1

Instead of expressing J as in Theorem 1, we rearrange it to a more convenient form for the proofs
in this section:
J = {(j1 , . . . , jL ) ∈ ZL :jl + jk ≤ nk ∀k = 1, . . . , l − 1 ∀l = 2, . . . , L
jl ≤ n0 ∀l = 1, . . . , L
0 ≤ jl ≤ nl ∀l = 1, . . . , L}.
Note that whenever we assume n0 ≥ max{n1 , . . . , nl }, then the bound inequality for n0 becomes
redundant and can be removed.
Some of the results have implications in terms of the exact maximal number of regions. We denote
it by R(n0 , n1 , . . . , nL ), following the same notation above.
Moreover, the following lemma is useful throughout the section.
Lemma 10.

    
k 
X
X
n1 + . . . + nL
n1
n2
nL
=
···
.
j
j
j
jL
1
2
j=0
j1 +...+jL ≤k
0≤jl ≤nl ∀l

Proof. The result comes from taking a generalization of Vandermonde’s identity and adding the
summation of j from 0 to k as above.
We first examine some properties related to 2-layer networks. The proposition below characterizes
the bound when L = 2 for large input dimensions.
Proposition 11. Consider a 2-layer network with widths n1 , n2 and input dimension n0 ≥ n1 and
n0 ≥ n2 . Then

n1 
X
n1 + n2
B(n0 , n1 , n2 ) =
j
j=0
Pn1 n1 +n2 
If n0 < n1 or n0 < n2 , the above holds with inequality: B(n0 , n1 , n2 ) ≤ j=0
.
j
Proof. If n0 ≥ n1 and n0 ≥ n2 , the bound inequalities for n0 in the index set J become redundant.
By applying Lemma 10, we obtain

   X
n1 
X
n1 + n2
n1
n2
.
B(n0 , n1 , n2 ) =
=
j1
j2
j
j=0
0≤j1 +j2 ≤n1
0≤jl ≤nl ∀l

If n0 < n1 or n0 < n2 , then its index set J is contained by the one above, and thus the first equal
sign above becomes a less-or-equal sign.
12

Preprint version

Recall that the expression on the right-hand side of Proposition 11 is equal to the maximal number
of regions of a single-layer network with n1 + n2 ReLUs and input dimension n1 , as discussed in
Section 2. Hence, the proposition implies that for large input dimensions, a two-layer network has
no more regions than a single-layer network with the same number of neurons, as formalized below.
Corollary 12. Consider a 2-layer network with widths n1 , n2 ≥ 1 and input dimension n0 ≥ n1
and n0 ≥ n2 . Then R(n0 , n1 , n2 ) ≤ R(n0 , n1 + n2 ).
Moreover, this inequality is strict when n0 > n1 .
Proof. This is a direct consequence of Proposition 11:
 X

n1 
n0 
X
n1 + n2
n1 + n2
R(n0 , n1 , n2 ) ≤ B(n0 , n1 , n2 ) =
≤
= R(n0 , n1 + n2 ).
j
j
j=0
j=0
Note that if n0 > n1 , then the second inequality can be turned into a strict inequality.
The next corollary illustrates the bottleneck effect for two layers. It states that for large input dimensions, moving a neuron from the second layer to the first strictly increases the bound.
Corollary 13. Consider a 2-layer network with widths n1 , n2 and input dimension n0 ≥ n1 + 1
and n0 ≥ n2 + 1. Then B(n0 , n1 + 1, n2 ) > B(n0 , n1 , n2 + 1).
Proof. By Proposition 11,
B(n0 , n1 + 1, n2 ) =

nX
1 +1 
j=0

(n1 + 1) + n2
j


>


n1 
X
n1 + (n2 + 1)
j

j=0

= B(n0 , n1 , n2 + 1).

The assumption that n0 must be large is required for the above proposition; otherwise, the input
itself may create a bottleneck with respect to the second layer as we decrease its size. Note that the
bottleneck affects all subsequent layers, not only the layer immediately after it.
However, it is not true that moving neurons to earlier layers always increases the bound. For instance,
with three layers, B(4, 3, 2, 1) = 47 > 46 = B(4, 4, 1, 1).
In the remainder of this section, we consider deep networks of equal widths n. The next proposition
can be viewed as an extension of Proposition 11 for multiple layers. It states that for a network with
widths and input dimension n and at least 4 layers, if we halve the number of layers and redistribute
the neurons so that the widths become 2n, then the bound increases. In other words, if we assume
the bound to be close to the maximal number of regions, it suggests that making a deep network
shallower allows for more regions when the input dimension is equal to the width.
Proposition 14. Consider a 2L-layer network with equal widths n and input dimension n0 = n.
Then
B(n, n, . . . , n) ≤ B(n, 2n, . . . , 2n).
| {z }
| {z }
2L times

L times

This inequality is met with equality when L = 1 and strict inequality when L ≥ 2.
Proof. When n0 = n, the inequalities jl ≤ min{n0 , 2n − j1 , . . . , 2n − jl−1 , 2n} appearing in J
(in the form presented in Theorem 1) can be simplified to jl ≤ n. Therefore, using Lemma 10, the
bound on the right-hand side becomes



L

 L
n X
n
n Y
L 
n 
n n−j
X
X
X
X
X1  n  n 
2n
2n
 =

...
=
B(n, 2n, . . . , 2n) =
| {z }
jl
j
j1
j2
j =0 j =0
j =0
j=0
j =0 j =0
1

L times

≥

2

X

L

l=1

1

2L  
Y
n
= B(n, n, . . . , n).
| {z }
jl

(j1 ,...,j2L )∈J l=1

2L times

13

2

Preprint version

where J above is the index set from Theorem 1 applied to n0 = nl = n for all l = 1, . . . , 2L.
Note that we can turn the inequality into equality when L = 1 (also becoming a consequence of
Proposition 11) and into strict inequality when L ≥ 2.
Next, we provide an upper bound that is independent of n0 .
Proposition 15. Consider an L-layer network with equal widths n and any input dimension n0 ≥ 0.
B(n0 , n, . . . , n) ≤ 2Ln



1
1
+ √
2 2 πn

L/2

√

2

Proof. Since we are deriving an upper bound, we can assume n0 ≥ n, as the bound is nondecreasing
on n0 . We first assume that L is even. We relax some of the constraints of the index set J from
Theorem 1 and apply Vandermonde’s identity on each pair:
B(n0 , n, . . . , n) ≤

n n−j
n n−j
X1  n  n  X
X3  n  n 
X

j1
j2


 L/2
n 
X
2n

=
=
j
j=0
j1 =0 j2 =0

Ln



=2

1
1
+ √
2 2 πn

j3 =0 j4 =0

22n +
2

j3
2n
n

j4

···

n−jL−1

n
X
jL−1 =0



 !L/2

≤

22n +

X  n  n 
jL−1
jL
jL =0
L/2
2n

2
√

πn

2



L/2
.


The bound on 2n
n is a direct application of Stirling’s approximation (Stirling, 1730). If L is odd,
then we can write

 



 L/2
 (L−1)/2 X
n 
n  
n 
X
X
2n
2n
n
2n

=


B(n0 , n, . . . , n) ≤ 

1/2
Pn
j
j
j
2n
j=0

j=0

j=0

j=0

j





 L/2
 L/2
n 
n 
n
X
X
√
2n 
2
2n 
≤
=
2
2n
1/2
j
j
(2 /2)
j=0
j=0
≤ 2Ln



1
1
+ √
2 2 πn

L/2

√

2

where the last inequality is analogous to the even case. Hence, the result follows.
Corollary 16. Consider an L-layer network with equal widths n and any input dimension n0 ≥ 0.
R(n0 , n, . . . , n)
=0
L→∞
2Ln
lim

Proof. By Proposition 15 and Theorem 1, the ratio between R(n0 , n, . . . , n) and 2Ln is at most
q
L√
√
1
√1
2. Since the base of the first term is less than 1 for all n ≥ 1 and 2 is a constant,
2 + 2 πn
the ratio goes to 0 as L goes to infinity.
In particular, Corollary 16 implies that if n0 exceeds the total size of the network, that is, n0 ≥ Ln,
0 ,n,...,n)
then limL→∞ R(n
R(n0 ,Ln) = 0. In other words, the ratio between the maximal number of regions of
a deep network and a shallow network goes to zero as L goes to infinity.
14

Preprint version

B

E XPONENTIAL MAXIMAL NUMBER OF REGIONS WHEN INPUT DIMENSION
IS LARGE

Proposition 17. Consider an L-layer rectifier network with equal widths n and input dimension
2
n0 ≥ n/3. Then the maximal number of regions is Ω(2 3 Ln ).
Proof. It suffices to show that a lower bound such as the one from Theorem 6 grows exponentially
QL
large. For simplicity, we consider the lower bound ( l=1 (bnl /n0 c + 1))n0 , which is the bound
obtained before the last tightening step in the proof of Theorem 6 (see Appendix F).
Note that replacing n0 in the above expression by a value n00 smaller than the input dimension still
yields a valid lower bound. This holds because increasing the input dimension of a network from n00
to n0 cannot decrease its maximal number of regions.
Choose n00 = bn/3c, which satisfies n00 ≤ n0 and the condition n ≥ 3n00 of Theorem 6. The
lower bound can be expressed as (bn/bn/3cc + 1)Lbn/3c ≥ 4Lbn/3c . This implies that the maximal
2
number of regions is Ω(2 3 Ln ).

C

P ROOF OF L EMMA 2

Lemma 2. Consider m hyperplanes in Rd defined by the rows of W x + b = 0. Then the number of
Prank(W ) m
regions induced by the hyperplanes is at most j=0
j .
Proof. Consider the row space R(W ) of W , which is a subspace of Rd of dimension rank(W ).
We show that the number of regions NRd in Rd is equal to the number of regions NR(W ) in R(W )
induced by W x + b = 0 restricted to R(W ). This suffices to prove the lemma since R(W ) has at
Prank(W ) m
most j=0
j regions according to Zaslavsky’s theorem.
Since R(W ) is a subspace of Rd , it directly follows that NR(W ) ≤ NRd . To show the converse, we
apply the orthogonal decomposition theorem from linear algebra: any point x̄ ∈ Rd can be expressed
uniquely as x̄ = x̂ + y, where x̂ ∈ R(W ) and y ∈ R(W )⊥ . Here, R(W )⊥ = Ker(W ) := {y ∈
Rd : W y = 0}, and thus W x̄ = W x̂ + W y = W x̂. This means x̄ and x̂ lie on the same side of each
hyperplane of W x = b and thus belong to the same region. In other words, given any x̄ ∈ Rd , its
region is the same one that x̂ ∈ R(W ) lies in. Therefore, NRd ≤ NR(W ) . Hence, NRd = NR(W )
and the result follows.

D

P ROOF OF T HEOREM 1

Theorem 1. Consider a deep rectifier network with L layers, nl rectified linear units at each layer
l, and an input of dimension n0 . The maximal number of regions of this neural network is at most
L  
X
Y
nl
jl
(j1 ,...,jL )∈J l=1

where J = {(j1 , . . . , jL ) ∈ ZL : 0 ≤ jl ≤ min{n0 , n1 − j1 , . . . , nl−1 − jl−1 , nl } ∀l = 1, . . . , L}.
This bound is tight when L = 1.
Proof. As illustrated in Figure 1, the partitioning can be viewed as a sequential process: at each
layer, we partition the regions obtained from the previous layer. When viewed in the input space,
each region S obtained at layer l − 1 is potentially partitioned by nl hyperplanes given by the rows
of W̄Sl + b = 0 for some bias b. Some of these hyperplanes may fall outside the interior of S and do
not partition the region.
With this process in mind, we recursively bound the number of subregions within a region. More
precisely, we construct a recurrence R(l, d) to be an upper bound to the maximal number of regions
obtained from partitioning a region of dimension d with layers l, l + 1, . . . , L. The base case of
15

Preprint version

Pmin{n ,d} nL 
the recurrence is given by Lemma 3: R(L, d) = j=0 L
j . Based on Lemma 4, we can
write the recurrence
by
grouping
together
regions
with
the
same
activation
set size |S l |, as follows:
Pnl
R(l, d) = j=0 Nnl ,d,j R(l + 1, min{j, d}) for all l = 1, . . . , L − 1. Here, Nnl ,d,j represents the
maximum number of regions with |S l | = j obtained by partitioning a space of dimension d with nl
hyperplanes. We bound this value next.

For each j, there are at most njl regions with |S l | = j, as they can be viewed as subsets of nl
Pmin{n ,d} nl 
neurons of size j. In total, Lemma 3 states that there are at most j=0 l
j regions. If we
l
allow theseregions to have the highest |S | possible, for each j from 0 to min{nl , d} we have at
l
most nln−j
= njl regions with |S l | = nl − j.
Therefore, we can write the recurrence as

min{nl ,d}  

X

nl


R(l + 1, min{nl − j, d}) if 1 ≤ l ≤ L − 1,


j

 j=0
R(l, d) =


min{nL ,d} 


X
nL



if l = L.


j
j=0

The recurrence R(1, n0 ) can be unpacked to

min{n1 ,d1 }   min{n2 ,d2 }  
min{nL ,dL } 
X
X
X
n1
n2
nL
···
j1
j2
jL
j =0
j =0
j =0
1

2

L

where dl = min{n0 , n1 − j1 , . . . , nl−1 − jl−1 }. This can be made more compact, resulting in the
final expression.

Pmin{n ,n }
The bound is tight when L = 1 since it becomes j=0 0 1 nj1 , which is the maximal number
of regions of a single-layer network.

E

P ROOF OF T HEOREM 5

Theorem 5. Consider a deep rectifier network with L layers, nl ≥ 3 rectified linear units at each
layer l, and an input of dimension 1. The maximal number of regions of this neural network is
QL
exactly l=1 (nl + 1).
Proof. Section 3 provides us with a helpful insight to construct an example with a large number of
regions. It tells us that we want regions to have large dimension in general. In particular, regions of
dimension zero cannot be further partitioned. This suggests that the one-dimensional construction
from Montúfar et al. (2014) can be improved, as it contains n regions of dimension one and 1 region
of dimension zero. This is because all ReLUs point to the same direction as depicted in Fig. 6,
leaving one region with an empty activation pattern.
Our construction essentially increases the dimension of this region from zero to one. This is done
by shifting the neurons forward and flipping the direction of the third neuron, as illustrated in Fig. 6.
We assume n ≥ 3.
We review the intuition behind the construction strategy from Montúfar et al. (2014). They construct
a linear function h̃ : R → R with a zigzag pattern from [0, 1] to [0, 1] that is composed of n
ReLUs. More precisely, h̃(x) = (1, −1, 1, . . . , ±1)> (h1 (x), h2 (x), . . . , hn (x)), where hi (x) for
i = 1, . . . , n are ReLUs. This linear function can be absorbed in the preactivation function of the
next layer.
The zigzag pattern allows it to replicate in each slope a scaled copy of the function in the domain
[0, 1]. Fig. 7 shows an example of this effect. Essentially, when we compose h̃ with itself, each
linear piece in [t1 , t2 ] such that h̃(t1 ) = 0 and h̃(t2 ) = 1 maps the entire function h̃ to the interval
[t1 , t2 ], and each piece such that h̃(t1 ) = 1 and h̃(t2 ) = 2 does the same in a backward manner.
16

Preprint version

Figure 6: (a) The 1D construction from Montúfar et al. (2014). All units point to the right, leaving
a region with dimension zero before the origin. (b) The 1D construction described in this section.
Within the interval [0, 1] there are five regions instead of the four in (a).

Figure 7: A function with a zigzag pattern composed with itself. Note that the entire function is
replicated within each linear region, up to a scaling factor.

In our construction, we want to use n ReLUs to create n + 1 regions instead of n. In other words,
we want the construct this zigzag pattern with n + 1 slopes. In order to do that, we take two
steps to give ourselves more freedom. First, observe that we only need each linear piece to go
from zero to one or one to zero; that is, the construction works independently of the length of each
piece. Therefore, we turn the breakpoints into parameters t1 , t2 , . . . , tn , where 0 < t1 < t2 <
. . . < tn < 1. Second, we add sign and bias parameters to the function h̃. That is, h̃(x) =
(s1 , s2 , . . . , sn )> (h1 (x), h2 (x), . . . , hn (x)) + d, where si ∈ {−1, +1} and d are parameters to be
set. Here, hi (x) = max{0, w̃i x + b̃i } since it is a ReLU.
We define wi = si w̃i and bi = si b̃i , which are the weights and biases we seek in each interval to
form the zigzag pattern. The parameters si are needed because the signs of w̃i cannot be arbitrary: it
must match the directions the ReLUs point towards. In particular, we need a positive slope (w̃i > 0)
if we want i to point right, and a negative slope (w̃i < 0) if we want i to point left. Hence, without
loss of generality, we do not need to consider the si ’s any further since they will be directly defined
from the signs of the wi ’s and the directions. More precisely, si = 1 if wi ≥ 0 and si = −1
otherwise for i = 1, 2, 4, . . . , n, and s3 = −1 if w3 ≥ 0 and s3 = 1 otherwise.
To summarize, our parameters are the weights wi and biases bi for each ReLU, a global bias d, and
the breakpoints 0 < t1 < . . . < tn < 1. Our goal is to find values for these parameters such that
each piece in the function h̃ with domain in [0, 1] is linear from zero to one or one to zero.
1
s
1
More precisely, if the domain is [s, t], we want each linear piece to be either t−s
x− t−s
or − t−s
x+
t
t−s , which define linear functions from zero to one and from one to zero respectively. Since we
want a zigzag pattern, the former should happen for the interval [ti , ti−1 ] when i is odd and the latter
should happen when i is even.

There is one more set of parameters that we will fix. Each ReLU corresponds to a hyperplane, or
a point in dimension one. In fact, these points are the breakpoints t1 , . . . , tn . They have directions
that define for which inputs the neuron is activated. For instance, if a neuron hi points to the right,
then the neuron hi (x) outputs zero if x ≤ ti and the linear function wi x + bi if x > ti .
17

Preprint version

As previously discussed, in our construction all neurons point right except for the third neuron h3 ,
which points left. This is to ensure that the region before t1 has one activated neuron instead of
zero, which would happen if all neurons pointed left. However, although ensuring every region
has dimension one is necessary to reach the bound, not every set of directions yields valid weights.
These directions are chosen so that they admit valid weights.
The directions of the neurons tells us which neurons are activated in each region. From left to right,
we start with h3 activated, then we activate h1 and h2 as we move forward, we deactivate h3 , and
finally we activate h4 , . . . , hn in sequence. This yields the following system of equations, where
tn+1 is defined as 1 for simplicity:
w3 x + (b3 + d) =

1
x
t1

(R1 )

1
t2
x+
(R2 )
t2 − t1
t2 − t1
t2
1
x−
(R3 )
(w1 + w2 + w3 ) x + (b1 + b2 + b3 + d) =
t3 − t2
t3 − t2
1
t4
(w1 + w2 ) x + (b1 + b2 + d) = −
x+
(R4 )
t4 − t3
t4 − t3



 (
ti−1
i−1
i−1
1
X
X
if i is odd
ti −ti−1 x − ti −ti−1
w1 + w2 +



wj x + b1 + b2 +
bj + d =
− ti −t1i−1 x + ti −ttii−1 if i is even
(w1 + w3 ) x + (b1 + b3 + d) = −

j=4

j=4

(Ri )
for all i = 5, . . . , n + 1
It is left to show that there exists a solution to this system of linear equations such that 0 < t1 <
. . . < tn < 1.
First, note that all of the biases b1 , . . . , bn , d can be written in terms of t1 , . . . , tn . Note that if we
subtract (R4 ) from (R3 ), we can express b3 in terms of the ti variables. The remaining equations
become triangular, and therefore given any values for ti ’s we can back-substitute the remaining bias
variables.
The same subtraction yields w3 in terms of ti ’s. However, both (R1 ) and (R3 ) − (R4 ) define w3 in
terms of the ti variables, so they must be the same:
1
1
1
=
+
.
t1
t3 − t2
t4 − t3
If we find values for ti ’s satisfying this equation and 0 < t1 < . . . < tn < 1, all other weights can
be obtained by back-substitution since eliminating w3 yields a triangular set of equations.
2i−1
1
and ti = 2n+1
for all i = 2, . . . , n. The
In particular, the following values are valid: t1 = 2n+1
remaining weights and biases can be obtained as described above, which completes the desired
construction.

As an example, a construction with four units is depicted in Fig. 6. Its breakpoints are t1 = 19 ,
3
t2 = 93 , t3 = 59 , and t4 = 79 . Its ReLUs are h1 (x) = max{0, − 27
2 x + 2 }, h2 (x) =
max{0, 9x − 3}, h3 (x) = max{0, 9x − 5}, and h4 (x) = max{0, 9x}. Finally, h̃(x) =
(−1, 1, −1, 1)> (h1 (x), h2 (x), h3 (x), h4 (x)) + 5.

F

P ROOF OF T HEOREM 6

Theorem 6. The maximal number of linear regions induced by a rectifier network with n0 input
units and L hidden layers with nl ≥ 3n0 for all l is lower bounded by
 n0 ! X

n0 
L−1
Y  nl 
nL
+1
.
n0
j
j=0
l=1

18

Preprint version

Proof. We follow the proof of Theorem 5 from (Montúfar et al., 2014) except that we use a different
1-dimensional construction. The main idea of the proof is to organize the network into n0 independent networks with input dimension 1 each and apply the 1-dimensional construction to each individual network. In particular, for each layer l we assign bnl /n0 c ReLUs to each network, ignoring
QL
any remainder units. In (Montúfar et al., 2014), each of these networks have at least l=1 bnl /n0 c
QL
regions. We instead use Theorem 5 to attain l=1 (bnl /n0 c + 1) regions in each network.
Since the networks are independent from each other, the number of activation patterns of the compound network is the product of the number of activation patterns of each of the n0 networks. Hence,
the same holds for the number of regions. Therefore, the number of regions of this network is at
QL
least ( l=1 (bnl /n0 c + 1))n0 .
In addition, we can replace the last layer by a functionP
representing
 an arrangement of nL hypern0
nL
planes in general position that partitions (0, 1)n0 into j=0
regions. This yields the lower
j
QL−1
Pn0 nL 
n0
bound of l=1 (bnl /n0 c + 1)
j=0 j .

G

P ROOF OF T HEOREM 7

Theorem 7. For any values of m ≥ 1 and w ≥ 2, there exists a rectifier
network with n0 input units
Pn0 −1 m−1
and L hidden layers of size 2m + w(L − 1) that has 2 j=0
(w
+ 1)L−1 linear regions.
j
Proof. Theorem 6.1 and Lemma 6.2 in Arora et al. (2016) imply that for any m ≥ 1, we can
Pn0 −1 m−1
construct a layer representing a function from Rn to R with 2m ReLUs that has 2 j=0
j
regions. Consider the network where this layer is the first one and the remaining layers are the onedimensional layers
from Theorem 5, each of size w. Then this network has size 2m + w(L − 1) and
Pn0 −1 m−1
2 j=0
(w + 1)L−1 regions.
j

H

P ROOF OF T HEOREM 8

Theorem 8. Consider a deep neural network with L layers, nl rank-k maxout units at each layer l,
and an input of dimension n0 . The maximal number of regions of this neural network is at most
dl  k(k−1) 
L X
Y
nl
2
j
j=0
l=1

where dl = min{n0 , n1 , . . . , nl }.
Asymptotically, if nl = n for all l = 1, . . . , L, n ≥ n0 , and n0 = O(1), then the maximal number
of regions is at most O((k 2 n)Ln0 ).
Proof. We denote by Wjl the nl × nl−1 matrix where the rows are given by the j-th weight vectors
of each rank-k maxout unit at layer l, for j = 1, . . . , k. Similarly, blj is the vector composed of the
j-th biases at layer l.
In the case of maxout, an activation pattern S = (S 1 , . . . , S l ) is such that S l is a vector that maps
from layer-l neurons to {1, . . . , k}. We say that the activation of a neuron is j if wj x + bj attains
the maximum among all of its functions; that is, wj x + bj ≥ wj 0 x + bj 0 for all j 0 = 1, . . . , j. In the
case of ties, we assume the function with lowest index is considered as its activation.
Similarly to the ReLU case, denote by φS l : Rnl ×nl−1 ×k → Rnl ×nl−1 the operator that selects the
rows of W1l , . . . , Wkl that correspond to the activations in S l . More precisely, φS l (W1l , . . . , Wkl ) is
a matrix W such that its i-th row is the i-th row of Wjl , where j is the neuron i’s activation in S l .
This essentially applies the maxout effect on the weight matrices given an activation pattern.
Pn0 k2 n
Montúfar et al. (2014) provides an upper bound of j=0
for the number of regions for a
j
single rank-k maxout layer with n neurons. The reasoning is as follows. For a single maxout unit,
19

Preprint version

there is one region per linear function. The boundaries between the regions are composed by pieces
that are each contained in a hyperplane. Each piece is part of the boundary of at least two regions
and conversely each pair of regions corresponds to at most one piece. Extending these pieces into
hyperplanes cannot decrease the number of regions. Therefore, if we now consider n maxout units
in a single layer, we can have at most the number of regions of an arrangement of k 2 n hyperplanes.
In the results below we replace k 2 by k2 , as only pairs of distinct functions need to be considered.

We need to define more precisely these k2 n hyperplanes in order to apply a strategy similar to the
one from the Section 3.1. In a single layer setting, they are given by wj x + bj = wj 0 + bj 0 for each

distinct pair j, j 0 within a neuron. In order to extend this to multiple layers, consider a k2 nl × nl−1
matrix Ŵl where its rows are given by wj − wj 0 for every distinct pair j, j 0 within a neuron i and for
every neuron i = 1, . . . , nl . Given a region S, we can now write the weight matrix corresponding to
the hyperplanes described above: ŴSl := Ŵ l φS l−1 (W1l−1 , . . . , Wkl−1 ) · · · φS 1 (W11 , . . . , Wk1 ). In
other words, the hyperplanes that extend the boundary pieces within region S are given by the rows
of ŴSl x + b = 0 for some bias b.
A main difference between the maxout case and the ReLU case is that the maxout operator φ does
not guarantee reductions in rank, unlike the ReLU operator σ. We show the analogous of Lemma 3
for the maxout case. However, we fully relax the rank.
Lemma 18. The number of regions induced by the nl neurons at layer l within a certain region S
k(k−1)
Pdl
nl 
2
is at most j=0
, where dl = min{n0 , n1 , . . . , nl }.
j
Proof. For a fixed region S, an upper bound is given by the number of regions of the hyperplane
arrangement corresponding to ŴSl x + b = 0 for some bias b. The rank of ŴSl is upper bounded by
rank(ŴSl ) = rank(Ŵ l φS l−1 (W1l−1 , . . . , Wkl−1 ) · · · φS 1 (W11 , . . . , Wk1 ))
≤ min{rank(Ŵ l ), rank(φS l−1 (W1l−1 , . . . , Wkl−1 )), . . . , rank(φS 1 (W11 , . . . , Wk1 ))}
≤ min{n0 , n1 , . . . , nl }.
Applying Lemma 2 yields the result.
Since we can consider the partitioning of regions independently from each other, Lemma 18 implies
k(k−1)
QL Pdl
nl 
2
that the maximal number of regions of a rank-k maxout network is at most l=1 j=0
j
where dl = min{n0 , n1 , . . . , nl }.

I

P ROOF OF T HEOREM 9

Theorem 9. Provided that |wil hl−1
+ bli | ≤ M for any possible value of hl−1 , a formulation with
j
the set of constraints (1) for each neuron of a rectifier network is such that a feasible solution with a
fixed value for x yields the output y of the neural network.
Proof. For ease of explanation, we expand the set of constraints (1) as follows:
l

Wil hl−1
+ bli = hli − hi
j

(2)

hli ≤ M zil

(3)

zil )

(4)

≥0

(5)

≥0

(6)

∈ {0, 1}

(7)

l
hi

≤ M (1 −
hli
l
hi
zil
20

Preprint version

It suffices to prove that the constraints for each neuron map the input to the output in the same way
l
that the neural network would. If Wil hl−1 + bli > 0, it follows that hli − hi > 0 according to (2).
Since both variables are non-negative
 due to (5) and (6) whereas one is non-positive due to (3), (4),
and (7), then zil = 1 and hli = max 0, Wil hl−1 + bli . If Wil hl−1 +bli < 0, then it similarly follows

P
l
l
that hli − hi < 0, zil = 0, and thus hi = min 0, Wil hl−1
+ bli . If j Wil hl−1
+ bli = 0, then
j
j
l

l

either hli = 0 or hi = 0 due to constraints (5) to (7) whereas (2) implies that hi = 0 or hli = 0,
respectively. In this case, the value of zil is arbitrary but irrelevant.

J

E XACT COUNTING FOR RECTIFIER NETWORKS USING A MIXED - INTEGER
FORMULATION

A systematic method to count these solutions is the one-tree approach (Danna et al., 2007), which
resumes the search after an optimal solution has been found using the same branch-and-bound tree.
That method can also be applied to near-optimal solutions by revisiting nodes pruned when solving
for an optimal solution. Note that in constraints (1), the variables zil can be either 0 or 1 when they
lie on the activation boundary, whereas we want to consider a neuron active only when its output is
strictly positive. This discrepancy may cause double-counting when activation boundaries overlap.
We can address that by defining an objective function that maximizes the minimum output f of an
active neuron, which is positive in non-degenerate cases. The formulation is as follows:
max f
s.t. (1)

for each neuron i in layer l
hli

f ≤ + (1 −
x∈X

zil )M

(8)

for each neuron i in layer l

Corollary 19. The number of z assignments of (8) yielding a positive objective function value
corresponds to the number of linear regions of the neural network.
Proof. Implicit in the discussion above.
Corollary 20. If the input X is a polytope, then (x, y) is mixed-integer representable.
Proof. Immediate from the existence of a mixed-integer formulation mapping x to y, which is correct as long as the input is bounded and therefore a sufficiently large M exists.
In practice, the value of constant M should be chosen to be as small as possible, which also implies
choosing different values on different places to make the formulation tighter and more stable numerically (Camm et al., 1990). For the constraints set (1), it suffices to choose M to be as large as
either hli or h̄li can be given the bounds on the input. Hence, we can respectively replace M with Hil
and H̄il in the constraints involving those variables. If we are given lower and upper bounds for X,
which we can use for H 0 and H̄ 0 , then we can define subsequent bounds as follows:


 X


l
Hil = max 0,
max 0, wij
Hjl−1 + bli


j



 X


l
l
max 0, −wij
Hjl−1 − bli
H i = max 0,


j

For the constraint involving f in formulation (8), we should choose a slightly larger value than Hil
for correctness because some neurons may never be active within the input bounds.
21

Preprint version

K

C OUNTING LINEAR REGIONS OF R E LU S WITH UNRESTRICTED INPUTS

More generally, we can represent linear regions as a disjunctive program (Balas, 1979), which consist of a union of polyhedra. Disjunctive programs are used in the integer programming literature to
generate cutting planes by lift-and-project (Balas et al., 1993). In what follows, we assume that a
neuron can be either active or inactive when the output lies on the activation hyperplane.
For each active neuron, we can use the following constraints to map input to output:
wil hl−1 + bli = hli
hli

≥0

(9)
(10)

For each inactive neuron, we use the following constraint:
wil hl−1 + bli ≤ 0
hli

=0

(11)
(12)

Theorem 21. The set of linear regions of a rectifier network is a union of polyhedra.
Proof. First, the activation set S l for each level l defines the following mapping:
[
 0 1
(h , h , . . . , hL+1 ) | (9) − (10) if i ∈ S l ; (11) − (12) otherwise
S l ⊆{1,...,n

(13)

l },l∈{1,...,L+1}

Consequently, we can project the variables sets h1 , . . . , hL+1 out of each of those terms by FourierMotzkin elimination (Fourier, 1826), thereby yielding a polyhedron for each combination of active
sets across the layers.
Note that the result above is similar in essence to Theorem 2 of Raghu et al. (2017).
Corollary 22. If X is unrestricted, then the number of linear regions can be counted using (8) if M
is large enough.
Proof. To count regions, we only need one point x from each linear region. Since the number of
linear regions is finite, then it suffices if M is large enough to correctly map a single point in each
region. Conversely, each infeasible linear region either corresponds to empty sets of (13) or else to
a polyhedron P such that {(h1 , . . . , hL+1 ) ∈ P | hli > 0 ∀l ∈ {1, . . . , L + 1}, i ∈ S l is empty,
and neither case would yield a solution for the z-projection of (8).

L

M IXED - INTEGER REPRESENTABILITY OF MAXOUT UNITS

In what follows, we assume that we are given a neuron i in level l with output hli . For that neuron,
we denote the vector of weights as w1li , . . . , wkli . Thus, the neuron output corresponds to

hli := max w1li hl−1 + b1 , . . . , wkli hl−1 + bk
Hence, we can connect inputs to outputs for that given neuron as follows:

hli

li
wjli hl−1
+ bli
j = gj ,
j

j = 1, . . . , k

(14)

hli ≥ gjli ,

j = 1, . . . , k

(15)

zjli )

j = 1, . . . , k

(16)

∈ {0, 1},

j = 1, . . . , k

(17)

≤

gjli

+ M (1 −
zjli

k
X

zjli = 1

j=1

22

(18)

Preprint version

The formulation above generalizes that for ReLUs with some small modifications. First, we are
computing the output of each term with constraint (14). The output of the neuron is lower bounded
li
by that of each term with constraint (15). Finally, we have a binary variable zm
per term of each
neuron, which denotes which neuron is active. Constraint (18) enforces that only one variable is
at one per neuron, whereas constraint (16) equates the output of the neuron with the active term.
Each constant M should be chosen in a way that the other terms can vary freely, hence effectively
disabling the constraint when the corresponding binary variable is at zero.

M

ACCURACY AND ERROR MEASURES OF THE SAMPLE NETWORKS

1.5

1010
108
106

1
104
0.5

0

102

0

5

10

15

100
20

2

1.5

1010
108
106

1
104
0.5

0

102

0

5

Training step

(a)

4x10
3x10
2x10
1x10

4x10
3x10
2x10
1x10

10

15

100
20

Linear regions with single output neuron

4x10
3x10
2x10
1x10

4x10
3x10
2x10
1x10

Validation error (CE)

Training error (CE)

2

Linear regions with single output neuron

Figure 8 shows the error during training for different configurations in the first experiment. Figure 9
shows the errors after training for different configurations in the second experiment. In both, we
observe some relation between accuracy and the order of magnitude of the linear regions, which
suggest that linear regions represent a reasonable proxy to the representational power of DNNs.

Training step

(b)

Figure 8: Contrast of cross-entropy along training with number of regions identifying a single digit
in the first experiment: (a) shows training error in green; (b) shows validation error in purple.

4.0

1010

1010

2.0
95%

Bound from Theorem 1
Exact count of sample networks
Final training error of networks
Final validation error of networks

1;21;10

6;16;10

(a)

11;11;10

16;6;10

106
104
Bound from Theorem 1
Exact count of sample networks
Accuracy of sample networks

102
100

102
100

21;1;10

1;21;10

Neurons on each layer

6;16;10

(b)

11;11;10

16;6;10

21;1;10

Neurons on each layer

Figure 9: Contrast of final errors with number of regions and bound in the second experiment: (a)
shows training error in green and validation error in purple; (b) shows accuracy in red.
23

Linear regions

104

108

Accuracy (MSE)

106

Linear regions

Cross-entropy

108

Preprint version

N

RUNTIMES FOR COUNTING THE LINEAR REGIONS

Table 1 reports the runtimes to count different configurations of networks on each experiment.
Experiment
1

2

Network widths
1 × 10
2 × 10
3 × 10
4 × 10
1; 21; 10
2; 20; 10
3; 19; 10
4; 18; 10
5; 17; 10
6; 16; 10
7; 15; 10
9; 13; 10
10; 12; 10
11; 11; 10
12; 10; 10
13; 9; 10
14; 8; 10
15; 7; 10
16; 6; 10
17; 5; 10
18; 4; 10
19; 3; 10
20; 2; 10
21; 1; 10

Runtime (s)
6.0 × 10−2
1.1 × 102
1.8 × 103
5.2 × 104
1.0 × 10−2
4.5 × 10−1
1.9 × 100
3.8 × 101
2.0 × 102
4.1 × 102
1.2 × 103
7.5 × 103
1.5 × 104
3.3 × 104
4.4 × 104
5.8 × 104
6.6 × 104
7.5 × 104
3.0 × 105
2.8 × 105
2.3 × 105
2.7 × 105
1.1 × 105
4.0 × 104

Table 1: Runtimes for counting the trained networks for each configuration used in the experiments.

O

U PPER BOUND BY VARYING THE TOTAL NUMBER OF NEURONS

Figure 10a shows that the upper bound from Theorem 1 can only be maximized if more layers are
added as the number of neurons increase. In contrast, Figure 10b shows that the smallest depth
preserving such growth is better because there is a secondary, although still exponential, effect that
starts shrinks the bound if the number of layers is too large for the total number of neurons.

100%

Relative upper bound

Upper bound

10142

1096
1
2
3
4

1050

104

60

120

180

240

300

360

420

1
2
3
4

50%

25%

60

Total number of neurons

120

180

240

300

360

420

Total number of neurons

(a)

(b)

Figure 10: Bounds from Theorem 1 in semilog scale for n0 = 60 as the total number of neurons
increase by evenly distributing such neurons in 1 to 4 layers: (a) actual values showing overall
impact of more depth; and (b) ratio by sum over all layers showing local impact of particular depths.
24

