Effects of Data Geometry in Early Deep Learning
Authors: Saket Tiwari
George Konidaris
Venue: NeurIPS 2022 Accept (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 density of boundary of linear regions and the distance to these boundaries 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 the results hold with changing neural network architectures. We further demonstrate how the complexity of linear regions is different on the low dimensional manifold of images as compared to the Euclidean space, using the MetFaces dataset.

Effects of Data Geometry in Early Deep Learning
Saket Tiwari
George Konidaris Department Computer Science Brown University Providence, RI 02906
Department of Computer Science
Brown University Providence, RI 02906 saket_tiwari@bronn edu
Abstract
Deep neural networks can approximate functions on different types of data, from images graphs, with varied underlying structure. This underlying structure 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 piece-wise linear activation splits the data manifold into regions where the neural network behaves as a linear function. We derive bounds on the density of boundary of linear regions and the distance to these boundaries on the data manifold. This leads insights into the expressivity of randomly initialized deep neural networks on non- con-Euclidean data sets. We empirically corroborate our theoretical results using toy supervised learning problem. Our experiments demonstrate that number of linear regions varies across manifolds and the results hold with changing neural network architectures. We further demonstrate how the complexity of linear regions is different on the low dimensional manifold of images as compared the Euclidean space, 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 is well known (Cybenko) 1989 Hornik al.. 1989 Anthony and Bartlett 1999]. Several different theoretical approaches have emerged that study the effectiveness and pitfalls of deep learning. These studies vary in their treatment neural networks and the aspects they study range from convergence [Allen-Zhu et al. 2019 Goodfellow and Vinyals 2015), generalization (Kawaguchi al.. [017 Zhang et 2017 Jacot et al. [018 [Sagun al.
2018 function complexity Montúfar et al. 2014 Mhaskar and Poggio 2016). adversarial attacks
Szegedy et al. 2014 Goodfellow et al. 2015) representation capacity [Arpit et al. 2017). Some
recent theories have also been shown to closely match empirical observations [Poole et al. 2016
Hanin and Rolnick 2019b Kunin et al. 2020
One approach to studying DNNs is to examine how the underlying structure, or geometry, of the data interacts with learning dynamics. The manifold hypothesis states that high-dimensional real world data typically lies on a low dimensional manifold [Tenenbaum 1997 Carlsson et al. [2007] Fefferman 2013). Empirical studies have shown that DNNs are highly effective deciphering this underlying structure by learning intermediate latent representations [Poole et al.] 2016). The ability of DNNs "flatten" complex data manifolds, using composition of seemingly simple piece-wise Hauser and Ray 2017].
linear functions, appears to be unique [Brahma et al. 2016
DNNs with piece-wise linear activations, such ReLU [Nair and Hinton 2010). divide the input
space into linear regions, wherein the DNN behaves as linear function [Montúfar et al. 2014]. The density of these linear regions serves as a proxy for the DNN's ability interpolate complex data landscape and has been the subject of detailed studies Montúfar et al. 2014 Telgarsky
2015 Serra
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

et al., 2018, Raghu et al., 2017]. The work by Hanin and Rolnick [2019a] on this topic stands out because they derive bounds on the average number linear regions and verify the tightness of these bounds empirically for deep ReLU networks, instead of larger bounds that rarely materialize. Hanni and Rolnick [2099]] conjecture that the number of linear regions correlates the expressive power of randomly initialized DNNs with piece-wise linear activations. However, they assume that the data is uniformly sampled from the Euclidean space Rd, for some By combining the manifold hypothesis with insights from Hanin and Rolnick [2019a], we are able to go further in estimating the number of linear regions and the average distance from linear boundaries. We derive bounds on how the geometry of the data manifold affects the aforementioned quantities.
To corroborate our theoretical bounds with empirical results, we design a 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 and the average distance the boundaries of linear regions on these two manifolds that neural network divides the two manifolds into. We demonstrate how the number of linear regions and average distance varies for these two distinct manifolds. 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 in most deep learning theory, but demonstrate that the number of linear regions change consequence of these constants. We also study linear regions of deep ReLU networks for high dimensional data that lies on low dimensional manifold with unknown structure and how the number of linear regions vary on and off this manifold, which a more realistic setting. To achieve this we present experiments performed the manifold of natural face images. We sample data from the image manifold using a generative adversarial network (GAN) [Goodfellow et al., 2014] trained on the curated images of paintings. Specifically,
generate images using the pre-trained StyleGAN [Krrra et al.. 2019] 20205) trained on the curated MetFaces dataset [Karras et al. 2020a]. We generate curves on the image manifold of faces, using StyleGAN, and report how the density of linear regions varies on and off the manifold. These results shed new light on the geometry of deep learning over structured data sets by taking data intrinsic approach understanding the expressive power of DNNs.
2 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 of 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 our work fits into one of the two main approaches within the theory of DNNs, from the expressive power perspective or from the learning dynamics perspective, we refer the reader to Appendix C
2.1 Data Manifold and Definitions
Figure A 2D surface, here represented by a 2-torus, is embedded in a larger input space, Suppose each point corresponds to an image of 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. Images corresponding to the points on the torus will have smoother variation in style and shape whereas there will be images corresponding to points on the straight line that are not faces.
R.3

---

