Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies how randomly initialized ReLU networks split the data into linear regions. It is based on Hanin and Rolnick [2019a] but focuses on data with low dimensional manifold structure.  It provides an upper bound for the density of the linear regions, which results in a lower bound for the average distance to the boundary of all linear regions. This lower bound is inverse linear in the number of neurons and related to the geometric properties of the manifold. The authors then empirically verify their statement over both synthetic datasets of two parameterized curves and one realistic dataset of a curve generated from StyGAN. 
strengths_and_weaknesses: Strength: 
The problem this paper trying to solve is interesting. In many applications, data exhibit low dimensional or low dimensional manifold structures. Understanding how the intrinsic dimension and geometries interact with the deep network is an interesting problem. The paper is able to relate the average distance from the linear region to parameters depending on the scalar curvature and dimensionality of the manifold, while still preserving the same dependence on the number of neurons as in the Euclidean case. The experiments are insightful and support the intuitions of the theory.

Weakness: 

1. The paper mostly serves as a theoretical paper, but some key definitions are not presented in a clear and rigorous way. The paper is partially based on Hanin 2019 so the authors seem to adopt some of the notation in that paper without further clarification. For example, the definition of $\mathcal B_{F, k}$ defined in line 162 is not clear in the first read. I need to go and forth between this and Hanin's paper to understand a similar definition and the relationship between them. I would encourage the author to provide a formal math definition of $\mathcal B_{F, k}$ in the appendix. 

2. The role of the geometries of the manifold is not clearly laid out in the theorem. The key benefit of considering data with structure is to understand how the structure interacts with the neural networks. Theorem 3.4, which is the main theorem of the paper, is very similar to the Euclidean case in the sense that it has inverse dependence over the number of neurons. However, the definition for $C_M$ and $C_{M, \kappa}$ is not provided in an intuitive way for the readers to understand the relationship between the geometries of the manifold and average distance. For example, one would like to know how $C_M$ and $C_{M, \kappa}$ depend on the scalar curvature and dimension of the manifold. In the current form, it would be hard for the reader to understand the exact benefit of considering data with low dimensional manifold structure. 

3. The linear region density (left-hand side of equation on line 145 or line 202) only serves as a proxy for the number of linear regions. In the later work of Hanin and Rolnick [2019b], the number of linear regions would still depend on $(\text{neurons})^{n_{in}}$. So Theorem 3.3 does not provide a bound for the number of linear regions directly. 


Minors:
1. Line 126, it should be $z(x) = W_{l-1}\sigma(\cdots \sigma(B_1 + W_{1}(x)))$. In line 127, it should be $z(x) = W_{1, z}(x)$. 
2. Line 22 in the appendix should be $g_{ij}(x)$. 
3. Many reference links in the appendix are broken. 
4. In appendix line 216, the definition of $Ker(D_MH_k)^\perp$ should be $Ker(D_MH_k)^\perp = \set{a \vert a \cdot z = 0 \forall z \in Ker(D_MH_k)}$ instead of for some $z$. 


questions: The questions would be related to some of the comments above.

1. The role of dimensionality and curvature. Are we able to relate $C_M$ and $C_{M, \kappa}$ to some intrinsic characterization of the manifold, like dimension or scalar curvature? How will the dimensionality of the manifold affect the number of linear regions or the average distance? Also, $C_{M, \kappa}$ is defined by $p_U(\zeta)$, which has an inverse dependence on the number of neurons. Why $C_{M, \kappa}$ will not depend on the number of neurons? 

2. The role of the depth of the network. One key observation in Hanin and this paper is that the number of linear regions has minimum dependence on the number of neurons. On the other hand, a deeper network would have more expressive power. It would be nice to observe this through experiments. In figure 8, there are attempts to understand how different choices of the network structure affect the number of linear regions. However, they are all two-layer networks. If one tries a deep network structure, will the result remain the same? 

3. As argued in section 3, one cannot apply Hanin's result directly because $Vol_{n_{in}}(M)$ is $0$. One can consider an $\epsilon$ neighborhood of $M$ and try to bound the volume by the geometric properties of the manifold. How is this approach different from the one in the paper? In other words, will this approach give non-optimal bounds compared to looking closer to the intrinsic characterization of the manifold? 

limitations: The authors have adequately addressed the limitations and potential negative social impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: With the assumption that a dataset is sampled from a low dimensional manifold, this paper incorporated such data geometry into measuring the effective approximation capacity of DNNs by deriving average bounds on the density of boundary regions and distance from the linear boundary, which is reported in previous work by Hannin and Rolnick. 
strengths_and_weaknesses: Strengths:

Originality: this work builds upon previous work by Hannin and Rolnick, which establishes the linear regions in deep networks, and provides an original study on how neural networks with ReLU activation can split data manifolds into regions where the neural network behaves as a linear function. 

Quality: the study is of relatively good quality. Bound on the number of linear regions and the distance to boundaries of these linear regions on the data manifold are derived. 

Clarity: the paper is very clearly presented. 

Weaknesses: 

Significance: while building upon Hannin and Rolnick's previous work, the significance of this extension is not very clear, especially how this work leads to understanding the expressivity of deep networks on non-Euclidean data sets. 
questions: Would it be possible to provide an example of how the findings of this study can help with users of deep neural networks to design, explain, and improve their systems? 
limitations: As mentioned by the authors, proving a lower bound on the number of linear regions still remains open.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the data geometry of randomly initialized deep neural networks with ReLU activation. Motivated by the manifold hypothesis, the authors present an extension of the previous result in Hanin and Ronick [1], where the previous assumption of uniform sampled data on the entire input space is relaxed to sampling on submanifolds. The authors develop analogous upper bounds on the density of boundary regions, and lower bound on expected distance to the boundary. The authors then verified their results empirically using both synthetic datasets and the MetFaces dataset.

[1] B.Hanin and D. Ronick. Complexity of linear regions in neural networks, ICML 2019.
strengths_and_weaknesses: __Quality and Clarity__: The paper is in general well-written. I enjoyed reading the motivations of the paper, as well the interpretation sections for the theorems. While I have not checked the proofs carefully, the progression of the theorems make sense to me. The experiments also empirically support the author’s interpretations, though I have some questions which I will ask in the next section. 

__Originality and Significance__: The paper is mainly an extension of the previous Hanin and Ronick paper onto the submanifold case. While the framework here is not new, I believe it is still a novel result, as the relaxed assumption of the data lying on a submanifold is indeed more realistic. That said, I am personally not a researcher in this field, and I would refer to other reviewers for further evaluation of the significance of the results. 
questions: I am looking at your final experiment on the MetFaces dataset (in Figure 9). 
- While I do agree that the neural network would eventually overfit, I would like to understand when the network starts to overfit, and whether that corresponds to the epoch when the number of linear regions starts to “plateau”.
- Have you tried comparing the plots of number of linear regions, together with the evolution of training/testing error of the network? Are there any correlation in the trends of these plots?
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper continues the work of Hanin and Rolnick [1,2] on the expressivity of PieceWise Linear (PWL) Deep Neural Networks (DNNs).
The main Contribution (**C1**) involves improving the theoretical bounds of both the number of linear regions and the average distance to the linear boundaries defined by a PWL DNN, by taking into account the geometry of the input manifold. The authors also provided a toy example to empirically validate the results. In addition, they performed an experiment of natural images (**C2**), to empirically show that both memorization and closeness to the data manifold have an effect on the density of linear regions.

### References
- [1] Boris Hanin and David Rolnick, “Deep ReLU Networks Have Surprisingly Few Activation Patterns”, NeurIPS 2019. 
- [2] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.
strengths_and_weaknesses: ### Strengths
- (**Strength 1**) The paper addresses the significant problem of extending the bounds on expressiveness metrics of PWL DNNs in [1,2], by taking into account the dimensionality and geometry of the input manifold.
- (**S2**) I really liked the toy example as a way to validate the analytical results, although the clarity could be improved.
- (**S3**) The authors helped the reader in understanding the intuition behind the theoretical results by providing useful Figures (1 and 2 in the main, 1 and 2 in the Appendix).

### Weaknesses
With regard to the weaknesses, some of the experimental results (2 out of 3) are not sufficiently clear or do not provide a significant contribution:
- (**Weakness 1**) **Sect. 4.2**: The authors claimed to have obtained results (Figures 6 and 7) in contrast with [2]. However, it is not clear to me which result in [2] the authors are referring to (see Questions).
- (**W2**) **Sect. 4.3**: the MetFaces experiment represents an additional, separate contribution (**C2**), but due to lack of space the results were not validated by enough empirical tests. For example, claiming a relationship between the decreasing number of linear regions during training and memorization was not validated against any hyperparameter change, as it was done in [1]. In fact, the behaviour of the number of regions in an overfitting scenario was shown in [1] to be dependent on both the number of points to be memorized against the capacity of the network and the performance of the model (not reported). 
- (**W3**) **Sect. 4.3**: the second result of the MetFaces experiment, i.e. the difference in the number of regions in and out of the data manifold was already shown in [3], Figure 2, with a slightly different experimental setting. Although using a GAN to fit the in-distribution manifold is a nice idea, the obtained result, in my opinion, doesn't contribute to the overall significance of the paper.

### Concluding Remarks
Although the paper addresses a significant research question, validated with a toy example, I think that more empirical experiments should have been devoted to the main contribution (the role of the manifold geometry), instead of focusing on the role of memorization and closeness to the data manifold (both already analyzed in-depth in previous papers [1,3]). Moreover, I have doubts about some of the claims resulting from the experimental results, which either are not clear or do not address the limitation of the experimental evaluation.

### Reviewer-Authors Discussion
After the reviewer-authors discussion, I increased the rating of both soundness and presentation. Moreover, I increased the overall rating from 4 to 6. Please refer to the discussion for the details.

### References
- [1] Boris Hanin and David Rolnick, “Deep ReLU Networks Have Surprisingly Few Activation Patterns”, NeurIPS 2019. 
- [2] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.
- [3] Roman Novak et al., “Sensitivity and Generalization in Neural Networks: An Empirical Study.” ICLR 2018.
questions: ### Questions
- With regard to (**W1**), to my understanding, in [1] (Theorem 1, page 3) the authors claimed that "The same result holds when computing the number of linear regions along any fixed 1-dimensional curve in a high-dimensional input space.", confirming the results obtained in Figures 6 and 7. The informal (not proven) claim in [1] about the exponential growth of regions with the input dimension in my opinion refers to the input manifold size $m$. In this regard, it would have been interesting to test the number of regions with increasing size $m$ of the manifold. Please better clarify the statement you are referring to and why your empirical results are in contrast with it.
- With regard to (**W2**), I didn't fully why should you claim in Sect. 4.3 that overfitting is the cause of the decrease in the number of regions during training. In my opinion, it could be a result of the chosen hyperparameters. Can you clarify your intuition?

### Minors and suggestions
- section 4.1 could have been more clear. In particular, please explicit that the domains of Sphere and Tractrix are similar for the sake of comparability, i.e. $[-\pi, \pi]$ and $[-3, 3]$, and that the parameters of the target function are the same.
- for the sake of consistency, are the x, y and z-scales in Figure 1 (a) the same as the ones used in the experiments?
- please explain how you computed the density in Figure 9.
- please report the performance of the PWL DNN used in Figure 9.
- use either “piece-wise” or “piecewise” in the text.
- line 248 (main): Figure 11 is probably Figure 2 of the Appendix.
- line 264: in the equation of the tractrix y should be t.
- line 22 (Appendix): typo of the subscript.
- broken refs in the Appendix.

### References
- [1] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.

limitations: I would have addressed the role of hyperparameter selection in the experimental results since previous work clearly stated that size, learning rate, and other hyperparameter choices have an effect on the evolution of the number of linear regions during training.
review_title: null

Meta-review: metareview: The paper studies the number of linear regions cut out by a randomly initialized deep network, for data with low-dimensional structure (manifold structured data). The main results pertain to the density of linear regions and the average distance to the boundary of a linear region: these results take the same form as in the Euclidean case (with distance inversely proportional to the number of neurons), but depend on geometric properties of the data manifold — in particular, its dimension and curvature. Reviewers generally appreciated the relevance of the paper’s setting: data arising in applications often have low-dimensional structure, and understanding how deep networks interact with the structure of data is an important research direction. At a technical level, the paper builds on techniques of [Hanin and Ronik 2019], but extends these results to manifold structured data. Questions raised by the reviewers include the role of curvature and input dimension in the results and the interpretation of real data experiments. After interacting with the authors, the reviewers considered their main concerns about the paper to be well-addressed. The AC concurs, and recommends acceptance. 
confidence: Certain
Decision: Accept