# Deep ReLU Networks Have Surprisingly Simple Polytopes

Feng-Lei Fan∗
Department of Mathematics
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
&Wei Huang
RIKEN AIP
<EMAIL_ADDRESS>
&Xiangru Zhong
Sun Yat-Sen University
<EMAIL_ADDRESS>
&Lecheng Ruan
BIGAI
&Tieyong Zeng
Department of Mathematics
The Chinese University of Hong Kong
Huan Xiong
Institute for Advanced Study in Mathematics
Harbin Institute of Technology
<EMAIL_ADDRESS>
&Fei Wang
Weill Cornell Medicine
Cornell University
<EMAIL_ADDRESS>
Corresponding author.

###### Abstract

A ReLU network is a piecewise linear function over polytopes. Figuring out the
properties of such polytopes is of fundamental importance for the research and
development of neural networks. So far, either theoretical or empirical
studies on polytopes only stay at the level of counting their number, which is
far from a complete characterization of polytopes. To upgrade the
characterization to a new level, here we propose to study the shapes of
polytopes via the number of simplices obtained by triangulating the polytope.
Then, by computing and analyzing the histogram of simplices across polytopes,
we find that a ReLU network has relatively simple polytopes under both
initialization and gradient descent, although these polytopes theoretically
can be rather diverse and complicated. This finding can be appreciated as a
novel implicit bias. Next, we use nontrivial combinatorial derivation to
theoretically explain why adding depth does not create a more complicated
polytope by bounding the average number of faces of polytopes with a function
of the dimensionality. Our results concretely reveal what kind of simple
functions a network learns and its space partition property. Also, by
characterizing the shape of polytopes, the number of simplices be a leverage
for other problems, e.g., serving as a generic functional complexity measure
to explain the power of popular shortcut networks such as ResNet and analyzing
the impact of different regularization strategies on a network’s space
partition.

##  1 Introduction

It was shown in a thread of studies Chu et al. (2018); Balestriero and
Baraniuk (2020); Hanin and Rolnick (2019b); Schonsheck et al. (2019) that a
neural network with the piecewise linear activation is to partition the input
space into many convex regions, mathematically referred to as polytopes, and
each polytope is associated with a linear function (hereafter, we use convex
regions, linear regions, and polytopes interchangeably). Hence, a neural
network is essentially a piecewise linear function over polytopes. Based on
this adorable result, the core idea of a variety of important theoretical
advances and empirical findings is to turn the investigation of neural
networks into the investigation of polytopes. Figuring out the properties of
such polytopes can shed light on many critical problems, which can greatly
expedite the research and development of neural networks. Let us use two
representative examples to demonstrate the utility of characterizing
polytopes:

The first representative example is the explanation of the power of depth. In
the era of deep learning, many studies (Mohri et al., 2018; Bianchini and
Scarselli, 2014; Telgarsky, 2015; Arora et al., 2016) attempted to explain why
a deep network can perform superbly over a shallow one. One explanation to
this question is on the superior representation power of deep networks, i.e.,
a deep network can express a more complicated function but a shallow one with
a similar size cannot (Cohen et al., 2016; Poole et al., 2016; Xiong et al.,
2020). Their basic idea is to characterize the complexity of the function
expressed by a neural network, thereby demonstrating that increasing depth can
greatly maximize such a complexity measure compared to increasing width.
Currently, the number of linear regions is one of the most popular complexity
measures because it respects the functional structure of the widely-used ReLU
networks. Pascanu et al. (2013) firstly proposed to use the number of linear
regions as the complexity measure. By directly applying Zaslavsky’s Theorem
(Zaslavsky, 1997), Pascanu et al. (2013) obtained a lower bound
$\left(\prod_{l=0}^{L-1}\left\lfloor{\frac{n_{l}}{n_{0}}}\right\rfloor\right)\sum_{i=0}^{n_{0}}\binom{n_{L}}{i}$
for the maximum number of linear regions of a fully-connected ReLU network
with $n_{0}$ inputs and $L$ hidden layers of widths
$n_{1},n_{2},\cdots,n_{L}$. Since this work, deriving the lower and upper
bounds of the maximum number of linear regions becomes a hot topic (Montufar
et al., 2014; Telgarsky, 2015; Montúfar, 2017; Serra et al., 2018; Croce et
al., 2019; Hu and Zhang, 2018; Xiong et al., 2020). All these bounds suggest
the expressive ability of depth. The second interesting example is the finding
of the high-capacity-low-reality phenomenon (Hu et al., 2021; Hanin and
Rolnick, 2019b), that the theoretical tight upper bound for the number of
polytopes is much larger than what is actually learned by a network, i.e.,
deep ReLU networks have surprisingly few polytopes both at initialization and
throughout the training. This counter-intuitive phenomenon can also be
regarded as an implicit bias, which to some extent suggests why a deep network
does not overfit.

Figure 1: The number of simplices a polytope contains can reveal the shape
information of a polytope, with which one can dig out valuable information of
a neural network.

We observe that the current studies on polytopes suffer a critical limit. So
far, either theoretical or empirical studies only stay at the level of
counting the number of polytopes, which is far from a complete
characterization of polytopes and the corresponding ReLU network. As we know,
in a feed-forward network of $L$ hidden layers, each polytope is encompassed
by a group of hyperplanes, as shown in Figure 1(a), and each hyperplane is
associated with a neuron. The details of how polytopes are formed in a ReLU
network are in Appendix A. Hence, any polytope is created by at most
$\sum_{i=1}^{L}n_{i}$ and at least $n_{0}+1$ hyperplanes, which is quite a
large range. Thus, face numbers of polytopes can vary a lot. Unfortunately,
the existing “counting” studies did not accommodate the differences among
polytopes. Can we upgrade the characterization of polytopes beyond counting to
capture a more complete picture of a neural network?

In this manuscript, 1) we propose to move one step further to study the shape
of polytopes by seamlessly dividing each polytope into simplices in a
triangulation of the polytope, as Figure 1(b) shows, and we describe the shape
of polytopes by the minimum number of simplices to partition it. 2) We observe
that polytopes formed by ReLU networks are surprisingly simple under both
initialization and gradient descent, which is a fundamental characteristic of
a ReLU network. Here, simplicity means that although theoretically quite
diverse and complicated polytopes can be derived, deep networks tend to find a
function with many simple polytopes. In addition, we underscore that the
purported simplicity is relative to the possibly most complicated polytopes by
a network in a given dimension. We do not compare polytopes in different input
dimensions. Our results concretely reveal what kind of simple functions a
network learns and its space partition property, which can be regarded as an
implicit simplicity bias, explaining why deep networks may not overfit. 3) We
establish a theorem that bounds the average face numbers of polytopes of a
network to a small number. This theorem explains why depth does not make
polytopes more complicated. The key idea is that increasing depth is to cut
the existing polytope with a new hyperplane that cannot intersect with all
faces of the existing polytope. Hence, the number of newly-generated faces is
smaller than the current, and the average face number will not increase. To
summarize, our contributions are threefold.

  1. 1.

We point out the limitation of counting #polytopes. To deepen our
understanding of how a ReLU network partitions the space, we propose to
investigate the shape of polytopes with the minimum number of simplices to
partition it. Investigating polytopes of a network can lead to a more complete
characterization of ReLU networks.

  2. 2.

We empirically find that a ReLU network has surprisingly simple polytopes
under both initialization and gradient descent. Such an interesting finding is
a new implicit bias from the perspective of shapes of linear regions.
Previously, Hanin and Rolnick (2019b) showed that deep ReLU networks have few
polytopes. Our discovery is that polytopes are simple, which is more fine-
grained. Our result and Hanin and Rolnick (2019b) address two essentially
different aspects: quantity and shape. Compared to (Hanin and Rolnick, 2019b),
our result more convincingly illustrates a deep network learns a simple
function. Showing the number of polytopes is few is insufficient to claim that
a network learns a simple solution because a network can have a small number
of very complicated polytopes.

  3. 3.

To substantiate our empirical finding, we use combinatorial techniques to
derive a tight upper bound for the average face number of polytopes, which not
only offers a theoretical guarantee but also explains why increasing depth
does not make polytopes more complicated.

##  2 Related Work

Studies on polytopes of a neural network. Besides the aforementioned works
(Pascanu et al., 2013; Xiong et al., 2020; Montufar et al., 2014; Hu and
Zhang, 2018) that count the number of polytopes, there are increasingly many
studies on polytopes of neural networks. Chu et al. (2018); Hanin and Rolnick
(2019b); Balestriero and Baraniuk (2020) showed that polytopes created by a
network are convex. Zhang and Wu (2020) studied how different optimization
techniques influence the local properties of polytopes, such as the inspheres,
the directions of the corresponding hyperplanes, and the relevance of the
surrounding regions. Gamba et al. (2020) showed that the angles between
activation hyperplanes defined by convolutional layers are prone to be similar
after training. Hu et al. (2020) studied the network using an arbitrary
activation function. They first used a piecewise linear function to
approximate the given activation function. Then, they monitored the change of
#polytopes to probe if the network overfits. Park et al. (2021) proposed
neural activation coding that maximizes the number of linear regions to
enhance the model’s performance. Our work goes beyond counting the number of
polytopes to consider the shapes of polytopes, with the goal of delineating a
more complete picture of neural networks.

Implicit bias of deep learning. A network used in practice is highly over-
parameterized compared to the number of training samples. A natural question
is often asked: why do deep networks not overfit? To address this question,
extensive studies have proposed that a network is implicitly regularized to
learn a simple solution. Implicit regularization is also referred to as an
implicit bias. Gradient descent algorithms are widely believed to play an
essential role in capacity control even when it is not specified in the loss
function (Gunasekar et al., 2018; Soudry et al., 2018; Arora et al., 2019a;
Sekhari et al., 2021; Lyu et al., 2021). Du et al. (2018); Woodworth et al.
(2020) showed that the optimization trajectory of neural networks stays close
to the initialization with the help of neural tangent kernel theory. A line of
works Arora et al. (2019b); Cao et al. (2019); Yang and Salman (2019);
Choraria et al. (2022) have analyzed the bias of a deep network towards lower
frequencies, which is referred to as the spectral bias. It was shown in Arora
et al. (2018); Yu et al. (2017) that replacing weight matrices with low-rank
matrices only deteriorates a network’s accuracy very moderately. Ongie and
Willett (2022); Le and Jegelka  identified the low-rank bias in linear layers
of neural networks with gradient flow. Both theoretical derivation Tu et al.
(2016); Li et al. (2020) and empirical findings Jing et al. (2020); Huh et al.
(2021); Galanti et al. (2023) suggested that gradient descent tends to find a
low-rank solution. What’s more, weight decay is a necessary condition to
achieve the low-rank bias. In contrast, our investigation identifies a new
implicit bias from the perspective of linear regions. Different from most
implicit biases highlighting a certain property of a network, our implicit
bias straightforwardly reveals what kind of simple functions a network learns.
Our finding is relevant to the spectral bias. Since polytopes are both few and
simple, a ReLU network does not produce a lot of oscillations in all
directions, which roughly corresponds to a low-frequency solution.

##  3 Preliminaries

Throughout this paper, we always assume that the input space of an NN is a
$d$-dimensional hypercube
$C(d,B):=[-B,B]^{d}=\\{\mathbf{x}=(x_{1},x_{2},\ldots,x_{d})\in\mathbb{R}^{d}:-B\leq
x_{i}\leq B\\}$ for some large enough constant $B$. Furthermore, we need the
following definition for linear regions (polytopes).

######  Definition 1 (Linear regions (polytopes) Hanin and Rolnick (2019a)).

Suppose that $\mathcal{N}$ is a ReLU NN with $L$ hidden layers and input
dimension $d$. An activation pattern of $\mathcal{N}$ is a function
$\mathcal{P}$ from the set of neurons to the set $\\{1,-1\\}$, i.e., for each
neuron $z$ in $\mathcal{N}$, we have $\mathcal{P}(z)\in\\{1,-1\\}$. Let
$\theta$ be a fixed set of parameters in $\mathcal{N}$, and $\mathcal{P}$ be
an activation pattern. Then the region corresponding to $\mathcal{P}$ and
$\theta$ is $\mathcal{R}(\mathcal{P};\theta):=\\{X\in
C(d,B):z(X;\theta)\cdot{\mathcal{P}(z)}>0\\},$ where $z(X;\theta)$ is the pre-
activation of a neuron $z$ in $\mathcal{N}$. A linear region of $\mathcal{N}$
at $\theta$ is a non-empty set $\mathcal{R}(\mathcal{P},\theta)\neq\emptyset$
for some activation pattern $\mathcal{P}$. Let $R_{\mathcal{N},\theta}$ be the
number of linear regions of $\mathcal{N}$ at $\theta$, i.e.,
$R_{\mathcal{N},\theta}:=\\#\\{\mathcal{R}(\mathcal{P};\theta):\mathcal{R}(\mathcal{P};\theta)\neq\emptyset~{}\text{
for some activation pattern }\mathcal{P}\\}.$ Moreover, let
$R_{\mathcal{N}}:=\max_{\theta}R_{\mathcal{N},\theta}$ denote the maximum
number of linear regions of $\mathcal{N}$ when $\theta$ ranges over
$\mathbb{R}^{\\#weights+\\#bias}$.

In the following, Preliminary 1 shows that the polytopes created by a ReLU
network are convex, which is the most important preliminary knowledge used in
this manuscript. Since each polytope of a ReLU network is convex, as Figure 1
shows, one can further divide each polytope into simplices in a triangulation
of polytopes to make it a simplicial complex (Preliminary 3), where a simplex
is a fundamental unit. The number of simplices contained by a polytope can
reflect the shape and complexity of the polytope. Then, Preliminary 3
introduces how to compute the vertices of polytopes. The detailed explanation
of Preliminaries 1 and 3 can be seen in the Appendix.

######  Preliminary 1 (Polytopes of a neural network).

A neural network with ReLU activation partitions the input space into many
polytopes (linear regions), such that the function represented by this neural
network becomes linear when restricted in each polytope (linear region). Each
polytope corresponds to a collection of activation states of all neurons, and
each polytope is convex (Chu et al., 2018). In this paper, we mainly focus on
$(n_{0}-1)$-dim faces of a $n_{0}$-dim polytope. For convenience, we just
simply use the terminology face to represent an $(n_{0}-1)$-dim facet of an
$n_{0}$-dim polytope.

######  Preliminary 2 (Simplex and simplicial complex).

A simplex is just a generalization of the notion of triangles or tetrahedrons
to any dimensions. More precisely, a $D$-simplex $S$ is a $D$-dimensional
convex hull provided by convex combinations of $D+1$ affinely independent
vectors $\\{\mathbf{v}_{i}\\}_{i=0}^{D}\subset\mathbb{R}^{D}$. In other words,
$\displaystyle S=\left\\{\sum_{i=0}^{D}\xi_{i}\mathbf{v}_{i}~{}|~{}\xi_{i}\geq
0,\sum_{i=0}^{D}\xi_{i}=1\right\\}$. The convex hull of any subset of
$\\{\mathbf{v}_{i}\\}_{i=0}^{D}$ is called a face of $S$. A simplicial complex
$\displaystyle\mathcal{S}=\bigcup_{\alpha}S_{\alpha}$ is composed of a set of
simplices $\\{S_{\alpha}\\}$ satisfying: 1) every face of a simplex from
$\mathcal{S}$ is also in $\mathcal{S}$; 2) the non-empty intersection of any
two simplices $\displaystyle S_{1},S_{2}\in\mathcal{S}$ is a face of both
$S_{1}$ and $S_{2}$. A triangulation of a polytope $P$ is a partition of $P$
into simplices such that the union of all simplices equals $P$, and the
intersection of any two simplices is a common face or empty. The triangulation
of a polytope results in a simplicial complex.

######  Preliminary 3 (Computing simplices in a polytope).

Given an $L$-hidden-layer ReLU network, neurons’ activation states lead to a
group of inequalities. A polytope with dimension $n_{0}$ is defined as
$\\{\mathbf{x}\in\mathbb{R}^{n_{0}}~{}|~{}\mathbf{a}_{k}\mathbf{x}^{\top}+b_{k}\leq
0,k\in[K]\\}$, where $K=\sum_{i=1}^{L-1}n_{i}$ and $n_{i}$ is the number of
neurons in the $i$-th layer. Given these inequalities, the vertices of the
polytope are derived based on the vertex enumeration algorithm (Avis and
Fukuda, 1992). Then, we can apply triangulation to these vertices to compute
the number of simplices constituting this polytope.

##  4 Deep ReLU Networks Have Simple Linear Regions

Here, by analyzing the number of simplices a polytope contains, we observe
that linear regions formed by ReLU networks are surprisingly simple under both
initialization and gradient descent. Although theoretically quite diverse
linear regions can be derived, simple linear regions dominate, which is a
high-capacity-low-reality phenomenon and a new implicit bias, which may
explain why a deep learning model tends not to overfit. Combining the finding
in (Hanin and Rolnick, 2019b), we can upgrade the conclusion to that deep ReLU
networks have surprisingly few and simple linear regions. We validate our
findings comprehensively and consistently at different initialization methods,
network depths, sizes of the outer bounding box, biases, the bottleneck,
network architecture, and input dimensions (Appendices H, I, J, and K).
Furthermore, we showcase that during the training, although the number of
linear regions increases, linear regions keep their simplicity. To ensure the
preciseness of the discovery, our experiments are primarily on low-dimensional
inputs.

###  4.1 Initialization

We validate four popular initialization methods: Xavier uniform, Xavier
normal111https://pytorch.org/docs/stable/nn.init.html, Kaiming, orthogonal
initialization (He et al., 2015). For each initialization method, we use two
different network architectures (3-40-20-1, 3-80-40-1). The bias values are
set to 0.01 for all neurons. A total of 8,000 points are uniformly sampled
from $[-1,1]^{3}$ to compute the polytope. At the same time, we check the
activation states of all neurons to avoid counting some polytopes more than
once. Each run is repeated five times.

$\bullet$ Initialization methods: Figure 2 shows the histogram of the
#simplices each polytope has under different initialization methods.
Hereafter, if no special specification, the x-axis of all figures denotes the
number of simplices a polytope has, and the y-axis denotes the count of
polytopes with a certain number of simplices. Without loss of generality,
suppose that in an experiment, the maximum #simplices a polytope has is
$\Omega$, we deem a polytope with no more than $\Omega/3$ as simple. The
spotlight is that for all initialization methods and network structures,
simple polytopes significantly dominate over complicated polytopes. We
calculate that simple polytopes take account for at least 57% and at most 76%
of the total. In addition, among different initialization methods, the Xavier
normal method tends to generate more uniform polytopes on four architectures.
The achieved polytope is far simpler than the theoretically most complicated
polytope.

Figure 2: Deep ReLU networks have simple linear regions at different
initialization methods.

$\bullet$ Depths: Here, we evaluate if the simplicity of polytopes still holds
for deeper networks. This question is non-trivial, since a deeper network can
theoretically generate more complicated polytopes. Will the depth break the
simplicity? We choose four different widths (20, 40, 80, 160). For
comprehensiveness, the network initialization methods are the Xavier uniform,
Xavier normal, Kaiming, and orthogonal initialization. The depth is set to 5
and 8, respectively. The bias value is 0.01. Likewise, a total of 8,000 points
are uniformly sampled from $[-1,1]^{3}$ to compute the polytope. At the same
time, we check the activation states of all neurons to avoid counting some
polytopes more than once. Each run is repeated five times. The results under
the Xavier uniform initialization are shown in Figure 3 (results under other
initialization methods are put into the Appendix E), from which we draw three
highlights. First, we find that both going deep and going wide can increase
the number of polytopes at different initializations. But the effect of going
deep is much more significant than that of going wide. Second, when the
network goes deep, although the total number of polytopes increases, simple
polytopes still dominate among all polytopes. Third, for different
initialization methods and different depths, the dominating polytope is
slightly different. For example, the dominating polytopes for the network
3-40-40-40-40-40-1 under Xavier normal initialization are those with 6$\sim$10
simplices, while the dominating polytopes for the network 3-20-20-20-20-20-1
under Xavier uniform initialization are those with 1$\sim$5 simplices.

Figure 3: The simplicity holds true for deep networks under Xavier uniform
initialization.

$\bullet$ Biases: Here, we are curious about how the bias value of neurons
will affect the distribution of polytopes. To address this issue, we set the
bias values to $0,0.01,0.05,0.1$, respectively for the network 3-80-40-1. The
outer bounding box is $[-1,1]^{3}$. A total of 8,000 points are uniformly
sampled from $[-1,1]^{3}$ to compute the polytope. At the same time, we check
the activation states of all neurons to avoid counting some polytopes more
than once. Each run is repeated five times. The initialization methods are the
Xavier uniform, Xavier normal, Kaiming, and orthogonal initialization. Figure
4 is from the Xavier uniform, and figures from other initialization methods
are put into Appendix G. We observe that as the bias value increases, more
polytopes are produced. However, the number of simple polytopes still takes up
the majority. It is worthwhile mentioning that when the bias equals 0, the
simplicity is crystal clear. The bias=0 is the extremal case, where all
hyperplanes of the first layer intersect at the original point, and much fewer
faces in polytopes are created.

Figure 4: The simplicity holds true for different bias values under Xavier
initialization.

###  4.2 Training

Earlier, we show that at the initialization stage, deep networks exhibit
simple linear regions. It is natural to ask will the simplicity of linear
regions be broken during training? We answer this question by training a
fully-connected network using ReLU activation function on a real-world problem
and counting the simplices of each polytope. The task is to predict if a
COVID-19 patient will be at high risk, given one’s health status, living
habits, and medical history. This prediction task has 388,878 raw samples, and
each has 5 medical features including ‘HIPERTENSION’,‘CARDIOVASCULAR’,
‘OBESITY’, ‘RENAL CHRONIC’, ‘TOBACCO’. The labels are ‘at risk’ or ‘no’. The
detailed descriptions of data and this task can be referred to in
Kaggle222https://www.kaggle.com/code/meirnizri/covid-19-risk-prediction. The
data are preprocessed as follows: The discrete value is assigned to different
attributes. If a patient has that pre-existing disease or habit, 1 will be
assigned; otherwise, 0 will be assigned. Then, the data are randomly split
into training and testing sets with a ratio of 0.8:0.2. We implement a network
of 5-20-20-1. The optimizer is Adam with a learning rate of 0.1. The network
is initialized by Xavier uniform. The loss function is the binary cross-
entropy function. The epoch number is 400 to guarantee convergence. A total of
8,000 points are uniformly sampled from $[-1,1]^{3}$ to compute the polytope.
The outer bounding box is $[-5,5]^{3}$ to ensure as many polytopes as possible
are counted.

Figure 5: The results over a COVID dataset show that throughout the training,
most polytopes are simple, despite that the number of linear regions drops
during the training.

Figure 5 shows that as the training goes on, the total number of linear
regions drops compared to the random initialization. Overall speaking,
throughout the training, polytopes with no more than 1500 simplices take the
majority. But the number of polytopes with 500-1000 simplices goes up, and the
number of polytopes with fewer than 500 simplices goes down. It may suggest
that the network may be primarily using them to fit data. Appendix L
supplements results obtained from other initialization methods: Xavier
normalization, Kaiming initialization, and orthogonal initialization.

We also train networks on MNIST, following the same procedure in (Hanin and
Rolnick, 2019b). Here, we can not compute the polytopes in $28\times 28$
dimensional space because the vertex enumeration algorithm suffers the curse
of dimensionality. Therefore, we visualize the polytopes in the cross-section
plane. We initialize a network of size 784-7-7-6-10 with Kaiming
normalization. The batch size is 128. The network is trained with Adam with a
learning rate of 0.001. The total epoch number is set to 480, which ensures
the convergence of the network.

Figure 6: A cross-sectional visualization of the polytopes learned by a
network over MNIST at different epochs. Almost all the polytopes are triangles
or quadrilaterals.

Figure 6 shows the cross-section of the function learned by a network at
different epochs. A cross-section is a plane that passes through two randomly-
selected images from MNIST. Figure 6 shows that as the training goes on, the
number of polytopes increases. But almost all the polytopes are triangles or
quadrilaterals. Although these polytopes are from a cross-section other than
the whole landscape, one can indirectly sense the simplicity of these
polytopes.

##  5 Theoretical Explanation (Simple Polytope Theorem)

In this section, we seek to provide a theoretical explanation for the simple
polytope phenomenon. We establish a theorem that bounds the average face
numbers of polytopes of a network to a small number under some mild
assumption, thereby substantiating our finding. Our theoretical derivation is
twofold: initialization and after training.

Geometric heuristics of multi-layer networks. Generically, we argue that a
deep ReLU network should still have simple polytopes. We think that the
simplicity of polytopes is given rise to two reasons. (1) First, since a ReLU
network divides the space into many local polytopes, to yield a complicated
polytope from a local polytope, two or more hyperplanes associated with
neurons in the later layers should intersect within the given local polytope,
which is hard because the area of polytopes is typically small. In (Hanin and
Rolnick, 2019b), where a deep ReLU network was proved to have few polytopes
because hyperplanes do not cross in a local polytope. Without crossing,
complicated polytopes will not emerge either. As such, the complexity of
polytopes probably only increases moderately as the network goes deeper. (2)
Take a polytope $P$ with $k$ faces as an example. If we add one hyperplane to
divide $P$ into two new polytopes $P_{1}$ and $P_{2}$, then the total number
of faces increases by $k_{0}+2$ (the hyperplane itself should be counted
twice), if the hyperplane intersects with $k_{0}$ faces in $P$. Usually,
$k_{0}$ should be smaller than $k$ because a hyperplane cannot cross all faces
of $P$, thus the average number of edges of $P_{1}$ and $P_{2}$ becomes
$(k+k_{0}+2)/2\leq k$. By this idea, we can see that in most cases, the number
of the average number of faces in polytopes of a general multi-layer ReLU
neural network $\mathcal{N}$ will not increase when the number of layers gets
deeper, since adding the hyperplanes one by one in a polytope will not
increase the average number of faces in the new polytopes they divide.

###  5.1 Initialization

######  Theorem 1 (Simple Polytope Theorem, One-hidden-layer NNs).

Let $\mathcal{N}$ be a one-hidden-layer fully-connected ReLU NN with $d$
inputs and $n$ hidden neurons, where $d$ is a fixed positive integer. Suppose
that $n$ hyperplanes generated by $n$ hidden neurons are in general position.
Let $C(d,B):=[-B,B]^{d}$ be the input space of $\mathcal{N}$. Furthermore,
assume that $n$ and $B$ are large enough, then the average number of faces in
linear regions of $\mathcal{N}$ is at most $2d+1$.

######  Theorem 2 (Simple Polytope Theorem, Multi-layer NNs, $d=2$).

Let $\mathcal{N}$ be an $L$-layer fully-connected ReLU NN with $d=2$ inputs
and $n_{i}$ hidden neurons in the $i$-th hidden layer. Let
$C(d,B):=[-B,B]^{d}$ be the input space of $\mathcal{N}$. Furthermore, assume
that $n_{i}$ and $B$ are large enough, then the average number of faces in
linear regions of $\mathcal{N}$ is at most $2d=4$.

######  Theorem 3 (Simple Polytope Theorem, Multi-layer NNs with Zero Biases).

Let $\mathcal{N}$ be an $L$-layer fully-connected ReLU NN with $d$ inputs and
$n_{i}$ hidden neurons in the $i$-th hidden layer where $d$ is a fixed
positive integer. Suppose that all the biases of $\mathcal{N}$ are equal to
zero. Let $C(d,B):=[-B,B]^{d}$ be the input space of $\mathcal{N}$.
Furthermore, assume that the number of hidden neurons and $B$ are large
enough, then the average number of faces in linear regions of $\mathcal{N}$ is
at most $3d-1$.

###### Proof.

Please see Appendix B. ∎

Interpretation of these bounds. It is desirable that no matter how deep a
network is, the average number of faces of polytopes produced by a network is
only concerned with the input dimension. We highlight that this bound is an
intrinsic quantity regarding a network. Considering that $3d-1$ is a rather
small bound, it can justify why simple polytopes dominate. If the dominating
polytopes are complex polytopes, the average face number should surpass $3d-1$
a lot. If simple polytopes only take up a small portion, the average face
number will be larger than $3d-1$, too. Although we assume that the network is
wide in deriving the bound, based on our geometric heuristics, the average
face number should also be small for narrow networks. We leave this question
for future exploration.

Theorem 3 and Theorems 1, 2 are built for cases of zero biases and non-zero
biases, respectively. It is a general practice to initialize biases with 0
before training a network, e.g., biases are often set to 0 in Xavier
initialization Glorot and Bengio (2010). Therefore, Theorem 3 aligns with
reality well. In addition, a ReLU network with zero biases becomes
homogeneous, i.e.,
$\mathcal{N}(\alpha\boldsymbol{\theta};\cdot)=\alpha^{L}\mathcal{N}(\boldsymbol{\theta};\cdot)$,
which is a widely-used setting when investigating implicit bias Lyu and Li
(2020); Vardi et al. (2022). Non-zero biases are so complicated to give a
general and complete theorem for arbitrary cases. We only make success for
one-hidden-layer networks with an arbitrary dimension and multi-layer networks
with $d=2$.

Deriving Theorems 1 and 3 is tricky. The basic idea can be divided into two
parts: Firstly, we derive the upper bound of simplices depending on the
observation that for each $(d-1)$-dim face of a $d$-dim polytope, it can only
be a face for one unique simplex in a triangulation of this polytope, thus the
total number of simplices in triangulations of polytopes must be smaller than
or equal to the total number of $(d-1)$-dim faces in all polytopes. Therefore,
we just need to derive the upper bound for the total number of $(d-1)$-dim
faces in all polytopes generated by a neural network $\mathcal{N}$, which can
be done by induction on the number of layers of $\mathcal{N}$. Secondly, we
derive the number of polytopes by the techniques and results from the classic
hyperplane arrangement theories (see Stanley et al. (2004)). Finally, the
quotient between the upper bound of simplices and the number of polytopes
gives the upper bound for the average number of faces in linear regions of
$\mathcal{N}$.

###  5.2 After Training: Low-Rank

Can we theoretically derive that polytopes remain simple after training? It
was shown that gradient descent-based optimization learns weight matrices of
low rank Galanti et al. (2023); Huh et al. (2021). Therefore, under the low-
rank setting, We also investigate if the polytopes are simple after the
training. We derive Theorems 4 and 5 to substantiate that after training,
polytopes remain simple.

######  Theorem 4 (Simple Polytope Theorem, Multi-Layer NNs with Zero Biases
and Low-rank Weight Matrices).

Let $\mathcal{N}$ be an $L$-layer fully-connected ReLU NN with $d$ inputs and
$n_{i}$ hidden neurons in the $i$-th hidden layer where $d$ is a fixed
positive integer. Assume that the weight matrix $W\in\mathbb{R}^{d\times n}$
has rank $d_{0}\leq d$. Suppose that all the biases of $\mathcal{N}$ are equal
to zero. Let $C(d,B):=[-B,B]^{d}$ be the input space of $\mathcal{N}$.
Furthermore, assume that the number of hidden neurons and $B$ are large
enough, then the average number of faces in linear regions of $\mathcal{N}$ is
at most $2d_{0}+d-1$.

######  Theorem 5 (Simple Polytope Theorem, One-hidden-layer NNs, Low-rank
Weight Matrices).

Let $\mathcal{N}$ be a one-hidden-layer fully-connected ReLU NN with $d$
inputs and $n$ hidden neurons, where $d$ is a fixed positive integer. Assume
that the weight matrix $W\in\mathbb{R}^{d\times n}$ has rank $d_{0}\leq d$.
Suppose that any $d_{0}$ hyperplanes generated by any $d_{0}$ hidden neurons
are in general position. Let $C(d,B):=[-B,B]^{d}$ be the input space of
$\mathcal{N}$. Furthermore, assume that $n$ and $B$ are large enough, then the
average number of faces in linear regions of $\mathcal{N}$ is at most
$2d_{0}+1$.

###### Proof.

For proofs of Theorems 4 and 5, please see Appendix B. ∎

According to Theorems 4 and 5, we can see that when the weight matrix has a
lower rank $d_{0}$, which is smaller than the input dimension $d$, then the
average number of faces in linear regions of $\mathcal{N}$ is determined by
$d_{0}$ and irrelevant to the input dimension $d$. This means that, after the
training of a ReLU neural network, if the weight matrices become low-rank
matrices (which is suggested by Galanti et al. (2023); Huh et al. (2021)),
then the average number of faces in linear regions of $\mathcal{N}$ would be
much smaller, which means that the linear regions tend to be much simpler
after training.

##  6 Discussion

Estimating the shape of polytopes by Monte Carlo samping. How to empirically
estimate the shape of polytopes for high-dimensional inputs? Our theoretical
derivation suggests that one can use the number of faces of a polytope as a
proxy for #simplices to describe the shape of polytopes. Thus, we don’t need
to compute the vertices and triangulation that are time-consuming for high-
dimensional space. Since a polytope with the dimension $n_{0}$ is defined as
$\\{\mathbf{x}\in\mathbb{R}^{n_{0}}~{}|~{}\mathbf{a}_{k}\mathbf{x}^{\top}+b_{k}\leq
0,k\in[K]\\}$, computing the number of faces is equivalent to finding which
inequalities are non-redundant. Non-redundant inequalities are the faces of a
polytope. Determining the non-redundant inequalities can be done by the hit-
and-run algorithms, a representative Monte Carlo sampling method. Appendix M
shows the methodology and provides an example that estimates the number of
faces of polytopes formed by a variant of LeNet-5 architectures for 784
dimensions.

Extension to CNNs. Our results on the average number of faces in polytopes
generated by multi-layer ReLU NNs can be extended to many kinds of
architectures such as CNNs. Theoretically, both CNNs and fully-connected
networks conform to the geometric restrictions. Since one hyperplane cannot
cross all faces of a polytope, the average face number will not tend to
increase. In Appendix M, using Monte Carlo estimation, experiments on a
LeNet-5 variant discovered that the average number of faces polytopes have is
much smaller than the maximum number of inequalities, suggesting that simple
polytopes are also held by CNNs.

#Simplices as a leverage for other problems. The focus of this draft is to use
#simplices to study the shape of polytopes formed by a ReLU network. However,
since #simplices that concerns the shape of polytopes is a more fine-grained
characterization compared to #polytopes, one can also use #simplices as a
complexity measure to describe the expressivity of a ReLU network. Appendix C
lists the potential advantages of #simplices as a complexity measure over
#polytopes in terms of uniqueness via modularization and applicability to
classification networks. As a basic complexity measure, #simplices can help us
understand the behavior of a network from a different angle such as explaining
the power of popular shortcut networks such as ResNet and analyzing the impact
of regularization on a network’s space partition.

For example, 1) in Appendix D, Theorems 6 and 7 summarize the upper and lower
bounds of the maximum #simplices of a feedforward ReLU network and ResNet. It
is found that the upper bound of the maximum #simplices of a feedforward ReLU
network and ResNet are the same. In other words, the addition of residual
connections may not increase the expressivity of a network a lot. The main
advantage of residual connections lies in the optimization because they can
facilitate the flow of gradients. 2) In Appendix N, we use the #simplices to
investigate the impact of weight decay on the shapes of learned polytopes. It
is observed that as the weight decay is exerted more and more heavily, the
number of polytopes goes down and on the other hand, learned polytopes have
fewer simplices, which means they are simpler.

##  7 Conclusion and Limitation

In this manuscript, we have advocated studying the properties of polytopes
instead of just counting them, towards revealing other valuable properties of
a neural network. Then, we observed that deep ReLU networks have simple linear
regions, which is not only a fundamental characterization but also an implicit
bias for ReLU networks explaining why deep networks do not overfit. Lastly, we
have mathematically established a small bound for the average number of faces
in polytopes, therefore supplying an explanation for the simple polytope
phenomenon.

An important limitation of our work is that we don’t fully illustrate the
relationship between our implicit bias and others. Just like in mathematics,
there can be more than one set of axioms for an axiom system, and different
axiom systems can be mutually deduced. Since the implicit bias is derived from
gradient descent, different implicit biases should be related to one another.
An important future direction will be building the relationship between
different forms of implicit biases Galanti et al. (2023). If so, the
understanding of implicit biases can be greatly deepened.

## References

  * Arora et al. (2016) Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  _arXiv preprint arXiv:1611.01491_ , 2016.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _International Conference on Machine Learning_ , pages 254–263. PMLR, 2018.
  * Arora et al. (2019a) Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo.  Implicit regularization in deep matrix factorization.  _Advances in Neural Information Processing Systems_ , 32, 2019a.
  * Arora et al. (2019b) Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pages 322–332. PMLR, 2019b.
  * Avis and Fukuda (1992) David Avis and Komei Fukuda.  A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra.  _Discrete & Computational Geometry_, 8(3):295–313, 1992.
  * Balestriero and Baraniuk (2020) Randall Balestriero and Richard G Baraniuk.  Mad max: Affine spline insights into deep learning.  _Proceedings of the IEEE_ , 109(5):704–727, 2020\.
  * Berbee et al. (1987) HCP Berbee, CGE Boender, AHG Rinnooy Ran, CL Scheffer, Robert L Smith, and Jan Telgen.  Hit-and-run algorithms for the identification of nonredundant linear inequalities.  _Mathematical Programming_ , 37:184–207, 1987.
  * Bianchini and Scarselli (2014) Monica Bianchini and Franco Scarselli.  On the complexity of neural network classifiers: A comparison between shallow and deep architectures.  _IEEE transactions on neural networks and learning systems_ , 25(8):1553–1565, 2014.
  * Cao et al. (2019) Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu.  Towards understanding the spectral bias of deep learning.  _arXiv preprint arXiv:1912.01198_ , 2019.
  * Caron et al. (1997) Richard J Caron, Arnon Boneh, and Shahar Boneh.  Redundancy.  _Advances in Sensitivity Analysis and Parametic Programming_ , pages 449–489, 1997.
  * Chen et al. (2021) Wuyang Chen, Xinyu Gong, and Zhangyang Wang.  Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective.  _arXiv preprint arXiv:2102.11535_ , 2021.
  * Choraria et al. (2022) Moulik Choraria, Leello Tadesse Dadi, Grigorios Chrysos, Julien Mairal, and Volkan Cevher.  The spectral bias of polynomial neural networks.  _arXiv preprint arXiv:2202.13473_ , 2022.
  * Chu et al. (2018) Lingyang Chu, Xia Hu, Juhua Hu, Lanjun Wang, and Jian Pei.  Exact and consistent interpretation for piecewise linear neural networks: A closed form solution.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1244–1253, 2018.
  * Cohen et al. (2016) Nadav Cohen, Or Sharir, and Amnon Shashua.  On the expressive power of deep learning: A tensor analysis.  In _Conference on learning theory_ , pages 698–728. PMLR, 2016.
  * Croce et al. (2019) Francesco Croce, Maksym Andriushchenko, and Matthias Hein.  Provable robustness of relu networks via maximization of linear regions.  In _the 22nd International Conference on Artificial Intelligence and Statistics_ , pages 2057–2066. PMLR, 2019.
  * Du et al. (2018) Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  _arXiv preprint arXiv:1810.02054_ , 2018.
  * Fan et al. (2020) Feng-Lei Fan, Rongjie Lai, and Ge Wang.  Quasi-equivalence of width and depth of neural networks.  _arXiv preprint arXiv:2002.02515_ , 2020.
  * Galanti et al. (2023) Tomer Galanti, Zachary Siegel, Aparna Gupte, and Tomaso Poggio.  Sgd and weight decay provably induce a low-rank bias in deep neural networks.  Technical report, Center for Brains, Minds and Machines (CBMM), 2023.
  * Gamba et al. (2020) Matteo Gamba, Stefan Carlsson, Hossein Azizpour, and Mårten Björkman.  Hyperplane arrangements of trained convnets are biased.  _arXiv preprint arXiv:2003.07797_ , 2020.
  * Glorot and Bengio (2010) Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pages 249–256. JMLR Workshop and Conference Proceedings, 2010.
  * Gunasekar et al. (2018) Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro.  Characterizing implicit bias in terms of optimization geometry.  In _International Conference on Machine Learning_ , pages 1832–1841. PMLR, 2018.
  * Hanin and Rolnick (2019a) Boris Hanin and David Rolnick.  Complexity of linear regions in deep networks.  In _International Conference on Machine Learning_ , pages 2596–2604, 2019a.
  * Hanin and Rolnick (2019b) Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In _Advances in Neural Information Processing Systems_ , pages 359–368, 2019b.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _IEEE International Conference on Computer Vision_ , pages 1026–1034, 2015.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hu and Zhang (2018) Qiang Hu and Hao Zhang.  Nearly-tight bounds on linear regions of piecewise linear neural networks.  _arXiv preprint arXiv:1810.13192_ , 2018.
  * Hu et al. (2020) Xia Hu, Weiqing Liu, Jiang Bian, and Jian Pei.  Measuring model complexity of neural networks with curve activation functions.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1521–1531, 2020.
  * Hu et al. (2021) Xia Hu, Lingyang Chu, Jian Pei, Weiqing Liu, and Jiang Bian.  Model complexity of deep learning: A survey.  _Knowledge and Information Systems_ , 63(10):2585–2619, 2021.
  * Huh et al. (2021) Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola.  The low-rank simplicity bias in deep networks.  _arXiv preprint arXiv:2103.10427_ , 2021.
  * Jing et al. (2020) Li Jing, Jure Zbontar, et al.  Implicit rank-minimizing autoencoder.  _Advances in Neural Information Processing Systems_ , 33:14736–14746, 2020.
  * (31) Thien Le and Stefanie Jegelka.  Training invariances and the low-rank phenomenon: beyond linear networks.  In _International Conference on Learning Representations_.
  * Li et al. (2020) Zhiyuan Li, Yuping Luo, and Kaifeng Lyu.  Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning.  _arXiv preprint arXiv:2012.09839_ , 2020.
  * Lyu and Li (2020) Kaifeng Lyu and Jian Li.  Gradient descent maximizes the margin of homogeneous neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Lyu et al. (2021) Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora.  Gradient descent on two-layer nets: Margin maximization and simplicity bias.  _Advances in Neural Information Processing Systems_ , 34:12978–12991, 2021.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of machine learning_.  MIT press, 2018.
  * Montúfar (2017) Guido Montúfar.  Notes on the number of linear regions of deep neural networks.  _Sampling Theory Appl., Tallinn, Estonia, Tech. Rep_ , 2017.
  * Montufar et al. (2014) Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  In _Advances in neural information processing systems_ , pages 2924–2932, 2014.
  * Ongie and Willett (2022) Greg Ongie and Rebecca Willett.  The role of linear layers in nonlinear interpolating networks.  _arXiv preprint arXiv:2202.00856_ , 2022.
  * Park et al. (2021) Yookoon Park, Sangho Lee, Gunhee Kim, and David Blei.  Unsupervised representation learning via neural activation coding.  In _International Conference on Machine Learning_ , pages 8391–8400. PMLR, 2021.
  * Pascanu et al. (2013) Razvan Pascanu, Guido Montufar, and Yoshua Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations.  _arXiv preprint arXiv:1312.6098_ , 2013.
  * Poole et al. (2016) Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  _Advances in neural information processing systems_ , 29, 2016.
  * Schonsheck et al. (2019) Stefan Schonsheck, Jie Chen, and Rongjie Lai.  Chart auto-encoders for manifold structured data.  _arXiv preprint arXiv:1912.10094_ , 2019.
  * Sekhari et al. (2021) Ayush Sekhari, Karthik Sridharan, and Satyen Kale.  Sgd: The role of implicit regularization, batch-size and multiple-epochs.  _Advances In Neural Information Processing Systems_ , 34:27422–27433, 2021.
  * Serra et al. (2018) 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.
  * Soudry et al. (2018) Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  _The Journal of Machine Learning Research_ , 19(1):2822–2878, 2018.
  * Stanley (2004) Richard P. Stanley.  An introduction to hyperplane arrangements.  In _Lecture Notes, IAS/Park City Mathematics Institute_ , 2004.
  * Stanley et al. (2004) Richard P Stanley et al.  An introduction to hyperplane arrangements.  _Geometric combinatorics_ , 13(389-496):24, 2004\.
  * Telgarsky (2015) Matus Telgarsky.  Representation benefits of deep feedforward networks.  _arXiv preprint arXiv:1509.08101_ , 2015.
  * Toth et al. (2017) Csaba D Toth, Joseph O’Rourke, and Jacob E Goodman.  _Handbook of discrete and computational geometry_.  CRC press, 2017.
  * Tu et al. (2016) Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht.  Low-rank solutions of linear matrix equations via procrustes flow.  In _International Conference on Machine Learning_ , pages 964–973. PMLR, 2016.
  * Vardi et al. (2022) Gal Vardi, Gilad Yehudai, and Ohad Shamir.  Gradient methods provably converge to non-robust networks.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Woodworth et al. (2020) Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro.  Kernel and rich regimes in overparametrized models.  In _Conference on Learning Theory_ , pages 3635–3673. PMLR, 2020\.
  * Xiong et al. (2020) Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao.  On the number of linear regions of convolutional neural networks.  In _International Conference on Machine Learning_ , pages 10514–10523. PMLR, 2020.
  * Yang and Salman (2019) Greg Yang and Hadi Salman.  A fine-grained spectral perspective on neural networks.  _arXiv preprint arXiv:1907.10599_ , 2019.
  * Yu et al. (2017) Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao.  On compressing deep models by low rank and sparse decomposition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7370–7379, 2017.
  * Zaslavsky (1975) T. Zaslavsky.  _Facing up to arrangements : face-count formulas for partitions of space by hyperplanes_.  Number 154 in Memoirs of the American Mathematical Society. American Mathematical Society, 1975.
  * Zaslavsky (1997) T Zaslavsky.  Facing up to arrangements: face-count formulas for partitions of space by hyperplanes.  _Memoirs of American Mathematical Society_ , 154:1–95, 1997\.
  * Zhang and Wu (2020) Xiao Zhang and Dongrui Wu.  Empirical studies on the properties of linear regions in deep neural networks.  _arXiv preprint arXiv:2001.01072_ , 2020.

## Contents of Appendices

Section A introduces why ReLU networks partition the space into polytopes and
how to compute the simplices that constitute each polytope.

Section B theoretically estimates the average number of faces in linear
regions of neural networks under initialization and after training.

Section C introduces the potential of #simplices as a complexity measure.

Section D estimate the upper and lower bounds of the maximum #simplices of
different networks such as feedforward networks and networks with residual
connections.

Section E provides supplementary experimental results for networks with
different depths.

Section F provides supplementary experimental results for much deeper networks
(depth=34 and 50).

Section G provides supplementary experimental results for networks initialized
with different biases.

Section H provides supplementary experimental results for bounding boxes of
different sizes.

Section I provides supplementary experiments for different network structures
such as pyramidal and inverted pyramidal structures.

Section J provides supplementary experiment results for networks with
bottleneck layers.

Section K supplements more experimental results for different dimensions.

Section L provides supplementary results on the COVID Dataset under other
initializations.

Section M shows that we can estimate the number of faces of polytopes by monte
carlo sampling.

Section N shows that we can use the number of simplices to investigate how
different regularization strategies can impact the shape of polytopes.

##  Appendix A Simplices, Polytopes, and Their Computation

###  A.1 Notations of a Network

For convenience and consistency, we inherit notations from [Chu et al., 2018].
For a ReLU network that contains $L$ hidden layers, we write the $l$-th layer
as $\mathcal{L}_{l}$. Specially, $\mathcal{L}_{0}$ is the input layer,
$\mathcal{L}_{L+1}$ is the output layer, and the other layers
$\mathcal{L}_{l},l\in\\{1,2,\ldots,L\\}$ are hidden layers. Hidden layers’
neurons are called hidden neurons. Let $n_{l}$ represent the number of neurons
in $\mathcal{L}_{l}$.

Given the $i$-th neuron of the $l$-th hidden layer, we denote by
$\mathbf{b}_{i}^{(l)}$ its bias, by $\mathbf{a}_{i}^{(l)}$ its output, and by
$\mathbf{z}_{i}^{(l)}$ the total weighted sum of its inputs plus the bias. For
all the $n_{l}$ neurons in $\mathcal{L}_{l}$, we arrange all their biases into
a vector
$\mathbf{b}^{(l)}=\left[\mathbf{b}_{1}^{(l)},\ldots,\mathbf{b}_{n_{l}}^{(l)}\right]^{\top}$,
their outputs into a vector
$\mathbf{a}^{(l)}=\left[\mathbf{a}_{1}^{(l)},\ldots,\mathbf{a}_{n_{l}}^{(l)}\right]^{\top}$,
and their inputs into a vector
$\mathbf{z}^{(l)}=\left[\mathbf{z}_{1}^{(l)},\ldots,\mathbf{z}_{n_{l}}^{(l)}\right]^{\top}$.
Neurons in two neighbor layers are linked by weighted edges. Denote by
$W_{ij}^{(l)}$ the weight of the edge between the $i$-th neuron in
$\mathcal{L}_{l+1}$ and the $j$-th neuron in $\mathcal{L}_{l}$. For
$l\in\\{1,\ldots,L\\}$, we compute $\mathbf{z}^{(l+1)}$ by

$\mathbf{z}^{(l+1)}=W^{(l)}\mathbf{a}^{(l)}+\mathbf{b}^{(l)},$ (1)

where $W^{(l)}$ is an $n_{l+1}$-by-$n_{l}$ matrix.

Let $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be the ReLU activation function.
We have $\mathbf{a}_{i}^{(l)}=\sigma\left(\mathbf{z}_{i}^{(l)}\right)$ for all
$l\in\\{1,\ldots,L\\}$. In an element-wise fashion, we write
$\sigma\left(\mathbf{z}^{(l)}\right)=\left[\sigma\left(\mathbf{z}_{1}^{(l)}\right),\ldots,\sigma\left(\mathbf{z}_{n_{l}}^{(l)}\right)\right]^{\top}$.
Then, for $l\in\\{1,\ldots,L\\}$, we have

$\mathbf{a}^{(l)}=\sigma\left(\mathbf{z}^{(l)}\right).$ (2)

The input is $\mathbf{x}\in\mathcal{X}$, where $\mathcal{X}\in\mathbb{R}^{d}$,
and $\mathbf{x}_{i}$ is the $i$-th dimension of $\mathbf{x}$. The input layer
$\mathcal{L}_{0}$ contains $n_{0}=d$ nodes, where
$\mathbf{a}_{i}^{(0)}=\mathbf{x}_{i},i\in\\{1,\ldots,d\\}$. The output of the
network is $\mathbf{a}^{(L+1)}\in\mathcal{Y}$, where
$\mathcal{Y}\subseteq\mathbb{R}^{n_{l+1}}$. The output layer
$\mathcal{L}_{L+1}$ employs the softmax function:
$\mathbf{a}^{(L+1)}=\operatorname{softmax}\left(\mathbf{z}^{(L+1)}\right)$.

###  A.2 Deriving Polytopes of a Network

For the $i$-th hidden neuron in $\mathcal{L}_{l}$,
$\sigma\left(\mathbf{z}_{i}^{(l)}\right)$ is in the following form:

$\sigma\left(\mathbf{z}_{i}^{(l)}\right)=\left\\{\begin{array}[]{cc}\mathbf{z}_{i}^{(l)},&\text{if}~{}\mathbf{z}_{i}^{(l)}\geq
0\\\ 0,&~{}\text{if}~{}\mathbf{z}_{i}^{(l)}<0,\end{array}\right.$ (3)

where $\sigma\left(\mathbf{z}_{i}^{(l)}\right)$ consists of two linear parts.
Given a network, an instance $\mathbf{x}\in\mathcal{X}$ determines the value
of $\mathbf{z}_{i}^{(l)}$, and further determines
$\sigma\left(\mathbf{z}_{i}^{(l)}\right)=0$ or
$\sigma\left(\mathbf{z}_{i}^{(l)}\right)=\mathbf{z}_{i}^{(l)}$. According to
which part $\sigma\left(\mathbf{z}_{i}^{(l)}\right)$ falls into, one can
encode the activation status of each hidden neuron by two states, each of
which uniquely corresponds to one part of
$\sigma\left(\mathbf{z}_{i}^{(l)}\right)$. Denote by
$\mathbf{c}_{i}^{(l)}\in\\{1,0\\}$ the state of the $i$-th hidden neuron in
$\mathcal{L}_{l}$, we have $\mathbf{z}_{i}^{(l)}\geq 0$ if and only if
$\mathbf{c}_{i}^{(l)}=1$ and $\mathbf{z}_{i}^{(l)}<0$ if and only if
$\mathbf{c}_{i}^{(l)}=0$. The states of different hidden neurons usually
differ from each other.

Let
$\mathbf{c}^{(l)}=\left[\mathbf{c}_{1}^{(l)},\ldots,\mathbf{c}_{n_{l}}^{(l)}\right]$
be the states of all hidden neurons in $\mathcal{L}_{l}$ and
$\mathbf{C}=\left[\mathbf{c}^{(1)},\ldots,\mathbf{c}^{(L)}\right]$ specify the
collective states of all hidden neurons. $\mathbf{C}$ of a given fixed network
is uniquely determined by the instance $\mathbf{x}$. We write the function
that maps an instance $\mathbf{x}\in\mathcal{X}$ to a configuration
$\mathrm{C}\in\\{1,0\\}^{N}$ as
$\mathrm{conf}:\mathcal{X}\rightarrow\\{1,0\\}^{N}$, where
$N=\sum_{i=0}^{L-1}n_{l}$. Then, we rewrite Eq. (2) as

$\mathbf{a}^{(l)}=\sigma\left(\mathbf{z}^{(l)}\right)=\mathbf{c}^{(l)}\circ\mathbf{z}^{(l)},$
(4)

where $\mathbf{c}^{(l)}\circ\mathbf{z}^{(l)}$ is the Hadamard product between
$\mathbf{c}^{(l)}$ and $\mathbf{z}^{(l)}$.

By plugging $\mathbf{a}^{(l)}$ into Eq. (1), we rewrite $\mathbf{z}^{(l+1)}$
as

$\mathbf{z}^{(l+1)}=W^{(l)}\left(\mathbf{c}^{(l)}\circ\mathbf{z}^{(l)}\right)+\mathbf{b}^{(l)}=\tilde{W}^{(l)}\mathbf{z}^{(l)}+\tilde{\mathbf{b}}^{(l)},$
(5)

where $\tilde{\mathbf{b}}^{(l)}=\mathbf{b}^{(l)}$ , and
$\tilde{W}^{(l)}=W^{(l)}\circ\mathbf{c}^{(l)}$ is the generalized Hadamard
product, such that the entry at the $i$-th row and $j$-th column of
$\tilde{W}^{(l)}$ is $\tilde{W}_{ij}^{(l)}=W_{ij}^{(l)}\mathbf{c}_{j}^{(l)}$.

By iteratively enforcing Eq. (5), we can write
$\mathbf{z}^{(l+1)},l\in\\{1,\ldots,L\\}$ as

$\mathbf{z}^{(l+1)}=\left(\prod_{k=1}^{l}\tilde{W}^{(k)}\right)\mathbf{z}^{(1)}+\sum_{h=1}^{l}\left(\prod_{k=h+1}^{l}\tilde{W}^{(k)}\right)\tilde{\mathbf{b}}^{(h)}.$
(6)

Substituting $\mathbf{z}^{(1)}=W^{(0)}\mathbf{x}+\mathbf{b}^{(1)}$ into the
above equation, we rewrite $\mathbf{z}^{(l+1)},l\in\\{1,\ldots,L\\}$ as

$\displaystyle~{}~{}~{}~{}~{}~{}~{}\mathbf{z}^{(l+1)}$ (7)
$\displaystyle=\left(\prod_{k=1}^{l}\tilde{W}^{(k)}\right)(W^{(0)}\mathbf{x}+\mathbf{b}^{(1)})+\sum_{h=1}^{l}\left(\prod_{k=h+1}^{l}\tilde{W}^{(k)}\right)\tilde{\mathbf{b}}^{(h)}$
$\displaystyle=\left(\prod_{k=0}^{l}\tilde{W}^{(k)}\right)\mathbf{x}+\mathbf{b}^{(1)}\left(\prod_{k=1}^{l}\tilde{W}^{(k)}\right)+\sum_{h=1}^{l}\left(\prod_{k=h+1}^{l}\tilde{W}^{(k)}\right)\tilde{\mathbf{b}}^{(h)}$
$\displaystyle=\hat{W}^{(0:l)}\mathbf{x}+\hat{\mathbf{b}}^{(0:l)},$

where $\hat{W}^{(0:l)}$ is the coefficient matrix of $\mathbf{x}$, and
$\hat{\mathbf{b}}^{(0:l)}$ is the sum of the remaining bias terms. Naturally,
$F(\mathbf{x})$ is

$F(\mathbf{x})=\operatorname{softmax}\left(\hat{W}^{(0:L)}\mathbf{x}+\hat{\mathbf{b}}^{(0:L)}\right).$
(8)

For a fixed network and a fixed instance $\mathbf{x},\hat{W}^{(0:l)}$ and
$\hat{\mathbf{b}}^{(0:l)}$ are constant parameters uniquely determined by
activation states of all neurons:
$\mathbf{C}=\operatorname{conf}(\mathbf{x})$. Furthermore, according to Eq.
(3), $\mathbf{C}$ leads to a group of inequalities:

$(2\mathbf{c}^{(l+1)}-1)\circ(\hat{W}^{(0:l)}\mathbf{x}+\hat{\mathbf{b}}^{(0:l)})\geq
0,~{}l=0,\cdots,L-1,$ (9)

which encompasses a convex polytope according to the $H$-definition of
polytopes (Chapter 16, Toth et al. [2017]). If
$\mathrm{conf}(\mathbf{x}_{1})=\mathrm{conf}(\mathbf{x}_{2})$,
$\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ lie in the same polytope due to the
uniqueness.

###  A.3 Computing #Simplices and Polytopes with Vertex Enumeration Algorithm

Algorithm 1 Calculate the #simplex of a polytope of a neural network

1:Identify a collective activation state of all neurons

2:Derive a group of inequalities whose hyperplanes encompass the targeted
polytope

3:Vertex enumeration algorithm to derive the vertices of the polytope

4:Delaunay triangulation

5:Count #simplices

Next, what is essential is to numerically compute #simplices. Unfortunately,
the exact computation relies on enumerating all collective states of neurons,
which is only possible i) when the total number of neurons in a network is
small or ii) when the input dimension is low. For the former, we can enumerate
possible activation states of all neurons by repeating
$2^{\sum_{i=0}^{L-1}n_{i}}$ times, while for the latter, we can uniformly
sample the input space by $(\frac{1}{\epsilon})^{d}$ times, where $\epsilon$
is the needed sampling interval, to identify the actual collective states of
all neurons. As highlighted earlier, the collective activation states
$\mathbf{C}$ lead to a group of inequalities, corresponding to a polytope. We
can solve all vertices of the polytope with the vertex enumeration algorithm
333https://pypi.org/project/pypoman/ [Avis and Fukuda, 1992] to find all
vertices of a polytope. The complexity of the vertex enumeration algorithm
scales linearly with the number of inequalities. Then, Delaunay triangulation
[Chapter 23, [Toth et al., 2017]] is executed for these vertices to see how
many non-overlapping simplices these vertices can gain. Lastly, we count the
#simplices. Sometimes, one may not need to compute all polytopes of a neural
network. Instead, the polytopes related to data are sufficient. For example,
in the training-free NAS experiment [Chen et al., 2021], the authors exhausted
all training data and identify associated unique polytopes.

##  Appendix B Average Number of Faces in Linear Regions of Neural Networks

###  B.1 Initialization

###### Proof of Theorem 1.

By Theorem 6, we obtain that the number of simplices in triangulations of
polytopes generated by $\mathcal{N}$ is at most $\\#\text{simplices}\leq
2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}.$ We know that
the number of $(d-1)$-dim faces is no more than the number of simplices. On
the other hand, since the $n$ hidden neurons are in general position and $B$
is large enough, we obtain that the total number of polytopes (i.e., linear
regions) produced by $\mathcal{N}$ is $\sum_{i=0}^{d}\binom{n}{i}.$ Therefore,
the average number of faces in linear regions of $\mathcal{N}$ is at most

$\frac{2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}}{\sum_{i=0}^{d}\binom{n}{i}}\\\
\leq\frac{2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}}{\sum_{i=0}^{d-1}\binom{n}{i+1}}.$
(10)

For each $0\leq i\leq d-1$, we have

$\displaystyle\frac{2n\cdot\binom{n-1}{i}+2d\binom{n}{i}}{\binom{n}{i+1}}$
$\displaystyle\leq
2(i+1)+\frac{2d(i+1)}{n-i}=2(i+1)\left(1+\frac{d}{n-i}\right)$
$\displaystyle\leq 2d\left(1+\frac{d}{n-d+1}\right).$

Therefore, when $n$ is large enough, we have the average number of faces in
linear regions of $\mathcal{N}$ is at most $2d+\mathcal{O}(\frac{1}{n})\leq
2d+1$. ∎

Let $\\#\mathcal{A}$ be the number of hyperplanes in an arrangement
$\mathcal{A}$ and $\text{rank}(\mathcal{A})$ be the dimension of the space
spanned by the normal vectors of the hyperplanes in $\mathcal{A}$. An
arrangement $\mathcal{A}$ is called central if
$\bigcap_{H\in\mathcal{A}}H\neq\emptyset$. Then we have the following results.

######  Lemma 1 (Theorems 2.4 and 2.5 from Stanley [2004]).

Let $\mathcal{A}$ be an arrangement in an $n$-dimensional vector space. Then
we have

$r(\mathcal{A})=\sum_{\begin{subarray}{c}\mathcal{B}\subseteq\mathcal{A}\\\
\mathcal{B}\text{
central}\end{subarray}}(-1)^{\\#\mathcal{B}-\text{rank}(\mathcal{B})}.$

######  Lemma 2.

Let $\mathcal{A}$ be an arrangement with $m$ hyperplanes in $\mathbf{R}^{n}$.
If all the hyperplanes in $\mathcal{A}$ pass through the origin, and any $n$
normal vectors of $n$ hyperplanes in $\mathcal{A}$ are linearly independent,
then we have

$r(\mathcal{A})=\binom{m-1}{n-1}+\sum_{i=0}^{n-1}\binom{m}{i}.$

###### Proof.

Since all the hyperplanes in $\mathcal{A}$ pass through the origin, then the
intersection of all hyperplanes in $\mathcal{A}$ is not empty, thus each
$\mathcal{B}\subseteq\mathcal{A}$ must be central. Since any $n$ normal
vectors of $n$ hyperplanes in $\mathcal{A}$ are linearly independent, we have

$\text{rank}(\mathcal{B})=\min\\{n,\\#\mathcal{B}\\}.$

Therefore, by Lemma 1 we obtain

$\displaystyle r(\mathcal{A})$
$\displaystyle=\sum_{\begin{subarray}{c}\mathcal{B}\subseteq\mathcal{A}\\\
\mathcal{B}\text{
central}\end{subarray}}(-1)^{\\#\mathcal{B}-\text{rank}(\mathcal{B})}$
$\displaystyle=\sum_{i=0}^{n}\binom{m}{i}+\sum_{i=n+1}^{m}(-1)^{i-n}\binom{m}{i}$
$\displaystyle=\binom{m-1}{n-1}+\sum_{i=0}^{n-1}\binom{m}{i}.$

∎

By Lemma 2 we can derive the proof of Theorem 3.

###### Proof of Theorem 3.

Since all the biases of $\mathcal{N}$ are equal to zero, then all the
hyperplanes produced by the hidden neurons pass through the origin. Assume
that the number of such hyperplanes is $n$ and they form an arrangement
$\mathcal{A}$. Then by Lemma 2 we obtain

$\displaystyle r(\mathcal{A})$
$\displaystyle=\binom{n-1}{d-1}+\sum_{i=0}^{d-1}\binom{n}{i}$
$\displaystyle=\frac{2}{(d-1)!}n^{d-1}+\mathcal{O}\left(n^{d-2}\right).$

On the other hand, for each $H\in\mathcal{A}$, it will be intersected by other
$n-1$ hyperplanes in $\mathcal{A}$. This will produce $n-1$ hyperplanes in
$H$, thus by Lemma 2, it will divide $H$ into
$\frac{2}{(d-2)!}n^{d-2}+\mathcal{O}\left(n^{d-3}\right)$ pieces since $H$ is
a $(d-1)$-dim hyperplane. Similarly, for each hyperplane in the boundary of
$C(d,B)$, it will be divided into
$\frac{1}{(d-1)!}n^{d-1}+\mathcal{O}\left(n^{d-2}\right)$ pieces by $n$
hyperplanes in $\mathcal{A}$. Therefore, the total number of faces of linear
regions formed by $\mathcal{A}$ is at most

$2n\cdot\frac{2}{(d-2)!}n^{d-2}+2d\cdot\frac{1}{(d-1)!}n^{d-1}+\mathcal{O}\left(n^{d-2}\right),$

which is equal to

$\left(\frac{4}{(d-2)!}+\frac{2d}{(d-1)!}\right)n^{d-1}+\mathcal{O}\left(n^{d-2}\right).$

Finally, the average number of faces in linear regions of $\mathcal{N}$ is at
most

$\frac{\left(\frac{4}{(d-2)!}+\frac{2d}{(d-1)!}\right)n^{d-1}+\mathcal{O}\left(n^{d-2}\right)}{\frac{2}{(d-1)!}n^{d-1}+\mathcal{O}\left(n^{d-2}\right)},$

which is

$3d-2+o\left(1\right)<3d-1.$

∎

###  B.2 After Training: Low-Rank

###### Proof of Theorem 2.

When $d=2$, the average number of faces can be naturally bounded. Let us start
with a quadrilateral and add lines to it, then after adding one line in some
linear region, the number of regions increases by $1$ and the total number of
edges increases by at most $4$, thus the total number of edges is at most 4
times the number of linear regions, thus the average edge number is at most
$4$ for the case $d=2$. ∎

Similar to the proof of Theorem 3, we can give the proof of Theorem 4 below.

###### Proof of Theorem 4.

Similar to the proof of Theorem 3, the total number of faces of linear regions
formed by $\mathcal{A}$ is at most

$\left(\frac{4}{(d_{0}-2)!}+\frac{2d}{(d_{0}-1)!}\right)n^{d_{0}-1}+\mathcal{O}\left(n^{d_{0}-2}\right).$

Finally, the average number of faces in linear regions of $\mathcal{N}$ is at
most

$\frac{\left(\frac{4}{(d_{0}-2)!}+\frac{2d}{(d_{0}-1)!}\right)n^{d_{0}-1}+\mathcal{O}\left(n^{d_{0}-2}\right)}{\frac{2}{(d_{0}-1)!}n^{d_{0}-1}+\mathcal{O}\left(n^{d_{0}-2}\right)},$

which is

$2d_{0}-2+d+o\left(1\right)<2d_{0}+d-1.$

∎

Similar to the proof of Theorem 1, we present the proof of Theorem 5 below.

###### Proof of Theorem 5.

Similar to the proof of Theorem 1, we obtain that the number of simplices in
triangulations of polytopes generated by $\mathcal{N}$ is at most
$\\#\text{simplices}\leq
2n\sum_{i=0}^{d_{0}-1}\binom{n-1}{i}+2d\sum_{i=0}^{d_{0}-1}\binom{n}{i}.$
Also, the total number of polytopes produced by $\mathcal{N}$ is
$\sum_{i=0}^{d_{0}}\binom{n}{i}$ since any $d_{0}$ hyperplanes generated by
any $d_{0}$ hidden neurons are in general position. Therefore, the average
number of faces in linear regions of $\mathcal{N}$ is at most

$\frac{2n\sum_{i=0}^{d_{0}-1}\binom{n-1}{i}+2d\sum_{i=0}^{d_{0}-1}\binom{n}{i}}{\sum_{i=0}^{d_{0}}\binom{n}{i}}\\\
\leq\frac{2n\sum_{i=0}^{d_{0}-1}\binom{n-1}{i}+2d\sum_{i=0}^{d_{0}-1}\binom{n}{i}}{\sum_{i=0}^{d_{0}-1}\binom{n}{i+1}}.$
(11)

For each $0\leq i\leq d_{0}-1$, we have

$\displaystyle\frac{2n\cdot\binom{n-1}{i}+2d\binom{n}{i}}{\binom{n}{i+1}}$
$\displaystyle\leq 2(i+1)+\frac{2d(i+1)}{n-i}\leq
2d_{0}+\frac{2dd_{0}}{n-d_{0}+1}.$

Therefore, when $n$ is large enough, we derive that the average number of
faces in linear regions of $\mathcal{N}$ is also at most
$2d_{0}+\mathcal{O}(\frac{1}{n})\leq 2d_{0}+1$, which is irrelevant to $d$. ∎

##  Appendix C #Simplices as a Complexity Measure

######  Definition 2 (#Simplices as a complexity measure).

We define the complexity of a ReLU network as the minimum number of simplices:
$M$ that are needed to fill each and every polytope to support the piecewise
linear function created by the ReLU network. The number of simplices contained
by each polytope can be obtained by doing Delaunay triangulation [Chapter 23,
[Toth et al., 2017]] with the vertices of each polytope.

Now we illustrate the desirable properties of #simplices relative to
#polytopes in terms of the uniqueness via modularization and network transform
and being applicable to classification networks. Here, #simplices refers to
the total number of simplices of a ReLU network, while #polytopes is the total
number of polytopes.

• One-to-one correspondence via modularization and network transform: Given
constant #polytopes, are there functions which can only be approximated by
ReLU FCNs with high #simplices and not low #simplices? The answer is yes. A
simplex is an elementary unit. Proposition 1 shows that an arbitrary ReLU
network can be transformed into a wide network whose depth is the input
dimension and width is determined by the #simplices. Therefore, as long as the
support of functions represented by two networks is filled by the same
#simplices, two networks can be represented by the network of the same width
and depth. As such, we can define the equivalent class of networks as those
with the same #simplices to cover their polytopes. In contrast, #polytopes
cannot be used to rigorously define the equivalent networks because the
polytopes are not elementary units. When one is told that two networks have
the same #polytopes, one is still not totally sure whether two networks are
equally complex.

######  Proposition 1 (#Simplices in network transform [Fan et al., 2020]).

Suppose that the representation of an arbitrary ReLU network is
$h:[-B,~{}B]^{D}\to\mathbb{R}$, and $M$ is the minimum #simplices to cover the
polytopes to support $h$, for any $\delta>0$, there exists a wide ReLU network
$\mathbf{H}$ of width $\mathcal{O}\left[D(D+1)(2^{D}-1)M\right]$ and depth
$D$, satisfying that

$\mathfrak{m}\Big{(}\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}(\mathbf{x})\\}\Big{)}<\delta$
(12)

where $\mathfrak{m}(\cdot)$ is the standard measure in $[-B,~{}B]^{D}$.

Figure 7: Model complex measure: the number of linear regions vs the number of
simplices.

• Being applicable to classification networks: The number of linear regions
loses its efficacy when it comes to the classification network, because the
number of linear regions will be equal to the number of labels regardless of
how many distinct regions the original network has. As shown in Figure 7, two
networks (2-6-1 and 2-3-1) are used to classify two concentric rings. We plot
the linear regions and classification regions for two networks, respectively.
Regarding classification regions, one network uses three neurons to define a
triangle domain, while the other has six neurons to form a hexagon. Although
the six-neuron network is apparently more complex than the other, the two
networks have the same number of classification regions. However, when taking
the number of simplices as the complexity measure, one can favorably avoid
this counterexample. This is because the number of simplices is dependent on
the number of vertices, and the number of vertices is robust in classification
networks. We count the number of simplices for classification regions of two
networks as 4 and 6, which agrees with the complexity of the two networks.

##  Appendix D Estimation to the Maximum #Simplices

######  Theorem 6 (Upper Bound).

Let $\mathcal{N}$ be a feedforward ReLU NN with $d$ input features and $L$
hidden layers with $n$ hidden neurons in each layer (with or without skip
connections between different layers). Then the number of simplices in
triangulations of all polytopes generated by $\mathcal{N}$ is at most

$\frac{2n^{dL}}{(d-1)!(d!)^{L-1}}+\mathcal{O}(n^{dL-1}).$ (13)

In particular, if $L=1$, we derive the following upper bound for the maximum
number of simplices

$\\#\text{simplices}\leq
2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}.$

######  Theorem 7 (Lower Bound).

Let $\mathcal{N}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n$ neurons in each layer. Then the
maximum number of simplices in triangulations of polytopes generated by
$\mathcal{N}$ is at least

$\frac{n^{dL}}{d^{d(L-1)}d!}+\mathcal{O}(n^{dL-1}).$

Furthermore, if $L=1$, we derive the following tighter lower bound for the
maximum number of simplices

$\\#\text{simplices}\geq\frac{2n}{d+1}\sum_{i=0}^{d-1}\binom{n-1}{i}.$

It is straightforward to see $(d-1)!(d!)^{L-1}<d^{d(L-1)}d!$; therefore, the
above upper bound is strictly higher than the lower bound. The basic idea to
derive the above upper bound depends on the following observation: for each
$(d-1)$-dim face of a $d$-dim polytope, it can only be a face for one unique
simplex in a triangulation of this polytope, thus the total number of
simplices in triangulations of polytopes must be smaller than or equal to the
total number of $(d-1)$-dim faces in all polytopes. Therefore, we just need to
derive the upper bound for the total number of $(d-1)$-dim faces in all
polytopes generated by a neural network $\mathcal{N}$, which can be done by
induction on the number of layers of $\mathcal{N}$. For the lower bound, we
use the fact that each $d$-simplex with dimension $d$ has $d+1$ faces, thus
the number of simplices should be at least the total number of $(d-1)$-dim
faces in all polytopes divided by $d+1$.

Our method to transfer the problems of calculating the above number of
simplices to calculating the total number of $(d-1)$-dim faces in all
polytopes is very versatile, and thus can be applied to many complicated
architectures such as fully-connected NNs, CNNs, and ResNets He et al. [2016].
Actually, we can always calculate the total number of faces in all polytopes
layer by layer, by considering each face and finding out how many new faces it
is divided into by new hyperplanes from the next layer.

###  D.1 Preliminary

Let’s recall some basic knowledge on hyperplane arrangements [Stanley et al.,
2004]. Let $V$ be a Euclidean space. A hyperplane in the Euclidean space
$V\simeq\mathbb{R}^{n}$, is a subspace $H:=\\{X\in V:\alpha\cdot X=b\\}$,
where $\mathbf{0}\neq\alpha\in V$, $b\in\mathbb{R}$ and $``\cdot"$ denotes the
inner product. A region of an arrangement $\mathcal{A}=\\{H_{i}\subset V:1\leq
i\leq m\\}$ is just a connected component in the complement set of the union
of all hyperplanes in the arrangement $\mathcal{A}$. Let $r(\mathcal{A})$ be
the number of regions for an arrangement $\mathcal{A}$. Also, a simplex in an
$n$-dimensional Euclidean space is just a $n$-dimensional polytope that is the
convex hull of $n+1$ vertices. For example, a triangle is a simplex in
$\mathbb{R}^{2}$, and a tetrahedron is a simplex in $\mathbb{R}^{3}$. A
triangulation on some polytope is a division of the polytope into simplices.

The following Zaslavsky’s Theorem is very crucial in the estimation of the
number of linear regions.

######  Lemma 3 (Zaslavsky’s Theorem [Zaslavsky, 1975, Stanley et al., 2004]).

Let $\mathcal{A}$ be an arrangement with $m$ hyperplanes in $\mathbf{R}^{n}$.
Then, the number $r(\mathcal{A})$ of regions for the arrangement $\mathcal{A}$
satisfies

$\displaystyle r(\mathcal{A})\leq\sum_{i=0}^{n}\binom{m}{i}.$ (14)

Furthermore, the above equality holds iff $\mathcal{A}$ is in general position
Stanley [2004].

###  D.2 Main results - One Layer ReLU NNs

Throughout this paper, we always assume that the input space of an NN is a
$d$-dimensional hypercube
$C(d,B):=\\{\mathbf{x}=(x_{1},x_{2},\ldots,x_{d})\in\mathbb{R}^{d}:-B\leq
x_{i}\leq B\\}$ for some large enough constant $B$. Note that for a one-layer
fully-connected ReLU NN, the pre-activation of each hidden neuron is an affine
linear function of input values. Based on the sign of the pre-activation, each
hidden neuron produces a hyperplane that divides the input space into two
linear regions. On the other hand, the $d$-dimensional hypercube $C(d,B)$ has
$2d$ hyperplanes in its boundary.

######  Theorem 8.

Let $\mathcal{N}$ be a one-layer feedforward ReLU NN with $d$ input features
and $n$ hidden neurons. Then the number of simplices in triangulations of
polytopes generated by $\mathcal{N}$ is at most

$2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}.$

###### Proof.

Let $H_{1},H_{2},\ldots,H_{n}$ be the $n$ hyperplanes generated by $n$ hidden
neurons and $H_{n+1},H_{n+2},\ldots,H_{n+2d}$ be the $2d$ hyperplanes in the
boundary of $C(d,B)$. Then for each $1\leq i\leq n$, the hyperplane $H_{i}$
may be intersected by other $n-1$ hyperplanes in $H_{1},H_{2},\ldots,H_{n}$.
This will produce at most $n-1$ hyperplanes in $H_{i}$, thus by Theorem 3, it
will divide $H_{i}$ into at most $\sum_{i=0}^{d-1}\binom{n-1}{i}$ pieces since
$H_{i}$ is a $(d-1)$-dim hyperplane. Also, for each $1\leq i\leq 2d$, the
hyperplane $H_{n+i}$ may be intersected by $H_{1},H_{2},\ldots,H_{n}$. This
will produce at most $n$ $(d-2)$-dim hyperplanes in $H_{n+i}$, thus by Theorem
3, it will divide $H_{i}$ into at most $\sum_{i=0}^{d-1}\binom{n}{i}$ pieces
since $H_{i}$ is a $(d-1)$-dim hyperplane. Moreover, each piece could be a
face of two linear regions, finally we will get at most

$2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}$

faces for all the polytopes. On the other hand, each simplex in a
triangulation of polytope can be corresponding to at least one face in the
polytope, and each face in the polytope can be corresponding to exactly one
simplex. Therefore, the total number of simplices must be smaller than or
equal to the total number of faces in all polytopes. Thus we obtain that the
number of simplices in triangulations of polytopes generated by $\mathcal{N}$
is also at most

$2n\sum_{i=0}^{d-1}\binom{n-1}{i}+2d\sum_{i=0}^{d-1}\binom{n}{i}.$

∎

The following results give a lower bound for the maximum number of simplices
in a triangulation of a one layer fully-connected ReLU NN.

######  Theorem 9.

Let $\mathcal{N}$ be a one-layer fully-connected ReLU NN with $d$ input
features and $n$ hidden neurons. If $n$ corresponding hyperplanes are in
general position and $C(d,B)$ is large enough, then the number of simplices in
a triangulation of polytopes among all $n$ corresponding hyperplanes is at
least

$\frac{2n}{d+1}\sum_{i=0}^{d-1}\binom{n-1}{i}=\frac{2n^{d}}{(d+1)(d-1)!}+\mathcal{O}(n^{d-1}).$

###### Proof.

Let $H_{1},H_{2},\ldots,H_{n}$ be $n$ hyperplanes generated by $n$ hidden
neurons. Then for each $1\leq i\leq n$, the hyperplane $H_{i}$ will be
intersected by other $n-1$ hyperplanes in $H_{1},H_{2},\ldots,H_{n}$. This
will produce exact $n-1$ hyperplanes in $H_{i}$ since
$H_{1},H_{2},\ldots,H_{n}$ are in general position, thus by Theorem 3, it will
divide $H_{i}$ into exact $\sum_{i=0}^{d-1}\binom{n-1}{i}$ pieces since
$H_{i}$ is a $(d-1)$-dim hyperplane. When $C(d,B)$ is large enough, we can
assume that every such a piece has a non-empty intersection with $C(d,B)$.
Therefore, the total sum of number of $(d-1)$-faces of all linear regions
(polytopes) will be at least $2n\sum_{i=0}^{d-1}\binom{n-1}{i}$ since every
piece is counted twice. On the other hand, every $d$-dim simplex has $d+1$
distinct $(d-1)$-dim faces, thus every triangulation with $N$ simplices will
contain $N(d+1)$ number $(d-1)$-dim faces. Therefore, if a triangulation of
all linear regions (polytopes) of $\mathcal{N}$ contains $N$ simplices, then

$N(d+1)\geq 2n\sum_{i=0}^{d-1}\binom{n-1}{i}$

and thus

$N\geq\frac{2n}{d+1}\sum_{i=0}^{d-1}\binom{n-1}{i}.$

Finally, we derive that a triangulation of all linear regions (polytopes) of
$\mathcal{N}$ contains at least
$\frac{2n}{d+1}\sum_{i=0}^{d-1}\binom{n-1}{i}=\frac{2n^{d}}{(d+1)(d-1)!}+\mathcal{O}(n^{d-1})$
simplices. ∎

###  D.3 Main results - Multi-Layer ReLU NNs

To study the multi-layer NNs, we need the following results from [Montúfar,
2017, Proposation 3].

######  Lemma 4 (Montúfar [2017]).

Let $\mathcal{N}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n_{1},n_{2},\ldots,n_{L}$ hidden neurons.
Then the number of polytopes of $\mathcal{N}$ is at most
$\prod_{i=1}^{L}\sum_{j=0}^{m_{i}}\binom{n_{i}}{j}$, where
$m_{i}=\min\\{d,n_{1},n_{2},\ldots,n_{i}\\}$.

######  Theorem 10.

Let $\mathcal{N}$ be a multi-layer feedforward ReLU NN with $d$ input features
and $L$ hidden layers with $n$ hidden neurons in each layer (with or without
skip connections between different layers). Then the number of simplices in
triangulations of polytopes generated by $\mathcal{N}$ is at most

$\displaystyle\frac{2n^{dL}}{(d-1)!(d!)^{L-1}}+\mathcal{O}(n^{dL}-1).$ (15)

###### Proof.

First, we prove by induction that the total number of faces generated by
$\mathcal{N}$ is at most

$\frac{2n^{dL}}{(d-1)!(d!)^{L-1}}+\mathcal{O}(n^{dL}-1).$

The case $L=1$ is proved in Theorem 8. When $L\geq 2$, we assume that Eq. (15)
holds for $L-1$. Thus by Lemma 4, and the induction hypothesis, the network
$\mathcal{N}^{\prime}$ with the first $L-1$ layers already has

$\frac{n^{d(L-1)}}{(d!)^{L-1}}+\mathcal{O}(n^{d(L-1)-1})$

linear regions and

$\frac{2n^{d(L-1)}}{(d-1)!(d!)^{L-2}}+\mathcal{O}(n^{d(L-1)-1})$

faces for all polytopes. Then when we add the $L$-th layer, for each polytope
$R$ with $f_{R}$ faces in $\mathcal{N}^{\prime}$, the $n$ neurons and the
$f_{R}$ faces create at most $n+f_{R}$ hyperplanes in $R$ (with or without
skip connections between different layers, since the skip connections will not
create more hyperplanes or polytopes), similar to Theorem 8 these creates

$2n\sum_{i=0}^{d-1}\binom{n-1}{i}+f_{R}\sum_{i=0}^{d-1}\binom{n}{i}$

faces for all the polytopes in $R$. Therefore, we obtain that the total number
of faces is at most

$\displaystyle~{}~{}~{}~{}~{}~{}2n\sum_{i=0}^{d-1}\binom{n-1}{i}\cdot\left(\frac{n^{d(L-1)}}{(d!)^{L-1}}+\mathcal{O}(n^{d(L-1)-1})\right)+\sum_{i=0}^{d-1}\binom{n}{i}\sum_{R}f_{R}$
$\displaystyle=2n\sum_{i=0}^{d-1}\binom{n-1}{i}\cdot\left(\frac{n^{d(L-1)}}{(d!)^{L-1}}+\mathcal{O}(n^{d(L-1)-1})\right)$
$\displaystyle~{}~{}~{}~{}~{}+\sum_{i=0}^{d-1}\binom{n}{i}\cdot\left(\frac{2n^{d(L-1)}}{(d-1)!(d!)^{L-2}}+\mathcal{O}(n^{d(L-1)-1})\right)$
$\displaystyle=\frac{2n^{dL}}{(d-1)!(d!)^{L-1}}+\mathcal{O}(n^{dL}-1).$

Therefore, the total number of simplices must be smaller than or equal to the
total number of faces in all polytopes. Thus we obtain that the number of
simplices in triangulations of polytopes generated by $\mathcal{N}$ is also at
most

$\frac{2n^{dL}}{(d-1)!(d!)^{L-1}}+\mathcal{O}(n^{dL}-1).$

∎

On the other hand, by the following lemma it is easy to derive the maximum
number of simplices in triangulations of polytopes generated by multi-layer
NNs.

######  Lemma 5 (Montufar et al. [2014]).

Let $\mathcal{N}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n_{l}$ hidden neurons in the $l$-th
layer. Then the maximum number of linear regions of $\mathcal{N}$ is at least
$\prod_{l=1}^{L-1}\left\lfloor\frac{n_{l}}{d}\right\rfloor^{d}\sum_{j=0}^{d}\binom{n_{L}}{j}$.

For the lower bounds, we have the following results.

######  Theorem 11.

Let $\mathcal{N}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n$ neurons in each layer. Then the
maximum number of simplices in triangulations of polytopes generated by
$\mathcal{N}$ is at least

$\frac{n^{dL}}{d^{d(L-1)}d!}+\mathcal{O}(n^{dL-1}).$

###### Proof.

By Lemma 5, the maximum number of linear regions is lower bounded by
$\left(\frac{n}{d}\right)^{d(L-1)}\sum_{i=0}^{d}\binom{n}{i}=\frac{n^{dL}}{d^{d(L-1)}d!}+\mathcal{O}(n^{dL-1})$.
Also, the number of simplies should be larger than or equal to the number of
linear regions. Thus we obtain the number of simplices in a triangulation of
polytopes among all $n$ corresponding hyperplanes is at least
$\frac{n^{dL}}{d^{d(L-1)}d!}+\mathcal{O}(n^{dL-1})$. ∎

Now, we can derive Theorems 6 and 7 in the main text.

###### Proof of Theorem 6.

Directly by Theorems 8 and 10. ∎

###### Proof of Theorem 7.

Directly by Theorems 9 and 11. ∎

We empirically validate our bounds in Table 1 with 4 structures. For a network
structure X-$Y_{1}$-$\cdots$-$Y_{h}$-$\cdots$-$Y_{H}$-1, X represents the
dimension of the input, and $Y_{h}$ is the number of hidden neurons in the
$h$-th hidden layer. For a given MLP architecture, we initialize all the
parameters based on the Xavier uniform initialization. Because all network
structures we validate have a limited number of neurons, we can compute
polytopes and their simplices by enumerating all collective activation states
of neurons, which ensures that all polytopes are identifiable. For each
structure, we repeat initialization ten times to report the maximum
#simplices. As shown in Table 1, the derived upper bound is compatible with
the numerical results of several network structures, which verifies the
correctness of our results.

Table 1: Numerically verify the correctness of the derived upper and lower bounds for the maximum #simplices. | 3-7-1 | 3-8-1 | 3-9-1 | 3-10-1
---|---|---|---|---
Upper Bounds by Theorem 6 | 482 | 686 | 942 | 1256
Enumeration Method | 446 | 663 | 893 | 1140
Lower Bounds by Theorem 7 | 77 | 116 | 166 | 230

###  D.4 Comparison of Different Network Architectures

The aim of this section is to compare the maximum #simplices based on bounds
obtained in Section D.2. Our conclusion is that deep NNs usually have more
number of simplices than shallow NNs with the same number of parameters.

First, let’s fix some notations. For two functions $f(n)$ and $g(n)$, we write
$f(n)=\Theta(g(n))$ if there exists some positive constants $c_{1},c_{2}$ such
that $c_{1}g(n)\leq f(n)\leq c_{2}g(n)$ for all sufficiently large $n$;
$f(n)=\mathcal{O}(g(n))$ if there exists some positive constant $c>0$ such
that $f(n)\leq cg(n)$ for all sufficiently large $n$; and $f(n)=\Omega(g(n))$
if there exists some positive constant $c$ such that $f(n)\geq cg(n)$ for all
sufficiently large $n$.

The number of parameters for the fully-connected ReLU NN $\mathcal{N}$ is easy
to compute [Pascanu et al., 2013, Proposition 7].

######  Lemma 6.

Let $\mathcal{N}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n$ hidden neurons in each layer. Then the
number of parameters in $\mathcal{N}$ is $\Theta(Ln^{2}).$

Let $S_{\mathcal{N}_{1}}$ be the maximum number of simplices in triangulations
of polytopes generated by $\mathcal{N}$. Now we can derive the number of
simplices per parameter for deep NNs and their shallow counterparts. The
following result follows directly from Lemma 6, Theorem 6 and Theorem 7.

######  Theorem 12.

Let $\mathcal{N}_{1}$ be a multi-layer fully-connected ReLU NN with $d$ input
features and $L$ hidden layers with $n$ hidden neurons in each layer, and
$d=\mathcal{O}(1)$. Then $\mathcal{N}_{1}$ has $\Theta(Ln^{2})$ parameters,
and the ratio of $S_{\mathcal{N}_{1}}$ to the number of parameters of
$\mathcal{N}_{1}$ is

$\frac{S_{\mathcal{N}_{1}}}{\\#\text{ parameters of
}\mathcal{N}_{1}}=\Omega\Bigl{(}\frac{1}{L}\cdot\frac{n^{dL-2}}{d^{d(L-1)}d!}\Bigr{)}.$

For a one-layer fully-connected ReLU NN $\mathcal{N}_{2}$ with $d$ input
features and $Ln^{2}$ hidden neurons, it has $\Theta(Ln^{2})$ parameters, and
the ratio for $\mathcal{N}_{2}$ is

$\frac{S_{\mathcal{N}_{2}}}{\\#\text{ parameters of
}\mathcal{N}_{2}}=\mathcal{O}\left(\frac{(Ln^{2})^{d-1}}{(d-1)!}\right).$

From Theorem 12 we obtain that $\frac{S_{\mathcal{N}_{1}}}{\\#\text{
parameters of }\mathcal{N}_{1}}$ grows at least exponentially fast with the
depth $L$ and polynomially fast with the width $n$. In contrast,
$\frac{S_{\mathcal{N}_{2}}}{\\#\text{ parameters of }\mathcal{N}_{2}}$ grows
at most polynomially fast with the numbers $L$ and $n$.

Therefore, we have that $\frac{S_{\mathcal{N}_{1}}}{\\#\text{ parameters of
}\mathcal{N}_{1}}$ is far larger than $\frac{S_{\mathcal{N}_{2}}}{\\#\text{
parameters of }\mathcal{N}_{2}}$ when $L$ and $n$ are sufficiently large. Thus
we conclude that fully-connected ReLU NNs usually create much more number of
simplices than one-layer fully-connected ReLU NNs with asymptotically the same
number of input dimensions and parameters. This result suggests that fully-
connected ReLU NNs usually have much more expressivity than one-layer fully-
connected ReLU NNs.

##  Appendix E Supplementary Experiments for Different Depths

Figure 8: The uniformity and simplicity hold true for deep networks under
Xavier normal initialization.  Figure 9: The uniformity and simplicity hold
true for deep networks under Kaiming initialization.  Figure 10: The
uniformity and simplicity hold true for deep networks under orthogonal
initialization.

##  Appendix F Supplementary Experiments for Much Deeper Networks

Figure 11: The simplicity and uniformity hold true for larger bounding boxes
under the Xavier uniform initialization.  Figure 12: The simplicity and
uniformity hold true for larger bounding boxes under the Xavier normal
initialization.  Figure 13: The simplicity and uniformity hold true for larger
bounding boxes under Kaiming initialization.  Figure 14: The simplicity and
uniformity hold true for larger bounding boxes under the orthogonal
initialization.

Here, we investigate if the simple polytope phenomenon holds for much deeper
networks. We compute the polytopes of three networks: depth=19, depth=34, and
depth=50. For all three networks, the input dimension is 3, and the width is
40. We set the bias values to $0.01$. The outer bounding box is $[-1,1]^{d}$,
where $d$ is the dimensionality. A total of 8,000 points are randomly sampled
from $[-1,1]^{d}$. At the same time, we check the activation states of all
neurons to avoid computing some polytope more than once. The initialization
methods are the Xavier uniform, Xavier normal, Kaiming, and orthogonal
initialization. Figures 11, 12, 13, and 14 show the distribution of
#simplices, from which we highlight that when the network goes deep, simple
polytopes still dominate among all polytopes. Most polytopes have fewer than
25 simplices. The most complicated polytopes can have over 100 simplices.