We use the example of the MetFaces dataset (Karras et al. 2020a| to illustrate how data lies on low dimensional manifold. The images in the dataset are 1028 1028 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; 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 [ 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 variations, to a high dimensional space of the actual data points, Such a function f X + Y. from one open subset X R to another open subset Y R², is a diffeomorphism if f is bijective, and both f and f-1 are differentiable (or smooth). Therefore, a manifold defined as follows.
Definition 2.1. Let k. m E No. A subset M C B is called smooth m nn-dimensional submanifold of R (or m-manifold in IR*) iff every point x E M has an open neighborhood U C R such that U n M is diffeomorphic to open subset Z C R diffeomorphism (i.e. differentiable mapping),
f M + Ω
called a coordinate chart of M and the inverse,
== f Ω U UMM
is called a smooth parametrization of 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 n RR 10 0 + MM R 1028x1028x33 1028x3 This parametrization and its inverse are unknown in general and computationally very difficult to estimate in practice.
There are similarities in how geometric elements are defined for manifolds and Euclidean spaces. smooth curve, on a manifold M, y - M is defined from an interval 7 to the manifold M as function that is differentiable for all t E I, just as for Euclidean spaces. The shortest such curve between two points on a manifold is no longer straight line, but is instead geodesic. One recurring geometric element, which is unique manifolds and stems from the definition of smooth curves, is that of a langent space, defined as follows.
Definition 2.2. Let M be an m-manifold in R² and x: E M be a fixed point. A vector R is called a tangent vector of M at x if there exists a smooth curve 7y -> M such that ((0) = x, (0) = where {1) is the derivative 7 at t. The set
T.M ;= (5(0))> R + M is smooth = x}
of tangent vectors of M at x is called the tangent space of M at æ.
In simpler terms, the plane tangent to the manifold M at point x: is called the tangent space and denoted by by T.M. Consider the upper half of a 2-sphere, S2 C R33, which 2-manifold in R3 The tangent space at fixed point E S2 is the 2D plane perpendicular to the vector x and tangential to the surface of the sphere that contains the point æ. For additional background on manifolds we refer the reader to Appendix B
2.2 Linear Regions of Deep ReLU Networks
The higher the density of these linear regions the more complex function DNN can approximate. For example, a sin curve in the range [0, 2Tr] is better approximated by 4 piece- wise linear regions as opposed to 2. To clarify this further, with the 4 "optimal" linear regions [0, æ x/2), /r/2, (2,22 (v, 3x 3r/2), and / 2m] a function could approximate the sin curve better than any 2 linear regions. In other words, higher density of linear regions allows DNN to approximate the variation in the curve better. We define the notion of boundary of a linear regions in this section and provide an overview of previous results.
We consider a neural network, F, which is a composition of activation functions. Inputs at each layer multiplied by matrix, referred to as the weight matrix. with additional bias vector that is added to this product. We limit our study to ReLU activation function [Nair and Hinton 2010). which piece-wise linear and one of the most popular activation functions being applied to various learning tasks on different types of data like text, images, signals etc. We further consider DNNs that map inputs, of dimension Rip. scalar values. Therefore, F _ - E is defined as,
F(z) = WIo + WL-10(...o (BI + Wiz))),
(I)
3

---

where Wi E M is the weight matrix for the 1th hidden layer, n; is the number of neurons in the 1th hidden layer, B, E R is the vector of biases for the 1th hidden layer, no = Bin and o R R is the activation function. For a neuron z in the 1 layer we denote the pre-activation of this neuron, for given input x E "R as 24 (x). For a neuron in the layer we have
z x(x) W WI- + Wiæ)),
for / > 1 (for the base case ( = we have x(x) 21, where Wi-1.s is the row of weights, in the weight matrix of the 1th layer, Wi, corresponding to the neuron z. We use Wz 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
Neural networks with piece-wise linear activations are piece-wise linear on the input space [Montúfar it al. 2014). Suppose for some fixed y E R" as z - y if we have z(xx) + -b, then we observe a discontinuity in the gradient V (b, Wzz(z)) at y. Intuitively, this because is approaching
the boundary of the linear region of the function defined by the output of z. Therefore, the boundary of linear regions, for feed forward neural network F, defined as:
BF
{xr V Fx)) is not continuous at x).
Hanin and Rolnick [2019a] argue that an important generalization for the approximation capacity of a neural network F. is the (Nin- -imeennnsoo volume density of linear regions defined as voln.- 1 (Bp n K) /)ovoln,, (K), for bounded set K C IR 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- non-lineat linear functions. The quantity applied to lower bound the distance between a point r K and the set By, which is
distance Br)
min neurons
|=(x)
b V+())l,
which measures the sensitivity over neurons a given input. The above quantity measures how "far"
the input is from flipping any neuron from inactive to active or vice-versa.
Informally, Hanin and Rolnick 2019a] provide two main results for randomly initialized DNN F, with a reasonable initialisation. Firstly, they show that
vol... (BF n nK) Re #1 neurons],
vol.... (K)
meaning the density of linear regions is bound above and below by some constant times the number of neurons. Secondly, for x E 1
E distance(r, Br)) 2 C#( neurons}
where C > O depends on the distribution of biases and weights, in addition to other factors. In other words, the distance to the nearest boundary 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 and Rolnick [2019a] also verify these results empirically to note that the constants lie in the vicinity of throughout training.
3 Linear Regions on the Data Manifold
One important assumption in the results presented by Hanin and Rolnick [019a] is that the input, x. lies in compact set K 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 input uniformly real world datasets, like images, lie on
distributed in [0, _1 As noted carlier, high-dimension low dimensional manifolds, therefore both these assumptions are false in practice. This motivates us to study the case where the data lies some dimensionn submanifold of ri, i.e. M C R where m & nin We illustrate how this constraint effects the study of linear regions in Figure
As introduced by Hanin and Rolnick [019a]]. we denote the "(nin dim-innnso piece" of Br as By More precisely, Br,0 and BF is recursively defined to be the set of points E BF [BF, U... BF with the added condition that in neighbourhood of a the set BF

---

Figure 2: A circle is an example of ID manifold in a 2D Euclidean space. The effective number of linear regions on the manifold, the upper half of the circle, are the number of linear regions on the are from -T to æ. In the diagram above, each color the 2D space corresponds to a linear region. When the upper half of the circle is flattened into ID space obtain line. Each color the line corresponds to a linear region of the 2D space.
coincides with hyperplane of dimension fin k. We provide detailed and formal definition for B with intuition in Appendix E. In our setting, where the data lies on manifold M, we define F k (Appendix E Proposition E.4). For example, the transverse intersection (see Definition E.3 of a plane in 3D with the 2D manifold $2 is 1D curve in S² and therefore has dimension 1. Therefore, F is a submanifold of dimension - 2 = 1. This imposes the restriction S m, for the intersection BF O M to have a well defined volume.
as FF, O M, and note that dim(B'p p.)
We first note that the definition of the determinant of the Jacobian, for collection of neurons 21, ..... Ak, different the case when the data lies on a manifold M as opposed to in a compact set of dimension nin in I Rin, Since the determinant of the Jacobian is the quantity and theorems repeatedly we will use the term Jacobian to refer to for succinctness. Intuitively, this follows from the Jacobian of function being defined differently in the ambient space Th as opposed to the manifold M. In case of the former is the volume of the paralellepiped determined by the vectors corresponding the directions with steepest ascent along each of the 74n axes. In case of the latter measure (we refer the reader the Appendix for background Hausdorff measure). The Jacobian of function on manifold M, as defined by Krantz and Parks (2008) (Chapter 5), is as follows.
utilise in proofs
more complex and defined below. Let 70 be the m dimenniooa Hausdorff
Definition 3.1. The (determinant of) Jacobian of a function M R& where dim(M) m. is defined as
MM (x) = sup { (DMH(P)) HPPP)
P is a k-dimensional parallelepiped contained in T,M.
where DAs .TM + R is the differential map (see Appendix B and we use D (P)) denote the mapping of the set P in T,M, which a parallelepiped, R The supremum is taken all parallelepipeds P.
We also say that neurons 21,-.., 25 good at if 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 and Rolnick [019aa]. are:
Theorem 3.2. Given F feed-forward ReLU network with imput dimension Tim output dimension 1, and random weights and biases. Then for any bounded measurable submanifold M C Rh and any I..... m the average (m k) dimensional volume of Br.k inside M,
E O MM)
Σ
I E[Y dd (x),
(3)
distinct neurORE Bk in F. J.M
where Y Y Ex... is JM Jm,Hg (I)) by (2), 2y (x)), times the indicator function of the event that is the density of the joint distribution
2j is good at for each j = 1,... k. Here the function of the biases by, ..., bsg.
5

---

This change in the formula, from Theorem 3.4 by Hanin and Rolnick [2019a]. is result of the fact that 2(z) has a different direction of steepest ascent when is restricted to the data manifold M, for any j. The proof is presented in Appendix E Formula 3 makes explicit the fact that the data manifold has dimension m S Thn and therefore the m k-dimensional volume a more representative measure of the linear boundaries. Equipped with Theorem 3.2 we provide result for the density of boundary regions on manifold M.
Theorem 3.3. For data sampled uniformly from a compact and measurable m. dimensional manifold M we have the following result for all S m.
vol. (Bm MM)
(# neeurnns
) (2eggaa CM)*
(M)
-k
V>(())] and the DNN's architecture, Cm depends on the geometry of M, and Cbius on the distribution of biases pb-
where Cgnd depends on
The constant Oм is the supremum over the matrix norm of projection matrices onto the tangent space, T,M, at any point x E M. For the Euclidean space Cyy is always equal to and therefore the term does not appear in the work by Hanin and Rolnick (2019a]. but cannot say the same for our setting. We refer the reader to Appendix | for the proof, further details, and interpretation. Finally, under the added assumptions that the diameter of the manifold M is 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 it depends on the geometry and dimensionality of the manifold.
Theorem 3.4. For any point, I, chosen randomly from M, we have:
CMA
Eldistance M (1. By (M) CoraaCoiaa Cas #neurons
where CM... depends on the scalar curvature. the input dimension and the dimensionality of the manifold M. The function distance M the distance on the manifold M.
This result gives us intuition on how the density of linear regions around a point depends on the geometry of the manifold. The constant CM., captures how volumes are distorted on the manifold M as compared to the Euclidean space, for the exact definition we refer the reader to the proof in Appendix G For a manifold which has higher volume of unit ball, on average, comparison to the Euclidean space the constant CM.,. is higher and lower when the volume of unit ball, on average, lower than the volume of the Euclidean space. For background on curvature of manifolds and a proof sketch we refer the reader to the Appendices and D respectively. Note that the constant C' is the same as in Theorem 3.3 Another difference to note is that we derive a lower bound on the geodesic distance on the manifold M and not the Euclidean distance in IR* as done by Hanin and Rolnick (2] This distance better captures the distance between data points on manifold while incorporating the underlying structure. In other words, this distance can be understood as how much a 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.
3.1 Intuition For Theoretical Results
One of the key ingredients of the proofs by Hanin and Rolnick [2019a] is the co-area formula Krantz and Parks 2008). The co-area formula is applied to get a closed form representation of the dimensional volume of the region where any set of neurons, 21, 22, ..., žạ 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 [Krantz and Parks 2008) to get closed form representation of the m -iddieensoonal volume of the region intersected with manifold, M, in terms of the Jacobian defined on a manifold (Definition 3.1). 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 1 if the set of neurons are good and 0 otherwise.
The value of the Jacobian as defined in Definition 3.1 has the same volume as the projection of the parallclepiped defined by the gradients V2(x) onto the tangent space (see Proposition F. in

---

Figure 3: The tractrix (a) and circle (b) are plotted in grey and the target function is in blue. This is for illustration purposes and does not match the actual function or domains used in our experiments.
Appendix). This introduces the constant Cm. defined above. Essentially, the constant captures how the magnitude of the gradients, Vz(z), are modified upon being projected to the tangent plane. Certain manifolds "shrink" vectors upon projection to the tangent plane more than others, on an average, which is a function of their geometry. We illustrate how two distinct manifolds "shrink" the gradients differently upon projection to the tangent plane as reflected in the number of linear regions on the manifolds (see Figure [I] in the appendix) for ID manifolds. We provide intuition for the curvature of a manifold in Appendix B due to space constraints, which is used in the lower
bound for the average distance in Theorem 3.4 The constant Car, depends on the curvature as the supremum of polynomial whose coefficients depend on the curvature, with order at most Vin and at least Vin - m. Note that despite this dependence on the ambient dimension, there are other geometric constants in this polynomial (see Appendix G). Finally, we also provide simple example to how this constant varies with Fiin and m, for a simple and contrived example, in Appendix G.I
Experiments
4.1 Linear Regions 1D Curve
To empirically corroborate our theoretical results, we calculate the number of linear regions and average distance the linear boundary ID eurves for regression tasks in two settings. The first is for 1D manifolds embedded in 2D and higher dimensions and the second is for the high-dimensional data using the MetFaces dataset. We use the same algorithm, for the toy problem and the high- dimensional dataset, to find linear regions on ID curves. We calculate the exact number of linear regions for ID curve in the input space, x + T where is interval in real numbers, by finding the points where 2(x(t)) = b, for every neuron z. The solutions thus obtained gives us the boundaries for neurons on the curve z. We obtain these solutions by using the programmatic activation of every neuron and using the sequential least squares programming (SLSQP) algorithm Kraft 1988) to solve for [=(x)t) bg 0 for t E I. In order obtain the programmatic activation of neuron we construct a Deep ReLU network as defined in Equation We do so for all the neurons for given DNN with fixed weights.
4.2 Supervised Learning on Toy Dataset
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 veiiele (- T) + R² where (0) = (cos 0, sin 0) and 0 is the angle made by the vector from the origin to the point with respect to the x-axis. We set the target function for regression task to be periodic function in 6. The target is defined as 2(f) sin(v0) where is the amplitude and v is the frequency (Figure B) DNNs have difficulty learning periodic functions (Ziyin al.. 2020]. The motivation behind this is to present the DNN with challenging task where it has to learn the underlying structure the data. Moreover the DNN will have to split the circle into linear regions. For the second regression task, tractrix is parametrized by Airariis RR_ + IR2 where Vimettrx (v) = (y tanh y, sech y) (see Figure 3). We assign target function z(1) sin (vt). For the purposes of our study we restrict the domain of a/trctrix to (-3.3). We choose
to ensure
7

