Effects of Data Geometry in Early Deep Learning
Authors: Saket Tiwari
George Konidaris
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep learning
geometry
manifolds
deep learning theory

Abstract: Deep neural networks can approximate functions on different types of data, from images to graphs, with varied underlying structure.This underlying structure can be viewed as the geometry of the data manifold. By extending recent advances in the theoretical understanding of neural networks, we study how a randomly initialized neural network with piecewise linear activation splits the data manifold into regions where the neural network behaves as a linear function. We derive bounds on the number of linear regions and the distance to boundaries of these linear regions on the data manifold. This leads to insights into the expressivity of randomly initialized deep neural networks on non-Euclidean data sets. We empirically corroborate our theoretical results using a toy supervised learning problem. Our experiments demonstrate that number of linear regions varies across manifolds and how our results hold upon changing neural network architectures. We further demonstrate how the complexity of linear regions changes on the low dimensional manifold of images as training progresses, using the MetFaces dataset.

Under review as a conference paper at ICLR 2022
EFFECTS OF DATA GEOMETRY IN EARLY DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks can approximate functions on different types of data, from images to graphs, with varied underlying structure. This underlying structure can be viewed as the geometry of the data manifold. By extending recent advances in the theoretical understanding of neural networks, we study how randomly initialized neural network with piecewise linear activation splits the data manifold into regions where the neural network behaves as a linear function. We derive bounds on the number of linear regions and the distance to boundaries of these linear regions on the data manifold. This leads to insights into the expressivity of randomly initialized deep neural networks non- non-Eucee Non-Euclidean data sets. We empirically corroborate our theoretical results using a toy supervised learning problem. Our experiments demonstrate that number of linear regions varies across manifolds and how our results hold upon changing neural network architectures. We further demonstrate how the complexity of linear regions changes on the low dimensional manifold of images as training progresses, using the MetFaces dataset.
INTRODUCTION
The capacity of Deep Neural Networks (DNNs) to approximate arbitrary functions given sufficient training data in the supervised learning setting well known (Cybenko 1989 Hornik al. 1989 Anthony & Bartlett 1999). Several different theoretical approaches have emerged that study the effectiveness and pittalls of deep learning. These studies vary in their treatment of neural networks and the aspects they study range from convergence (Allen-Zhu et al. 2019 Goodfellow & Vinyals 2015), generalization (Kawaguchi et al., 2017 Zhang et al.| 2207 7| Jacot et al. 2018 (Sagun et al. 2018), function complexity (Montúfar et al. 2014, Mhaskar & Poggio 2016). adversarial attacks
(Szegedy et al. 2014 Goodfellow et al. 2015) to representation capacity (Arpit et al. 2017)) Some
recent theories have also been shown to closely match empirical observations (Poole et al. 2016
Hanin & Rolnick 2019b Kunin et al. 2020).
One approach for studying DNNs is to examine how the underlying structure, geometry, of the data interacts with learning dynamics. The manifold hypothesis states that high-dimensional real world data typically lies low dimensional manifold (Tenenbaum) 1997; Carlsson al.. |007] Fefferman et al. 2013). Studies have shown that DNNs are highly effective in deciphering this underlying structure by learning intermediate latent representations (Poole al. 2016). The ability of DNNs to "flatten" complex data manifolds, using composition of seemingly simple piece-wise linear functions, appears to be unique (Brahma et al. 2016 Hauser & Ray 2017).
DNNs with piecewise linear activations, such as ReLU (Nair & Hinton 2010), divide the input space into linear regions, wherein the DNN behaves as a linear function (Montúfar et al. (0144). The density of these linear regions serves as proxy for the DNN's ability to interpolate a complex data landscape and has been the subject of detailed studies (Montáfar et al., 2014, Telgarsky 2015 Serra et al.. 2018. Raghu et al.] (017). The work by Hanin & Rolnick (2019a) on this topic stands out because they derive bounds on the average number of linear regions, as opposed to worst case bounds, and verify the tightness of these bounds empirically for deep ReLU networks. Hanin & Rolnick (2019a) conjecture that the number of linear regions correlates to the expressive power of randomly initialized DNNs with piecewise linear activations. However, they assume that the data is uniformly sampled from the Euclidean space Rdd, for some d. By combining the manifold hypothesis with insights from Hanin & Rolnick (2019a), are able to go further in estimating the the number of linear regions

---

Under review as a conference paper at ICLR 2022
and the average distance from linear boundaries. We derive bounds on how the geometry of the data manifold affects the aforeementioned quantities.
To corroborate our theoretical bounds with empirical results, design toy problem where the input data is sampled from two distinct manifolds that can be represented in a closed form. We count the exact number of linear regions these two manifolds that randomly initialized neural network splits them into. We also observe the average distance to the boundaries of linear regions. We demonstrate how the number of linear regions varies for two distinct manifolds in our setting, These results show that the number of linear regions on the manifold do not grow exponentially with the dimension of input data. Our experiments do not provide estimates for theoretical constants, as is the case in deep learning theory, but demonstrate that the number of linear regions change as consequence these constants. We also study high dimensional data that lies on low dimensional manifolds with unknown structure and how the number of linear regions vary and off this manifold, which is a more realistic setting. To achieve this we present experiments performed on the manifold of natural images. We sample data from the image manifold using generative adversarial network (GAN) [Goodfellow et al. 2014) trained on the curated images of paintings. Specifically, we generate images using the pre-trained StyleGAN (Karras et al., 2019 2020b) trained on the curated MetFaces dataset (Karras et al., 2020a). We also assign random labels to the images in the dataset and train a deep ReLU network in a supervised manner, scenario in which it would overfit (Zhang et al. (017). We generate curves on the image manifold of faces, using StyleGAN, and show how overfitting is reflected the density of linear regions of the aforementioned deep ReLU network.
PRELIMINARIES AND BACKGROUND
Our goal is to understand how the underlying structure of real world data matters for deep learning. We first provide the mathematical background required to model this underlying structure as the geometry data. We then provide a summary of previous work on understanding the approximation capacity of deep ReLU networks via the complexity of linear regions. For the details on how work fits into the theory of DNNs we refer the reader to Appendix C
2.1 DATA MANIFOLD AND DEFINITIONS
We use the example of the MetFaces dataset (Karras et al. 2020a) to illustrate how data lies on a low dimensional manifold. The images in the dataset are 1028 T028 x 3 dimensional. By contrast, the number of realistic dimensions along which they vary are limited, e.g. painting style, artist, size and shape of the nose, jaw and eyes, background, clothing style; in fact, very few 1028 1028 x dimensional images correspond to realistic faces. We illustrate how this affects the possible variations in the data in Figure T
A manifold formalises the notion of limited variations in high dimensional data. One can imagine that there exists an unknown function f X - Y from a low dimensional space of variations, to high dimensional space of the actual data points. Such function f X + Y, from one open subset X R.m to another open subset Y R is a diffeomorphism if f is bijective, and both f and f-1 are differentiable, also referred to as smooth. Therefore, a manifold is defined as follows.
Definition 2.1. Let k. m E No. A subset M C. RR is called smooth m m-ddimensional submanifold of & (or m-manifold in TR.) iff every point x E M has an open neighhorhood U R such that U nn M is diffeomorphic to an open subset Ω C R A diffeomorphism (i.e. differentiable mapping),
f:UN +2
is called a coordinate chart of M and the inverse,
h f + UM
is called a smooth parametrization U M.
For the MetFaces dataset example, suppose there are 10 dimensions along which the images vary. Further assume that each variation can take value continuously in some interval of R. Then the smooth parametrization would map f ΩnR + M R 1028x 1028x3 This parametrization and its inverse unknown in general, and computationally very difficult to estimate in practice.
2

---

Under review as a conference paper at ICLR 2022
A visualization of how the 2D surface, here represented by 2-torus, is embedded in larger input space, R Suppose each point corresponds to an image of the face on this 2-torus. We can chart two curves: one straight line cutting across the 3D space and another curve that stays on the torus. The images corresponding to the points on the torus will have a smoother variation in style and shape whereas there will be images corresponding to points on the straight line that do not belong to the class of pictures of faces.
Figure I:
There are similarities how geometric elements are defined for manifolds and Euclidean spaces. A smooth curve, manifold M, 7 I M is defined from interval to the manifold M function that is diffcrentiable for all t E I, just as is done for Euclidean spaces. The shortest such curve between two points on manifold is no longer straight line, but instead a geodesic. One recurring geometric element, which is unique to manifolds and stems from the definition of smooth curves, that of tangent space, defined follows.
Definition 2.2. Let M be an m-manifold in R and E M be a fixed point. A vector E R is called a tangent vector of M x if there exists a smooth curve ? M such that 7(0) = x, (0) where it) is the derivative of Y at t. The set
T.M == {+(0)) IR + M is smoothe;(0) xx),
of tangent vectors of M at x is called the tangent space of M at x.
In simpler terms, the plane tangent to the manifold M at point æ is called the tangent space and denoted by by T. Consider the upper half of a 2-sphere, S C R²,, which is a 2-manifold in R3 The tangent space at fixed point S the 2D plane perpendicular to the surface of the sphere that contains the point æ. We refer to these concepts in the text that follows. For additional background on manifolds we refer the reader to Appendix
the vector x and tangential
2.2 LINEAR REGIONS OF DEEP RELU NETWORKS
We consider neural network, F. which is composition of activation functions. Inputs each layer are multiplied by a matrix, referred to as the weight matrix, with an additional bias vector that is added to this product. We limit our study to ReLU activation function (Nair& & Hinton 2010). which piece-wise linear and one the most popular activation functions being applied to various learning tasks different types of data like text, images, signals etc. We further consider DNNs that map inputs, of dimension Nin. to scalar values, i.e. values R. Therefore, F : mh -> IR is defined as,
F F(x) = Wr. + W...o + Wir))),
(1)
where W, E M X is the weight matrix for the 1th hidden layer, n, the number neurons in the 1th hidden layer, Bj E R is the vector of biases for the 1th hidden layer, no Bin and R
IR

---

Under review as a conference paper at ICLR 2022
is the activation function. For neuron 2 in the 1th layer denote the pre-activation of this neuron, for given imput x E Ri,,, as 21 (2). For a neuron 2 in the layer we have
z 2(z) Wi (.. + Wi,
for l > 1 (for the base case / = we have z(x) wI.= where W1-1,= is the row of weights, in the weight matrix of the 1th layer, Wi, corresponding to the neuron z. We use W to denote the weight vector for brevity, omitting the layer index in the subscript. We also use by to denote the bias term for the neuron 2.
Neural networks with piecewise linear activations are piecewise linear on the input space (Montúfar et al. 2014). Suppose for some fixed y E RT as y if we have = z(xx) -by then we observe discontinuity the gradient V (b2 + W=z(x)) at y. Intuitively, this is because x is approaching the boundary of the linear region of the function defined by the output of z. Therefore, the boundary of linear regions, for a feed forward neural network F, is defined as:
Bp
{x V (x)) is not continuous at x).
Hanin & Rolnick (2119) argue that an important generalization for the approximation capacity of a neural network F is the (Mi 1) dimensiional volume density of linear regions defined as voln,-11 (Br n /))vol,,,, ()), for bounded set K" C Ii This quantity serves as a proxy for density of linear regions and therefore the expressive capacity of DNNs. Intuitively, higher density of linear boundaries means higher capacity of the DNN to approximate complex non-linear functions. The quantity applied to lower bound the distance between a point x K and the set Br, which is
distance (2r, Br) min beurons
|=(x)
which measures the sensitivity over neurons given input. The above quantity measures how "far" the input is from flipping any neuron from inactive to active or vice-versa.
Informally, Hanin & Rolnick (2019)) provide two main results for randomly initialized DNN F, with a reasonable initialisation. Firstly, they show that
vol (Br K)
# neurons].
vol.... (K)
meaning the density of linear regions is bound above and below by some constant times the number of neurons. Secondly, for æ E [0, 1
distance(s, Br) 2 C## neurons]
-1
where C >>> depends on the distribution of biases and weights, in addition other factors. Meaning that the distance to the nearest boundary is bounded above and below by a constant times the inverse of the number of neurons. These results stand in contrast to earlier worst case bounds that are exponential in the number of neurons. Hanin & Rolnick (2019a) also verify these results empirically to note that the constants lie in the vicinity of throughout training.
LINEAR REGIONS ON THE DATA MANIFOLD
One important assumption in the results presented by Hanin & Rolnick (019a) that the input, æ, lies in a compact set K C R and that vol,., (K) is greater than O. Also, the theorem pertaining to the lower bound on average distance of x to linear boundaries the input assumes the imput uniformly distributed in [0, 1i As noted earlier, high-dimensional real world datasets, like images, lie on low dimensional manifolds, therefore both these assumptions are false in practice. Therefore, we study the case where the data lies some m- midmmensional submanifold of 1 i.c. M C. R where m < Tin- We illustrate how this additional constraint effects the study of linear regions in Figure
As introduced by Hanin & Rolnick (2019a). we denote the "(rin k) dimeenssio piece" of BP as Br More precisely, By = and BF is recursively defined to be the set of points BF \ {1FF,0 U ... U BFA--1) } with the added condition that in neighbourhood of Ir the set B coincides with hyperplane of dimension nin k. our setting, where the data lies on a manifold M, m k (Appendix E Proposition 6). For define Byy B M, and note that dim
4

---

Under review as a conference paper at ICLR 2022
Figure 2: A circle is an example of ID manifold in a 2D Euclidean space. The effective number of linear regions the manifold, the upper half of the circle, are the number of linear regions on the arc from -T to æ. In the diagram above, each color in the 2D space corresponds to a linear region. When the upper half of the circle is flattened into 1D space we obtain line. Each color on the line corresponds to a linear region of the 2D space.
example, the transverse intersection (see Definition E.1 of plane in 3D with the 2D manifold 5 is a ID curve in 5 and therefore has dimension 1. Therefore, F' is submanifold of dimension 3 - = 1. This imposes the restriction k S m, for the intersection B O M to have a well defined volume.
We first note that the definition of the determinant of the Jacobian, for a collection neurons 21,-.., 2k, is different in the case when the data lies on manifold M opposed in compact set of dimension 7am "is. Since the determinant of the Jacobian is the quantity we utilise in our proofs and theorems repeatedly we will use the term Jacobian refer for succinetness. Intuitively, this follows from the Jacobian of a function being defined differently in the ambient space IR as opposed the manifold M. In case of the former is the volume of the paralellepiped determined by the vectors corresponding to the directions with steepest ascent along each one of the axes. In case of the latter more complex and defined below. Let 71"h be the on-dimensional Hausdorff measure (we refer the reader to the Appendix for background on Hausdorff measure). The Jacobian of function on manifold M, defined by Krantz & Parks) (2008) (Chapter 5), as follows
Definition 3.1. The (determinant of) Jacobian of a fuunction H M - R*, where S ddi(M)- = m, is defined as
J (x) sup { HH (DM i k-diiennsooal parallelepiped contained in TyM. HPPP)
J
where DM T.M- + R is the differential map (see Appendix By and we use (P)) denote the mapping of the set P in T,M, which a parallelepiped, to T. The supremum is taken over all parallelepipeds P.
We also say that neurons 21, .... 24 are good at there exists a path of neurons from the output in the computational graph of F so that each neuron is activated along the path. Our three main results that hold under the assumptions listed in Appendix [A] each of which extend and improve upon the theoretical results by Hanin & Rolnick (2019a). are:
Theorem 1. Given F feed-forward ReLU network with input dimension nhp output dimension and random weights and biases. Then for any bounded measurable submanifold M C. 18 and any ..... m the average (m k) dimdimensaaa volume of BF inside M,
Elvolm- MM)
Σ
J E|. dvvo (z),
(2)
distinct neurOnE in F M
where Y Yz..... is JM m, Hy (b)) (21 (x) 2k (x))), times the indicator function of the event that 2ÿ is good at x for each j 1, ... ht Here the function Pb.gr...b is the density of the joint distribution of the biases b bzg-
5

---

Under review as a conference paper at ICLR 2022
This change in the formula, from Theorem 3 by Hanin & Rolnick (2019a), is result of the fact that z(x) has a different direction of steepest ascent when it is restricted to the data manifold M, for any J. The proof is presented in Appendix []] Formula also makes explicit the fact that the data manifold has dimension m S Thn and therefore the m k-dimensional volume is a more representative measure of the linear boundaries. Equipped with Theorem we provide result for the density of linear regions on manifold M.
Theorem 2.
For data sampled uniformly from a compact and measurable mn dimensional manifold M we have the following result for all ls S m.
(2C 1olm-a(BRR nM) < (#herroon) ) OM)*
(M)
where Cgrad depends V>((x) and the DNN's architecture, Cas depends on the geometry of M, and Coias on the distribution of biases pb-
The constant Cm is the supremum over the matrix norm of projection matrices onto the tangent space, T,M, at any point I E M. For the Euclidean space Ca is always equal to 1 and therefore the term does not appear in the work by HHanin& & Rolnick (2019a), but we cannot say the same for our setting. We refer the reader to Appendix for the proof, further details, and interpretation. Finally, under that added assumptions that the diameter of the manifold M finite and M has polynomial volume growth we provide a lower bound on the average distance to the linear boundary for points on the manifold and how depends on the geometry and dimensionality of the manifold.
Theorem 3. For any point, H. chosen randomly from M, we have:
CMA
Eldistance M (x. Br M)) Z OgraaCoiaa Cas #neurons
where CM... depends the scalar curvature and dimensionality of the munifold M. The function distance M is the distance on the manifold M.
This result gives intuition on how the density of linear regions around a point depends on the geometry of the manifold. Note that the constant Css is the same as in Theorem 2 Another difference to note is that we derive lower bound on the geodesic distance Euclidean distance in R as done by Hanin & Rolnick (2019a). This distance better captures the distance between data points on a manifold while incorporating the underlying structure. In other words, this distance can be understood as how much data point should change to reach a linear boundary while ensuring that all the individual points on the curve, tracing this change, are "valid" data points. We provide proof for the above theorem in Appendix G For background on curvature of manifolds and a proof sketch we refer the reader to the Appendices and D respectively.
the manifold M and not the
3.1 INTUITION FOR THEORETICAL RESULTS
One of the key ingredients of the proofs by Hanin & Rolnick (019aa is the co-area formula The co-area formula is applied to get a closed form representation of the dd-mensiionll volume of the region where any set of k neurons, 21, 22, ..., Zy is "good" in terms of the expectation over the Jacobian, in the Euclidean space. Instead of the co-area formula we use the smooth co-area formula, 2 to get closed form representation of the m k- dimeeniional volume of the region intersected with manifold, M, in terms of the Jacobian defined on a manifold (Definition 3.J). The key difference between the two formulas is that in the smooth co-area formula the Jacobian (of function from the manifold M) is "restricted" to the tangent plane. While the determinant of the vanilla Jacobian measures the distortion of volume around a point in Euclidean space the determinant of the Jacobian defined as above (Definition 3.1) measures the distortion of volume on the manifold instead for the function with the same domain, the function that is the set of neurons are good and 0 otherwise.
The value of the determinant as defined in 3.1 has the same volume as the projection of the paral- lelepiped defined by the gradients V²(2)) onto the tangent space (see Proposition 8p. This introduces the constant Cm, defined above. Essentially, the constant captures how the magnitude of the gra- dients, Vz(x), are modified upon being projected to the tangent plane. Certain manifolds "shrink"
Formul

---

Under review as a conference paper at ICLR 2022
0.
(b)
Figure 3: The tractrix (a) and circle (b) are plotted in grey the x-y plane, which are the ID input data manifolds. The target function is in blue, on the z-axis, and periodic in nature.
vectors upon projection to the tangent plane more than others, average, which is function of their geometry. We illustrate of how two distinct manifolds "shrink" the gradients differently upon projection to the tangent plane and it is reflected in the number of linear regions on the manifolds (see Figure in the appendix). We provide intuition for the curvature of a manifold in Appendix B due to space constraints, which used in the lower bound for the average distance Theorem
4 EXPERIMENTS
4.1 SUPERVISED LEARNING ON TOY DATASET
To empirically corroborate our theoretical results, we calculate the number of linear regions and average distance the linear boundary, bounds for which presented in the theorems above, regression task for two different manifolds. To achieve this we define two similar regression tasks where the data is sampled from two different manifolds with different geometries. We parameterize the first task, a unit circle without its north and south poles, by t'iirete (-,, тT) - I2 where (eircte (0) (cos f, sin f)) and
the angle made by the vector from the origin the point with respect to the x-axis. We set the target function for regression task to be periodic function in A. The target is defined as =()) = a sin(v0) where is the amplitude and is the frequency (Figure B). DNNs have difficulty learning periodic functions (Ziyin et al. 2020). The motivation behind this is to present the DNN with a challenging task where has to learn the underlying structure of the data. Moreover the DNN will have to split the circle into linear regions. For the second regression task, tractrix is parametrized by Viractix R + I² where Vrrnuui (1) = (t tanh t, sech t) (see Figure 3 We assign target function =(t) a sin(vt), For the purposes of our study restrict the domain of Viractrix to ( 3, 3). This allows us to observe effects of varying data geometry across the manifolds.
The results, averaged over 20 runs, presented in Figures 4 and 5 We note that CM is smaller for Sphere (based on Figure and the curvature is positive whilst CM is larger for tractrix and the curvature is negative. Both of these constants (curvature and C1r) contribute the lower bound in Theorem 3 Similarly, we show results of number of linear regions divided by the number of neurons upon changing architectures. consequently the number of neurons, for the two manifolds in Figure g, averaged over 30 runs. Note that this experiment observes the effect of C' X Cymaa. since changing the architecture also changes Gyzad- Although this variation in Cgradl is quite low in magnitude as observed empirically by Hanin & Rolnick (2019a). The empirical observations are consistent with our theoretical results. observe that the number of linear regions starts off close to #neurons and remains close throughout the training process for both the manifolds. This supports our theoretical results (Theorem 2) that the constant Cм. which is distinct across the two manifolds, affects the number of linear regions throughout training. The tractrix has a higher value of C's and that is reflected in the results. This due to different "shrinking" of vectors upon being projected to the tangent space discussed in Section 3.1
7

---

Under review as a conference paper at ICLR 2022
2.90
6429
180
150
200
212
Figure 4: Graph of number of linear regions for tractrix (blue) and sphere (orange). The shaded regions represent one standard deviation. Note that the number of neurons is 26 and the number of linear regions is comparable but different for both the manifolds.
Figure 5: Graph of distance to linear regions for tractrix (blue) and sphere (orange). The distances are normalized by the maximum distance on the range, for both tractrix and sphere. The shaded regions represent one standard deviation.
E.005
0.005
Sapeee o1 Unee ReVMs
5.004
-3
5.000
255 25
100 1.0
140
00
90 100 120
140
Figure 6: We observe that as the dimension nin is increased, while keeping the manifold dimension constant, the number of linear regions remains proportional number of neurons (26).
Figure 7: We observe that as the dimension nin is increased, while keeping the manifold dimension constant, the average distance varies very little.
Nemder PrgAmt/
-34
1.00
-25
-35
16, Sphere
52, sphore
5, Tracrio
10, 16, hocine
JtL 42. mncet
-22
80
J20
100
Spoch
Spoch
Figure 8: The effects of changing the architecture on the number of linear regions. We observe that the value of Cm effects the number of linear gions proportionally. The number of hidden units for three layer networks are in the legend along with the data manifold.
Figure 9: We observe that the log density of num- ber of linear regions is lower on the manifold (blue) compared to off the manifold (green). As training progresses, in contrast to previous examples with generalization, the log density de- creases.
8

---

Under review as a conference paper at ICLR 2022
4.2 VARYING TINN
To empirically corroborate the results of Theorems 2 and we vary the dimension Tin while keeping m constant. We achieve this by counting the number of linear regions and the average distance to boundary region on the ID circle as we vary the imput dimension in steps of 5. We draw samples of ID circles in 1 by randomly choosing two perpendicular basis vectors. We then train a neural network with the same architecture as in the previous section on the periodic target function (a sin(v0) as defined above. The results in Figure shows that the quantities stay proportional to #neurons, and do not vary as Ylin is increased, as predicted by our theoretical results. This stands in contrast to the results by Haani& & Rolnick (2019a) where the upper and lower bounds both grow exponentially with ii for the number of linear regions in compact set of R We provide implementation details in Appendix H
4.3 METFACES: HIGH DIMENSIONAL DATASET
Our goal with this experiment to study how overfitting relates to the number of linear regions of deep ReLU networks, in addition to observing the density of linear regions for very high dimensional image data that lies on a low dimensional manifold. To discover latent low dimensional underlying structure of data we employ GAN. Adversarial training of GANs can be effectively applied to learn a mapping from a low dimensional latent space to high dimensional data (Goodfflllww et al. 2014). The generator is neural network that maps g R+ - R Recently, Karras et al. (2019) introduced a new generator, StyleGAN, that interpolates better, meaning that it can disentangle the factors of variation in the dataset. As follow up. Kaaraa et al. (2020a) train the StyleGAN in a data efficient manner on the MetFaces dataset. We train a deep ReLU network on the MetFaces dataset with random labels (chosen from 0, 1) with cross entropy loss. As noted by /Zhag et al. (2017). training with random labels can lead to the DNN memorizing the entire dataset with poor generalization. Further implementation details are in Appendix []
We compare the log density of number of linear regions on a curve on the manifold with a straight line off the manifold (see Figure 9. This leads to two observations: 1) the density of the linear regions decreases as training progresses, in case of overfitting, which is in contrast to the scenario without overfitting (Hanin & Rolnick 2019a) and it ties the pathological behavior of deep ReLU networks to density of linear regions, 2) the density of linear regions is significantly lower on the data manifold and devising methods to "concentrate" these linear regions on the manifold a promising research direction. That could lead to increased expressivity for the same number of parameters.
5 DISCUSSION AND FUTURE WORK
There is significant amounts of work in both supervised and unsupervised learning settings for non-Euclidean data (Bronstein et al. 2017). Despite these empirical results most theoretical analysis remains agnostic to data geometry, with few prominent exceptions (Cloninger & Klock 2020 Shaham et al., 2015 Chen et al.] 2019 Schmidt-Hieberi 2019). We incorporate the idea of data geometry into measuring the effective approximation capacity of DNNs. We derive average bounds on the number of linear regions and distance from the linear boundary under the added assumption that the data is sampled from a low dimensional manifold. Our experimental results corroborate our theoretical results. We also present insights into overfitting in high dimensional datasets where the data lies on low dimensional manifold. Estimating the geometry, dimensionality and curvature, of these image manifolds accurately is a problem that remains largely unsolved (Brehmer & Cranmer 2020; Perraul-Joncas & Meila, 2013), which limits our inferences on high dimensional dataset to observations that guide future research. We note that proving a lower bound on the number of linear regions, as done by Hanin& & Rolnick (2019a), for the manifold setting remains open. Our work opens up avenues for further research that combines model geometry and data geometry and can lead to empirical research geared towards developing DNN architectures for high dimensional datasets that lie on low dimensional manifold.

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
We offer the following details for all the experiments we have performed: hyperparameters, sample sizes, GPU-hours, CPU-hours, code, neural network architectures, python libraries, input sizes, and external code bases. We also provide the code with instructions on running it in the readme txt in the exp/ folder of the supplementary material. Specifically, for Sections 4.1 and [42 the imple- mentation details are in Appendix H Section 4.3 in Appendix [ for running the StyleGan2 code and its license Appendix
We also provide additional details
REFERENCES
Zeyuan Allen-Zhu, Y. Li, and Zhao Song. convergence theory for deep learning via over- parameterization. ArXiv, abs/181 0ts//81110399 1.03962, 2019.
M. Anthony and P. Bartlett. Neural network learning theoretical foundations. 1999.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. ArXiv, wwss/8022 000260599, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. ArXiv, abs/ 1111810.0 10.02281, 2019a.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In NeurIPS, 2019b.
D. Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj, Asja Fischer, Aaron C. Courville, Yoshua Bengio, and S. Lacoste-Julien. A closer look at memorization in deep networks. ArXiv, abs/1706.053944 2017.
Peter L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve-dimension bounds for piecewise polynomial networks. Neural Computation, 10:2159-2173, 1998.
P. P. Brahma, Dapeng Oliver Wu, and Y. She. Why deep learning works: A manifold disentanglement perspective. IEEE Transactions on Neural Networks and Learning Systems, 27: 27:1997-2008, 2016.
Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estimation. ArXiv, abs/2003.13915 2020.
M. Bronstein, Joan Bruna, Y. LeCun, Arthur Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34:15 14:18-4, 2017.
Michael M. Bronstein, Joan Bruna. Taco Cohen, and Petar Velivekovi'e. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. ArXiv, abs/2104. 134788 2021.
Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. ArXiv, abs/2008. 1245, 2021.
G. Carlsson, T. Ishkhanov, V. D. Silva, and A. Zomorodian. On the local behavior of spaces of natural images. International Journal of Computer Vision, 76:1-12, 2007.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. ArXiv, ab4.190022199 2019.
Alexander Cloninger and Timo Klock. Relu nets adapt to intrinsic dimensionality beyond the target domain. ArXiv, abs/2008.025.4 2020.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:303-314 1989.
Simon Shaolei Du, Wei Hu, and J. Lee. Algorithmic regularization in learning deep homogencous models: Layers are automatically balanced. In NeurlPS, 2018
C. Fefferman, S. Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. arXiv: Statistics Theory, 2013.
10

---

Under review as a conference paper at ICLR 2022
ectavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmannn. Hyperbolic neural networks. ArXiv, abs/1805.00 12, 2018.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modelling the influence of data structure learning in neural networks. ArXiv, abs/1909.1 1500, 2020.
I. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.
lan J. Goodfellow and Oriol Vinyals. Qualitatively characterizing neural network optimization problems. CoRR, abs/ 1412.5444,, 2015.
lan J. Goodfelllo,,Jonathoon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, 412.6572, 2015.
Alfred Gray. The volume of small geodesic ball of riemannian manifold. Michigan Mathematical Journal, 20:329-344 1974.
Victor Guillemin and Alan Pollack. Differential Topology. Prentice- Hall, 1974.
B. Hanin and M. Nica. Products of many large random matrices and gradients in deep neural networks. Communications Mathematical Physics, 376:287-322, 2018.
B. Hanin and D. Rolnick. Complexity of linear regions in deep networks. ArXiv, abs/ 19.02,,,, 2019a.
B. Hanin and D. Rolnick, Deep relu networks have surprisingly few activation patterns. In NewrIPS, 2019b.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. ArXiv, abs/1708.02691, 2019.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. ArXiv, hbss/199.059899 2020.
M. Hauser and A. Ray. Principles of riemannian geometry in neural networks. In NIPS, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. ArXiv, 5bs.1500.,5163, 2015.
K. Hornik, M. Stincheombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 2:359-366, 1989.
Arthur Jacot, F. Gabriel, and C. Hongler. Neural tangent kerne:: Convergence and generalization in neural networks. In NeurIPS, 2018.
Tero Karras, S. Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4396 4405, 2019.
Tero Karras, Miika Aittala, Janne Hellsten, S. Laine, Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. ArXiv, abs/2006.06676, 2020a.
Tero Karras, S. Laine, Miika Aittala, Janne Hellsten, J. Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8107-8116. 2020b.
Kenji Kawaguchi, L. Kaelbling, and Yoshua Bengio. Generalization in deep learning. ArXiv, abs/1710.05468, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, Abs/1412.6980, 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abs/1 609.02907, 2017.
11

---

Under review as a conference paper at ICLR 2022
Dieter Kraft. A software package for sequential quadratic programming. Tech. Rep. DFVLR-FB 88-28, DLR German Aerospace Center Institute for Flight Mechanics, 1988.
S. Krantz and Harold R. Parks. Geometric integration theory. 2008.
Daniel Kunin, Javier Sagastuy-Breias S. Ganguli, Daniel L. K. Yamins, and H. Tanaka. Neu- ral mechanics: Symmetry and broken conservation laws deep learning dynamics. ArXiv, abs/2012.04728,, 2020.
Jachoon Lee,
Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jascha Sohl-Dickstein. Wide neural networks of any depth evolve as linear models under gradient descent. ArXiv, abs/1902.06720, 2019.
Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. ArXiv, abs/1711.01533 2019.
L. Loveridge. Physical and geometric interpretations of the riemann tensor, ricci tensor, and scalar curvature. 2004.
H. Mhaskar and T. Poggio. Deep vs. shallow networks: An approximation theory perspective. ArXiv, 0os/1608.03222 2016.
Federico Monti, D. Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5425-5434, 2017.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In NIPS, 2014.
V. Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In ICML, 2010.
Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nathan Srebro. A pac-bayesian approach to -ootralll--oommaieeddd margin bounds for neural networks. ArXiv, abs/1707.09555 2018.
Jonas Paccolat, Leonardo Petrini, Mario Geiger, Kevin Tyloo, and Matthieu Wyart. Geometric compression of invariant manifolds in neural networks, Journal of Statistical Mechanics: Theory and Experiment, 2021, 2020.
Dominique Perraul-Joncas and Marina Meila. Non-linear dimensionality reduction: Riemannian metric estimation and the problem of geometric discovery. arXiv: Machine Learning, 2013.
Ben Poole, S. Lahiri, M. Raghu, Jascha Sohl-Dickstein, and S. Ganguli. Exponential expressivity in deep neural networks through transient chaos. ArXiv, abs/1606.05344 2016.
C. Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. 2017 IEEE Conference Computer Vision and Puttern Recognition (CVPR), pp. 85, 2017.
M. Raghu, Ben Poole, J. Kleinberg, S. Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. ArXiv, 606.05336.. 2017.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Dräxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the spectral bias of neural networks. In ICML, 2019.
Joel W. Robbin, Uw Madison, and Dietmar A. Salamon. INTRODUCTION TO DIFFERENTIAL. GEOMETRY. Preprint, 2011.
Levent Sagun, Utku Evei, V. U. Güney, Yann Dauphin, and L. Bottou. Empirical analysis of the 2018.
hessian of over-parametrized neural networks. ArXiv,
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. CoRR, abs/1312.6120 2014.
12

---

Under review as a conference paper at ICLR 2022
Johannes abs/1908.00695, 2019.
Deep relu network approximation of functions manifold. ArXiv,
Thiago Serra, Christian Tjandraatmadja, and S. Ramalingam. Bounding and counting linear regions of deep neural networks. In ICML, 2018.
Uri Shaham, Alexander Cloninger, and Ronald R. Coifman. Provable approximation properties for deep neural networks. ArXiv, abs/1509.07385. 2015.
Samuel L.. Smith and Quoe V. Le. A bayesian perspective generalization and stochastic gradient descent. ArXiv, abs/1 710.06451,, 2018.
Weijie J. Su, Stephen P. Boyd, and Emmanuel J. Candès. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. Mach. Learn. Res., 2016.
Christian Szegedy, W. Zaremba, Ilya Sutskever, Joan Bruna, D. Erhan, lan J. Goodfellow, and R. Fergus. Intriguing properties of neural networks. CoRR, abs/1312.6199 2014.
Matus Telgarsky. Representation benefits of deep feedforward networks. ArXiv, fbss/1509.080...
2015.
Joshua B. Tenenbaum. Mapping manifold of perceptual observations. In NIPS, 1997.
Z. Wan. Geometric interpretations of curvature. 2016.
Tingran Wang, Sam Buchanan, Dar Gilboa, and John Wright. Deep networks provably classify data on curves. ArXiv, abs/2107.14324 2021.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics (TOG), 38:1 12, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32:4-24, 24, 2019.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ArXiv, abs/1611 1.03530. 2017.
Liu Ziyin, Tilman Hartwig, and Masahito Ueda. Neural networks fail learn periodic functions and how to fix it. ArXiv, abs/2006.08 08900, 2020.
A ASSUMPTIONS
We first make explicit the assumptions on the distribution of weights and biases.
Al:
The conditional distribution of any of biases beg ... by, given all other weights and biases has density Pzi....:> (b,,..., by) with respect to Lebesgue measure on R
A2: The joint distribution of all weights has density with respect to Lebesgue measure on IR weights
A3: The data manifold M is smooth.
A4: (Only needed for Theorem 3) the diameter of M defined by da suPa.yEM distance (I. u) is finite.
A5: (Only needed for Theorem 3) geodesic ball in manifold M has polynomial volume growth of order m.
13

---

Under review as a conference paper at ICLR 2022
B ADDITIONAL BACKGROUND ON MANIFOLDS
We provide further background on the theory of manifolds. In this section we first provide the background, definition and interpretation for the scalar curvature of manifold point. Every smooth manifold is also equipped with a Riemannian metric tensor (or metric tensor in short). Given any two vectors, and w, the langent space of a point on a manifold M, the metric tensor defines parallel to the dot product in Euclidean spaces. The metric tensor, at a point is defined by the smooth functions Ity M + RR i,j {i..., k}. Where the matrix defined by
(1)
(1)
G2 = (o0((>)
(x)
(nn(())
symmetric and invertible. The inner product of u, v E T, is then defined by (u, v) w² G2u. the inner product is symmetric, non-degenerate, and bilinear, i.e.
(ku, u) M =k(u, u) M = (u)ke) (u + w, u)M =u,, v)M + (w, v) (u, v) =(v, u)M-
As can be seen, these properties also hold for the Euclidean inner product (with G₂ = 7 for all x).
Let the inverse G [x)] be denoted by [g (x)). Building on this definition of the metric tensor the Ricci curvature tensor is defined
8 9ky
gah
8g
Rij = 2
Σ
gab
Ox. dr,Ox, 0r,0ra
dx,0xa
o,b=1
Oga Aged + Ogie Ogia Ogie 0ggb dz, dr,
ar dry dx Oxs ga0 god
a.b,
Ogic +
Ogie Ogú gobgrd
Or; dz, dx.
0,b,c,d=1
For geometric interpretations of the above tensors we refer the reader the work by Loveridge (2004).
Another quantity, from the theory of manifolds, which utilise in our proofs and theorems, is scalar curvature (or Ricci curvature). The curvature is measure how much the volume of a geodisic ball on the manifold M, e.g. S², deviates from d sphere in the flat space, e.g. R The volume on the manifold deviates by an amount proportional to the curvature. We illustrate this idea in figure 10 We refer the reader to works by Gray (1974) and Wan (2016) for further technical details. Since our main theorems relate to the volume of linear regions the scalar curvature plays an important role. Formally, the scalar curvature of manifold M at point with metric tensor [gtÿ] and Ricci tensor [Ray] is defined as
C=
Raj.
1-=1
Another important concept is that of Hausdorff' measure. Since the volumes are "distorted" on manifold it requires careful consideration when defining a measure and integrating using on manifold. The m midimensional Hausdorff measure, of a set S, is defined as
HTT(S) == sup inf 6>0
Σ (diam U, C U U, diam U, <
Next we introduce the definition of the differential map that used in Definition 3.1 for the determinant of the Jacobian. The differential map of smooth function H from manifold M to a manifold at a point x e MM is the smooth map dH T,M + T,S such that the tangent vector corresponding any smooth curve 7 + M at x. 7() T,M, maps to the tangent vector of
14

---

Under review as a conference paper at ICLR 2022
(a)
(b)
Figure 10: The geodesic circle on S (blue region in (a)) does not have the same area as the flat circle (b), both of radius e. One can imagine cutting the blue top off the sphere's 's surface and trying to "flatten" it. Such effort will lead to failure, if the material of the sphere does not "stretch", since the geodesic ball, on 5², cannot be mapped to circle in R22 in a distance preserving manner. Thus, the area of the two blue regions in (a) and (b) vary. This deviation in the area spanned by the two spheres, despite their radii being the same, is proportional to the scalar curvature.
H o b in N. This is the analog of the total derivative of "vanilla calculus". More intuitively, the differential map captures how the function changes along different directions on N its input changes along different directions on M, this also has an analog to how rows of the Jacobian matrix are viewed in calculus. Definition 3.1 we use the specific case where the funetion H maps from manifold M to the Fuclidean space I and the tangent space of Euclidean space is the Fuclidean space itself. Finally, a paralellepiped's s, P in T,M, mapping via the differential map gives us the points in g* that correspond to this set P.
N.
C RELATED WORK
There have been various approaches to explain the efficacy of DNNs in approximating arbitrarily complex functions. We briefly touch upon two such promising approaches. Broadly, the theory of
DNNs can be viewed from two lenses: expressive power (Horikk al.) 1989 Bartlett et al.,
1998
Poole et al. 2016 Raghu et al. 2017 Kawaguchi et al. 2017 Neyshabur et al. 2018 Hanin 2019
and learning dynamics (Saxe al. 2014:1 Su et al. 2016 Smith & Le 2018 Jacot et al.
2018
Lee et al. 2019; Arora et al. 2019 b). These approaches are not independent of one another but complementary. For example. Kawaguchi al. (2017) argue theoretically how the family of DNNS generalize well despite the large capacity of the function class. Neyshabur et al. (2018) provide PAC-Bayes generalization bounds which are improved upon by Arora al. (2018 Hanin (2019) shows that Deep ReLU networks of finite width can approximate any continuous, convex or smooth functions on unit cube. These works look DNNs from the lens of expressive power. More recently, there has been surge in explaining how various algorithms arrive at these almost accurate function approximations by applying different theoretical models of DNNs. Jacot al. (2018) provide results for convergence and generalization of DNNs in the infinite width limit by introducing a the neural tangent kernel (NTK). Hanin Nica (2020) provide finite depth and width corrections for the NTK. Another line of work within the learning dynamics literature looks at implicit regularization that emerge from the learning algorithm and wver-prramerrise DNNs (Arora et al.) 2019a Du et al. 2018 Liang et al. 2019)
Researchers have begun to incorporate data geometry into the theoretical analyses of DNNs by applying the assumption that the data lies general manifold. First note the works looking at DNNs from the lens of expressive power combined with the idea of data geometry. [Shaham et al. (205)) demonstrate that the size of the neural network depends the curvature of the data
15

---

Under review as a conference paper at ICLR 2022
manifold and the complexity of the function, whilst depending weakly on the input data dimension, for their construction of pparsely-connectte 4-layer neural networks. Cloninger & Klock (2020) show that their construction of deep ReLU nets achieve near optimal approximation rates which depend only on the intrinsic dimensionality of the data. Chen et al. (201)) exploit the low dimensional structure of data enhance the function approximation capacity of Deep ReLJU networks by means of theoretical guarantees. Schmidd-Hiebbr (2019) shows that sparsely connected deep ReLU networks can approximate Holder function on low dimensional manifold embedded in high dimensional space. Simultaneouslyy researchers have incorporated data geometry into the learning dynamics line of work (Goldt et al. (2000, Paccolat et al. [020 Buchanan et al., [021] Wang et al., (021). Buchanan et al. (2021) apply the NTK model to study how DNNs can separate two curves, representing the data manifolds of two separate classes, on the unit sphere. [oldt et al. (2020) introduce the Hidden Manifold Model for structured data sets to capture the dynamics of two-layer neural networks trained
with stochastic gradient descent. Finally, we also note that Rahaman et al. (2019) provide empirical results on which data manifolds are learned faster.
Our work fits into the study of expressive power of DNNs. The number of linear regions is a good proxy for the practical expressive power approximation capacity of Deep ReLU networks (Montúfar et al. 2014). The results surrounding the density of linear regions make the fewest simplifying assumptions both the data and the architecture of the DNN. The results by |Hanin & Roonick] (2019a) bound the number of linear regions orders of magnitude tighter than previous results by deriving bounds for the average case and not the worst case. Moreover, they demonstrate the validity empirically in setting with very few simplifying assumptions. We introduce the manifold hypothesis to this setting in order obtain tighter bounds for the first time. This introduces toolbox of ideas from differential geometry to analyse the approximation capacity of deep ReLU networks.
In addition to the theoretical works listed above, there has been significant empirical work that applies DNNs to non- -ucllddid data (Bronstein et al. 2017 2021). Here the data is assumed to be sampled from manifolds with certain geometric properties. For example, Ganea et al.) (2018) design DNNs for data sampled from Hyperbolic spaces of arbitrary dimensionality and modify the forward and backward passes accordingly. There have been numerous applications of modified DNNs, namely graph convolutional networks, to graph data that incorporate the idea that graphs are discrete samples from a smooth manifold (Henaff et al.) 2015) Monti et al. 2017 Kipf & Welling 2017). see Wu et al. (2019) for comprehensive review. Graph convolutional networks have also been applied to point cloud data for applications in graphics (Qi et al. 2017 Wang et al. 2019).
D PROOF SKETCH
In this section provide overview of how the three main theorems proved. Theorem 1 provides an equality for measuring the volume of m - h dimensional boundary regions on the manifold. To this effect, we introduce the idea of viewing boundary regions as submanifolds on the data manifold instead of hyperplanes (Proposition 6). We then prove an equality between the volume of boundary regions and the Jacobian of the neurons over the manifold. We utilise the smooth coarea formula that, intuitively, is applied to integrate a function using level sets on a manifold. This completes the proof for Theorem 1.
To prove Theorem 2 we first prove that the Jacobian of a function on a manifold can be denoted using the volume of paralellepiped of vectors the ambient space subject to linear transform (Proposition 8). Using this result and combining it with Theorem 1 we can then give an inequality for the density of linear regions. As can be expected this volume depends on the aforementioned projection, which in turn is related to the geometry of the manifold.
Finally, for proving Theorem we first provide an inequality over the tubular neighbourhood of the boundary region. We then use this result to lower bound the geodesic distance between the boundary region and any random point on the manifold. The proof strategy follows that of Hanin & Rolnick (2019a) but there are major deviations when it comes accounting for the geometry of the data manifold. To the best of our knowledge, we are utilising elements of differential topology that are unique to machine learning when it comes to developing a theoretical understanding of DNNs.
16

---

Under review as a conference paper at ICLR 2022
E PROOF OF THEOREM 1
We follow the proof strategy used by Hanin & Rolnick (2019a) but deviate from to account for setting where z E M. Let S₂ be the set of values at which the neuron has discontinuity in the differential its output (or the neuron switches between the two linear regions of the piecewise linear activation d),
S = fo E 2== - b- = =0}.
We also have
s.t. x BEERNN = 1,.,, I. neuron 2 with 1(z) j s.t. d'(x(z) - bz) # #0]
O =
Further,
S.
We state propositions and 10 by Hanin & Rolnick (2019a) as we apply them to prove Theorem 1, relabeling them as needed.
Proposition 4. (Proposition 9 by Hanin & Rolnick (019aa) Under assumptions Al and A2, we have, with probability 1,
BF U Sz.
By extending the notion of S₂ to multiple neurons we have
2 n Szy J=1
meaning that the set S St..... is, intuitively, the collection of inputs in Ri where the neurons Zj.j = I..,..k k; switch between linear regions for a and at which the output of F' is affected by the outputs of these neurons. We refer the reader section of the appendix in the work by Hanin & Rolnick (2019a) for an intuitive explanation of proposition Next we state proposition 10 by Hanin &Rolnick (2019a).
Proposition (Prosposition 10 by Hanin & Rolnick (2019a)) Fix k: = 1.... Tim and le distinct neurons Zx in F. Then, with probability for every BF, there exists a neighbourhood in which BF coincides with a Ti -imen-idnn hyperplane.
We now present Proposition 6 and its proof, which incorporates the additional constraint that M, which is an m-dimennional manifold "R, To prove the proposition we need the definition of tranversal intersection of two manifolds (Guillemin & Pollack 1974).
Definition F.1. Two submanifolds, M1 and Mz, of are said to intersect transversally if at every point of intersection their tangent spaces, at that point, together generate the tangent space of the manifold, S, by means of linear combinations. Formally, for all x E M1 O M2
T + T2,
if and only if M1 and M2 intersect transversally.
For example, given 2D hyperplane, P, and the surface of a 3D sphere, S², intersect in the ambient space IR3. We have that this intersection is transverse if and only if P is not tangent to Sz. For the case where 2D hyperplane, P. intersects with S at point but does not intersect tranversally it coincides exactly with the tangent plane S at point {p) S2 P. i.e. T,S P. Note that in either case the tangent space of the 2D hyperplane P at any point of intersection is the plane itself.
Proposition Fix I,..., m and k distinct neurons 2 2n in F. Then, with probability 1, for every x E BE n M there exists a neighbourhood in which BE coincides with an m k dimensional submanifold in "
Proof. From Proposition 5 we already know that BF is a Pin k-dimensional hyperplane in some neighbourhood of x, with probability 1, for any x E BF n M. Let this hyperplane be denoted by Pt. This is an A dimensional submanifold of Th The tangent space of this hyperplane at is the hyperplane itself. Therefore, from assumptions A1 and A2 we have that the probability that this hyperplane intersects the manifold M transversally with probability 1. In other words the probability that this plane Ps contains or is contained in T, M is 0. Finally, we have the intersection, M n Hę. has dimension dim(M) dim (Hx) Tin (Guillemin & Pollack 1974), which is equal to k. 11
17

---

Under review as a conference paper at ICLR 2022
One implication of Proposition 6 that for any I the (k + dimensional volume of Вς O M is O. addition to that, Proposition O implies that, with probability 1,
volm-k(BF.))
volm volm-u($ nM).
(3)
distinct neurons R1y
The final step in the proof of Theorem is to prove the following result. Proposition 7. Let ...... 2k be distinct neurons in F and k S. m. Then a bounded -Hausdorff measurable manifold M embedded in R
E. (S ( nM)
B B E/ (1)) (x) dr,
where Ys (I) equals
J.h (s))b,.....b bb (z1 (z),
=x(x)) -k)))
times the indicator function of the event that 2j. for = 1,..., k, is good at for every and Hy: R + R is such that (z)z) = (2)( ... (x))) The expectation is over the distribution of weights and biases.
Proof. Let 21, 2 be distinct neurons in F and M be m-dimensional compact Haudorff measurable manifold. We seek compute the mean of volm - (S $1.., M) over the distribution of weights and biases. We can rewrite this expression as
J
1,, good dvo)
Js......a nM
The map Hg is Lipschitz and C almost everywhere. We first note the smooth coarea formula (theorem 5.3.9 by Krantz & Parks (2008) in context of our notation. Suppose m 2 h and H4 2T R* is C² and M R is m dimensnsioo C² manifold in RT then
I g(a)J k,H, (z)dvolm (
J MMHH"()) (v)
(5)
for every mee-measurable function g where J., is as defined Definition 3.1.
We denote preactivations and biases of neurons as z(x) = [2) (x)))² and b, (B2,) DeylT.
From the notation AI, we have that
Pb.
Pb ....
is the joint conditional density of bzy .... dr, given all other weights and biases. The mean of the term equation 4 over the conditional distribution of byy..., beg Pb. therefore
f (=)
bdvool.(b) RR
12 is good a dvolm-A(x))
(6)
where we denote [b,,-.. b as b. Thus applying the smooth co-area formula (Fquation 5) to the expression in 6 shows that the average is equal to
/ Y Ys..... (x)dx. M
Finally, take the average over the remaining weights and biases and commute the expectation with the dr integral. We can do this since the integrand is non-negative. This gives us the result:
volm- (
n (
Y
(x) dx,
as required.
L
Finally, taking the summation over all possible sets distinct neurons 21...., 2g and combining equation with Proposition completes the proof for Theorem 1.
18

---

Under review as a conference paper at ICLR 2022
F PROOF OF THEOREM 2
To prove the upper bound in Theorem 2 we first show that the (determinant of) Jacobian for the function Hi: M + RR Hg (z) (z), ..., (x(x)² as defined 3.1 is equal to the volume of the parallelopiped deñiedd by the vectors ΦH, (z)( for = 1..,,k k, where 0 R - T, F.M is an orthogonal projection onto the orthogonal complement of the kernel of the differential DM Ha. Intuitively, this shows that with the added assumption E M in Theorem 2 how exactly we can incorporate the geometry of the data manifold M into the upper bound provided by Hanin Rolnick (2019a) in corollary 7.
Proposition 8. Given Hx M - I such that (x( [21(2), ... 2x (z)]² and the differential Da Hy is surjective at then
H. (x) V/de(/Gram( (V2( (V (Vz((z)))),
where 0H, IR + R is a linear map and Gram denotes the Gramian matrix.
Proof. We first define the orthogonal complement of the kernel of the differential Das Hg. For manifold M C I2" and fixed point z we have that T₃ M is a m m-ddimensions hyperplane. If we choose an orthonormal basis E1, e, of R" such that Ei...., em spans T,M M for fixed æ we can denote all vectors in T.M using coordinates corresponding to this basis. Therefore, for any onto T. using a m X n matrix which we
vector y E R² we can get the orthogonal projection denote as Pa, where PaY (matrix multiplied by vector) represents vector in T corresponding to the basis 61, Emn- For any manifold M in Rt" and function Hę M - I2* we have that Da H T.M R at fixed point is linear function. Therefore we write D (T((v) Au where V E Tg M is denoted using the aforementioned basis of T M. This implies that A is l: x m matrix. Therefore, the kernel of D DMHH & for a fixed point x E M1 is
ker ( M HR)
=|Az and E T.MM
Since we can create a canonical basis for the space ker DM H2) starting from the basis G1.... em in R" using the Bram-Schmidt process given the matrix we have that for any y E R we can project it orthogonally onto ker (D H.). The orthogonal complement of (er(Das Hx) is therefore defined by
(cr(DM = aala = 0 for some 2 E ker(Dxy and a E TTM).
Similar to the previous argument, we construct a canonical basis starting from e1 e1, ..,.... Em for (erMDHHH)) and therefore can denote the orthogonal projection onto ker (DM H+ linear transformation. We denote this linear projection for fixed x using Φx.
We denote the basis vectors El,.... Cm as m n matrix E' where each row corresponds to the vector e; Therefore, the orthogonal projection of any vector E IR" is Ey. Now we can get the matrix A using EV (xx) corresponding each row j for j 1, .... m. This uses the fact that the direction of steepest ascent (z) restricted to the tangent space T.M of the manifold M is an orthogonal projection of the direction of steepest ascent in R.
Finally, from lemma 5.3.5 by Guillemin & Pollack 1974) we have that
JM (s) H*hh (DMs HDMHH Hx
for any parallelepiped P contained in (ker M0 H+) Arguing similar to the proof of lemma 5.3.5 by Guillemin Pollack (1974) we get that
MM (x) det (e(((A))A) / det Gram Gram (EaamEVVzii (T EVzz
thereby showing that Φn,, (w) Ey is a linear mapping.
Although we state Proposition g for neurons 2j (z). = 1, ..., in the proof, it applics to any function that satisfy the conditions laid out in the proposition. Equipped with Proposition 8 we prove Theorem
19

---

Under review as a conference paper at ICLR 2022
2. When the weights and biases of F are independent obtain upper bound Pba,,...bay (B1,..., by) as
n p= (b) .. bb) =
sup Pb. (b))
C
ncurons 2
Hence,
Y Fx Chiss K,Hx
From Proposition 8 we have that J H. is equal to the k-dimensional volume of the paralellopiped spanned by du (z)) for j 1,... k. Therefore, we have
J.H 2 1 EV (x)]l < ||B|)"T
where ||| denotes the matrix norm which is defined
F = sup [ y E R 1e5,1ll1l [ -
Note that E does not depend on F (or 21,..., 2 but only on T. or more generally the geometry of M at any point æ. From theorem by Hanin & Nica 2018)) we have, for any fixed x,
k
11 [ < (Caraa)
(10)
where,
Ograd = sup sup [
1/k - Ce 2i
2E3"
wherein > 0 depends only on μ and not on the architecture of and ny is the width of the hidden layer j. Let Cm be defined
Cm == sup {cI there exists set, S, of
k-dimensional Hausdorff measure such that ||41| 2 CVz e $}
Therefore, combining equations 10 9 and result from Theorem we have
E [[vollm=<(B n MM]
numberr of neurons'
(2CandChias
vol, (M)
k
where the expectation is over the distribution of weights and biases.
G PROOF OF THEOREM
We first prove the following proposition
Proposition For a compact m-diimensional submanifold M in TR"" m.n 2 and m n let S C RD be compact fixed continuous piecewise linear submanifold with finitely many pieces and given any U > 0. Let So and let Sy be the union of the interiors of all k-dimensional pieces of S (So U U Sk Denote by T. the e-tubuluar neighbourhood of any X C. M such that
Tx(X) = (yldu (y, < and M).
where e U), d is the geodesic distance between the point y and set X on the manifold M, we have
vol. (T.(S)) & Σ vole O M M) CkRRUs
where CK..UU > 0 is a constant that depends on the average sealar curvature K(sunar) and U, and Wa-k the volume of the unit ball in Ran
20

---

Under review as a conference paper at ICLR 2022
08
05
04
-05
-1.5
(a)
We illustrate how vectors project differently on tangent planes of two different manifolds: circle (a) and tractrix (b). case of the tractrix the tangents (and the projection of vectors onto them) the inside of the tractrix whereas for the sphere the tangents sphere. Since the projections of vectors onto the tangent space are an essential aspect of our proof we end up with the term Cm, which quantífies the "shrinking" of these vectors upon projection, in the inequalities for Theorems andd
Figure 11:
always the outside of the
Proof. Define be the maximal dimension of linear pieces in Let x E Tx(X1 n M). Suppose
& (xX n M) for all h = n m....,d 1. Then the intersection of geodesic ball of radius around a with a ball inside Sy M. Using the convexity this ball, with respect to the manifold
M (Robbin et al. 2011), there exists point y in Sa n M such that the geodesic y [0, 1] M with 7(0) and 7(1) x is perpendicular to Sa n at y. Formally, TSAnM M at y is perpendicular to (0) TM at Let (N' n M)) be the union of all the balls along the fiber of the submanifold Sa M. Therefore, we have
vol. (T.(S n M) < vol (B.(N" n M)) + vol, (T.(Sed-1 M)),
(11)
where Sea-1 := U We also note that
volm
where B, ((M n +a)+) is the average volume of ball in the submanifold of M orthogonal to n Sa. This volume depends on the average scalar curvature, K(MnSa) of the submanifold (M n S As shown by Wan (2016), for fixed point (M n Sx)
vol,-a (ah-aa(,, ((B, (M n Sa)+)) wn-dt -- <(() (M)S)) 2 + 0(64))
n d
where wn-a is the volume of the unit ball of dimension n (2, (M L Sa)= (MMS of radius in the manifold (M n S2)= centered at æ and ((M (x)) denotes the scalar curvature at point x. Gray (1974) provides the second order expansion of the formula above. Given that (0, U) for all E (n- m.
is the geodesic ball
+ 1,.., d}. then have smallest CR,K,U such that
vol. (z, (M n Sk)+)) s C
(12)
The above inequality follows from assumption A5. Using the above inequalities II 12 and repeating the argument d - n + m times we get the result of the proposition.
We also note that CR.K.U increases monotonically with U, this also follows from the volume being monotonically increasing and positive for >> 0. Finally, we can prove Theorem 3. Let & E M
21

---

Under review as a conference paper at ICLR 2022
be uniformly chosen. Then, for all (0,U), using Markov's inequality and Proposition we have E E/distancear (z, By 0 M)] 2 6 Prr(distance (z. Br n M) > c)
= < Pr(distance (2r, Bp O M) <=())
2 c(1
vol 0 M) Cnn-kuae -k,,
Aemnii
2
E(1
k=
Note that as we increase U the constants U, increase, although not strictly, for all k. To find the supremum of the expression the right hand side, of the last inequality, in E (0, U)
multiply and divide the expression by Cgrad Chian Cm #nurons to get the polynomial
<(1 Ex Lk Ona Cma-kM,U(*
(C(())
Cyrad Crass #neronns
where Ç = e Dinn Cm #neurons and Ç (0, U²) where U' = UC Cm #neurons. Let da be the diameter of the manifold M, defined by das supx,ye distance (zt, v). We assume that dı is finite. Taking the supremum over all U (0, dwl U" E (0, dl where d'r dy Cana Cs #neurons, gives us the constant CM.x
CM. sup { sup {P)()))}- U'E(U.d's) SE(O,U")
Since das is finite the constant above exists and is finite. We make note the existence of this constant CM.s. in the absence of the constraint that the diameter of manifold M is finite. As U increases the constants UU U also increase and are all positive. The solution for (C) 0, >> 0, which we denote by Çv. is unique and keeps decreasing as U increases, The uniqueness of the solution follows from the fact that the coefficients -,,,kk,.U are all positive. We also note that po (Su) need not be equal to suPce(o,U7) (Pu(()) because ÇU need not lie in (0, U"). In all pU") Given the polynomial pC(() above if we can assert that there exists a Cu. and the corresponding Cur, such that for all U > Cu. and corresponding U' > Cur, we have suPce(0,U") (pu (C)) = Pu(Cu) < oo and for all 0 < U S Cy we have sup:e(o.U") (()) = pr (U') < co. Therefore, CM,N exists and finite if the previous assertion holds, proving this assertion is beyond the scope of our current work and particularly challenging.
such cases supçe(o, U") (()(())
Finally, taking the average over distribution of weights gives us the inequality
CM,
Eldistance Mr M)) Cegna Ca #neurons*
where CM. is a constant which depends the average scalar curvature of the manifold M. This completes the proof of Theorem 3.
H Toy SUPERVISED LEARNING PROBLEMS
For the two supervised learning tasks with different geometries (tractrix and sphere), we uniformly sample 1000 data points from each ID manifold come up with samples of (I,, y4 pairs. We then add Gaussian noise to y. We train DNN with 2 hidden layers, with 10 and 16 neurons in each layer and a single linear output neuron, for total of 26 neurons with piecewise linearity, using the PyTorch library. The optimization is performed using the Adam optimizer (Kingma & Bal 2015) with learning rate 0.01. We ensure a reasonable of the model by reducing the test time mean squared error (see Figure 12 We then calculate the exact number of linear regions
the respective domains by finding the points where 2(x) = bg for every neuron 2 and x is on the ID manifold. We do this by adding neurons, 2, one by at every layer and using the SLSQP (Kraft 1988) solve for [=(x) - bzl = 0. We then split linear region depending on where this solution lies compared to previous layers. For every epoch, we then uniformly randomly sample points from the 1D manifold,
22

---

Under review as a conference paper at ICLR 2022
02
0.1
0.0
100
150
200
250
300
tyuch Num bei
Figure 12: The test errors for the cases where data is sampled from the tractrix (blue) and the circle (green). We see that the tractrix converges slower but the magnitude of the errors remains comparable as training progresses across the two manifolds.
by sampling directly from 0 and f. to measure average distance to the nearest linear boundaries. The experiment was run on CPUs, from training to counting number of linear regions. The intel cpus had access to 4 GB memory per core. A total of, approximately, 24 cpu hours were required for all the experiments in this section. This was run on an on demand cloud instance, All implementations are in PyTorhh, except for SLQSP for which we used sklearn
H.1 VARYING TIN
The experimental setup, hyperparameters, network architecture, target function and methods are all the same as described for the toy supervised learning problem for the case where the geometry is sphere. The only difference is that the input dimension varies, fli--
I HIGH DIMENSIONAL DATASET
We utilise the official implementation of pretrained StyleGAN generator generate curves of images that on the manifold of face images. Specifically, for each curve we sample random pair of latent vectors: 21, 22 k this gives the start and end point of the curve using the generator g(=1) and g(22). We then generate 100 images to approximate a curve connecting the two images on the image manifold in piece-wise manner. We do by taking 100 points on the line connecting ž and 22 in the latent space that are evenly spaced and generate an image from each one of them. Therefore, the 7th image generated as: v; g ((10(000)))))) X 21 + 22) 1/10)), using the StyleGAN generator g. We qualitatively verify the images to ensure that they lie on the manifold of images of faces. 4 examples of these curves, sampled as above, are illustrated the video here; Mh 3Q22D Sa www.oo/wwwwwww///oso/o
google
The neural network, used for classification in our MetFaces experiment, is feed forward with ReLU activation. There are two hidden layers with 256 and 64 neurons in the first and second layers respectively. We downsample the images to 128 x 128 3. We augment the dataset using random horizontal flips of the images. All inputs are normalized. We use a batch size of 32. The neural network is trained using SGD. The learning rate is 0.01 and the momentum is 0.5. The total time required, for these experiments RTX GPU that has 24 GB memory. This was run on an on demand cloud instance. We chose hyperparameters by trial and error, targeting better fit for the training data.
metfaces dataset, was approximately 36 GPU hours a Titan
23

---

Under review as a conference paper at ICLR 2022
J CODE, DATA AND LICENSES
All the code used for our experiments (except the StyleGAN2 code) is enclosed in the folder exp/ The instructions the code as an open github repository under the MIT License (https: opensourcee..... org/ licenses MIT). The files changed on the github repository for the official implementation of com NVlabb /ttsssstyyeann ada- ada-pytorch are enclosed in The instructions to run the experiments are documented
all the experiments are enclosed exp readme. txt. We plan releasing
StyleGAN2 wayleeggn--adaaaaaaaaaa -adaann--aaa---yoorrae the folder sty wgann in stylegallle - aataaddappprreeeeeeeeee reaeechhrrrrdeee..mee. txt..
approxxaato on the man- Finally, the images we used to sample linear regions on a curve's ifold of face images, for the MetFaces experiment, are in the zip httpp://dd/: goog le com/ we/ffile//a 1.:5t-sccNIWS3 2BXUMOWefX to0
K BROADER IMPACT STATEMENT
Although DNNs have been highly effective in approximating arbitrarily complex functions the reason behind their effectiveness remains open. Similarly, the cases and theoretical reasons for where they fail to approximate or introduce bias remain underexplored. Our work is unique in the sense that it looks at both data and model together when estimating the approximation capabilities of the model. Our empirical results are also close to the theoretical predictions which enables us to be more confident of our assertions. The negative impact and ethical concern that work has, and it pertains to deep learning as a whole, is that we use a lot of compute. This has two dimensions of concern: 1) the environmental costs are fairly high, and 2) further research deep learning that uses excessive compute creates barriers for smaller labs and individuals from training state of the art models.
24


Reviews:
[{"review_id": "uYMF_GLGVdL", "reviewer": "Reviewer_1oFk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\n### Strengths\n\n- The study of data with low-dimensional manifold structure is important for\n  understanding practical performance of neural networks, so the problem the\n  authors study is well-motivated.\n- Some of the geometric results that are relied on to enable the proofs are\n  somewhat esoteric, at least with respect to the ML literature. Therefore the\n  fact that the authors have collected them in their proofs may be a useful\n  contribution. Although I have not checked every proof line by line (see some\n  comments below), roughly the right kinds of tools seem to be in use here\n  (transversality; manifold coarea formula; mean curvature estimates;\n  geodesics; ...).\n\n### Weaknesses\n\n- The theoretical content of the paper is very incremental -- in effect, it\n  consists of a translation of the results of Hanin and Rolnick to the setting\n  of manifold data. In particular, almost all arguments of Hanin and Rolnick\n  are reproduced in the proofs of this paper (the theorems are in one-to-one\n  correspondence, for a start), just with the corresponding concepts for\n  manifolds substituted in (for example, replace Hanin and Rolnick's coarea\n  formula with the smooth coarea formula; replace integration over euclidean\n  space with integration with respect to the volume form on the manifolds, and\n  handle the corresponding curvature and \"reach\" quantities that arise, which\n  leads to the new constants relative to the theorems of Hanin and Rolnick). As\n  in the previous section, there may be a useful contribution just in the\n  organization of these manifold concepts; on the other hand, the *stylistic*\n  similarities between the proofs of the authors and the corresponding proofs\n  of Hanin and Rolnick is sometimes uncanny (for example, compare the content\n  of section E of Hanin and Rolnick to the content of section F of the current\n  submission).\n- In a similar vein, the writing style of the authors is often imprecise, in\n  that the framework of the paper is so identical to that of Hanin and Rolnick\n  that certain notions that were defined in Hanin and Rolnick's paper are taken\n  for granted by the authors. For example, the notations for the neural\n  network's neurons at the top of page 4 are not defined correctly because\n  Hanin and Rolnick do not define these precisely (the weights in the formula\n  should be \"full\", rather than single neurons, and the \"column of weights\"\n  does not make sense here, unless the notation is transposed for some reason\n  relative to equation (1)); the discussion of dimensions at the bottom of page\n  4 does not mention transversality (it is discussed in the appendix) or in\n  particular that these results hold only almost surely; nowhere is it\n  mentioned concretely that the weights of $F$ need to satisfy certain\n  assumptions on the density until the beginning of the appendix (these are\n  important e.g. in the context of the transversality claim made in the body,\n  because this is not true for general initializations).\n- The presentation of theorem 3 seems to be unnecessarily uninsightful: for\n  example, one naturally wants to understand when this result is\n  non-vacuous. In addition, the proof has some odd aspects: it seems to\n  use an asymptotic statement for $C_{\\kappa, k}$ in $\\epsilon$, but the\n  theorem asserts the result for all $\\epsilon > 0$ and does not show that this\n  constant depends on $\\epsilon$. It seems that this result needs to be\n  rewritten to be asymptotic for small $\\epsilon$ -- this should also enable a\n  more precise conclusion to be asserted, similar to in Hanin and Rolnick\n  2019a. This makes me feel like the other proofs may need to be checked for\n  minor errors or imprecisions that affect the statements of the results\n  (specifically, the constants).\n- The experiments conducted and the authors' discussion of them does not\n  provide very much insight into the unique circumstances present in the\n  manifold case, relative to what is known and expected from Hanin and\n  Rolnick's work. For example, the toy experiments are helpful to see the\n  effect of curvature, but this should be investigated more systematically\n  across many geometries to give a sense of what is going on (the authors only\n  provide minimal interpretation of their results in the captions of each\n  figure). The StyleGAN results should be discussed more at length -- only one\n  figure is presented, and it is not completely clear what the implication is\n  (the task consists of fitting a neural network to face images with random\n  labels, and then looking at \"off manifold\" and \"on manifold\" linear region\n  counts, which are different -- what is the implication of this study for\n  practice?). This is important because it relates to the authors' stated aim\n  for the paper.\n- There are missing references to highly related work motivated similarly to\n  the authors. The authors only mention other theoretical works on interactions\n  between neural networks and manifold data in passing in a sentence in section\n  5 -- a more detailed comparison should be made that highlights what the\n  authors contribute to this context. In addition, the only works the authors\n  reference are about approximation properties of deep neural networks on\n  manifolds: there are also very relevant works on algorithmic results for\n  training DNNs to perform classification/regression on manifolds, e.g. [2-6]\n  below. Again, it would be best to discuss this context in detail in the\n  related work/intro.\n\n\n### Minor Points\n- It is best not to use wikipedia links (bottom of page 6) -- these should be\n  changed to the corresponding references used in the proofs.\n\n### Mentioned references\n\n[1] http://arxiv.org/abs/2006.13409\n\n[2] http://dx.doi.org/10.1103/PhysRevX.10.041044\n\n[3] https://openreview.net/forum?id=O-6Pm_d_Q-\n\n[4] http://arxiv.org/abs/2107.14324\n\n[5] https://arxiv.org/abs/2106.04156\n\n[6] http://arxiv.org/abs/2006.13409\n\n", "summary_of_the_paper": "The authors study average-case representation capacity of random ReLU neural\nnetworks, as measured through their linear regions, as in Hanin and Rolnick\n2019 -- the difference in the authors' setting is that they consider the input\nspace to be defined on a low-dimensional manifold, whereas Hanin and Rolnick\nconsidered inputs on the solid cube. The authors derive analogues of each of\nthe results of Hanin and Rolnick in the manifold setting -- these results\ninclude formulas for the \"average volume density\" of linear regions, a proxy\nfor the exact number of linear regions, and the average distance to the\nboundary of the linear regions -- where the dimension dependence is on the\nintrinsic manifold dimension rather than the ambient dimension, and additional\nconstants appear that depend on properties like curvatures of the manifolds.\nThey provide toy experiments to verify the theory (involving testing linear\nregion properties on a pair of 1D manifolds with different curvatures), as well\nas an experiment on 'manifolds of faces' generated by the StyleGAN model -- in\nboth cases, the linear regions are studied throughout training rather than just\nat initialization (as the theory pertains to).\n\n", "summary_of_the_review": "The work represents a theoretical generalization of the results of Hanin and\nRolnick on linear regions in random ReLU networks, but it is an incremental\none, with proofs whose structure nearly agrees with those of the prior work.\nThe empirical results could be more systematic in helping to illustrate the\nkey novel differences between this setting and the previous setting, and why\nthey are important.\n\n", "strength_and_weaknesses": "", "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": "in4SKNdY1cK", "reviewer": "Reviewer_gvJZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "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_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.", "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.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "OZ9HBp6KFcY", "reviewer": "Reviewer_WSLJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n\nThe 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.\n\nWeakness:\n\n1. 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.\n\nTheorem 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.\n\n2. 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?\n\n\n\n", "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.\n\nTo 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.", "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.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6mWspjqu3N7", "reviewer": "Reviewer_5YsV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "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. \n\nThe 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.\n", "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. ", "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. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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