Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides an analysis of the impact of data geometry on the regions of linearity in deep neural networks. To this end, it extends previous results by Hanin and Rolnick, which were established in terms of the Euclidean ambient feature space of input data, to account here for nonlinear structure when modeling the data as being sampled from a manifold submersed in this ambient space. The quantities related to the local linear structure of ReLU networks are directly related to the number of neurons, and theoretical results are validated empirically, albeit limited to simplified toy examples.
main_review: The theoretical results presented here are insightful and interesting. To the extent that I could verify, they seem correct, and the empirical validation (even if a bit simplistic) demonstrates them well. The shift from Euclidean space to intrinsic manifold yields interesting differences in the results from previous work by Hanin  and Rolnick, such as eliminating exponential growth in the bounds established in the latter. It should be noted that the results here focus on capacity over unoptimized (randomly initialized) networks, and do not cover aspects in learnability. However, I believe the topics explored and exposed here are of interest in their own right, even without addressing the effects of learning or optimization of the network.
summary_of_the_review: As said in the main review, this is an interesting and insightful work. Its main focus is theoretical, and clearly expands on previous work in a non-trivial way. Empirical results are somewhat simplistic, but as their main purpose is to demonstrate theoretical results this is fine in the context of this submission. Therefore, I recommend accepting it and look forward to seeing it presented in the conference.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study average-case representation capacity of random ReLU neural
networks, as measured through their linear regions, as in Hanin and Rolnick
2019 -- the difference in the authors' setting is that they consider the input
space to be defined on a low-dimensional manifold, whereas Hanin and Rolnick
considered inputs on the solid cube. The authors derive analogues of each of
the results of Hanin and Rolnick in the manifold setting -- these results
include formulas for the "average volume density" of linear regions, a proxy
for the exact number of linear regions, and the average distance to the
boundary of the linear regions -- where the dimension dependence is on the
intrinsic manifold dimension rather than the ambient dimension, and additional
constants appear that depend on properties like curvatures of the manifolds.
They provide toy experiments to verify the theory (involving testing linear
region properties on a pair of 1D manifolds with different curvatures), as well
as an experiment on 'manifolds of faces' generated by the StyleGAN model -- in
both cases, the linear regions are studied throughout training rather than just
at initialization (as the theory pertains to).


main_review: 
### Strengths

- The study of data with low-dimensional manifold structure is important for
  understanding practical performance of neural networks, so the problem the
  authors study is well-motivated.
- Some of the geometric results that are relied on to enable the proofs are
  somewhat esoteric, at least with respect to the ML literature. Therefore the
  fact that the authors have collected them in their proofs may be a useful
  contribution. Although I have not checked every proof line by line (see some
  comments below), roughly the right kinds of tools seem to be in use here
  (transversality; manifold coarea formula; mean curvature estimates;
  geodesics; ...).

### Weaknesses

- The theoretical content of the paper is very incremental -- in effect, it
  consists of a translation of the results of Hanin and Rolnick to the setting
  of manifold data. In particular, almost all arguments of Hanin and Rolnick
  are reproduced in the proofs of this paper (the theorems are in one-to-one
  correspondence, for a start), just with the corresponding concepts for
  manifolds substituted in (for example, replace Hanin and Rolnick's coarea
  formula with the smooth coarea formula; replace integration over euclidean
  space with integration with respect to the volume form on the manifolds, and
  handle the corresponding curvature and "reach" quantities that arise, which
  leads to the new constants relative to the theorems of Hanin and Rolnick). As
  in the previous section, there may be a useful contribution just in the
  organization of these manifold concepts; on the other hand, the *stylistic*
  similarities between the proofs of the authors and the corresponding proofs
  of Hanin and Rolnick is sometimes uncanny (for example, compare the content
  of section E of Hanin and Rolnick to the content of section F of the current
  submission).
- In a similar vein, the writing style of the authors is often imprecise, in
  that the framework of the paper is so identical to that of Hanin and Rolnick
  that certain notions that were defined in Hanin and Rolnick's paper are taken
  for granted by the authors. For example, the notations for the neural
  network's neurons at the top of page 4 are not defined correctly because
  Hanin and Rolnick do not define these precisely (the weights in the formula
  should be "full", rather than single neurons, and the "column of weights"
  does not make sense here, unless the notation is transposed for some reason
  relative to equation (1)); the discussion of dimensions at the bottom of page
  4 does not mention transversality (it is discussed in the appendix) or in
  particular that these results hold only almost surely; nowhere is it
  mentioned concretely that the weights of $F$ need to satisfy certain
  assumptions on the density until the beginning of the appendix (these are
  important e.g. in the context of the transversality claim made in the body,
  because this is not true for general initializations).
- The presentation of theorem 3 seems to be unnecessarily uninsightful: for
  example, one naturally wants to understand when this result is
  non-vacuous. In addition, the proof has some odd aspects: it seems to
  use an asymptotic statement for $C_{\kappa, k}$ in $\epsilon$, but the
  theorem asserts the result for all $\epsilon > 0$ and does not show that this
  constant depends on $\epsilon$. It seems that this result needs to be
  rewritten to be asymptotic for small $\epsilon$ -- this should also enable a
  more precise conclusion to be asserted, similar to in Hanin and Rolnick
  2019a. This makes me feel like the other proofs may need to be checked for
  minor errors or imprecisions that affect the statements of the results
  (specifically, the constants).
- The experiments conducted and the authors' discussion of them does not
  provide very much insight into the unique circumstances present in the
  manifold case, relative to what is known and expected from Hanin and
  Rolnick's work. For example, the toy experiments are helpful to see the
  effect of curvature, but this should be investigated more systematically
  across many geometries to give a sense of what is going on (the authors only
  provide minimal interpretation of their results in the captions of each
  figure). The StyleGAN results should be discussed more at length -- only one
  figure is presented, and it is not completely clear what the implication is
  (the task consists of fitting a neural network to face images with random
  labels, and then looking at "off manifold" and "on manifold" linear region
  counts, which are different -- what is the implication of this study for
  practice?). This is important because it relates to the authors' stated aim
  for the paper.
- There are missing references to highly related work motivated similarly to
  the authors. The authors only mention other theoretical works on interactions
  between neural networks and manifold data in passing in a sentence in section
  5 -- a more detailed comparison should be made that highlights what the
  authors contribute to this context. In addition, the only works the authors
  reference are about approximation properties of deep neural networks on
  manifolds: there are also very relevant works on algorithmic results for
  training DNNs to perform classification/regression on manifolds, e.g. [2-6]
  below. Again, it would be best to discuss this context in detail in the
  related work/intro.


### Minor Points
- It is best not to use wikipedia links (bottom of page 6) -- these should be
  changed to the corresponding references used in the proofs.

### Mentioned references

[1] http://arxiv.org/abs/2006.13409

[2] http://dx.doi.org/10.1103/PhysRevX.10.041044

[3] https://openreview.net/forum?id=O-6Pm_d_Q-

[4] http://arxiv.org/abs/2107.14324

[5] https://arxiv.org/abs/2106.04156

[6] http://arxiv.org/abs/2006.13409


summary_of_the_review: The work represents a theoretical generalization of the results of Hanin and
Rolnick on linear regions in random ReLU networks, but it is an incremental
one, with proofs whose structure nearly agrees with those of the prior work.
The empirical results could be more systematic in helping to illustrate the
key novel differences between this setting and the previous setting, and why
they are important.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper investigates the number of linear regions of deep neural nets. More specifically how deep neural nets split the input data manifold into regions where it behaves approximately linearly.  It generalizes the results by Hanin and Rolnick 19’ to the manifold setting. Two theoretical bounds: 1) an upper bound for the number of linear regions and 2) a lower bound for the average manifold distance between points on the manifold to the linear boundary. Experiments were done on both toy datasets and MetFaces dataset. 
main_review: The main results extend the recent results by Hanin and Rolnick 19’ on the density of linear regions and the distance from points to the linear boundary from a compact set to the manifold setting. The extension is meaningful in that it takes advantage of the structure of high-dimensional data and makes the theoretical results more applicable to real-world data. 

The bounds depend on the number of neurons, neural net architecture, the distribution of biases,  and the geometry of the manifold.  The experiments on two toy datasets were designed to demonstrate the effects of manifold geometry and the neural net architecture. Although the toy example helps understand the effects of all terms. There seems to be a gap between the toy example and applying the analysis to real-world data. If C_M of real datasets are unknown, can the author give examples of what kind of analyses can be done besides the one example in Figure 9. Overall I think the paper can benefit from more empirical results and discussion.

summary_of_the_review: Overall I think the paper can benefit from more empirical results and discussion. While the extension to the manifold setting is a valuable contribution by itself. The significance lacks empirical support.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically characterizes the number of linear regions of ReLU neural networks at initialization. Compared to existing results, the authors take the data manifold into consideration, and the number of linear regions is measured on the data manifold. Moreover, for uniformly random sampled data on a compact manifold, the expected (geodesic) distance to the linear boundary is analyzed.

To further support the theory and also extend to the behavior through the training process, the paper provides synthetic data and real data experiments. There are indications of the number of linear regions does not deviate significantly from their initialization and is faithful to the data manifold dimension.
main_review: Strengths:

The structure of the paper is clear. I believe that the study of linear regions of ReLU networks possesses value and has interesting implications. Taking data intrinsic structures into consideration is very important in understanding deep learning, as pointed out by the authors, practical data are often low-dimensional due to local regularities, symmetries, etc. In addition to theoretical study, the paper also provides numerical experiments, in support of the theory.

Weakness:

1. Technical ambiguity. The presentation of theoretical results suffer from some ambiguity. For example, on page 5 before Definition 3.1, the explanation of Jacobian of a function may be elaborated with formal mathematical expressions and necessary verbal description. Another example is in Theorem 1. Quantity $Y_{z_1, \dots, z_k}$ is defined by some expression, times the indicator function of the event that $z_j$ is good at $x$ for $j = 1, \dots, k$. The reviewer found this paragraph very complicated and hard to follow. It can be better explained to define $Y_{z_1, \dots, z_k}$ before the statement of the theorem.

Theorem 2 and 3 both involve several parameters $C_{\rm xxx}$ depending on the geometry of manifold, initialization of weights, etc. However, even looking into the proofs, these parameters are not explicitly given. This in turn makes clear interpretations of Theorem 2 and 3 elusive. The reason I am asking this is two-fold: (1) on page 4, the results in Hanin & Rolnick (2019a) are summarized in a very clean form. Nonetheless, the results in Theorem 2 and 3 seem not comparable with Hanin & Rolnick (2019a). Some quick glance can result in with data intrinsic structures, Theorem 2 indicates a worse polynomial dependence on the size of networks. Moreover, it is possible to choose an optimal $\epsilon$ in Theorem 3. (2) In experiments, there are extensive discussion on $C_M$ and $C_{\rm grad}$. While without any explicit formulas, it is hard to expect how will $C_M$ and $C_{\rm grad}$ scale with the problem setting.

2. Unclear connection with expressivity of neural networks. The experiments devote to plot the number of linear regions resulting from initialization and training. However, there is no connection between the performance of the network with the number of linear regions. For example, in periodic regression problems, what is the testing error? Does it have any correlation with the number of linear regions across 20 runs? When changing the number of neurons, does the number of linear regions change correspondingly as predicted by Theorem 2?




summary_of_the_review: The paper displays a systematic treatment of studying the number of linear regions in ReLU neural networks. However, the theories and experiments have some issues, which undermine the overall quality of the paper.
review_title: null

Meta-review: The paper studies the effect of manifold geometry on the complexity of the function implemented by a random ReLU network, as measured through its decomposition into linear / affine regions. In particular, it provides bounds on a surrogate for the number of such regions and the distance of a fixed point to the boundary of its region. These bounds follow from an extension of an argument of Hanin and Rolnick for Euclidean space. The bounds hold at random initialization, and are complemented with experiments in which they remain valid through training. 

Initial reviews of the paper were mixed. All reviewers recognized the extension to structured / non-euclidean data as an important direction, and the results as extending the argument of Hanin and Rolnick to this setting. At the same time, there were questions about the novelty, clarity, and implications of the paper. One issue concerns the implications of the results and the amount of insight they offer into the data complexity - network complexity relationship. In particular, the paper would be stronger with a more explicit accounting for the constant C_{M,\kappa} and intuitive explanations of how manifold properties such as curvature and reach affect the number of linear regions. There were also concerns regarding the statement and proof of Theorem 3, the initial version of which only held for small \epsilon. The review also raised other smaller issues regarding the paper's clarity and implications. After considering the authors feedback and revisions, reviewers retained their mixed evaluation of the paper. This appears to be a promising direction, but a paper that could benefit from further refinement.
Decision: Reject