---

that the number of peaks and troughs, 6, in the periodic target function are the same for both the manifolds. This ensures that the domains of both the problems have length close to 6.28. Further experimental details are in Appendix H
The results, averaged over 20 runs, are presented in Figures 4 and [ We note that Cm is smaller for Sphere (based on Figure 4) and the curvature is positive whilst Cm is larger for tractrix and the curvature is negative. Both of these constants (curvature and Cm) contribute to the lower bound in Theorem 3.4 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 8 averaged over 30 runs. Note that this experiment observes the effect of Cм x Cgad,, since changing the architecture also changes C Cgrad and the variation Carad is quite low in magnitude as observed empirically by [Hanin and Rolmick (2019a]. The empirical observations are consistent with our theoretical results. We 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 3.3) that the constant Cas. which is distinct across the two manifolds, affects the number of linear regions throughout training. The tractrix has higher value of Cλ and that is reflected in both Figures 4 and S Note that its relationship is inverse to the average distance to the boundary region, as per Theorem 3.4 and it is reflected as training progresses in Figure 5 This is due to different "shrinking" of vectors upon being projected to the tangent space (Section 3.1
4.3 Varying Input Dimensions
To empirically corroborate the results of Theorems 2 and we vary the dimension 7'm while keeping m constant. We achieve this by counting the number of linear regions and the average distance to boundary region on the ID cirele as we vary the input dimension in steps of We draw samples of 1D circles in R by randomly choosing two perpendicular basis vectors. We then train a network with the same architecture as the previous section on the periodic target function (a (in0)) as defined above. The results in Figure @ shows that the quantities stay proportional to #neurons, and do not vary as ni is increased, as predicted by our theoretical results. Our empirical study asserts how the relevant upper and lower bounds, for the setting where data lies on a oow-dimensional manifold, does not grow exponentially with nin for the density of linear regions in a compact set of R"a but instead depend on the intrinsic dimension. Further details are in Appendix H
4.4 MetFaces: High Dimensional Dataset
Our goal with this experiment is to study how the density of linear regions varies across a low dimensional manifold and the input space. To discover latent low dimensional underlying structure of data we employ a GAN. Adversarial training of GANs can be effectively applied to learn a mapping
from a low dimensional latent space to high dimensional data [Goodfellow et al., 2014). J) The generator
is a neural network that maps g : IR + RT We train deep ReLU network on the MetFaces dataset with random labels (chosen from 0, 1) with cross entropy loss. As noted by Zhang et al. (2017).
training with random labels can lead to the DNN memorizing the entire dataset.
We compare the log density of number of linear regions on a curve on the manifold with a straight line off the manifold. We generate these curves using the data sampled by the StyleGAN by [Karras et al.) 2020a]. Specifically, for each curve we sample a random pair of latent vectors: 21, 22 E R this gives the start and end point of the curve using the generator g(21) and g(=2). We then generate 100 images to approximate a curve connecting the two images on the image manifold in a piece-wise manner. We do so by taking 100 points on the line connecting 2 and 22 in the latent space that are evenly spaced and generate an image from each one of them. Therefore, the th image is generated as: 2! = (((0000 i) X 21 + i x 22)/ /000), using the StyleGAN generator g. We qualitatively verify the images to ensure that they lie on the manifold of images of faces. The straight line, with two fixed points g(²1) and g(22), is defined as z(t) = (1 - f)g(2))) + (2() with t E [0, 1J. The approximated curve on the manifold is defined as x (t) = (1 - t)9(2()) )++ + (g(2(_1) where i = floor floor(100t). We
then apply the method from Section 4.1 to obtain the number of linear regions these curves.
The results are presented in Figure This leads us to the key observation: the density of linear regions is significantly lower on the data manifold and devising methods to "concentrate" these linear regions on the manifold is promising research direction. That could lead to increased expressivity for the same number of parameters. We provide further experimental details in Appendix
8

---

0.46
0007
0008
Spech
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 comparable 26 but differ- ent for both the manifolds throughout training.
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.
0.00
0004
0.002
8 C
120
Figure 6: We observe that the dimension Pin is increased, while keeping the manifold dimension constant, the number of linear regions remains proportional to number of neurons (26).
Figure 7: We observe that the dimension nim is increased, while keeping the manifold dimension constant, the average distance varies very little.
424
-33
1.29
-34
0.75
035
Spven
-17
16 Thxcte
-30
1y0.2 Paam
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 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). This for the MetFaces dataset.

---

5 Discussion and Conclusions
There is significant work in both supervised and unsupervised learning settings for non-Euclidean data [Bronstein et al., 2017]. Despite these empirical results most theoretical analysis is agnostic to data geometry, with a few prominent exceptions [Cloninger and Klock 2020 Shaham et al. SolbidSchmddtHiebee 2019]. We incorporate the idea of data geometry into measuring the effective approximation capacity of DNNs, deriving average bounds on the density of boundary regions and distance from the boundary when the data is sampled from low dimensional manifold. Our experimental results corroborate our theoretical results. We also present insights into expressivity of DNNS on low dimensional manfiolds for the case of high dimensional datasets. Estimating the geometry, dimensionality and curvature, of these image manifolds accurately is problem that remains largely unsolved [Brehmer and Cranmer 2020 Perraul-Joncas and Meila 2013), which limits our inferences on high dimensional dataset to observations that guide future research. We note that proving lower bound on the number of linear regions, as done by Hanin and 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.
Acknowledgements
This work was funded by L.2M (DARPA Lifelong Learning Machines program under grant number 188750018-2-011 the Penn MURI (ONR under the PERISCOPE MURI Contract N00014- 17- 1-2699), and the ONR Swarm (the ONR under grant number was conducted using computational resources and services at the Center for Computation and Visualization, Brown University.
This research
We would like to thank Sam Lobel, Rafael Rodriguez Sanchez, and Akhil Bagaria for refining work, multiple technical discussions, and their helpful feedback on the implementation details. We also thank Tejas Kotwal for assistance on deriving the mathematical details related to the ID Tractrix and sources for various citations. We thank Professor Pedro Lopes de Almeida, Nihal Nayak, Cameron Allen and Aarushi Kalra for their valuable comments on writing and presentation of our work. We thank all the members of the Brown robotics lab for their guidance and support at various stages of our work. Finally, we are indebted to, and graciously thank, the numerous anonymous reviewers for their time and labor as their valuable feedback and thoughtful engagement have shaped and vastly refine our work.
References
Zeyuan Allen-Zu,, Y. Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. ArXiv, abs/181 0///1811.0300 1.03662, 2019.
M. Anthony and P. Bartlett. Neural network learning theoretical foundations. In 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, abs/1802.0522% 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. ArXiv, abs/ 810.0228..1111 2019a.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In NeurlPS, 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.05394, 2017.
Peter I.. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve-dimension bounds for piecewise polynomial networks. Neural Computation, 10:2159-2173, 1998.
10

---

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:1997-2008, 2016.
Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estimation. ArXiv, abs/2003.13913, 2020.
Richard P. Brent. An algorithm with guaranteed convergence for finding a zero of function. Comput. J. 14:422-425, 1971.
M. Bronstein, Joan Bruna, Y. LeCun, Arthur Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34:18 18 42, 2017.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velivckovi'c. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. ArXiv, abs/2104. 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, abs/ /tts//998.0082,, 2019.
Alexander Cloninger and Timo Klock. Relu nets adapt to intrinsic dimensionality beyond the target domain. ArXiv, hbss2008.005445 2020.
G. Cybenko. Approximation by superpositions of 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 homogeneous models: Layers are automatically balanced. In NeurlPS, 2018.
C. Fefferman, S. Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. arXiv: Statisties Theory, 2013.
Octavian-Fuger Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. ArXiv, 0oss/800.0911 12, 2018
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modelling the influence of data structure learning neural networks. ArXiv, 19t.19999.111000.0 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.
Ian J. Goodfellow and Oriol Vinyals. Qualitatively characterizing neural network optimization problems. CoRR, abs// 1412.6444 2015.
Ian J. Goodfelloo, Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, abs/1412.6572, 2015.
Alfred Gray. The volume of small geodesic ball of a 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/1901..m 9900009911,, 2019a.
B. Hanin and 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, abs/1909.05989, 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 graph-structured data. ArXiv, abs/1506.051633, 2015.
K. Hornik, M. Stinchcombe, 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 kernll: Convergence and generalization in neural networks. NeurIPS, 2018.
Tero Karras, S. Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 4396 4405, 2019.
Tero Karras, Miika Aittala, Janne Hellsten, S. Laine, J. Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. ArXiv, 06660000006666.... 2020a.
Tero Karras, S. Laine, Miik 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), pages 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/1609.02907, 2017.
Dieter Kraft. A software package for sequential quadratie programming. Tech. Rep. DFVLR-FB 88-28, DLR German Aerospace Center - Institute for Flight Mechanics, 1988.
Krantz and Harold Parks, Geometric integration theory. In Geometric Integration Theory, 2008.
Daniel Kunin, Javier Sagastuy-Breña, S. Ganguli, Daniel L. K. Yamins, and H. Tanaka. Neu- ral mechanics: Symmetry and broken conservation laws in deep learning dynamics. ArXiv, abs/2012.004728, 2020.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jaseha Sohl-Dickstein. Wide neural networks of any depth evolve as linear models under gradient descent. ArXiv, Abs/1990,, 2019.
Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. ArXiv, abs/1711 1.015300,, 2019.
L. Loveridge. Physical and geometric interpretations the riemann tensor, ricci tensor, and scalar curvature. In Physical and Geometric Interpretations of the Riemann Tensor, Ricci Tensor, and Scalar Curvature, 2004.
H. Mhaskar and T. Poggio. Deep shallow networks: An approximation theory perspective. ArXiv, abs/ 1008.0328877.... 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. 20/7 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 5425-5434, 2017.
12

---

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 spectrally margin bounds for neural networks. ArXiv, 10s//177,,9964, 2018.
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization neural networks: an empirical study. In International Conference on Learning Representations, 2018. URL / pet//forumidd-HJ02255
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, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. In NIPS, 2016.
C. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 77-85, 2017.
M. Raghu, Ben Poole, J. Kleinberg, S. Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. ArXiv, abs/1600 00s/16006.553333 00336. 2017.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Dräxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the spectral bias of neural networks. In ICMI,, 2019.
Joel W. Robbin, Uw Madison, and Dietmar A. Salamon. INTRODUCTION TO DIFFERENTIAL GEOMETRY. Preprint, 2011.
Levent Sagun, Utku Evci, V. U. Güney, Yann Dauphin, and L. Bottou. Empirical analysis of the hessian of over-parametrized neural networks. ArXív, abs/1706.04454, 2018.
Andrew M. Saxe, James I.. McClelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks. CoRR, abs/1312.6120,, 2014.
Johannes
Deep relu network approximation of functions on manifold. ArXiv,
abs/1908.00653 00695, 2019.
Thiago Serra, Christian Tjandraatmadja, and Ramalingam. Bounding and counting linear regions of deep neural networks. In /CML, 2018.
Uri Shaham, Alexander Cloninger, and Ronald R. Coifiman. Provable approximation properties for deep neural networks. ArXiv, abs/1 0ts//150900785, 2015.
Samuel L. Smith and Quoe V. Le. A bayesian perspective on generalization and stochastic gradient descent. ArXiv, abs/17 7 710.006116441 2018.
Weijie J. Su, Stephen Boyd, and Emmanuel J. Candès, A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. J. Mach. Learn. Res., 2016.
Christian Szegedy, W. Zaremba, Ilya Sutskever, Joan Bruna, D. Erhan, Ian J. Goodfellow, and R. Fergus. Intriguing properties of neural networks. CoRR, abs/1312.6199, 2014.
Matus Telgarsky. Representation benefits of deep feedforward networks. ArXiv, 2015.
Joshua B. Tenenbaum. Mapping manifold of perceptual observations. In NIPS, 1997.
13

---

Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland. Tyler Reddy, David Couraaeeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors, SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10.1038/s41599 152--01--666--.
Z. Wan. Geometric interpretations of curvature. In GEOMETRIC INTERPRETATIONS OF CURVA- TURE, 2016.
Tingran Wang, Sam Buchanan, Dar Gilboa, and John Wright. Deep networks provably classify data curves. ArXiv, abs/2107.14324 2021.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph cnn 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. JEEE Transactions Neural Networks and Learning Systems, 32:4-24, 2019.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ArXiv, abs/161 1. 1.03530, 2017.
Liu Ziyin, Tilman Hartwig, and Masahito Ueda. Neural networks fail to learn periodic functions and how to fix it. ArXiv, abs/2006.08 01150, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is primarily theoretical with few toy experiments we do not see its applicability
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Appendix for a list
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions nceded to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Appendix
J
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See experimental sections in the Appendix and main body
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Except for the cases where there are multiple graphs that are overlapping (Figure 6,7, 8) because would make interpreting them difficult.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Appendix
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
14

---

(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "nYWwmjYui1S", "reviewer": "Reviewer_J3BE", "summary": "The paper continues the work of Hanin and Rolnick [1,2] on the expressivity of PieceWise Linear (PWL) Deep Neural Networks (DNNs).\nThe main Contribution (**C1**) involves improving the theoretical bounds of both the number of linear regions and the average distance to the linear boundaries defined by a PWL DNN, by taking into account the geometry of the input manifold. The authors also provided a toy example to empirically validate the results. In addition, they performed an experiment of natural images (**C2**), to empirically show that both memorization and closeness to the data manifold have an effect on the density of linear regions.\n\n### References\n- [1] Boris Hanin and David Rolnick, “Deep ReLU Networks Have Surprisingly Few Activation Patterns”, NeurIPS 2019. \n- [2] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.", "questions": "### Questions\n- With regard to (**W1**), to my understanding, in [1] (Theorem 1, page 3) the authors claimed that \"The same result holds when computing the number of linear regions along any fixed 1-dimensional curve in a high-dimensional input space.\", confirming the results obtained in Figures 6 and 7. The informal (not proven) claim in [1] about the exponential growth of regions with the input dimension in my opinion refers to the input manifold size $m$. In this regard, it would have been interesting to test the number of regions with increasing size $m$ of the manifold. Please better clarify the statement you are referring to and why your empirical results are in contrast with it.\n- With regard to (**W2**), I didn't fully why should you claim in Sect. 4.3 that overfitting is the cause of the decrease in the number of regions during training. In my opinion, it could be a result of the chosen hyperparameters. Can you clarify your intuition?\n\n### Minors and suggestions\n- section 4.1 could have been more clear. In particular, please explicit that the domains of Sphere and Tractrix are similar for the sake of comparability, i.e. $[-\\pi, \\pi]$ and $[-3, 3]$, and that the parameters of the target function are the same.\n- for the sake of consistency, are the x, y and z-scales in Figure 1 (a) the same as the ones used in the experiments?\n- please explain how you computed the density in Figure 9.\n- please report the performance of the PWL DNN used in Figure 9.\n- use either “piece-wise” or “piecewise” in the text.\n- line 248 (main): Figure 11 is probably Figure 2 of the Appendix.\n- line 264: in the equation of the tractrix y should be t.\n- line 22 (Appendix): typo of the subscript.\n- broken refs in the Appendix.\n\n### References\n- [1] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.\n", "limitations": "I would have addressed the role of hyperparameter selection in the experimental results since previous work clearly stated that size, learning rate, and other hyperparameter choices have an effect on the evolution of the number of linear regions during training.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- (**Strength 1**) The paper addresses the significant problem of extending the bounds on expressiveness metrics of PWL DNNs in [1,2], by taking into account the dimensionality and geometry of the input manifold.\n- (**S2**) I really liked the toy example as a way to validate the analytical results, although the clarity could be improved.\n- (**S3**) The authors helped the reader in understanding the intuition behind the theoretical results by providing useful Figures (1 and 2 in the main, 1 and 2 in the Appendix).\n\n### Weaknesses\nWith regard to the weaknesses, some of the experimental results (2 out of 3) are not sufficiently clear or do not provide a significant contribution:\n- (**Weakness 1**) **Sect. 4.2**: The authors claimed to have obtained results (Figures 6 and 7) in contrast with [2]. However, it is not clear to me which result in [2] the authors are referring to (see Questions).\n- (**W2**) **Sect. 4.3**: the MetFaces experiment represents an additional, separate contribution (**C2**), but due to lack of space the results were not validated by enough empirical tests. For example, claiming a relationship between the decreasing number of linear regions during training and memorization was not validated against any hyperparameter change, as it was done in [1]. In fact, the behaviour of the number of regions in an overfitting scenario was shown in [1] to be dependent on both the number of points to be memorized against the capacity of the network and the performance of the model (not reported). \n- (**W3**) **Sect. 4.3**: the second result of the MetFaces experiment, i.e. the difference in the number of regions in and out of the data manifold was already shown in [3], Figure 2, with a slightly different experimental setting. Although using a GAN to fit the in-distribution manifold is a nice idea, the obtained result, in my opinion, doesn't contribute to the overall significance of the paper.\n\n### Concluding Remarks\nAlthough the paper addresses a significant research question, validated with a toy example, I think that more empirical experiments should have been devoted to the main contribution (the role of the manifold geometry), instead of focusing on the role of memorization and closeness to the data manifold (both already analyzed in-depth in previous papers [1,3]). Moreover, I have doubts about some of the claims resulting from the experimental results, which either are not clear or do not address the limitation of the experimental evaluation.\n\n### Reviewer-Authors Discussion\nAfter the reviewer-authors discussion, I increased the rating of both soundness and presentation. Moreover, I increased the overall rating from 4 to 6. Please refer to the discussion for the details.\n\n### References\n- [1] Boris Hanin and David Rolnick, “Deep ReLU Networks Have Surprisingly Few Activation Patterns”, NeurIPS 2019. \n- [2] Boris Hanin and David Rolnick, “Complexity of Linear Regions in Deep Networks,” ICLR 2019.\n- [3] Roman Novak et al., “Sensitivity and Generalization in Neural Networks: An Empirical Study.” ICLR 2018.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G8i4yWUh6b4", "reviewer": "Reviewer_o5b5", "summary": "With the assumption that a dataset is sampled from a low dimensional manifold, this paper incorporated such data geometry into measuring the effective approximation capacity of DNNs by deriving average bounds on the density of boundary regions and distance from the linear boundary, which is reported in previous work by Hannin and Rolnick. ", "questions": "Would it be possible to provide an example of how the findings of this study can help with users of deep neural networks to design, explain, and improve their systems? ", "limitations": "As mentioned by the authors, proving a lower bound on the number of linear regions still remains open.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nOriginality: this work builds upon previous work by Hannin and Rolnick, which establishes the linear regions in deep networks, and provides an original study on how neural networks with ReLU activation can split data manifolds into regions where the neural network behaves as a linear function. \n\nQuality: the study is of relatively good quality. Bound on the number of linear regions and the distance to boundaries of these linear regions on the data manifold are derived. \n\nClarity: the paper is very clearly presented. \n\nWeaknesses: \n\nSignificance: while building upon Hannin and Rolnick's previous work, the significance of this extension is not very clear, especially how this work leads to understanding the expressivity of deep networks on non-Euclidean data sets. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AHBZih7n-vm", "reviewer": "Reviewer_gb2e", "summary": "The paper studies how randomly initialized ReLU networks split the data into linear regions. It is based on Hanin and Rolnick [2019a] but focuses on data with low dimensional manifold structure.  It provides an upper bound for the density of the linear regions, which results in a lower bound for the average distance to the boundary of all linear regions. This lower bound is inverse linear in the number of neurons and related to the geometric properties of the manifold. The authors then empirically verify their statement over both synthetic datasets of two parameterized curves and one realistic dataset of a curve generated from StyGAN. ", "questions": "The questions would be related to some of the comments above.\n\n1. The role of dimensionality and curvature. Are we able to relate $C_M$ and $C_{M, \\kappa}$ to some intrinsic characterization of the manifold, like dimension or scalar curvature? How will the dimensionality of the manifold affect the number of linear regions or the average distance? Also, $C_{M, \\kappa}$ is defined by $p_U(\\zeta)$, which has an inverse dependence on the number of neurons. Why $C_{M, \\kappa}$ will not depend on the number of neurons? \n\n2. The role of the depth of the network. One key observation in Hanin and this paper is that the number of linear regions has minimum dependence on the number of neurons. On the other hand, a deeper network would have more expressive power. It would be nice to observe this through experiments. In figure 8, there are attempts to understand how different choices of the network structure affect the number of linear regions. However, they are all two-layer networks. If one tries a deep network structure, will the result remain the same? \n\n3. As argued in section 3, one cannot apply Hanin's result directly because $Vol_{n_{in}}(M)$ is $0$. One can consider an $\\epsilon$ neighborhood of $M$ and try to bound the volume by the geometric properties of the manifold. How is this approach different from the one in the paper? In other words, will this approach give non-optimal bounds compared to looking closer to the intrinsic characterization of the manifold? \n", "limitations": "The authors have adequately addressed the limitations and potential negative social impact of their work. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \nThe problem this paper trying to solve is interesting. In many applications, data exhibit low dimensional or low dimensional manifold structures. Understanding how the intrinsic dimension and geometries interact with the deep network is an interesting problem. The paper is able to relate the average distance from the linear region to parameters depending on the scalar curvature and dimensionality of the manifold, while still preserving the same dependence on the number of neurons as in the Euclidean case. The experiments are insightful and support the intuitions of the theory.\n\nWeakness: \n\n1. The paper mostly serves as a theoretical paper, but some key definitions are not presented in a clear and rigorous way. The paper is partially based on Hanin 2019 so the authors seem to adopt some of the notation in that paper without further clarification. For example, the definition of $\\mathcal B_{F, k}$ defined in line 162 is not clear in the first read. I need to go and forth between this and Hanin's paper to understand a similar definition and the relationship between them. I would encourage the author to provide a formal math definition of $\\mathcal B_{F, k}$ in the appendix. \n\n2. The role of the geometries of the manifold is not clearly laid out in the theorem. The key benefit of considering data with structure is to understand how the structure interacts with the neural networks. Theorem 3.4, which is the main theorem of the paper, is very similar to the Euclidean case in the sense that it has inverse dependence over the number of neurons. However, the definition for $C_M$ and $C_{M, \\kappa}$ is not provided in an intuitive way for the readers to understand the relationship between the geometries of the manifold and average distance. For example, one would like to know how $C_M$ and $C_{M, \\kappa}$ depend on the scalar curvature and dimension of the manifold. In the current form, it would be hard for the reader to understand the exact benefit of considering data with low dimensional manifold structure. \n\n3. The linear region density (left-hand side of equation on line 145 or line 202) only serves as a proxy for the number of linear regions. In the later work of Hanin and Rolnick [2019b], the number of linear regions would still depend on $(\\text{neurons})^{n_{in}}$. So Theorem 3.3 does not provide a bound for the number of linear regions directly. \n\n\nMinors:\n1. Line 126, it should be $z(x) = W_{l-1}\\sigma(\\cdots \\sigma(B_1 + W_{1}(x)))$. In line 127, it should be $z(x) = W_{1, z}(x)$. \n2. Line 22 in the appendix should be $g_{ij}(x)$. \n3. Many reference links in the appendix are broken. \n4. In appendix line 216, the definition of $Ker(D_MH_k)^\\perp$ should be $Ker(D_MH_k)^\\perp = \\set{a \\vert a \\cdot z = 0 \\forall z \\in Ker(D_MH_k)}$ instead of for some $z$. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8bMpYIWsUck", "reviewer": "Reviewer_QPts", "summary": "This paper studies the data geometry of randomly initialized deep neural networks with ReLU activation. Motivated by the manifold hypothesis, the authors present an extension of the previous result in Hanin and Ronick [1], where the previous assumption of uniform sampled data on the entire input space is relaxed to sampling on submanifolds. The authors develop analogous upper bounds on the density of boundary regions, and lower bound on expected distance to the boundary. The authors then verified their results empirically using both synthetic datasets and the MetFaces dataset.\n\n[1] B.Hanin and D. Ronick. Complexity of linear regions in neural networks, ICML 2019.", "questions": "I am looking at your final experiment on the MetFaces dataset (in Figure 9). \n- While I do agree that the neural network would eventually overfit, I would like to understand when the network starts to overfit, and whether that corresponds to the epoch when the number of linear regions starts to “plateau”.\n- Have you tried comparing the plots of number of linear regions, together with the evolution of training/testing error of the network? Are there any correlation in the trends of these plots?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Quality and Clarity__: The paper is in general well-written. I enjoyed reading the motivations of the paper, as well the interpretation sections for the theorems. While I have not checked the proofs carefully, the progression of the theorems make sense to me. The experiments also empirically support the author’s interpretations, though I have some questions which I will ask in the next section. \n\n__Originality and Significance__: The paper is mainly an extension of the previous Hanin and Ronick paper onto the submanifold case. While the framework here is not new, I believe it is still a novel result, as the relaxed assumption of the data lying on a submanifold is indeed more realistic. That said, I am personally not a researcher in this field, and I would refer to other reviewers for further evaluation of the significance of the results. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept