Beyond Counting Linear Regions of Neural Networks, Simple Linear Regions Dominate!
Authors: FENGLEI FAN
Wei Huang
Lecheng Ruan
Tieyong Zeng
Huan Xiong
Fei Wang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Functions represented by a neural network with the widely-used ReLU activation are piecewise linear functions over linear regions (polytopes). Figuring out the properties of such polytopes is of fundamental importance for the development of neural networks.
So far, either theoretical or empirical studies on polytopes stay at the level of counting their number. Despite successes in explaining the power of depth and so on, counting the number of polytopes puts all polytopes on an equal booting, which is essentially an incomplete characterization of polytopes. Beyond counting, here we study the shapes of polytopes via the number of simplices obtained by triangulations of polytopes. First, we demonstrate the properties of the number of simplices in triangulations of polytopes, and compute the upper and lower bounds of the maximal number of simplices that a network can generate. Next, by computing and analyzing the histogram of simplices across polytopes, we find that a ReLU network has surprisingly uniform and simple polytopes, although these polytopes theoretically can be rather diverse and complicated. This finding is a novel implicit bias that concretely reveals what kind of simple functions a network learns and sheds light on why deep learning does not overfit. Lastly, we establish a theorem to illustrate why polytopes produced by a deep network are simple and uniform. The core idea of the proof is counter-intuitive: adding depth probably does not create a more complicated polytope. We hope our work can inspire more research into investigating polytopes of a ReLU neural network, thereby upgrading the knowledge of neural networks to a new level. 

Under review as a conference paper at ICLR 2023
BEYOND COUNTING LINEAR REGIONS OF NEURAL NETWORKS, SIMPLE LINEAR REGIONS DOMINATE!
Anonymous authors Paper under double-blind review
ABSTRACT
Functions represented by a neural network with the widely-used ReLU activation are piecewise linear functions over linear regions (polytopes). Figuring out the properties of such polytopes is of fundamental importance for the development of neural networks. So far, either theoretical or empirical studies on polytopes stay at the level of counting their number. Despite successes in explaining the power of depth and so on, counting the number of polytopes puts all polytopes on an equal booting, which is essentially counting, here we study the shapes of polytopes via the number of simplices ob- tained by triangulations of polytopes. First, demonstrate the properties of the number of simplices in triangulations of polytopes, and compute the upper and lower bounds of the maximum number of simplices that network can generate. Next, by computing and analyzing the histogram of simplices across polytopes, we find that a ReLU network has surprisingly uniform and simple polytopes, although these polytopes theoretically can be rather diverse and complicated. This finding is a novel implicit bias that coneretely reveals what kind of simple functions a network learns and sheds light on why deep learning does not overfit. Lastly, we establish a theorem to illustrate why polytopes produced by a deep network are simple and uniform. The core idea of the proof is counter-intuitiv: adding depth probably does not create a more complicated polytope. We hope our work can inspire more research into investigating polytopes of ReLU neural network, thereby upgrading the knowledge of neural networks to a new level.
incomplete characterization of polytopes. Beyond
INTRODUCTION
was shown in a thread of studies Chu et al. (2018): Balestriero & Baraniuk (2020); : Hanin & Rolnick (2019by; SSchonsheck 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 linear function (hereafter, regions, and polytopes interchangeably). Hence, a neural network essentially a piecewise linear function over the input domain. Based on this adorable result, the core idea of variety of important theoretical advances and empirical findings is to turn the investigation of neural networks into the investigation of polytopes. By addressing basic questions such as how common operations affect the formation of polytopes (Zhang & Wu. 2020). how the network topology affects the number of polytopes (Cohen al., 2016| et al.) 2016 Xiong et al. 2020), and so on, the understanding to expressivity of the networks is greatly deepened. To demonstrate the utility of the study on polytopes, we present two representative examples as follows:
use convex regions, linear
The first representative example is the explanation to the power of depth. In the era of deep learning, many studies (Mohri et al., [2018] |Bianchini & Scarselli 2014 Telgarsky 2015) Arora et al. (016) attempted to explain why 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 shallow one with 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 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 respects the functional structure

---