##  Appendix G Supplementary Experiments for Different Biases

Figure 15: The simplicity and uniformity hold true for different bias values
under Xavier normal initialization.  Figure 16: The simplicity and uniformity
hold true for different bias values under Kaiming initialization.  Figure 17:
The simplicity and uniformity hold true for different bias values under
orthogonal initialization.

##  Appendix H Supplementary Experiments for Bounding Boxes of Different Sizes

Figure 18: The simplicity and uniformity hold true for larger bounding boxes
under the Xavier uniform initialization.  Figure 19: The simplicity and
uniformity hold true for larger bounding boxes under the Xavier normal
initialization.  Figure 20: The simplicity and uniformity hold true for larger
bounding boxes under Kaiming initialization.  Figure 21: The simplicity and
uniformity hold true for larger bounding boxes under the orthogonal
initialization.

In the above experiments, we set the outer bounding box to $[-1,1]^{d}$, where
$d$ is the dimension. Will the size of the bounding box change the uniformity
of linear regions? Potentially, a larger bounding box will include more
regions, and these regions may be complicated. To resolve this ambiguity, we
derive the linear regions of the network 3-80-40-1 when setting the bounding
box size to $[-1,1]^{3},[-2,2]^{3},[-5,5]^{3},[-10,10]^{3}$, respectively.
Earlier, we have shown that different bias values do not affect the uniformity
and simplicity of polytopes. Therefore, here we randomly set the bias value to
0.01. The initialization methods are the Xavier uniform, Xavier normal,
Kaiming, and orthogonal initialization. The results are plotted in Figures 18,
19, 20, and 21, from which we have two observations. First, for different
initialization methods, when the size of the outer bounding box increases, the
number of polytopes increases. This is probably because more polytopes are
included in the larger area. Second, we find that the uniformity and
simplicity of polytopes hold for both smaller and larger bounding boxes for
different initialization methods.

##  Appendix I Supplementary Experiments for Network Structures

Figure 22: The simplicity and uniformity hold true for both pyramidal and
inverted pyramidal structures under the Xavier uniform initialization.  Figure
23: The simplicity and uniformity hold true for pyramidal and inverted
pyramidal structures under the Xavier normal initialization.  Figure 24: The
simplicity and uniformity hold true for pyramidal and inverted pyramidal
structures under the Kaiming initialization.  Figure 25: The simplicity and
uniformity hold true for pyramidal and inverted pyramidal structures under the
orthogonal initialization.

In the above experiments, the structures of all networks we use are pyramidal.
Here, we investigate how pyramidal and inverted pyramidal structures affect
the uniformity and simplicity of polytopes. Earlier, we have shown that
different bias values and bounding boxes do not undermine the uniformity and
simplicity of polytopes. Therefore, here we randomly set the bias value to
0.01, and the bounding box size to $[-1,1]^{3}$. A total of 8,000 points are
uniformly sampled from $[-1,1]^{3}$ to compute the polytope. At the same time,
we check the activation states of all neurons to avoid counting some polytopes
more than once. The initialization methods are the Xavier uniform, Xavier
normal, Kaiming, and orthogonal initialization. The compared network
structures are (3-40-20-1, 3-20-40-1), (3-40-20-10-1, 3-10-20-40-1),
(3-80-40-20-1, 3-20-40-80-1), and (3-160-80-40-20-10-1, 3-10-20-40-80-160-1).
The histograms are shown in Figures 22, 23, 24, and 25. First, we find that
given the same number of neurons, for different initialization methods, the
total number of polytopes generated by inverted pyramidal structures is
smaller than that of pyramidal structures. This might be because a neural
network is a sequential model, the earlier layer forms a basis for layer
layers to cut. The earlier layers with more neurons can have more hyperplanes,
which can facilitate more polytopes. Second, for different initialization
methods, the uniformity and simplicity of polytopes are respected by both
pyramidal and inverted pyramidal structures.

##  Appendix J Supplementary Experiments for Bottlenecks

Here, we investigate if the bottleneck layer in a network will affect the
uniformity and simplicity of polytopes. We randomly set the bounding box size
to $[-1,1]^{3}$, and the bias value to 0.01. A total of 8,000 points are
uniformly sampled from $[-1,1]^{3}$ to compute the polytope. At the same time,
we check the activation states of all neurons to avoid repetitive calculation.
The initialization methods are the Xavier uniform, Xavier normal, Kaiming, and
orthogonal initialization. The network structures with bottlenecks are
3-20-10-20-1, 3-20-10-10-20-1, 3-20-20-10-20-20-1, and 3-20-20-10-10-20-20-1.
The histograms are shown in Figures 26, 27, 28, and 29. We find that for
different initialization methods, the polytopes generated by a network with
bottleneck layers are still uniform and simple.

Figure 26: The simplicity and uniformity hold true for bottlenecks under
Xavier initialization.  Figure 27: The simplicity and uniformity hold true for
bottlenecks under the Xavier normal initialization.  Figure 28: The simplicity
and uniformity hold true for bottlenecks under the Kaiming initialization.
Figure 29: The simplicity and uniformity hold true for bottlenecks under the
orthogonal initialization.

##  Appendix K Supplementary Experiments for Different dimensions

Figure 30: The simplicity and uniformity hold true for different dimensions
under Xavier initialization  Figure 31: The simplicity and uniformity hold
true for different dimensions under Xavier normal initialization  Figure 32:
The simplicity and uniformity hold true for different dimensions under Kaiming
initialization  Figure 33: The simplicity and uniformity hold true for
different dimensions under orthogonal initialization

Here, we investigate how the input dimension will affect the distribution of
polytopes. We compute the polytopes of three networks: 4-40-20-1, 5-40-20-1,
and 6-40-20-1. Due to the intrinsic difficulty of computing simplices in high
dimensional space, it is very time-consuming to go higher dimensions. We set
the bias values to $0.01$. The outer bounding box is $[-1,1]^{d}$, where $d$
is the dimensionality. A total of 8,000 points are randomly sampled from
$[-1,1]^{d}$. At the same time, we check the activation states of all neurons
to avoid computing some polytope more than once. The initialization methods
are the Xavier uniform, Xavier normal, Kaiming, and orthogonal initialization.
Figures 30, 31, 32, and 33 show the distribution of #simplices. As the
dimension increases, a polytope tends to have much more simplices, while the
total number of polytopes only slightly increases. We use the triangulation
method to compute the number of simplices. According to triangulation
properties, the maximum number of simplices approximately equals
$\mathcal{O}(M^{d/2})$, where $M$ is the number of simplices, and $d$ is the
dimension. This is why the complexity of the linear regions will increase. For
different initialization methods, most polytopes are those with a smaller
number of simplices.

##  Appendix L Supplementary Results on the COVID Dataset Under Other
Initialization

Figure 34: After training, the simplicity and uniformity hold true for Xavier
normal initialization.  Figure 35: After training, the simplicity and
uniformity hold true under Kaiming initialization.  Figure 36: After training,
the simplicity and uniformity hold true under orthogonal initialization.

##  Appendix M Estimating the Number of Faces of Polytopes by Monte Carlo
Sampling

###  M.1 Methods

As mentioned earlier, for a fixed network and a fixed instance
$\mathbf{x},\hat{W}^{(0:l)}$ and $\hat{\mathbf{b}}^{(0:l)}$ are constant
parameters uniquely determined by activation states of all neurons:
$\mathbf{C}=\operatorname{conf}(\mathbf{x})$. Furthermore, according to Eq.
(3), $\mathbf{C}$ leads to a group of inequalities:

$(2\mathbf{c}^{(l+1)}-1)\circ(\hat{W}^{(0:l)}\mathbf{x}+\hat{\mathbf{b}}^{(0:l)})\geq
0,~{}l=0,\cdots,L-1,$ (16)

which encompasses a convex polytope according to the $H$-definition of
polytopes (Chapter 16, Toth et al. [2017]). If
$\mathrm{conf}(\mathbf{x}_{1})=\mathrm{conf}(\mathbf{x}_{2})$,
$\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ lie in the same polytope due to the
uniqueness. Each inequality corresponds to a hyperplane. However, not all
hyperplanes are faces of the encompassed polytope. We call the inequalities
that are faces of the encompassed polytope non-redundant inequalities.

Although for high dimensional problems, it’s difficult to find all the non-
redundant inequalities (faces of a polytope) in a short time, we can, however,
apply probabilistic methods to find as many as possible to provide an
effective estimation. There are various probabilistic methods to find
necessary linear inequalities Caron et al. [1997]. As Figure 37 shows, their
basic idea is that one randomly "hits" the boundaries of the polytope from its
inside. Here we simply use the classic Hit-and-Run algorithm Berbee et al.
[1987]. More specifically, we use the coordinate direction method, that is, we
generate random directions along each coordinate axis with equal probability.

1:Input: $C(I)$, $x_{0}\in int(X(I))$

2:$j\leftarrow 0$ $D_{0}\leftarrow\emptyset$

3:Unless Terminating Conditions

4: Generate a random direction $v_{j}\in B(x_{j},1)$

5: For $i\in\\{1,\dots,m\\}$

6: $\lambda_{i}\leftarrow\frac{b_{i}-a_{i}^{T}x_{j}}{a_{i}^{T}v_{j}}$

7: $\lambda^{+}\leftarrow\min_{1\leq i\leq m}\\{\lambda_{i}:\lambda_{i}>0\\}$

8: $\lambda^{-}\leftarrow\max_{1\leq i\leq m}\\{\lambda_{i}:\lambda_{i}<0\\}$

9: Denote the indices of the minimum and the maximum above as $u_{j}^{+}$ and
$u_{j}^{-}$, then  $D_{j+1}=D_{j}\cup\\{u_{j}^{+},u_{j}^{-}\\};$

10: Generate $\sigma$ from a uniform distribution on $[0,1]$, and set
$\displaystyle x_{j+1}\leftarrow
x_{j}+(\lambda^{-}+\sigma(\lambda^{+}-\lambda^{-}))v_{j};$

11: $j\leftarrow j+1$

12:output: Indices of necessary inequities, and indices of redundant
inequities $D_{j}$, $I\/D_{j}$

Algorithm 2 Hit-and-Run algorithm Figure 37: Hit-and-Run Algorithm

###  M.2 Experiments

We use the above method to estimate the number of faces of polytopes generated
by a modified LeNet-5 trained on the MINST dataset. The modification is
removing one convolutional layer and replacing all activation functions with
ReLU. We randomly generate 200 instances from a uniform distribution on
$[0,1]^{28\times 28}$. For each instance, we iteratively apply the Hit-and-Run
process to detect the boundaries of the polytope containing it, and record
every newly found boundaries. We set a checkpoint every 1000 iterations. Once
the algorithm cannot find any new boundary in the last 1000 iterations, we
consider it has found most of the boundaries of that polytope, and stop the
process. The distributions of the number of boundaries we find and the number
of iterations taken are shown in Figures 38 and 39. As can be seen, among
$26,796$ inequalities, our algorithm finds $1,677$ boundaries on average for
each polytope, with the cost of around $1.2\times 10^{5}$ iterations on
average. On no polytopes, our algorithm can find more than $2,000$ boundaries
before reaching the stopping criteria. Therefore, this result shows that,
compared with the complex structure of the network, its polytopes in fact have
much fewer faces.

Figure 38: Distribution of Number of Boundaries Found Figure 39: Distribution
of Number of Iterations

##  Appendix N How Do Regularization Strategies Impact the Formation of
Polytopes

As we mentioned, the shapes of polytopes can convey information on the mapping
of a ReLU network. Here, with the number of simplices, we can provide a more
quantitative approach to investigate how different regularization strategies
affect a ReLU network’s mapping. Let us take the weight decay as an example:

Figure 40: The pattern of how the strength of weight decay changes the
complexity of polytopes under Xavier initialization. Figure 41: The pattern of
how the strength of weight decay changes the complexity of polytopes under
Xavier normal initialization. Figure 42: The pattern of how the strength of
weight decay changes the complexity of polytopes under Kaiming initialization.
Figure 43: The pattern of how the strength of weight decay changes the
complexity of polytopes under orthogonal initialization.

###  N.1 Weight Decay

Weight decay is a widely-used strategy to regularize the complexity of a
neural network. It adds the power of all weights into the loss function to
penalize the large weights. Here, we investigate how weight decay affects a
ReLU network’s mapping. Our natural curiosity is will the small weights tend
to make simple polytopes even simpler or more complex?

Here, we follow the experimental configuration of Section 4.2. Then, we add
the regularization of weight decay with the strength of
$10^{-5},10^{-6},10^{-7}$. The histograms of #simplices under four different
initialization are shown in Figures 40, 41, 42, 43. It can be seen that when
weight decay is increased, the total number of polytopes decreases for four
different initialization methods. Particularly, when the weight decay is set
to $10^{-5}$, the total number of polytopes is dramatically smaller than that
obtained without the total number of polytopes. Moreover, for the existing
polytopes, their comprised simplices are fewer as the weight decay increases.
Combining these observations, we summarize that weight decay can make the ReLU
network learn a simpler mapping in terms of fewer polytopes and simpler
polytopes.