Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:
- 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.
- The idea of studying the complexity of linear regions in terms of their simplicial decomposition seem novel and relevant.
- If confirmed, the results claimed by the authors provide further insight into what functions we can expect to obtain from neural networks.

Weaknesses:
- 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). 
- Although Section 4 has ReLU in its title, Subsection 4.2 discusses results with maxout (why?).
- 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.
- As far as I can understand, each plot is based on a single network, which is far from ideal.
- It is not clear to me what the authors mean by the linear regions being uniform in Section 4.
- 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.

clarity,_quality,_novelty_and_reproducibility: Here are some detailed points about the writing:
- What the authors describe as a face starting in the bold part at the end Preliminary 1 could more precisely be called a *facet*.
- The description of a polytope in Preliminary 3 is a little confusing with so many commas for different purposes in the set.
- In Theorem 2, I would advise the authors against using the term *maximal* if *maximum* would be more precise (they don't mean the same thing).
- Most plots presented in the paper lack axis titles or at least a description in the caption for what the axis title of each plot should be.
- I believe the use of "surprisingly" in the title of Section 4 is completely unnecessary and actually cliché for imitating previous papers.
- In the second line of Section 4, I believe you meant to say "linear regions" when you wrote "simplices".
- The use of "thing" and "pretty small" in Remark 1 is too informal and uninformative.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength:

1. A good mix of theoretical and empirical results for counting the number of simplices.

2. 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.

Weaknesses:

1. 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.

2. 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.

3. 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.

4. 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?

5. 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?

clarity,_quality,_novelty_and_reproducibility: Clarity: 

The paper is mostly clear on its technical contributions, but the discussions relating the results to actual phenomena in neural nets like generalisation and spectral bias is mostly imprecise.


summary_of_the_review: The paper attacks a novel question, whose significance is of questionable value.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

1. The research problem of the paper is very meaningful for deep learning.

2. The paper explains the relationship between ReLU and deep neural network overfitting.

3. The paper gives proof of the theorem. This makes sense for theoretical explanations of deep neural networks.

Weaknesses:

1. 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?

2. The paper assumes that the input space of an NN is a d-dimensional hypercube. What is the correlation between this assumption and the 
convolutional neural networks? If The author's analysis here seems only to contain fully connected layers?

3. 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.

4. 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?

5. What is the meaning of 3-4-1 in Table 1? I'm a little confused.
clarity,_quality,_novelty_and_reproducibility: 1. Clarity:
Some of the proofs of the paper are obscure. Authors are advised to add a Jupiter notebook or more explanations to aid understanding.

2. Quality:
I cannot accurately assess the quality of the paper. I hope the author answers my question in the reply.

3. Novelty:
The paper looks innovative. But I'm not quite sure about the impact of this innovation on subsequent work.

4. Reproducibility:
The point of the paper is not to reproduce the code. I am more worried about whether the conclusions proved by the paper are in line with the actual situation. What assumptions did the author make?
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.   
strength_and_weaknesses: Strengths

* 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.

* The numerical results show that, at initialization, the polytopes of deep ReLU networks consistently have triangulations composed by few simplices.

Key weaknesses

* 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. 

* 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.



Minor weaknesses


* 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.

* 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$?

* 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)?

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written.

The originality is questionable. In fact, the paper adds one more observation to the earlier work by Hanin & Rolnick (2019b): Hanin & Rolnick (2019b) showed that deep ReLU networks have few polytopes, and this paper shows that such polytopes have to be simple (namely with small number of simplices). The theoretical results are interesting, although they remain at the level of a (cute) observation. The numerical results only deal with networks at initialization.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The submission investigates triangulations of the linear regions of ReLU networks. The idea has interesting aspects but it is not convincingly executed. The reviewers agree that the work is not good enough. 


justification_for_why_not_higher_score: The reviewers give good reasons why they did not give this article a higher score. 

I would like to add a few observations that I hope the authors might find useful. 

* Contrary to a claim on pg 2, it is not clear how a direct application of Zaslavsky's theorem could be used to obtain a non-trivial lower bound on the maximum number of linear regions of a deep ReLU network. The referenced work uses an explicit construction. 
* It would be useful to note that for the subdivision of input space the work of Hanin and Rolnick and later also Tseran and Montufar for maxout estimated the number of faces of any dimension, including faces of co-dimension 1. 
* Contrary to a claim on pg 1 and pg 2, the subdivision of input space into regions does not necessarily consist of polytopes strictly speaking but rather polyhedra which may be unbounded and may have fewer than $n_0+1$ facets. 
* On pg 5 it is stated that a "(d-1)-dim face of a d-dim polytope, it can only be a face for one unique simplex in a triangulation of this polytope" and that "thus the total number of simplices ... must be smaller than or equal to the total number of (d-1)-dim faces". However, if a face is not a simplex, then in a triangulation it must be subdivided into simplices, meaning that it will appear on several simplices. Note that for instance a triangulation of a d-cube will need to contain all 2^d vertices of the cube and since each simplex has only d+1 vertices, there will be at least 2^d/(d+1) simplices in a triangulation of the cube, which certainly is larger than the number of (d-1)-dim faces, which is just 2d. 
* Triangulations of polytopes are a non trivial subject that has been explored in the literature, which in my view is not adequately discussed in this submission. 
justification_for_why_not_lower_score: Taking concerns about correctness into account, the article could be given a lower score.
Decision: Reject