Under review as a conference paper at ICLR 2023
of the widely-used ReLU networks. Pascanu et al. (013) firstly proposed to use the number of linear regions as the complexity measure. By directly applying Zaslavsky's 's Theorem (Zaslavkky 1997),
Pascanu et al. (213)) obtained a lower bound (T'''' mi of linear regions of a fully-connected ReLU network with no inputs and L hidden layers of widths 741, 702, -. nr, Since this work, deriving the lower and upper bounds of the maximum number of
Ee (7)-) for the maximum number
ng
linear regions becomes a hot topic (Montufar et al. 2014 Telgarsky 2015: Montúfar 2017 Serra
ct al., 2018: Croce et al. 2019 Hu & Zhang 2018 Xiong et al. 2020). All these bounds suggest
the expressive ability of depth.
The second interesting example is the finding of the highh-capccit-loo-reailt phenomenon (Hu et al.
2021 Hanin & 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. Specifically, [Hanin & Rolnick (2019)) proved that the expected number of linear regions in ReLU network is bounded by function of the number of total neurons and the input dimension. This counter-intuitive phe- nomenon can also be regarded as an implicit bias, which to some extent suggests why a deep network does not overfit. Although theoretically lot of linear regions can be generated learn a task, a deep network tends to find a simple function for a given task that is with few polytopes.
Despite figuring out the properties of polytopes of neural network is of fundamental importance for the understanding of neural networks, the current studies on the polytopes have an important limit. So far, either theoretical or empirical stud- ies only stay at the level of counting the number of polytopes, which blocks us from gaining other valuable findings. As know, in a feed-forward network of L hidden layers, each polytope is encompassed by group of hyperplanes, as shown in Figure [a), and each hyperplane is associated with a neu- ron. The details of how polytopes are formed in a ReLU net- work can be referred to in Appendix A Hence, any polytope hyperplanes, which is a large range. Face numbers
Linear Regions
Simple
Figure 1:
The number of simplices polytope contains can reveal the shape information of polytope, with which one can dig out valuable information of neural network.
is created by at most Σ n4 and at least ni + +o+ of polytopes can vary a lot. Unfortunately, the existing "counting" studies did not accommodate the differences among polytopes. Therefore, it is highly necessary to move step forward, i.e., know what each polytope is, thereby capturing a more complete picture of a neural network. To realize so, first attempt, polytope, and we describe the shape of polytopes by the minimum number of simplices to partition it, as Figure 1 shows. For example in R if a polytope comprises three simplices, it is pentagon.
seamlessly divide each polytope into simplices in triangulation of the
In this manuscript, 1) to demonstrate the utility of the total number of simplices (#simplices) relative to the total number of polytopes (#polytopes), we characterize the basic proprieties and estimate the lower and upper bounds of the maximum #simplices for ReLU networks. The key to bound estimation is to estimate the total sum of the number of faces for all polytopes. 2) We observe that polytopes formed by ReLU networks are surprisingly uniform and simple. Here, the uniformity and simplicity mean that although theoretically quite diverse and complicated polytopes can be derived, simple polytopes dominate, i.e., deep networks tend to find a function with a uniform and simple polytope pattern instead of a complicated polytope pattern. This is another high-capacity-low--eeee phenomenon and an implicit simplicity bias of neural network, implying how fruitful it is to go beyond counting. Previously, Hanin& & Rolnick (2019b) showed that deep ReLU networks have few polytopes. Our report is that polytopes
not only few but also simple and uniform. Compared to (Hanin& & Rolnick 2019b), our observation more convincingly illustrates why deep networks do not overfit. Showing the number of polytopes is few is insufficient to claim that network learns simple solution because a network can have a small number of very complicated polytopes. 3) We establish theorem that bounds the average face numbers of polytopes of network a small number under some mild assumption, thereby illustrating why polytopes produced by a deep network are simple and uniform.
To summarize, our contributions are threefold. 1) We point out the limitation of counting #polytopes. To solve it, we propose use the #simplices to investigate the shape of polytopes. Investigating polytopes of a network can lead to more complete characterization of ReLU networks and upgrade the knowledge of ReLU networks to a new level. 2) We empirically find that a ReLU network
2

---

Under review as a conference paper at ICLR 2023
has surprisingly uniform and simple polytopes. Such an interesting finding is implicit bias from the perspective of linear regions, which can shed light on why deep networks tend not to overfit. 3) To substantiate our empirical finding, we mathematically derive a tight upper bound for the average face number of polytopes, which not only offers theoretical guarantee but also deepens understanding of how a ReLU network partitions the space.
RELATED WORK
Studies on polytopes of a neural network. Besides the aforementioned works (Pascanu et al, 2013 Xiong et al. 2020; Montufar et al. 22044] Hu & Zhang 2018) that count the number of poly- topes, there are increasingly many studies on polytopes of neural networks. [Cuu et al. (2018): Hanin & Rolnick (2019b); Balestriero & Baraniuk (2020) showed that polytopes created by network are convex. Zhang & Wu (2020) studied how different optimization techniques influence the local properties polytopes, such as the inspheres, the directions of the corresponding hyperplanes, and the relevance of the surrounding regions. 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. (202T) proposed the so-called neural activation coding that maximizes the number of linear regions to enhance the model's performance. Our work moves one step forward from counting the num- ber of polytopes to considering the variability in shapes of polytopes, in hope to delineate a more complete picture of neural networks.
Implicit bias of deep learning. 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 regu- larized to learn simple (not more expressive than necessary) 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 al. (2020) showed that the optimization trajectory of neural networks stays close to the initialization with the help of neural tangent kernel theory. Both theoretical derivation Tu et al.
(2016); Li al. (2020) and empirical findings Jing al. (2020); Huh al. (202T) suggested that
deep network tends to find a low-rank solution. To explain why deep networks first learn "simple patterns". line of works Arora al. (2019b); Cao et al. (2019); Yang & Salman (2019); Choraria et al. (2022) have analyzed the bias of a deep network towards lower frequencies. In contrast, our
investigation identifies new implicit bias from the perspective of linear regions. Different from most implicit biases highlighting a certain property of a network, our implicit bias concretely and straightforwardly reveals what kind of simple functions a network tends to learn.
3 PRELIMINARIES AND BASIC PROPERTIES
3.1 PRELIMINARIES
Throughout this paper, we always assume that the input space an NN is a d-dimensional hyper- cube C(d, B) [- B, Bld fx T2,.. Fa) E Rd -
< 2;
B} for some large
enough constant B.
Furthermore, we need the following definition for linear regions (polytopes).
Definition 1 (Linear regions (polytopes) Hanin & Rolnick (2019a); Xiong et al. (020 Suppose that N is a ReLU NN with L, hidden layers and input dimension d. An activation pattern of N is function P from the set of neurons to the set (1, -1), ie., for each neuron in N. we have P(z) E (1, -1). Let 0 be a fixed set of parameters N. and P be an activation pattern. Then the region corresponding to P and 0 is
R(P;0) == (X C(d, B) : 2(x;0) P(2) > 0, Vz neuron in N}.
where z(X;0) is the pre-activation of a neuron z. A linear region (polytope) of N at 0 is a non- empty set R(P, 0) # for some activation pattern P. Let RN be the number of linear regions of N at 0, iee. RN = # (R((P:) R(P:8) 8) + @ for some activation pattern P}. Moreover, let RN == maxa RN denote the maximum number of linear regions of N when 0 ranges over R weigights
3

---

Under review as a conference paper at ICLR 2023
In the following, Preliminary shows that the polytopes created by ReLU network convex, which is the most important preliminary knowledge used in this manuscript. Since each polytope of ReLU network is convex, as Figure [ shows, one can further divide each polytope into simplices in triangulation of polytopes to make it a simplicial complex (Preliminary 2). where a simplex is a fundamental unit. The number of simplices contained by polytope can refecc the shape and com- plexity of the polytope. Then, Preliminary introduces how to compute the vertices of polytopes. The detailed explanation of Preliminaries and 3 can be seen in Appendix [A]
Preliminary 1 (Polytopes of a neural network are convex). 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 (Chul et al. 2018). In this paper, we mainly focus on (ng - -1-dim faces of a dim polytope. For convenience, we just simply use the terminology face to represent an (no 1-- facet of an no-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 + affinely independent vectors [v:] C R.D.
In other words, S
Gv,, 1& 2 1...
The convex hull of any subset of {v:)
i=0
is called a face of S. A simplicial complex S = UUS Sa composed of a set of simplices {Sa}
satisfying: 1) every face of a simplex from S is also in S: 2) the non-empty intersection of any two simplices S1, S2 E is face of both S1 and S2. A triangulation of a polytope P a partition of P into simplices such that: The union of all simplices equals P, and the intersection of any two simplices a common face or empty.
Preliminary (Computation of a polytope). Given a ReLU network of L hidden layers, a collection of activation states of all neurons leads to group of inequalities. Mathematically, a polytope with L-1 ni and n; is
dimension no is defined as {x E Re agx + by < 0, k E [K]], where K =
the number of neurons in the i-th layer. Given a group of inequalities, the vertices of the polytope can be computed based on the vertex enumeration algorithm (Avis & Fukuda 1992).
3.2 CHARACTERIZING PROPERTIES OF #SIMPLICES
Reflecting the shape variability of polytopes: We plot the his-
25
togram of the number of simplices a polytope contains for a ran- domly initialized network of the structure 3-20-10-1 in Figure 2 As can be seen, the most complicated polytope comprises 40 simplices, while the simplest one only has 3 simplices, suggesting that poly- topes formed by the network vary significantly. Naturally, these poly- topes should not be regarded as equally complex. But when counting #polytopes, polytopes varying a lot are automatically treated equally. In contrast, since how many simplices a linear region comprises in- dicates how complex linear region is, #simplices can characterize the differences of polytopes in shapes and further reveal more infor- mation about what kind of functions a ReLU network learns.
20
Count
10
20
30
40
#Simplices of a Polytope
Figure 2: The histogram of #simplices with respect to dif- ferent polytopes.
Estimating the bound of the maximum #simplices. Here, we estimate the upper and lower bounds of the maximum #simplices of ReLU network. Such results help us grasp the properties of #simplices and serve as solid base for future theoretical or empirical applications of #simplices, such as understanding the generalization behavior of network, estimating the computation time when using #simplices in experiments, etc. The detailed proofs are put into Appendix B
Theorem 1 (Upper Bound), Let N be a multi-layer fully-connected ReLU NN with d input fea- tures and L, hidden layers with hidden neurons in each layer. Then the nunber of simplices in triangulations of all polytopes generated by N is at most
dr.
dd- 1 + -O
(I)
4

---

Under review as a conference paper at ICLR 2023
In particular, if 1, we derive the following upper bound for the maximum number of simplices
d-1
#simplices S 2n
) 2d
Σ 6=
-
+
Theorem (Lower Bound). Let N be 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 N is at least
n
+ O(ndh-1))
dd(L-1)
Furthermore, if L 1, we derive the following tighter lower bound for the maximum number of simplices
d-1
2n
m--1)
#simplices
The basic idea to derive the above upper bound depends on the following observation: for cach (d - 1)- face of a d-dim polytope, it only be face for one unique simplex in triangulation of this polytope, thus the total number of simplices than or equal the total number of (d 1)-dim faces in all polytopes. Therefore,
triangulations of polytopes must be smaller just need to derive the upper bound for the total number of (d - 1) dim faces in all polytopes generated by neural network N, which can be done by induction on the number of layers of A. For the lower bound, we use the fact that each d-simplex with dimension d has d + faces, thus the number of simplices should be least the total number of (d dim faces in all polytopes divided by + 1.
We empirically validate our bounds in Table with 7 structures for comprehensive evaluation. For a network structure X-Y X-Y -H-1, X represents the dimension of the input, and Y, 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, can compute polytopes and their simplices by enumerating all collective activation states of neurons, which ensures that all polytopes are identifiable. For each structure, repeat initialization ten times 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 Numerically verify the correctness of the derived upper and lower bounds for the maximum #simplices.
3-4-1
3-5-1
3-6-1
3-7-1
3-8-1
3-9-1
3-10-1
Upper Bounds by Theorem
122
206
482
686
942
1256
Estimation by Enumeration Method
119
183
317
446
663
893
I140
Lower Bounds by Theorem
14
27
116
166
230
DEEP RELU NETWORKS HAVE SIMPLE AND UNIFORM LINEAR REGIONS
Previously, deep neural networks were both theoretically and empirically identified to have surpris- ingly fewer linear regions than their maximum capacity (Hanin & Rolnick 2019b). By analyzing the number of simplices a polytope contains, we observe that linear regions formed by ReLÚ net- works are surprisingly simple and uniform. Although theoretically quite diverse linear regions can be derived, simple linear regions dominate, which is another gegh--ppccity-lo--rellee (Hu al. 2021) and new implicit bias, which may explain why deep learning model tends not to overfit. Combining the finding in (Hanin & Rolnick (019b)) we can upgrade the conclusion to that deep ReL.U networks have surprisingly few, simple, and uniform linear regions. Compared to other implicit biases emphasizing properties of network such as capacity, rank, and frequency, we concretely show what kinds of simple functions a ReLU network learns. We validate our finding comprehensively at different initialization methods, network depths, sizes of the outer bounding box. biases, the bottleneck, network architecture, and input dimensions. Furthermore, we showcase that during the training, although the number of linear regions increases, linear regions keep their uni- formity and simplicity. To ensure the preciseness of the discovery and be limited by the prohibitive computational cost of deriving simplices, experiments are primarily on low-dimensions inputs.
phenomenon
5

---

Under review as a conference paper at ICLR 2023
4.1 INITIALIZATION
We validate four popular initialization methods: Xavier uniform, Xavier normal ! Kaiming, orthog- onal initialization (He al. 2015). For each initialization method, we use two different network 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, 133
architectures (3-40-20-1, 1, 3-80
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. Figure 3 shows the histogram of the #simplices each polytope has. Hereafter, if no special specification, the x-axis of all figures denotes the number of simplices polytope has, and the y-axis denotes the count of polytopes with a certain number of simplices. Without loss of generality, suppose that in experiment, the maximum #simplices polytope has is 22, deem a polytope with no more than 02/3 as simple; otherwise, is complex. The spotlight is that for all initialization methods and network structures, simple polytopes significantly dominate over compli- cated 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. In Appendices D-I, via systematic experiments, we find that the simple linear regions still take the majority at different network depths, sizes of the outer bounding box, biases, the bottleneck, network architecture, and input dimensions.
Orthogonal
Kaiming
2508
1003
3-48-20-1
3-40-20-1
3-18-294
3-40-20-1
2008
1250
800
1840
618
600
480
500
208
250
20
60
40
60
20
40
60
20
40
60
50
Our not
Xavser Uniform
Xavier Normal
Kaiming Normal
2003
3-90-46-1
3-50-40-1
3860
3-30-40-3
3-50-40-3
3880
2500
1509
2000
1580
4000
508
1860
1860
2008
500
Figure 3: Deep ReLU networks have surprisingly uniform linear regions at different initialization methods.
4.2 TRAINING
Earlier, we show that at the initialization stage, deep networks exhibit simple and uniform linear regions. Next, is natural to ask will the uniformity and simplicity of linear regions be broken dur- ing training? We answer this question by training fully-connected network using ReLU activation function on a real-world problem and counting the simplices of polytopes. The task is to predict if 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 medical features includ- 'OBESITY". 'RENAL CHRONIC', 'TOBACCO'. ing 'HIPERTENSION' CARDIOVASCULAT
TTe labels are at risk' or "no". The detailed descriptions of data and this task can be referred to in Kaggld The data are preprocessed as follows: The discrete value is assigned to different attributes. If a patient has that pre-existing disease or habit, 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 network of 5-20-20-1. The optimizer is Adam with learning rate of 0.1. The network is initialized by Xavier uniform. The loss function the binary cross-entropy function. The epoch number is 400 guarantee convergence. A total of 8,000 points are uniformly sampled
http://wwww.aaggg....ommmeeeeeem htwp://ooiiii--9---------eeeeeee prediction

---

Under review as a conference paper at ICLR 2023
from [-1, to compute the polytope. The outer bounding box is [-5, 5] to ensure many polytopes as possible are counted. Figure shows that as the training goes on, the number of linear regions drops compared to the random initialization. Furthermore, throughout the training, most polytopes are simple.
Epeched
Epoch-100 100
Epech-250
500
200
160
20:00
5000
75:0
10000
2000
4860
0060
1000
2000
4008
6000
Upach-100
Epoch--000
Prech-920
330
400-
400
410
330-
230
200
200
110
2000
10000
6000
8003
2006
4000
6000
2006
4000
1000
Figure 4: The results show that throughout the training, most polytopes are simple.
We also train networks on MNIST, following the same procedure in (Hanin & Rolnick 2019b). Here, we can compute the polytopes in 28 28 dimensional space because the vertex enumer- ation algorithm suffers the curse of dimensionality. Therefore, we visualize the polytopes in the cross-section plane. We initialize network of size 784-7-7-6-1 with Kaiming normalization. The batch size is 128. The network is trained with Adam with learning rate of 0.001. The total epoch number is set to 35, which ensures the sufficient training of the network.
Fpods=O
E
Epoch-10
Epodl
Epoct=20
Fpodh225
Epod==30
Fpoch+rs
Figure 5: A cross-sectional visualization to the polytopes learned by network different epochs.
Figure 5 shows the cross-section of the function learned by network at different epochs. The cross-section plane that pass through two randomly-selected images from MNIST. Figure 5 shows that the training goes on, the number of polytopes increases. The spotlight is that almost all the polytopes are triangles or quadrilaterals. Although these polytopes are from a cross-section other than the whole landscape, one indirectly sense the uniformity of these polytopes.
5 MATHEMATICAL INTERPRETATION
Here, we mathematically explain why simple polytopes dominate in ReL.U networks.
Geometric heuristics. We attribute the uniformity and simplicity of polytopes to the locality created by the ReLU activation function. Since ReLU network divides the space into many local polytopes, to yield a complicated polytope from 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. As such, the complexity of polytopes probably does not increase the network goes deeper. Our heuristics where a deep ReLU network was proved to have few polytopes because hyperplanes do not cross in local polytope. Without crossing, complicated polytopes will not emerge either. Furthermore,
also supported by (Hanin & Rolnick] 2019b)'s 's proof,

---

Under review as a conference paper at ICLR 2023
believe the average face number is intrinsic quantity of ReLU network majorly due to the property of space partition and the network's ' hierarchical structure. Such an intrinsic quantity is essentially only weakly dependent on the width and depth of a network.
Now, we formalize our hcuristic into a tight bound of the average face numbers of polytopes.
Theorem (One-hidden-layer NNs). Let N be a one-hidden-layer fully-connected ReLU NN with d inputs and n hidden neurons, where d is fixed positive integer. Suppose that hyperplanes generated by hidden neurons are in general position. Let C(dd, B) [-B, B] be the input space of N. Furthermore, assume that and B are large enough, then the average number of faces in linear regions of N at most 2d + 1.
1 Proof. By Theorem
we obtain that the number of simplices in triangulations of polytopes gener-
ated by N is at most
#simplices I 2n
Σ 2=0
2d
(=U
On the other hand, since the n hidden neurons are in general position and large enough, we ob- tain that the total number of polytopes (i.e., linear regions) produced by A is Σ -o (?). Therefore, the average number of faces in linear regions of N is most
2n >
+ 2d 2d
(
2n (n-1) 2d
E1
Σ
i+1
For each 0 S í < d have
2n (": 2d)
2d(i +
(0(1111) d
(1+==²)
S 2(1+
2(i +
S 2d
|+
Therefore, when is large enough, we have the average number of faces in linear regions of N is most 2d + ( $ 2d +1.
Theorem 4 (Multi-layer NNs). Let N be an L-layer fully-connectdd ReLU NN with d inputs and n, hidden neurons in the i-th hidden layer where d is fixed positive integer. Suppose that for each linear region S produced by the first (i 1)-th layers of N, the us hyperplanes hidden neurons in the i-th layer are always in general position. Let C(d, B) == [-B, B be the input space of N. Furthermore, assume that each ng and B are large enough, then the average number of faces in linear regions of N is most 2d
S generated by
Proof. Please see Appendix B.5
Remark 1. One desirable property about this bound is that it is independent of the width and depth. which validates our heuristics. Considering that 2d + rather small bound, Theorems 3 and can justify why simple polytopes dominate. If the dominating polytopes are complex polytopes, the average face number should surpass 2d + 1 lot. simple polytopes only take up a small portion, the average face number will be larger than 2d + 1, too. Although 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.
DISCUSSION AND CONCLUSION
Implication to spectral bias. Previously, plethora of studies observed that deep networks first learn patterns of low frequencies (Arora et al. 2019b, Cao et al. 2019 Yang & Salman 2019 Choraria et al. 2022). This observation is referred to as the spectral bias. Our finding is highly
relevant to the spectral bias. Combined with the observation in (Hanin & Rolnick, 2019b), since
polytopes are few, simple, and uniform, the function learned by a ReLU network does not produce lot of oscillations in all directions, which roughly corresponds to low-frequency solution. Our opinion that the function represented by a ReLU network is initialized express function without too many oscillations. When the stride by gradient descent is small, network naturally tends to first learn patterns of low frequencies.
8

---

Under review as a conference paper at ICLR 2023
Decoding the learning of neural networks. Going from the linear regions to the simplices also contributes to a novel un- derstanding of the training of neural network. It has been clear that the learning of a neural network is the process of the function fitting with a piecewise linear function. The view of simplices connects with the finite element method (Bathe) 2007). Since simplex is an elementary unit, we argue that the learning of a neural network is nothing but formulating finite elements towards solving the stationarity of the func- tional:
66
12
II / R(u(x)) + Σ 5(x xx)(x(x) dxx))xx, (2) Figure 6: Decoding the learning of neu- ral network constructing finite ele- ment under the stationary functional.
where u(x) = Ei= Ej= Cy ūxx) is the ground-
truth function, R R(u(x)) denotes some regularization to u(x). N, is the shape function over finite element (simplex) that obtained through coordinate transform, and Giý are coefficient solved
A11 = 0, = 1,2, n.. = 1, .0..,.,,,. d. The viewpoint constructing finite elements is by Beg
highly related to moving mesh methods in the field of scientific computing (Di et al. 2005). which could inspire more discoveries in the future.
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. To show such a direction is beneficial, we have characterized the desirable properties of #simplices and estimated its upper and lower bounds to pave the way for future applications. Then, we have presented that deep ReLU networks have surprisingly simple and uniform linear regions, which is an implicit bias for ReLU networks, and may explain why deep networks not overfit. Lastly, we have mathematically established small bound for the average number of faces in polytopes to explain our finding. In the future, more efforts should be put into investigating the polytopes of a network and designing advanced algorithms to calculate the polytopes.
7 REPRODUCIBILITY STATEMENT
To ensure that the experimental results and conclusions of our paper are totally reproducible, we make efforts as the following:
Theoretically, we state the full set of preliminaries, list all requisites of theorems, and include com- plete proofs of theorems in Sections and Appendices and
Experimentally, we provide the code in the supplementary material. Our code contains all necessary comments and is highly readable to ensure that interested readers can reproduce it. In addition, we specify all the training and implementation details in Section
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 161.v:6611.014000 2016.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-322222222 -32.. PMLR, 2019b.
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.
Randall Balestriero and Richard Baraniuk. Mad max: Affine spline insights into deep learning. Proceedings of the IEFE, 10955)7044-727, 2020.

---

Under review as a conference paper at ICLR 2023
Klaus Jauus-Jürgnn Bathe. Finite element method. Wiley encyclopedia of computer science and engineer- ing. pp. 1-12, 2007.
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A compar- ison between shallow and deep architectures. IEEE transactions on neural networks and learning systems, (5(8):155--165 2014.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 1912.01192. 2019.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. arXiv preprint arXiv:2102.1/535, 2021.
Moulik Choraria, Leello Tadesse Dadi, Grigorios Chrysos, Julien Mairal, and Volkan Cevher. The spectral bias of polynomial neural networks. arXiv preprint 1xX1:2202.13473, 2022.
Lingyang Chu, Xia Hu, Juhua Hu, Lanjun Wang, and Jian Pei. Exact and consistent interpretation for piecewise linear neural networks: closed form solution. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1244-1253, 2018.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory. pp. 698-728. PMLR, 2016.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu net- works via maximization of linear regions. In the 22nd International Conference on Artificial Intelligence and Statistics, pp. 2057-2066. PMLR, 2019.
Yana Di, Ruo Li, Tao Tang, and Pingwen Zhang. Moving mesh finite element methods for the incompressible navier-stokes equations. SIAM Journal on Scientific Computing, 26(3):1036- 1056, 2005.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018
Feng-Lei Fan, Rongjie Lai, and Ge Wang. Quasi-cquivalencee of width and depth of neural networks. arXiv preprint 2xXxx:0002.0255.. 2020.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832- 1841. PMLR, 2018
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference Machine Learning, pp. 2596-2604, 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, pp. 359-368, 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpass- ing human-level performance on imagenet classification. In IEEE International Conference on Computer Vision, pp. 1026-1034, 2015.
Qiang Hu and Hao Zhang. Nearly tight bounds linear regions of piecewise linear neural networks. arXiv preprint arXiv: 1810. 13192, 2018.
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, pp. 1521-1531, 2020.
Xia Hu, Lingyang Chu, Jian Pei, Weiqing Liu, and Jiang Bian. Model complexity of deep learning: A survey. Knowledge and Information Systems, 63(10):255--261, 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.
10

---

Under review as a conference paper at ICLR 2023
Li Jing. Jure Zbontar, et al. Implicit rank-aanniinnn minimizing autoencoder. Advances in Neural Information Processing Systems, 15:11436--17466 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:20/2.09839 2020.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent two-layer nets:
Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34:12978 12991, 2021.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT press, 2018.
Guido Montúfar. Notes on the number linear regions deep neural networks. Sampling Theory Appl., Tallinn, Estonia, Tech. Rep, 2017.
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, pp. 2014.
Yookoon Park. Sangho Lee, Gunhee Kim, and David Blei. Unsupervised representation learning via neural activation coding. In International Conference on Machine Learning, pp. 8391-8400. PMLR, 2021.
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.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
Stefan Schonsheck. Jie Chen, and Rongjie Lai. Chart auto-encoders for manifold structured data. 2019.
arXiv preprint arXiv:
Ayush Sekhari, Karthik Sridharan, and Satyen Kale. Sgd: The role of implicit regularization, batch- size and multiple-epochs. Advances Neural Information Processing Systems, 34:27422-27433, 2021.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions deep neural networks. In International Conference on Machine Learning, pp. 4558- 4566. PMLR, 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Richard P. Stanley. An introduction hyperplane arrangements. In Lecture Notes, IAS/Park City Mathematics Institute, 2004.
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13 (389-496):24, 2004.
Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv preprint 100.001500.08101, 2015.
Csaba Toth, Joseph O' Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. CRC press, 2017.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi. and Ben Recht. Low-rank lutions of linear matrix equations via procrustes flow. In International Conference on Machine Learming, pp. 964 943. PMLR, 2016.
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 Learning Theory, pp. 3635-3673. PMLR, 2020.

---

Under review as a conference paper at ICLR 2023
Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. International Conference on Machine Learning, pp- 10514-10523. PMLR, 2020.
Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. arXiv preprint arXiv: 10599, 2019.
T. Zaslavsky. Facing up to arrangements face-count formulas for partitions of space by hyper- planes. Number 154 in Memoirs of the American Mathematical Society, American Mathematical Society, 1975.
Zaslaavkk.. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Memoirs of American Mathematical Society, 154:1 1997.
Xiao Zhang and Dongrui Wu. Empirical studies on the properties of linear regions in deep neural networks, arXiv preprint arXiv:2001.0107,, 2020.
12

---

Under review as a conference paper at ICLR 2023
A SIMPLICES, POLYTOPES, AND THEIR COMPUTATION
A.1 NOTATIONS OF A NETWORK
For convenience and consisteney, we inherit notations from (Chu et al. 2018). For ReLU network that contains L hidden layers, we write the (-th layer as Lt. Specially, Lp is the input layer, CL+1 is the output layer, and the other layers Li, E (1,2.... L) are hidden layers. Hidden layers' neurons are called hidden neurons. Let ny represent the number of neurons in LT.
( its output, and by Given the i-th neuron of the 1-th hidden layer, we denote by by¹ its bias, by a,
2 the total weighted sum of its inputs plus the bias. For all the ni neurons in Lt. we arrange all their
biases into a vector (( [b
bui their outputs into a vector a (1) = |a ( an
(1)
Neurons in two neighbor layers are linked and their inputs into vector z 2 Zm:
by weighted edges. Denote by w:l the weight of the edge between the i-th neuron in L++1 and the j-th neuron in Lt. For / E (1,..., L). we compute (1+11) by
z (++1) = ( a ( + bb")
(3)
where W(() an n1+1 by-1- matrix.
Let R I be the ReLU activation function. We have a
(2,))
(2, for all / E (1,...; LJ. In
an element- wise fashion, we write (zx)) we have
[0 21] ......
(1)
Then, for I {l,.... L),
(1) (2())
(4)
The input is E X, where X' Rd, and x; is the i-th dimension of x. The input layer Co contains
ni = nodes, where (0) = x,, E (l....,d) dd. The output the network is a (L+1) E y, where y C RM41, The output layer L++1 employs the softmax function: (L++1) softmax (z (2)
A.2 DERIVING POLYTOPES OF A NETWORK
For the i-th hidden neuron in Li, a (z;") (1)
is in the following form:
{
( if 2
(2)))
(5)
(1)
0,
if z < 0,
where (z.") consists of two linear parts. Given network, instance E X' determines the (z] 0 or
z,") According to which part 2 falls into, one can encode the activation status of each hidden neuron by two states, each of which uniquely corresponds one part of (z.")) Denote by c.0 {1, the state of the i-th
value of z 11) and further determines
(2. (2,))= =z(")
hidden neuron in Li, we have 2, (1) 2 0 if and only if c." and z (1) < 0 if and only if c! 0. The states of different hidden neurons usually differ from each other.
Let ( | ( c.. be the states of all hidden neurons in L; and C (c. c,,] specify the collective states of all hidden neurons. C of given fixed network is uniquely determined by the instance x. We write the function that maps an instance x E to a configuration C (1,0) as
conf:: X' + {1, NN,, where N = Ei- ny. Then, we rewrite Eq. (4) as
a ( (0 = ( (z)
(6)
where c(1) z00 is the Hadamard product between c()) and (1)
13

---

Under review as a conference paper at ICLR 2023
By plugging a (0 into Eq.
rewrite z (1++1)
(1+1) w (c o (0)
+ b = 7000 + b:00
where ( = bod and w = w o (0)) is the generalized Hadamard product, such that the entry the i-th row and j-th column of W is W w (!)
By iteratively enforcing Eq. 7 we can write z ((++)),1 , {l...., . L} as
((42)
(()))
2 (2)
Σ h=1
II wi A==+1
b
Substituting z!!) (1(0)x + ( into the above equation, we rewrite
z ((+1),, LE {1...., ,, L}
((+1)=
II (4)
1w0x++bll +
II Amm++11
wr()))
B
Aml
II ((())
bbb
II (V())
Σ
II
wi()) (())
wr(0x)x x + (00))
where ((.))) the coefficient matrix of and (00:.) is the sum of the remaining bias terms. Natu- rally, F(x) is
F(x) = softmax (w7(0:))) x + B(o:)))
(10)
For a fixed network and a fixed instance x, (0:1 and (0:!) are constant parameters uniquely deter- mined by activation states of all neurons: C conf(x). Furthermore, according to Eq. (5). C leads to group of inequalities:
(2c (2) 1) (Wi(0.1) x b (01)) 2 0, / 1= 0, 1I
(11)
which encompasses convex polytope according to the H-definition of polytopes (Chapter 16, Toth al. (0177)) If conf(xx) = conf(x2), X1 and x₂ lie in the same polytope due to the uniqueness.
A.3 COMPUTING #SIMPLICES AND POLYTOPES WITH VERTEX ENUMERATION ALGORITIM
Algorithm Calculate the #simplex of 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 when the total number of neurons in a network is small or ii) when the imput dimension is low. For the former, we can enumerate possible activation states of all neurons by repeating 2 mi times, while for the latter, we can uniformly sample the input space by (t)d times, where is the needed sampling interval, to identify the actual collective states of all neurons. As highlighted earlier, the collective activation states C lead to group of inequalities, corresponding to a polytope. We can solve all vertices of the polytope with the vertex enumeration algorithm [ [Avis Fukuda 1992) find all vertices of polytope. The complexity of the vertex enumeration algorithm scales linearly with the number of inequalities. Then, Delaunay triangulation [Chapter 23, (Toth et 2017]] is executed for these vertices to see how many non-overlapping simplices these vertices can gain. Lastly, count the #simplices. Sometimes, one may not need to compute all polytopes of a neural network. Instead, the polytopes related to data sufficient. For example, in the training-free NAS experiment (Chen eet al. 2021), the authors exhausted all training data and identify associated unique polytopes.
14

---

Under review as a conference paper at ICLR 2023
B ESTIMATION TO THE MAXIMUM #SIMPLICES
B.1 PRELIMINARY
Let's recall some basic knowledge on hyperplane arrangements (Stanley et al. 2004). Let V be Euclidean space. A hyperplane in the Euclidean space V ~ IR", is a subspace H1 = {X E V V. b E I and 4." denotes the inner product. A H C V 1 I S m) is just connected component in the complement set of the union of all hyperplanes
a X = b), where 0 *
region of an arrangement
the arrangement A. Let r(AA) be the number of regions for an arrangement A. Also, simplex in an n-dimensional Euclidean space is just n--dimensional polytope that is the vertices. For example, a triangle
convex hull of simplex in R². A triangulation some polytope is division of the polytope into into simplices.
simplex in IR? and a tetrahedron is a
The following Zaslavsky's s Theorem very crucial in the estimation of the number of linear regions. Lemma (Zaslavsky's Theorem (Zaslavsky 1975 Stanley al. 2004)). Let A be arrangement with m hyperplanes in R". Then, the number r(A) of regions for the arrangement A satisfies
m
r(A)
(12)
i=0
Furthermore, the above equality holds iff A in general position Stanley (204)).
B.2 MAIN RESULTS ONE LAYER RELU NNs
Throughout this paper, we always assume that the input space of an NN is a d-dimensional hyper- cube C(d, B) := (x = (I), .2,..., Id) E IR -B < x4 S B} for some large enough constant B. Note that for 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 5. Let N be a one-layer fully-connected ReLU NN with d input features and n hidden neurons. Then the number of simplices in triangulations of polytopes generated by N is most
d-1
2n Σ
i 2
n -
+ 2d
x=
Proof. Let H1, H2...., B.....,,, Hn be the n hyperplanes generated by n hidden neurons and Hn+1, Ha42............................ Hn+2d be the 2d hyperplanes in the boundary of C(d, B). Then for each < i S. n, the hyperplane H;; may be intersected by other n - 1 hyperplanes in H1, H2...., Hn. hyperplanes in H;, thus by Theorem [ it will divide H, into at most Ei= ("T1) pieces since H; is a (d dim hyperplane. Also, for each 1 S < 2d, the hyperplane Ha+: may be intersected by H1, Hz...., H,, This will produce at most n (d 2)m hyperplanes in Ha+i, thus by Theorem 1 will divide H; into at most Σi= (?) pieces since H; a (d 1)-dim hyperplane. Moreover, each piece could be face of two linear regions, finally we will get at most
This will produce at most
Σ >
2n
2d
1=0
faces for all the polytopes. On the other hand, each simplex in a triangulation of polytope can be corresponding to at least one face 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 simplices in triangulations of polytopes generated by N is also at most
d=
n1
71
2n
+
2d
i
==0
1=0
15

---

Under review as a conference paper at ICLR 2023
The following results gives lower bound for the maximum number of simplices in triangulation of for a one layer fully-connecte ReLU NN.
Theorem 6. Let N be one-layer fully-connected ReLU NN with d input features and hidden neurons. If n corresponding hyperplanes are in general position and C(d, B) is large enough, then the number of simplices a triangulation of polytopes umong all n corresponding hyperplanes is at least
2n
d-1
n-1)
2nd (d (d+ 0(1
d+1
Proof. Let H1, ......... Hn be hyperplanes generated by hidden neurons. Then for each 1 S i I n, the hyperplane H; will be intersected by other n - hyperplanes in H1, Hz...., Hn. This will produce exact
hyperplanes in H, since H1, H2. .... H, are in general position, thus by Theorem 1 it will divide H, into exact Σi= ("7²) pieces since H2 is (d 1)-dim hyperplane. When C(d, B) is large enough,
assume that every such piece has non-empty intersection with (d, B). Therefore, the total sum of number of (d - ff-ee of all linear regions (polytopes) will be at least 2n Σi=o ("-²) since every piece is counted twice. On the other hand, every d-dim simplex has d + distinct (d - dim faces, thus every triangulation with N simplices will contain d-m faces. Therefore, if triangulation of all linear regions (polytopes) of N contains N simplices, then
N + 1) number
N(d + 1) 2n
i=0
and thus
d
2n
- 1
N 2
d+1 1=0
Finally, we derive that a triangulation of all linear regions (polytopes) of N' contains at least 2nd (a+1)d-iy) + O(nd-1) simplices.
2n d-1 ("71)
DE
L
B.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 (Montáfar (017)). Let N be multi-layer filly-connected ReLU NN with input features and L hidden layers with n1, ........ T2L hidden neurons. Then the number of polytopes of N is at min(d, ni, , n.;}-
mulli-layerffllyy-oomeeet
most I1 E5=o m, (")), where
Theorem 7. Let N be 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 simplices in triangulation of polytopes generated by N is at most
2L
(d 1) + O(n 1).
(13)
Proof. First, we prove by induction that the total number of faces generated by A is at most
dL
(d ()!(-L + O(n - 1).
The case L proved Theorem 5 When L 2 2, we assume that Eq. 13 holds for L 1.
Thus by Lemma 2 and the induction hypothesis, the network ''' with the first L 1 layers already has
n d(L-1)
(d!) (1
linear regions and
2m 1I
(d 1)!(d!)--2 + O(n ((n
16

---

Under review as a conference paper at ICLR 2023
faces for all polytopes. Then when we add the L-th layer, for each polytope R. with fn faces in N', the n neurons and the fR faces create at most n + fn hyperplanes R. similar to Theorem 5 these creates
fn
i
faces for all the polytopes in R. Therefore, obtain that the total number of faces is
nd(L-1) (dl) + O(1(L--1-11)
2n
Σ
fR
t=0
R
nd(L-1)
(d)) + + -0((((-1)-1)
2m
2n III-
(d 1)!(d!)b-2 + 0(1((11))11)
dz
On 1).
()!(d))
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 N also at most
(d - L) + O( 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 (Montufar et al. (2014)). Let N be multi-layer fully-comnected ReLU NN with d input features and L hidden layers with n4 hidden neurons in the 1-th layer. Then the maximun number of linear regions of N at least [1--1
T d Σラ= (1))
For the lower bounds, have the following results.
Theorem 8. Let N be multi-layer fully-connectdd ReLU NN with input features and hidden layers with n neurons in each layer. Then the maximum number of simplices in triangulations of polytopes generated by N is at least
n dL
dd(L-1) 1) + #(n
Proof. By Lemma the the maximum number of linear regions is lower bounded by (#) (z) ((( -
dz wa + O(n Also, the number of simplies should be larger than
or equal to the number of linear regions. Thus we obtain the number of simplices triangulation
of polytopes among all n corresponding hyperplanes is at least Ddl + OndL-11).
Now, we can derive Theorems 1 and 2 in the main text.
Proof of Theorem
Directly by Theorems and
Proof of Theorem Directly by Theorems 6 and
17

---

Under review as a conference paper at ICLR 2023
B.4 COMPARISON OF DIFFERENT NETWORK ARCHITECTURES
The aim of this section is to compare the the maximum #simplices based on bounds obtained in Section B.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) (gg(n) if
there exists some positive constants c2 C2 such that cig(n) S f(n) S (2g(n) for all sufficiently large n; fn) ((g(n)) if there exists some positive constant c 0 such that f(n) I cg(n) for all sufficiently large and f(n) ((g(n)) if there exists some positive constant such that f(n) 2 (n) for all sufficiently large n.
The number of parameters for the fully-connected ReLU NN N is easy to compute (Pascanu et al., 2013 Proposition 7).
Lemma 4. Let N be a multi-layer fully-connected ReLU NN with d input features and L hidden layers with hidden neurons in each layer. Then the number of parameters in N is ((Ln²).
Let SN; be the maximum number of simplices triangulations of polytopes generated by 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 4 Theorem | and Theorem [
Theorem 9. Let Nı be a multi-layer fully-connected ReLUU NN with d input features and L hidden layers with hidden neurons in each layer, and d = O(1). Then No has @(In²) parameters, and the ratio of Sv, to the number of parameters of NN is
# parameters Nf = 52( st
SN.
ndL-2
dd(
For one-layer fully-connected ReLU NN N2 with d imput features and Lnd hidden neurons, it has ((n²)) parameters, and the ratio for N₂ is
SN₂
(LL
# parameters of N₂
(d 1 1)!
Sxy From Theorem we obtain that parameters grows at least exponentially fast with the depth L, SN₂
and polynomially fast with the width In contrast, parametens grows at most polynomially fast with the numbers L and n.
Therefore, we have that # parameters N. is far larger than parameters No when L and n are suffi- ciently large. Thus we conclude that folne-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.
SN
SNa
B.5 AVERAGE NUMBER OF FACES LINEAR REGIONS OF NEURAL NETWORKS
In this subsection, we provide the proofs of Theorem 4
Proof of Theorem 4 Similar to the proof of Theorem 3 we obtain that for each linear region S produced by the first (i (i-1)- 1)-th layers of N, the average number of faces in lincar regions of S after adding the i-th layer at most
2ns d-1 (ns
+ d-1 (s))
+
2ns
(n--1 + E ("$)
==
Σd
(1))
n
0i=0 (44)
where f is the number of faces S. For each
Sis 1, we have
2ng: ( : 1) (":)
< 1) f(i + 1) ny
< 2d
2(ns - d d
When ng large enough, 2(ns dd41 should tend to thus the right hand side of the last inequality should be smaller than 2d + 1. Therefore, the average number of faces linear regions of also at most 2d + 1.
18

---

Under review as a conference paper at ICLR 2023
C OTHER PROPERTIES OF #SIMPLICES
One-to-one correspondence via modularization and network transform: simplex is an ele- mentary unit. Proposition shows that an arbitrary ReLU network can be transformed into wide network whose depth is the input dimension and width is determined by the #simplices. Therefore, as long 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 told that two networks have the same #polytopes, one still not totally sure whether two networks are equally complex.
Proposition 1 (#Simplices in network transform (Fan et al. 2020)). Suppose that the representa- tion of an arbitrary ReLU network is h [-B, B - Kh, and M is the minimum #simplices to cover the polytopes to support h, for any > O, there exists a wide ReLU network H of width [ 1)(2 - M and depth D, satisfying that
m m(x1 h(xxx()))))))())) + H(x)}) <
(14)
where m(-) is the standard measure in [-B, B)
19

---

Under review as a conference paper at ICLR 2023
D SUPPLEMENTARY EXPERIMENTS FOR DIFFERENT DEPTHS
Depth-8
Depthe8
Depthe8
3.20-20-20.26222222.0024
80m
3-80- 10--93-90 11--5000----0000 10-00---00
3-160.100. 1i66:100-t00-1kk 1100-10---8---0e-- 1-8--19---6--1660
4000
6009
3000
4019
4000
4000
2000
2303
2000
25
$9
25
50
75
50
100
50 Depth
100
Deptti
3-20-20-33 20-20030000 20-3
3-40 40140 001400-00-1
3. 3-80-800 11-8800--0800 $0-1
3000
6009
6800
2000
4030
1160-160-140-166--166
1000
2000-
0.
Figure 7: The uniformity and simplicity hold true for deep networks under Xavier uniform initialization.
Depdi
Depth-8
Depthe
Depth
60
20.22...200 1.2022.22.22222223333333
-40-400-4--44-000000 40-44-44-00004-44---1
3:38: 83-83 50 101--8--0000 $0-50-0000
3.16e: 260. www.11o--08--10-1e-- 1ew.1-6--10---0
88:
6918
6004
6009
4000
4800
4130
2000
2003
100
25
100
50
100
Dephhs
Depth-5
DepileS
Depthe55
3-20-20-233
$800
8000
4000
69UB
6900
6100
3000
4000
3-40-40-40-40-00-
5.00--0--0-3--0-11
1000
01
75
Figure 8: The uniformity and simplicity hold true for deep networks under Xavier normal initialization.
Depthed
Depth-8
60
2::00-8-220-2-------------0
3-40-48-49-44 40----0----00------111
3:68-900-00- 1608--8--81-00-80-----------31
8000
$4000
4000
6203
6300
3-160-1
60--100-66--188-1ee 18--168---8--66-11
2000
4000
4000
2000
2000
Depdb-5
Depthrrd
Depthr5
Depthrr5
6803
10000
8000
4003
6000
2000
4000
1000
0
1001
180
Figure 9: The uniformity and simplicity hold true for deep networks under Kaiming initialization.
Here, evaluate if the uniformity and simplicity of polytopes still hold for deeper networks. This question non- son-trivial, since deeper network can theoretically generate more complicated poly- topes. Will the depth break the uniformity? We choose four different widths (20, 40, 80, 160).
20

---

Under review as a conference paper at ICLR 2023
Dephh-
Depthed
Deptie8
Depthe8
-0--0-00-50-
60.u
$8c0
6903
6400
6400
2000
2000
0.
Depdi
Deptii -5
Depth 5
Degch
5900
3-20-20-20
40.40 40-4-
3-168-144
6909
5100
60100
4009
4300
4009
2003
2000
2000
25
50
50 100
50
Figure 10: The uniformity and simplicity hold true for deep networks under orthogonal initialization.
For comprehensiveness, the network initialization methods are the Xavier uniform, Xavier normal, Kaiming, and orthogonal initialization. The depth set and 8, respectively, The bias value is 0.01. Likewise, total of 8,000 points are uniformly sampled from [-1, 1 to compute the polytope. At the same time, we check the activation states of all neurons avoid counting some polytopes more than once. Each run is repeated five times. The results under four different initialization are and [0 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 that 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~~10 simplices, while the dominating polytopes for the network --20-20-20-20-22 under Xavier uniform initialization are those with I~5 simplices.
shown in Figures 7
21

---

Under review as a conference paper at ICLR 2023
E SUPPLEMENTARY EXPERIMENTS FOR DIFFERENT BIASES
Bizs-0
Baa-0000
Har 0.00
Bias
12509
6000
10003
4800
4080-
2000
2000
Figure 11: The simplicity and uniformity hold true for different bias values under Xavier initialization.
Biss-O
0.01
Bise 0.05
Bias:0.1
12509
5000-
6000
3000
2000
2000
2000
1860
1080
20
50
75
25
Figure 12: The simplicity and uniformity hold true for different bias values under Xavier normal initialization.
Biasm0.05
12509
10009
5008
4000
2010
3000
2038
2003
1098
1000
10
20
25
50
25
15
25
Figure 13: The simplicity and uniformity hold true for different bias values under Kaiming initialization.
Bise
Bias 0.00
Blas 0.05
Biss 0.1
12509
6/83
5000
4130
3000
5003
2000
2008
Figure 14: The simplicity and uniformity hold true for different bias values under orthogonal initialization.
Here, we are curious about how the bias value of neurons will affect the distribution of polytopes. To address this issue, we the bias values 0.01, 0.05, 0.1, respectively for the network 3-80-40-1
The outer bounding box is 133. A total of 8,000 points are uniformly sampled from [|
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. As shown Figures 13 and [4 for different initialization methods,
observe that 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 uniformity crystal clear. The bias=0 the extremal case, where all hyperplanes the first layer intersect at the original point, and much fewer facets in polytopes created.
22

---

Under review as a conference paper at ICLR 2023
F SUPPLEMENTARY EXPERIMENTS FOR BOUNDING BOXES OF DIFFERENT SIZES
[-1, 1
[-2, 2]
[-5.
1-10,10]
6000
4000
4000
4000
4000
2000
2000
2000
2000
50
50
Figure 15: The simplicity and uniformity hold true for larger bounding boxes under the Xavier uniform initial- ization.
[-1, 1
[-2, 2]
[-5.5]] 5]²
[-10,10]
6000
6000
4000
2000
2000
2000
50
100
Figure 16: The simplicity and uniformity hold true for larger bounding boxes under Xavier normal initial- ization.
[-1, 1]3
[-2, 2]
[-5,
[-10, 101²
6000
6000
4000
4000
4000
2000
2000
2000
50
50
Figure 17: The simplicity and uniformity hold true for larger bounding boxes under Kaiming initialization.
[]
[-2, 2]
[_3
[-10, 10j
6000
6000
6000
4000
4000
4000
4000
2000
2000
2000
2000
50
S0
50
50
Figure The simplicity and uniformity hold true larger bounding boxes under orthogonal initialization.
In the above experiments, we set the outer bounding box to []1, 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 2- 2|3 5,5 [-10, 10 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 0.01. The initialization methods the Xavier uniform. Xavier normal, Kaiming, and orthogonal initialization. The results are plotted Figures [5] [6] 17 and [8] from which we have two observations. First, for different initialization methods, when the size of the outer bounding box
23

---

Under review as a conference paper at ICLR 2023
increases, the number of polytopes increases. This is probably because more polytopes 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.
24

---

Under review as a conference paper at ICLR 2023
G SUPPLEMENTARY EXPERIMENTS FOR NETWORK STRUCTURES
348383
1-8-0-10-1
3-844026-303
1800
100
140
328-6-3
190
4001
13k
100
7700
Figure 19: The simplicity and uniformity hold true for both pyramidal and inverted pyramidal structures under the Xavier uniform initialization.
541-64
54N0
410
0:0
200
200
250-
308-
190
100
200
100
Figure 20: The simplicity and uniformity hold true for pyramidal and inverted pyramidal structures under the Xavier normal initialization.
54K33
SANDMIN
340-62241611
100
6000
2.8
184
018
1:0
180
200
58
200
100
200
180
303
240
Figure 21: The simplicity and uniformity hold true for pyramidal and inverted pyramidal structures under Kaiming 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.
25

---

Under review as a conference paper at ICLR 2023
248-3-
2-00099
190
3.0
194
794
250
0:0
150
300
184
203+
200
94
200+
170
14
290
668-
300
210
58
109
100
Figure 22: The simplicity and uniformity hold true for pyramidal and inverted pyramidal structures under the orthogonal initialization.
Earlier, we have shown that different bias values and bounding boxes do not undermine the uni- formity and simplicity of polytopes. Therefore, here we randomly set the bias value to 0.01, and the bounding box size to | A total of 8,000 points are uniformly sampled from [-1, 1 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-L 3- 20-40-1), (3-40-20-10- 10-00-11111---110001 3-10-20-40-11 1), (3-80-40-20-1) 3-20-40 80- 1), and (3-160-800 1000-00440-0---1 10-1,
1-1020-40080-160- 1). The histograms are shown in Figures 19 20 21 and 22 First, we find that given the same number of neurons, for different initialization methods, the total number of polytopes generated by inverted pyramidal strcutures is smaller than that of pyramidal structures. This might be because neural network is sequential model, the earlier layer forms 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.
26

---

Under review as a conference paper at ICLR 2023
H SUPPLEMENTARY EXPERIMENTS FOR BOTTLENECKS
Here, we investigate the bottleneck layer in network will affect the uniformity and simplicity of polytopes. We randomly the bounding box size to 1-1,1|%, and the bias value 0.01. total of 8,000 points are uniformly sampled from [-1, 1 to compute the polytope. At the same time, we check the activation states of all neurons to avoid repetitive calculation. The initialization meth- ods 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- 10-10000-20-. 1. The histograms are shown in Figures 23
20-0220-1: 3-20-20 10-12022--1,, and 3-20-20- 1-20-10-1-2000
We find that for different initialization methods, the polytopes generated by a network with bottleneck layers are still uniform and simple.
24
25
and 26
33-20-20 201---0-00-0--0--------0-11
3080
2000
2000
208
3-20-30-10-20-206
1000
1080
2000
50
25
50
25
50
50
Figure 23: The simplicity and uniformity hold true for bottlenecks under Xavier initialization.
3-20-10-20-1
3:20:20-10-20-20-
1500
3098
4000
1500
1000
1000
3-20-10-10-29-1
2000
2000
3-20-28-20-10--1 10--200110-10-2222--200
500
500
1080
25
50
50
50
50
Figure 24: The simplicity and uniformity hold true for bottlenecks under the Xavier normal initialization.
4090
2000
3-20-10-28-1
2000
3000
1500
4000
3-20-10-10-29-1
208
3-20-20-10- 10-2020-0-00--0-1
1000
1000
1090
2000
50
50
50
Figure 25: The simplicity and uniformity hold true for bottlenecks under the Kaiming initialization.
4090
3-20-10-20-1
1-20-10-10-20-1
0:20-28-20-10-10-22-----00
2000
3000
2000
3-20-20-10-20-20-
1000
1000
1080
2000
S0
Figure 26: The simplicity and uniformity hold true for bottlenecks under the orthogonal initialization.
27

---

Under review as a conference paper at ICLR 2023
1
SUPPLEMENTARY EXPERIMENTS FOR DIFFERENT DIMENSIONS
Dim
Dim
Dim
12500
8000
12500
6000
10000
7500
4000
5000
5000
2500
2500
500
1000
5000
10000
15000
20000
100000
200000
300000
Figure 27: The simplicity and uniformity hold true for different dimensions under Xavier initialization
Dim-4
Dim=5
Dim-6
10000
6000
8000
4000
6000
6000
4000
4000
2000
2000
2000
250
500
750
1000
5000
10000
15000
100000
200000
Figure 28: The simplicity and uniformity hold true for different dimensions under Xavier normal initialization
Dim
Dim
Dim-6
12500
6000
10000
10000
4000
7500
5000
5000
2000
2500
2500
250
500
750
1000
5000
10000
15000
20000
100000
200000
300000
Figure 29: The simplicity and uniformity hold true for different dimensions under Kaiming initialization
Dim-4
Dim=5
Dim=6
8000
10000
6000
8000
10000
6000
7500
4000
2000
2500
250
750
1000
5000
15000
20000
100000
200000
300000
Figure 30: 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 com- pute the polytopes of three networks: 4-40-20-1, 5-40-20-1, and 6-40-20-1. Due 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 dimensionality. A total of 8,000 points are randomly sampled from [|1, At the same time, 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 initializa- tion. Figures 27 28 29 and 30 show the distribution of #simplices. As the dimension increases, polytope tends have much simplices, while the total number of polytopes only slightly
28

---

Under review as a conference paper at ICLR 2023
increases. We use the triangulation method to compute the number of simplices. According to trian- gulation properties, the maximum number of simplices approximately equals O ((M4/2), where M the number of simplices, and is the dimension. This why the complexity of the linear regions will increase. For different initialization methods, most polytopes those with smaller number of simplices.
29


Reviews:
[{"review_id": "osF5RFGkxr", "reviewer": "Reviewer_H4R5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "1) The paper establishes a theorem to explain why polyhedra produced by deep networks are simple and uniform and the linear region dominates. 2) The paper proves that deep learning does not overfit. 3) The paper promotes the theoretical research of ReLU. 4) The paper is submitted with a basic implementation.", "summary_of_the_review": "I am not very clear about some details and derivations of the paper. In addition, I do not know the impact of the paper on subsequent research work. I would like the author to reply to my question. Also, I would like to discuss this with the other reviewers to determine the final score.", "strength_and_weaknesses": "Strength:\n\n1. The research problem of the paper is very meaningful for deep learning.\n\n2. The paper explains the relationship between ReLU and deep neural network overfitting.\n\n3. The paper gives proof of the theorem. This makes sense for theoretical explanations of deep neural networks.\n\nWeaknesses:\n\n1. The paper explains why deep learning does not overfit. This is contrary to my previous perception. I want to ask what assumptions did the author make when proving this conclusion? Are these assumptions adequately accounted for in the paper?\n\n2. The paper assumes that the input space of an NN is a d-dimensional hypercube. What is the correlation between this assumption and the \nconvolutional neural networks? If The author's analysis here seems only to contain fully connected layers?\n\n3. What implications do the authors' conclusions have for subsequent research? I'm a little confused about what kind of inspiration this proof can bring us.\n\n4. The authors show that deep neural networks do not overfit. However, this conflicts with existing cognition. Has the author analyzed this conflict? Under what circumstances will deep neural networks not overfit?\n\n5. What is the meaning of 3-4-1 in Table 1? I'm a little confused.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VJKjHbGPkkK", "reviewer": "Reviewer_htwS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper refines the study of linear regions in neural networks by analyzing how each linear region can be decomposed into simplices. The authors argue through theoretical results and experiments that most linear regions can be decomposed into very few simplices; hence implying in yet another form that neural networks end up producing simple functions despite their potential to also represent much more complex functions.", "summary_of_the_review": "The paper brings interesting ideas and communicates them in an accessible way for the most part. However, it is not clear to me if all results are correct and whether their experiments reflect what would happen in networks with larger inputs.", "strength_and_weaknesses": "Strengths:\n- The introduction is very well written and gives great context for the problem of analyzing the complexity of neural networks under the optics of linear regions.\n- The idea of studying the complexity of linear regions in terms of their simplicial decomposition seem novel and relevant.\n- If confirmed, the results claimed by the authors provide further insight into what functions we can expect to obtain from neural networks.\n\nWeaknesses:\n- The numerical experiments lack consistency. For example, forms of initialization change between one experiment and another without any justification (sometimes 4 are used, sometimes only Xavier, sometimes only Kaiming). \n- Although Section 4 has ReLU in its title, Subsection 4.2 discusses results with maxout (why?).\n- The only experiment in which the input dimension goes beyond 3 clearly show some gain in complexity of the linear regions, but this seems to be ignored by the authors.\n- As far as I can understand, each plot is based on a single network, which is far from ideal.\n- It is not clear to me what the authors mean by the linear regions being uniform in Section 4.\n- I am curious and puzzled about Theorem 4. Given that linear regions are typically in general position in shallow networks, which implies a large number of linear regions and consequently simpler linear regions, I can easily buy Theorem 3. However, the number of linear regions drops when the network gets deeper. I don't see any intuition for why Theorem 4 should be true.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9hgui0SJUx", "reviewer": "Reviewer_rZ3w", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "It is well known that the function represented by a ReLU network is piecewise linear, with each linear region corresponding to an activation pattern. There have been papers showing that despite the potential number of possible activation patterns being exponential in the number of neurons, the actual number for a typical randomly initialised network is only polynomial in the number of neurons. This paper extends the idea further and argues that the number of faces of the polyhedral linear regions is also small, and hence typical neural nets are not as complicated as the worst case.", "summary_of_the_review": "The paper attacks a novel question, whose significance is of questionable value. ", "strength_and_weaknesses": "Strength:\n\n1. A good mix of theoretical and empirical results for counting the number of simplices.\n\n2. Simplifying the core argument of \"expected number of polytopes\" in Hanin et al. to a simple general position argument clears up some mental space for other arguments.\n\nWeaknesses:\n\n1. The argument that the number of simplices or faces of the linear regions a measure of complexity seems reasonable but needs more validation. e.g. there are easy VC type bounds linking the number of pieces in a piecewise linear function family to generalisation bounds, similar bounds for the number of simplices (without going through the number of linear regions) would be valuable.\n\n2. The statement for Theorem 2 is slightly confusing. \"Maximal number of simplices is at least ...\" what is the maximum over? Do dring the dependence of the different variables clearly.\n\n3. The upper and lower bounds are quite tight (assuming general position assumptions), but the number seems too large to make any reasonable conclusion for even some moderately sized networks -- conditions on the parameters of the neural under which this can be significantly smaller (or larger) would give some insight into complexity of neural nets.\n\n4. The only constraint on the parameters I can see is its requirement to be in general position. For one layer nets that happens with probability 1 under typical inits. But what about the condition in Theorem 4 that generalises to multiple hidden layers? Can you argue that this also happens with probability 1 under typical initialisations?\n\n5. A study on when (for what parameter configurations especially) is the number of simplices small/large would be more valuable, when juxtaposed with other important properties of neural nets, such as generalisation/frequency bias. e.g. questions like are there more simplices after training with random data than true labels? e.g a ranking study of different networks of the same architecture (and same init) trained on same data (but different mini-batches or different learning rates or different optimisation algorithms) on the basis of generalisation error and number of simplices. Do the two rankings agree?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "-XtTWhj65AV", "reviewer": "Reviewer_KuXu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the number of simplices contained in triangulations of all polytopes generated by ReLU networks. From the theoretical viewpoint, the authors prove upper (Theorem 1) and lower (Theorem 2) bounds on the maximal number of simplices. This implies that the average number of faces in a polytope grows only linearly in the input dimension (Theorem 3 and 4, for neural networks with one and multiple hidden layers, respectively). From the experimental viewpoint, the authors demonstrate that, at initialization, most of the polytopes are simple (i.e., have few faces). The authors vary the initialization method, the depth, the dynamic range of the input, the size of the biases and (to the extent allowed by numerical simulations) the input dimensions, showing that their conclusions hold in rather large generality.   ", "summary_of_the_review": "The paper provides an observation about the number of simplices in the polytopes of deep ReLU networks. Even if this observation is novel, the connection to gradient descent training and its implicit bias is not sufficiently well discussed to bring the paper above the acceptance bar. Another (minor) weakness is that the results hold only for networks in which the input dimension is significantly smaller than the number of neurons, and this number of neurons is the same in every layer. ", "strength_and_weaknesses": "Strengths\n\n* To the best of my knowledge, the number of simplices has not been investigated before, as a measure of the inherent simplicity of the solution found by a ReLU network.\n\n* The numerical results show that, at initialization, the polytopes of deep ReLU networks consistently have triangulations composed by few simplices.\n\nKey weaknesses\n\n* The experimental results only concern initialization, and there is a single qualitative experiment concerning the training of the neural network (Figure 8). It is hard to draw any conclusions on the training dynamics in absence of more quantitative results about gradient descent training. \n\n* The theoretical results are interesting, but relatively straightforward and, given the lack of a more formal connection with gradient training, the insight they bring on the phenomenon of implicit bias remains questionable.\n\n\n\nMinor weaknesses\n\n\n* Because of the inherent difficulty of the counting problem, only relatively small input dimensions can be investigated. This makes it very difficult to scale the experiments of this work to any setting where the input dimension is closer to practice.\n\n* The authors seem to always consider the regime in which the number of neurons $n$ is large and the input dimension $d$ is constant. What happens when $d$ is allowed to scale with $n$? In this case, it seems that both the upper and the lower bound of Theorem 1-2 are dominated by $\\mathcal O(n^{dL-1})$. Is it be possible to understand the constant hidden in the $\\mathcal O(\\cdot)$? Do the results of Theorem 3-4 still hold if $d$ is allowed to grow with $n$?\n\n* Can the results be generalized to deep networks in which the number of neurons in the various layers differ? Is some interesting behavior happening in the presence of a bottleneck (i.e., a layer with few neurons in the middle of two layers with many more neurons)?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject