Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies linear regions of a ReLU neural network, which naturally form a "canonical polyhedral complex". They introduce a dual complex, the so-called "sign sequence complex", which is also a generalization of activation patterns. They prove that the sign sequences of the vertices of the canonical complex is sufficient to determine the facet poset structure of the sign sequence complex. They develop and implement algorithms for computing sign sequences and the canonical polyhedral complex, which can be used to obtain topological information of the decision boundary.
strength_and_weaknesses: Strengths
-------------

The strengths of the paper is its clarity and its novel approach. They introduce a generalization of activation patterns, which is very elegant due to its simplicity and in the sense that they induce a polyhedral complex that is dual to the canonical polyhedral complex formed by the linear regions. The authors provide code for computing the objects they introduced, and clear instructions on how to use it.

Weaknesses
-----------------

The biggest weakness of the paper is that it does not clearly answer the following question: What is the advantage of working with the sign sequence approach and the sign complex S(F) over working with the canonical polyhedral complex C(F)?
In detail:

   * There doesn't seem to be an algorithm for computing S(F) without computing C(F). Section 4.1 is titled "Obtaining the sign sequence complex", but the algorithm works by computing C(F).

   * The point about the numerical stability is unclear. Section 4.3 states: "As long as the error in computing solutions to linear equations is small compared to the size of the cells in the polyhedral complex, the proposed algorithm will find the correct sign sequence [...], and [...] the correct combinatorics of the polyhedral complex". But under the same assumptions shouldn't an approximately computed C(F) also have the same combinatorial structure as the exact C(F)?

   * The point about the algorithmic complexity is unclear. Section 4.3 states: "the number of possible combinations [...] is also polynomial in the total number of hidden units". But does that really mean that the algorithm is "polynomial expected time in the number of hidden units"? For each combination one still needs to compute the intersection points, and it is not clear whether the expected number of intersection points is polynomial in the number of hidden units?

Additionally, the paper talks about "decision boundaries", however it only considers networks with a single output dimension, i.e., decision boundaries of binary classification tasks. It would be good if the authors could comment how their work can be applied to decision boundaries of non-binary classification tasks. If the work is only restricted to decision boundaries of binary classification tasks, then this should be clearly stated.

A few very minor comments:

   * Section 3.2, first paragraph: double "a" in "may serve as a a labeling scheme"

   * Section 3.2, first paragraph: missing "the" in "encode all face relationships and [] topology of a network's canonical polyhedral complex"

   * Section 4.1, computing sign sequences: In Point 1., "F_ij" should be "F_1j"

   * Appendix A.1, Definition 1: The definition for polyhedron is wrong, it is for open polyhedra and not closed polyhedra. H_i^+ needs to be the euclidean closure of a connected component of RR^n \ H_i.

   * Appendix A.1, Definition 5: Mention that \pi_j denotes the projection onto the j-th coordinate

   * Appendix A.2, Definition 11: Some of the indices are wrong:
     - F^i maps from RR^{n_{i-1}} (by Definition 4)
     - F_i maps to RR^{n_i} (by Definition 4)
     - R^(i-1) lives in RR^{n_{i-2}} (by Definition 2)

   * Appendix A.2, Definition 13: Mention that sgn(F_ij(C)) denotes the sign of the linear function restricted to C (and not the sign of the points in the image of C under F_ij)

   * Appendix A.2, Lemma 18 onwards: sign sequences are denoted with a capital "S", and not a small "s" anymore.
clarity,_quality,_novelty_and_reproducibility: The clarity and quality of the mathematical portion of the work is great admirable. The paper is both nicely structured and written. The only complaints are minor inconsistencies and typos outlined in "Strength And Weaknesses". Additionally, the code comes with basic documentation and clear guidance for both installation and usage. This makes the work easily reproducible. However, some of the claims that are supposed to demonstrate the advantage of the approach in the paper are unfounded or not well evidenced, see also "Strength and Weaknesses".

The reviewer is not aware of any other work discussing the computation of the canonical polyhedral complex using sign sequences.
summary_of_the_review: The paper describes a very interesting approach to study linear regions of ReLU networks. It is very nicely written, and even closer inspection revealed no mathematical errors in the proofs.

However, the claims that advocate for the superiority of the approach in terms of numerical stability and algorithmic are unfounded. This does not mean that the claims are wrong, just that the paper lacks proof or evidence. Additionally, the main part of the paper restricts to decision boundaries of binary classification tasks without ever mentioning it explicitly in the introduction.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents the mathematical theory and corresponding methods for computing a full characterization of all the linear regions of a neural network with ReLU activations. In other words, it provides the structure of the polyhedron associated with each of the linear regions defined by a rectifier network and its lower-dimensional faces, which I understand as a generalization of the face lattice that would describe a single polyhedron (i.e., one linear region). They further show that the union of the vertices across all such polyhedra along with a sign characterization of those vertices with respect to each neuron (-1, 0, +1) is sufficient to determine the facial structure of the same polyhedra. Whereas this can be combinatorially explosive, the authors argue that this can be used to evaluate the linear regions of a neural network with respect to the low-dimensional subspaces of the input.

In full disclosure, I have previously reviewed this paper when it was submitted to NeurIPS 2022. I do bid to review the same papers when I see potential in them, since I believe this would make the process easier for the authors than starting all over again. Consequently, the wording in my review is very similar to what I wrote before, but I did compare the two versions side by side to make sure my assessment remains the same.
strength_and_weaknesses: On the one hand, the authors are boldly approaching a rather intractable problem, and one which I believe would help us understand what neural networks encode across all their linear regions. In terms of presentation, I liked how the theorems from the appendix were brought in at the point that they would be helpful to continue the discussion. Moreover, the authors included some missing references that overlapped with their contribution and corrected some issues that I spotted when I reviewed their work previously.

On the other hand, it is still my impression that this paper expects too much from the reader and cannot be read on its own. I understand that it is hard to do justice to this work in so few pages, but I believe that would have helped to informally explain the main ideas and how they relate before going very technical (even if that means sending more of the theory to the appendix). One interesting example of that done in practice is Boris & Hanin (2019b). I was really hoping that the authors would have altered their paper to be a little more like that.
clarity,_quality,_novelty_and_reproducibility: In comparison to the version submitted to NeurIPS, I see that there were some significant changes in the second paragraph of the introduction to explain some terms that I could not understand previously. If I am not mistaken, the authors also included a third paragraph after the NeurIPS rebuttal to provide even more context, but this paragraph was not included in this submission. 

I have also noticed other minor modifications elsewhere. I understand that it is difficult to start a paper with too many definitions and that it is hard to define everything that might have been used in related work, but I was hoping to see more definitions presented by section 3 rather than the reader still being referred to the appendix for definitions.


summary_of_the_review: I anticipate other reviewers objecting to the usefulness of a computationally expensive characterization such as the one studied by the authors, but I do believe this is a necessary step if we want to understand what neural networks represent.

With that said, I was hoping for deeper changes that could potentially make this paper more accessible to the machine learning community at large, and I cannot say that the current submission is at the stage yet.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors deal with the problem of identifying the different regions of space as they are partitioned by the parameters of a ReLU neural network, specifically identifying what combinatorial properties govern the induced partition.

The authors provide a combinatorial description of the canonical polyhedral complex of ReLU nets and its dual. They rely on something called the "sign sequence complex" and use it to determine the facets relations and the locations of vertices of the complex.

Having established these theoretical insights, they proceed by implementing and cheking an algorithm to obtain the sign sequence complex. The algorithm appears to work for small values of input dimension, and to be polynomial in the #neurons. Furthermore, the algorithm is numerically well-behaved.

The theory developed also is used to understand some topological properties of ReLU networks and points to the fact that depth is more important than width. (see quick question below too)
strength_and_weaknesses: Strengths are:
+ the paper builds upon the theory of fully-connected ReLU feedforward networks and yield interesting insights about the geometry of neural nets
+ the theory is then used to understand different types of networks, e.g., shallow vs deep, and to identify the exact topology of the linear regions.
+ the paper can serve as further evidence of the benefits of depth in neural nets

Weaknesses/Unclear things to clarify/Questions:
- in terms of theory, I am not convinced about the necessity of exponential dependence in the dimension. Is there an example or counterexample that shows the true dependence should behave like this? (maybe there is a simple example that I am missing out)
- in terms of experiments, I would like to have seen a comparison of the algorithm with simpler algorithms like naive searching of the input space and how it is mapped, or random sampling and tweaking of a starting point moving along some curve or sth. I know these may be trivial baselines, but it's always nice to see "failure" cases too.
-in terms of experiments, can the theory developed be used to learn something interesting about MNIST let's say? or even ImageNET? about the topological properties of the networkds used?
- I am confused about the 4th bullet in the contributions part of the intro (page 2). The statement that at initialization depth seems to be more important than the #aparams of intermediate neurons, isn't is contradicting recent work of Hanin and Rolnick that is cited in the paper (end of section 4.3)? Can there be a clarification please? 

clarity,_quality,_novelty_and_reproducibility: Pretty well-written.

Some typos/clarifications: 
-abstract: "determines" should be "determine" as it refers to locations I believe.
-theorems are numbered 14 and 20, but it would be better to have 1 and 2 so that reader is not confused. Also, the numbering is not consistent or consecutive numbers. Eg Lemma 21 appears after Lemma 23 and 22.

One More Question:
-Even though this is a nice theoretical paper, I would like to ask whether more applications can be described. Is the insight gained useful let's say for optimization purposes? In conclusion, the paper states generalization which makes sense to me.

summary_of_the_review: Overall, the paper looks at an interesting theoretical question regarding how the different linear regions of a ReLU network are positioned into space, how they intersect or not, what is their boundary. The main result is a characterization and an algorithm that finds the different linear regions. Then this is used to understand topological properties of small networks. I believe the algorithm is nice, and perhaps the one that is the natural algorithm to run in order to obtain the boundaries. (looping over intersections and how they are passed through the net).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper had borderline overall final ratings 6,6,5. 

* The main strengths of the paper are mathematical rigour and novelty of a proposed mathematical object to study linear regions in ReLU networks. 

* The main weaknesses are insufficient evidence in support of claims about possible advantages of the proposed methods and concerns about the suitability of the work for ICLR in terms of its motivation, practical utility, and presentation. 
justification_for_why_not_higher_score: None of the reviewers was ready to offer a higher score for the reasons outlined above. I concur with this view. 


justification_for_why_not_lower_score: The article has merits as outlined above.
Decision: Reject