Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 et al., 1989; Anthony & Bartlett, 1999). Several different theoretical approaches have emerged that study the effectiveness and pitfalls 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., 2017; 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, 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 et al., 2013). Studies have shown that DNNs are highly effective in deciphering this underlying structure by learning intermediate latent representations (Poole et 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., 2014). The density of these linear regions serves as a 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., 2017). 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 Rd, for some d. By combining the manifold hypothesis with insights from Hanin & Rolnick (2019a), we are able to go further in estimating the 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 on these two manifolds that a 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 a consequence of 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 on 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 a 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, a scenario in which it would overfit (Zhang et al., 2017). We generate curves on the image manifold of faces, using StyleGAN, and show how overfitting is reflected in the density of linear regions of the aforementioned deep ReLU network.

heading: 2 PRELIMINARIES AND BACKGROUND
text: 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 the theory of DNNs we refer the reader to Appendix C.

heading: 2.1 DATA MANIFOLD AND DEFINITIONS
text: 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 × 1028 × 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× 3 dimensional images correspond to realistic faces. We illustrate how this affects the possible variations in the data in Figure 1.
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 a high dimensional space of the actual data points. Such a function f : X → Y , from one open subset X ⊂ Rm, to another open subset Y ⊂ Rk, 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 ∈ N0. A subset M ⊂ Rk is called a smooth m-dimensional submanifold of Rk (or m-manifold in Rk) iff every point x ∈ M has an open neighborhood U ⊂ Rk such that U ∩M is diffeomorphic to an open subset Ω ⊂ Rm. A diffeomorphism (i.e. differentiable mapping),
f : U ∩M → Ω
is called a coordinate chart of M and the inverse,
h := f−1 : Ω→ U ∩M
is called a smooth parametrization of U ∩M .
For the MetFaces dataset example, suppose there are 10 dimensions along which the images vary. Further assume that each variation can take a value continuously in some interval of R. Then the smooth parametrization would map f : Ω∩R10 →M ∩R1028×1028×3. 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. A smooth curve, on a manifold M , γ : I → M is defined from an interval I to the manifold M as a function that is differentiable for all t ∈ I , just as is done for Euclidean spaces. The shortest such curve between two points on a manifold is no longer a straight line, but is instead a geodesic. One recurring geometric element, which is unique to manifolds and stems from the definition of smooth curves, is that of a tangent space, defined as follows. Definition 2.2. LetM be anm-manifold in Rk and x ∈M be a fixed point. A vector v ∈ Rk is called a tangent vector of M at x if there exists a smooth curve γ : I →M such that γ(0) = x, γ̇(0) = v where γ̇(t) is the derivative of γ at t. The set
TxM := {γ̇(0)|γ : R→M is smoothγ(0) = x}, 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 x is called the tangent space and denoted by by TxM . Consider the upper half of a 2-sphere, S2 ⊂ R3, which is a 2-manifold in R3. The tangent space at a fixed point x ∈ S2 is the 2D plane perpendicular to the vector x and tangential to the surface of the sphere that contains the point x. We refer to these concepts in the text that follows. For additional background on manifolds we refer the reader to Appendix B.

heading: 2.2 LINEAR REGIONS OF DEEP RELU NETWORKS
text: We consider a neural network, F , which is a composition of activation functions. Inputs at 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 is 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 nin, to scalar values, i.e. values in R. Therefore, F : Rnin → R is defined as,
F (x) = WLσ(BL−1 +WL−1σ(...σ(B1 +W1x))), (1)
where Wl ∈Mnl×nl−1 is the weight matrix for the lth hidden layer, nl is the number of neurons in the lth hidden layer, Bl ∈ Rnl is the vector of biases for the lth hidden layer, n0 = nin and σ : R→ R
is the activation function. For a neuron z in the lth layer we denote the pre-activation of this neuron, for given input x ∈ Rnin , as zl(x). For a neuron z in the layer l we have
z(x) = Wl−1,zσ(...σ(B1 +W1,zx)),
for l > 1 (for the base case l = 1 we have z(x) = W1,zx) where Wl−1,z is the row of weights, in the weight matrix of the lth layer, Wl, corresponding to the neuron z. We use Wz to denote the weight vector for brevity, omitting the layer index l in the subscript. We also use bz to denote the bias term for the neuron z.
Neural networks with piecewise linear activations are piecewise linear on the input space (Montúfar et al., 2014). Suppose for some fixed y ∈ Rnin as x→ y if we have z(x)→ −bz then we observe a discontinuity in the gradient ∇xσ(bz +Wzz(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:
BF = {x|∇F (x) is not continuous at x}.
Hanin & Rolnick (2019a) argue that an important generalization for the approximation capacity of a neural network F is the (nin − 1)−dimensional volume density of linear regions defined as volnin−1(BF ∩ K)/volnin(K), for a bounded set K ⊂ Rnin . 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 is applied to lower bound the distance between a point x ∈ K and the set BF , which is
distance(x,BF ) = min neurons z |z(x)− bz|/||∇z(x)||,
which measures the sensitivity over neurons at 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 & Rolnick (2019a) provide two main results for a randomly initialized DNN F , with a reasonable initialisation. Firstly, they show that
E [volnin−1(BF ∩K)
volnin(K)
] ≈ #{ neurons},
meaning the density of linear regions is bound above and below by some constant times the number of neurons. Secondly, for x ∈ [0, 1]nin ,
E [ distance(x,BF ) ] ≥ C#{ neurons}−1,
where C > 0 depends on the distribution of biases and weights, in addition to 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 1 throughout training.

heading: 3 LINEAR REGIONS ON THE DATA MANIFOLD
text: One important assumption in the results presented by Hanin & Rolnick (2019a) is that the input, x, lies in a compact set K ⊂ Rnin and that volnin(K) is greater than 0. Also, the theorem pertaining to the lower bound on average distance of x to linear boundaries the input assumes the input uniformly distributed in [0, 1]nin . 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 on some m−dimensional submanifold of Rnin , i.e. M ⊂ Rnin where m nin. We illustrate how this additional constraint effects the study of linear regions in Figure 2. As introduced by Hanin & Rolnick (2019a), we denote the “(nin − k)−dimensional piece” of BF as BF,k. More precisely, BF,0 = ∅ and BF,k is recursively defined to be the set of points x ∈ BF \ {BF,0 ∪ ... ∪ BF,k−1} with the added condition that in a neighbourhood of x the set BF,k coincides with hyperplane of dimension nin − k. In our setting, where the data lies on a manifold M , we define B′F,k as BF,k ∩M , and note that dim(B′F,k) = m − k (Appendix E Proposition 6). For
example, the transverse intersection (see Definition E.1) of a plane in 3D with the 2D manifold S2 is a 1D curve in S2 and therefore has dimension 1. Therefore, B′F,k is a submanifold of dimension 3− 2 = 1. This imposes the restriction k ≤ m, for the intersection BF,k ∩M to have a well defined volume.
We first note that the definition of the determinant of the Jacobian, for a collection of neurons z1, ..., zk, is different in the case when the data lies on a manifold M as opposed to in a compact set of dimension nin in Rnin . Since the determinant of the Jacobian is the quantity we utilise in our proofs and theorems repeatedly we will use the term Jacobian to refer to it for succinctness. Intuitively, this follows from the Jacobian of a function being defined differently in the ambient space Rnin as opposed to the manifold M . In case of the former it is the volume of the paralellepiped determined by the vectors corresponding to the directions with steepest ascent along each one of the nin axes. In case of the latter it is more complex and defined below. LetHm be the m−dimensional Hausdorff measure (we refer the reader to the Appendix B for background on Hausdorff measure). The Jacobian of a function on manifold M , as defined by Krantz & Parks (2008) (Chapter 5), is as follows Definition 3.1. The (determinant of) Jacobian of a function H : M → Rk, where k ≤ dim(M) = m, is defined as
JMk,H(x) = sup {Hk(DMH(P ))
Hk(P ) ∣∣∣P is a k-dimensional parallelepiped contained in TxM.}, where DM : TxM → Rk is the differential map (see Appendix B) and we use DMH(P ) to denote the mapping of the set P in TxM , which is a parallelepiped, to Rk. The supremum is taken over all parallelepipeds P .
We also say that neurons z1, ..., zk are good at x if there exists a path of neurons from z to 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 a feed-forward ReLU network with input dimension nin, output dimension 1, and random weights and biases. Then for any bounded measurable submanifold M ⊂ Rnin and any k = 1, ....,m the average (m− k)−dimensional volume of BF,k inside M ,
E[volm−k(BF,k ∩M)] = ∑
distinct neurons z1,...,zk in F
∫ M E[Yz1,...,zk ]dvolm(x), (2)
where Yz1,...,zk is J M m,Hk (x)ρb1,...,bk(z1(x), ..., zk(x)), times the indicator function of the event that zj is good at x for each j = 1, ..., k. Here the function ρbz1 ,...,bzk is the density of the joint distribution of the biases bz1 , ..., bzk .
This change in the formula, from Theorem 3 by Hanin & Rolnick (2019a), is a 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 E. Formula 2 also makes explicit the fact that the data manifold has dimensionm ≤ nin and therefore them−k-dimensional volume is a more representative measure of the linear boundaries. Equipped with Theorem 1, we provide a result for the density of linear regions on manifold M . Theorem 2. For data sampled uniformly from a compact and measurable m dimensional manifold M we have the following result for all k ≤ m:
volm−k(BF,k ∩M) volm(M)
≤ (
# neurons k
) (2CgradCbiasCM ) k,
where Cgrad depends on ||∇z(x)|| and the DNN’s architecture, CM depends on the geometry of M , and Cbias on the distribution of biases ρb.
The constant CM is the supremum over the matrix norm of projection matrices onto the tangent space, TxM , at any point x ∈M . For the Euclidean space CM is always equal to 1 and therefore the term does not appear in the work by Hanin & Rolnick (2019a), but we cannot say the same for our setting. We refer the reader to Appendix F for the proof, further details, and interpretation. Finally, under that 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. For any point, x, chosen randomly from M , we have:
E[distanceM (x,BF ∩M)] ≥ CM,κ
CgradCbiasCM#neurons
where CM,κ depends on the scalar curvature and dimensionality of the manifold M . The function distanceM is 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. Note that the constant CM is the same as in Theorem 2. 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 Rk 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 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. 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 B and D, respectively.

heading: 3.1 INTUITION FOR THEORETICAL RESULTS
text: One of the key ingredients of the proofs by Hanin & Rolnick (2019a) is the co-area formula.1 The co-area formula is applied to get a closed form representation of the k−dimensional volume of the region where any set of k neurons, z1, z2, ..., zk 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 a closed form representation of the m− k−dimensional 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 a 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 determinant as defined in 3.1 has the same volume as the projection of the parallelepiped defined by the gradients∇z(x) onto the tangent space (see Proposition 8). This introduces the constant CM , defined above. Essentially, the constant captures how the magnitude of the gradients,∇z(x), are modified upon being projected to the tangent plane. Certain manifolds “shrink”
1https://en.wikipedia.org/wiki/Coarea_formula 2https://en.wikipedia.org/wiki/Smooth_coarea_formula
vectors upon projection to the tangent plane more than others, on an average, which is a 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 11 in the appendix). 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.

heading: 4 EXPERIMENTS

heading: 4.1 SUPERVISED LEARNING ON TOY DATASET
text: To empirically corroborate our theoretical results, we calculate the number of linear regions and average distance to the linear boundary, bounds for which are presented in the theorems above, on a 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 ψcircle : (−π, π) → R2 where ψcircle(θ) = (cos θ, sin θ) and θ 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 a periodic function in θ. The target is defined as z(θ) = a sin(νθ) where a is the amplitude and ν is the frequency (Figure 3). DNNs have difficulty learning periodic functions (Ziyin et al., 2020). The motivation behind this is to present the DNN with a challenging task where it 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, a tractrix is parametrized by ψtractrix : R1 → R2 where ψtractrix(y) = (t− tanh t, sech t) (see Figure 3). We assign a target function z(t) = a sin(νt). For the purposes of our study we restrict the domain of ψtractrix to (−3, 3). This allows us to observe effects of varying data geometry across the manifolds. The results, averaged over 20 runs, are presented in Figures 4 and 5. 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. 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 CM × Cgrad, since changing the architecture also changes Cgrad. Although this variation in Cgrad is quite low in magnitude as observed empirically by Hanin & Rolnick (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 2) that the constant CM , which is distinct across the two manifolds, affects the number of linear regions throughout training. The tractrix has a higher value of CM and that is reflected in the results. This is due to different “shrinking” of vectors upon being projected to the tangent space as discussed in Section 3.1.
4.2 VARYING nIN
To empirically corroborate the results of Theorems 2 and 3 we vary the dimension nin while keeping m constant. We achieve this by counting the number of linear regions and the average distance to boundary region on the 1D circle as we vary the input dimension in steps of 5. We draw samples of 1D circles in Rnin 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(νθ)) as defined above. The results in Figure 6 shows that the quantities stay proportional to #neurons, and do not vary as nin is increased, as predicted by our theoretical results. This stands in contrast to the results by Hanin & Rolnick (2019a) where the upper and lower bounds both grow exponentially with nin for the number of linear regions in a compact set of Rnin . We provide implementation details in Appendix H.

heading: 4.3 METFACES: HIGH DIMENSIONAL DATASET
text: Our goal with this experiment is 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 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). The generator is a neural network that maps g : Rk → Rnin . 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 a follow up, Karras 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 Zhang 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 I.
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 is a promising research direction. That could lead to increased expressivity for the same number of parameters.

heading: 5 DISCUSSION AND FUTURE WORK
text: 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 a few prominent exceptions (Cloninger & Klock, 2020; Shaham et al., 2015; Chen et al., 2019; Schmidt-Hieber, 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 a 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 a low dimensional manifold.

heading: 6 REPRODUCIBILITY STATEMENT
text: 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 4.2 the implementation details are in Appendix H, Section 4.3 in Appendix I. We also provide additional details for running the StyleGan2 code and its license in Appendix J.

heading: A ASSUMPTIONS
text: We first make explicit the assumptions on the distribution of weights and biases.
A1: The conditional distribution of any set of biases bz1 , ..., bzk given all other weights and biases has a density ρz1,...,zk(b1, ..., bk) with respect to Lebesgue measure on Rk.
A2: The joint distribution of all weights has a density with respect to Lebesgue measure on R#weights.
A3: The data manifold M is smooth.
A4: (Only needed for Theorem 3) the diameter of M defined by dM = supx,y∈M distanceM (x, y) is finite.
A5: (Only needed for Theorem 3) a geodesic ball in manifold M has polynomial volume growth of order m.

heading: B ADDITIONAL BACKGROUND ON MANIFOLDS
text: We provide further background on the theory of manifolds. In this section we first provide the background, definition and an interpretation for the scalar curvature of a manifold at a point. Every smooth manifold is also equipped with a Riemannian metric tensor (or metric tensor in short). Given any two vectors, v and w, in the tangent space of a point x on a manifold M , the metric tensor defines a parallel to the dot product in Euclidean spaces. The metric tensor, at a point x, is defined by the smooth functions gij : M → R, i, j ∈ {1, ..., k}. Where the matrix defined by
Gx = [gij(x)] = g11(x) . . . g1n(x)... . . . ... gn1(x) . . . gnn(x)  is symmetric and invertible. The inner product of u, v ∈ TxM is then defined by 〈u, v〉M = uTGxv. the inner product is symmetric, non-degenerate, and bilinear, i.e.
〈ku, v〉M =k〈u, v〉M = 〈u, kv〉M , 〈u+ w, v〉M =〈u, v〉M + 〈w, v〉M , 〈u, v〉M =〈v, u〉M .
As can be seen, these properties also hold for the Euclidean inner product (with Gx = I for all x). Let the inverse of G = [gij(x)] be denoted by [gij(x)]. Building on this definition of the metric tensor the Ricci curvature tensor is defined as
Rij =− 1
2 n∑ a,b=1 ( ∂2gij ∂xa∂xb + ∂2gab ∂xi∂xj − ∂ 2gib ∂xj∂xa − ∂ 2gjb ∂xi∂xa ) gab
+ n∑ a,b,c,d=1 (1 2 ∂gac ∂xi ∂gbd ∂xj + ∂gic ∂xa ∂gjd ∂xb − ∂gic ∂xa ∂gjb ∂xd ) gabgcd
− 1 4 n∑ a,b,c,d=1 (∂gjc ∂xi + ∂gic ∂xj − ∂gij ∂xc ) gabgcd.
For geometric interpretations of the above tensors we refer the reader to the work by Loveridge (2004).
Another quantity, from the theory of manifolds, which we utilise in our proofs and theorems, is scalar curvature (or Ricci curvature). The curvature is a measure how much the volume of a geodisic ball on the manifold M, e.g. S2, deviates from a d− 1 sphere in the flat space, e.g. R3. 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 a manifold M at a point x with metric tensor [gij ] and Ricci tensor [Rij ] is defined as
C = n∑ i,j=1 gijRij .
Another important concept is that of Hausdorff measure. Since the volumes are “distorted” on a manifold it requires careful consideration when defining a measure and integrating using it on a manifold. The m−dimensional Hausdorff measure, of a set S, is defined as
Hm(S) := sup δ>0 inf { ∞∑ i=1 (diam Ui)d|S ⊆ ∪∞i=1Ui, diam Ui < δ } .
Next we introduce the definition of the differential map that is used in Definition 3.1, for the determinant of the Jacobian. The differential map of a smooth function H from a manifold M to a manifold S at a point x ∈M is the smooth map dH : TxM → TxS such that the tangent vector corresponding to any smooth curve γ : I → M at x, γ′(0) ∈ TxM , maps to the tangent vector of
H ◦ γ in TH(x)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 as its input changes along different directions on M , this also has an analog to how rows of the Jacobian matrix are viewed in calculus. In Definition 3.1 we use the specific case where the function H maps from manifold M to the Euclidean space Rk and the tangent space of a Euclidean space is the Euclidean space itself. Finally, a paralellepiped’s, P in TxM , mapping via the differential map gives us the points in Rk that correspond to this set P .

heading: C RELATED WORK
text: 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 (Hornik et 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 et al., 2014; Su et al., 2016; Smith & Le, 2018; Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019a;b). These approaches are not independent of one another but complementary. For example, Kawaguchi et 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 et al. (2018). Hanin (2019) shows that Deep ReLU networks of finite width can approximate any continuous, convex or smooth functions on a unit cube. These works look at DNNs from the lens of expressive power. More recently, there has been a surge in explaining how various algorithms arrive at these almost accurate function approximations by applying different theoretical models of DNNs. Jacot et 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 over-parametrised DNNs (Arora et al., 2019a;b; 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 on a general manifold. First we note the works looking at DNNs from the lens of expressive power combined with the idea of data geometry. Shaham et al. (2015) demonstrate that the size of the neural network depends on the curvature of the data
manifold and the complexity of the function, whilst depending weakly on the input data dimension, for their construction of sparsely-connected 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. (2019) exploit the low dimensional structure of data to enhance the function approximation capacity of Deep ReLU networks by means of theoretical guarantees. Schmidt-Hieber (2019) shows that sparsely connected deep ReLU networks can approximate a Holder function on a low dimensional manifold embedded in a high dimensional space. Simultaneously, researchers have incorporated data geometry into the learning dynamics line of work (Goldt et al., 2020; Paccolat et al., 2020; Buchanan et al., 2021; Wang et al., 2021). 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. Goldt 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 or 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 on the data and the architecture of the DNN. The results by Hanin & Rolnick (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 a setting with very few simplifying assumptions. We introduce the manifold hypothesis to this setting in order to obtain tighter bounds for the first time. This introduces a 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-Euclidean 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 a 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).

heading: D PROOF SKETCH
text: In this section we provide an overview of how the three main theorems are proved. Theorem 1 provides an equality for measuring the volume of m − k 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 in the ambient space subject to a 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 3 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 to 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.

heading: E PROOF OF THEOREM 1
text: We follow the proof strategy used by Hanin & Rolnick (2019a) but deviate from it to account for our setting where x ∈ M . Let Sz be the set of values at which the neuron z has a discontinuity in the differential of its output (or the neuron switches between the two linear regions of the piecewise linear activation σ), Sz := {x ∈ Rnin |z(x)− bz = 0}. We also have
O := { x ∈ Rnin |∀j = 1, ..., L ∃ neuron z with l(z) = j s.t. σ′(z(x)− bz) 6= 0 } .
Further, S̃z := Sz ∩ O. We state propositions 9 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 (2019a)) Under assumptions A1 and A2, we have, with probability 1,
BF = ⋃
neurons z
S̃z.
By extending the notion of Sz to multiple neurons we have
S̃z1,...,zk := k⋂ j=1 S̃zj ,
meaning that the set S̃z1,...,zk is, intuitively, the collection of inputs in Rin where the neurons zj , j = 1, ..., k, switch between linear regions for σ and at which the output of F is affected by the outputs of these neurons. We refer the reader to section B of the appendix in the work by Hanin & Rolnick (2019a) for an intuitive explanation of proposition 4. Next we state proposition 10 by Hanin & Rolnick (2019a). Proposition 5. (Prosposition 10 by Hanin & Rolnick (2019a)) Fix k = 1, ..., nin, and k distinct neurons z1, ..., zk in F . Then, with probability 1, for every x ∈ BF,k there exists a neighbourhood in which BF,k coincides with a nin−k−dimensional hyperplane.
We now present Proposition 6, and its proof, which incorporates the additional constraint that x ∈M , which is an m-dimensional manifold in Rnin . To prove the proposition we need the definition of tranversal intersection of two manifolds (Guillemin & Pollack, 1974). Definition E.1. Two submanifolds, M1 and M2, of S 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 ∈M1 ∩M2
TxS = TxM1 + TxM2,
if and only if M1 and M2 intersect transversally.
For example, given a 2D hyperplane, P , and the surface of a 3D sphere, S2, intersect in the ambient space R3. We have that this intersection is transverse if and only if P is not tangent to S2. For the case where a 2D hyperplane, P̄ , intersects with S2 at a point p but does not intersect tranversally it coincides exactly with the tangent plane of S2 at point {p} = S2 ∩ P , i.e. TpS = P . Note that in either case the tangent space of the 2D hyperplane P at any point of intersection is the plane itself. Proposition 6. Fix k = 1, ...,m and k distinct neurons z1, ..., zk in F . Then, with probability 1, for every x ∈ BF,k ∩M there exists a neighbourhood in which BF,k coincides with an m − k dimensional submanifold in Rin.
Proof. From Proposition 5 we already know that BF,k is a nin − k-dimensional hyperplane in some neighbourhood of x, with probability 1, for any x ∈ BF,k ∩M . Let this hyperplane be denoted by Pk. This is an n− k dimensional submanifold of Rnin . The tangent space of this hyperplane at x 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 Pk contains or is contained in TxM is 0. Finally, we have the intersection, M ∩Hk, has dimension dim(M) + dim(Hk)−nin (Guillemin & Pollack, 1974), which is equal to m−k.
One implication of Proposition 6 is that for any k ≤ m the m − (k + 1) dimensional volume of BF,k ∩M is 0. In addition to that, Proposition 6 implies that, with probability 1,
volm−k(BF,k) = ∑
distinct neurons z1,...,zk
volm−k(S̃z1,...,zk ∩M). (3)
The final step in the proof of Theorem 1 is to prove the following result. Proposition 7. Let z1, ..., zk be distinct neurons in F and k ≤ m. Then for a bounded m−Hausdorff measurable manifold M embedded in Rnin ,
E [ volm−k ( S̃z1,...,zk ∩M )] = ∫ M E [ Yz1,...,zk(x) ] dx,
where Yz1,...,zk(x) equals JMm,Hk(x)ρb1,...,bk(z1(x), ..., zk(x)), times the indicator function of the event that zj , for j = 1, ..., k, is good at x for every j and Hk : Rnin → Rk is such that Hk(x) = [z1(x), ..., zk(x)]T . The expectation is over the distribution of weights and biases.
Proof. Let z1, ..., zk be distinct neurons in F and M be an m−dimensional compact Haudorff measurable manifold. We seek to compute the mean of volm−k(S̃z1,...,zk ∩M) over the distribution of weights and biases. We can rewrite this expression as∫
Sz1,...,zk∩M 1zj is good at xdvolm−k(x). (4)
The map Hk is Lipschitz and C1 almost everywhere. We first note the smooth coarea formula (theorem 5.3.9 by Krantz & Parks (2008)) in context of our notation. Suppose m ≥ k and Hk : Rnin → Rk is C1 and M ⊆ Rnin is an m−dimensional C1 manifold in Rnin , then∫
M g(x)JMk,Hk(x)dvolm(x) = ∫ Rk ∫ M∩H−1k (y) g(y)dvolm−k(y)dvolk(x), (5)
for everyHm-measurable function g where JMk,Hk is as defined in Definition 3.1.
We denote preactivations and biases of neurons as z(x) = [z1(x), ..., zk(x)]T and bz = [bz1 , ..., bzk ]T . From the notation in A1, we have that
ρbz = ρbz1 ,...,bzk ,
is the joint conditional density of bz1 , ..., bzk given all other weights and biases. The mean of the term in equation 4 over the conditional distribution of bz1 , ..., bzk , ρbz , is therefore∫
Rk bdvolk(b) ∫ {z=b}∩M 1zj is good at xdvolm−k(x), (6)
where we denote [b1, ..., bk]T as b. Thus applying the smooth co-area formula (Equation 5) to the expression in 6 shows that the average 4 is equal to∫
M
Yz1,...,zk(x)dx.
Finally, we take the average over the remaining weights and biases and commute the expectation with the dx integral. We can do this since the integrand is non-negative. This gives us the result:
E [ volm−k ( S̃z1,...,zk ∩M )] = ∫ M E [ Yz1,...,zk(x) ] dx, (7)
as required.
Finally, taking the summation over all possible sets of distinct neurons z1, ..., zk and combining equation 3 with Proposition 7 completes the proof for Theorem 1.

heading: F PROOF OF THEOREM 2
text: To prove the upper bound in Theorem 2 we first show that the (determinant of) Jacobian for the function Hk : M → Rk, Hk(x) = [z1(x), ..., zk(x)]T , as defined in 3.1 is equal to the volume of the parallelopiped defined by the vectors φHk(∇zj(x)), for j = 1, ..., k, where φHk : Rk → TxM is an orthogonal projection onto the orthogonal complement of the kernel of the differential DMHk. Intuitively, this shows that with the added assumption x ∈ 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 Hk : M → Rk such that Hk(x) = [z1(x), ..., zk(x)]T and the differential DMHk is surjective at x then
JMk,Hk(x) = √ det(Gram(φHk(∇z1(x)), ..., φHk(∇zk(x)))), (8)
where φHk : Rn → Rk is a linear map and Gram denotes the Gramian matrix.
Proof. We first define the orthogonal complement of the kernel of the differential DMHk. For a manifold M ⊂ Rn and a fixed point x we have that TxM is a m−dimensional hyperplane. If we choose an orthonormal basis e1, ..., en of Rn such that e1, ..., em spans TxM for a fixed x we can denote all vectors in TxM using m coordinates corresponding to this basis. Therefore, for any vector y ∈ Rk we can get the orthogonal projection of y onto TxM using a m× n matrix which we denote as Px, where Pxy (matrix multiplied by a vector) represents a vector in TxM corresponding to the basis e1, ..., em. For any manifold M in Rn and function Hk : M → Rk we have that DMHk : TxM → Rk at a fixed point x is linear function. Therefore we can write DMHk(v) = Av where v ∈ TxM is denoted using the aforementioned basis of TxM . This implies that A is a k ×m matrix. Therefore, the kernel of DMHk for a fixed point x ∈M is
ker(DMHk) = { z|Az = 0 and z ∈ TxM } .
Since we can create a canonical basis for the space ker(DMHk) starting from the basis e1, ..., em in Rn using the Gram-Schmidt process given the matrix A we have that for any y ∈ Rn we can project it orthogonally onto ker(DMHk). The orthogonal complement of ker(DMHk) is therefore defined by
ker(DMHk) ⊥ = { a|a · z = 0 for some z ∈ ker(DMHk) and a ∈ TxM } .
Similar to the previous argument, we construct a canonical basis starting from e1, ..., em for ker(DMHk)
⊥ and therefore we can denote the orthogonal projection onto ker(DMHk)⊥ as a linear transformation. We denote this linear projection for fixed x using φk.
We denote the basis vectors e1, ...., em as a m × n matrix E where each row i corresponds to the vector ei. Therefore, the orthogonal projection of any vector y ∈ Rn is Ey. Now we can get the matrix A using E∇zj(x) corresponding to each row j for j = 1, ...,m. This uses the fact that the direction of steepest ascent on zj(x) restricted to the tangent space TxM of the manifold M is an orthogonal projection of the direction of steepest ascent in Rn.
Finally, from lemma 5.3.5 by Guillemin & Pollack (1974) we have that
JMk,Hk(x) = H k(DMHk(P ))/Hk(P ),
for any parallelepiped P contained in (ker(DMHk))⊥. Arguing similar to the proof of lemma 5.3.5 by Guillemin & Pollack (1974) we get that
JMk,Hk(x) = √ det((A)TA) = √ det Gram(E∇z1(x), ..., E∇zk(x)),
thereby showing that φHk(y) = Ey is a linear mapping.
Although we state Proposition 8 for neurons zj(x), j = 1, ..., k in the proof, it applies to any function that satisfy the conditions laid out in the proposition. Equipped with Proposition 8 we prove Theorem
2. When the weights and biases of F are independent obtain an upper bound on ρbz1 ,...,bzk (b1, ..., bk) as
Πkj=1ρbzj (b1, ..., bk) ≤ (
sup neurons z
ρbz (b) )k = Ckbias.
Hence, Yz1,...,zk ≤ CkbiasJMk,Hk .
From Proposition 8 we have that JMk,Hk is equal to the k-dimensional volume of the paralellopiped spanned by φx(∇zj(x)) for j = 1, ..., k. Therefore, we have
JMk,Hk ≤ Π k j=1||E∇zj(x)|| ≤ ||E||kΠkj=1||∇zj(x)||, (9)
where ||E|| denotes the matrix norm which is defined as ||E|| = sup { ||Ey|| ∣∣∣y ∈ Rk, ||y|| = 1}. Note that E does not depend on F (or z1, ..., zk) but only on TxM or more generally the geometry of M at any point x. From theorem 1 by Hanin & Nica (2018) we have, for any fixed x,
E [ Πkj=1||∇zj(x)|| ] ≤ ( Cgrad )k , (10)
where,
Cgrad = sup z sup x∈Rnin
E[||∇z(x)||2k]1/k ≤ CeC ∑d j=1 1 nj ,
wherein C > 0 depends only on µ and not on the architecture of F and nj is the width of the hidden layer j. Let CM be defined as
CM := sup { C| there exists a set, S, of non zero m− k-dimensional Hausdorff measure
such that ||Ex|| ≥ C∀x ∈ S }
Therefore, combining equations 10, 9 and result from Theorem 1 we have
E[volm−k(BF,k ∩M)] volm(M)
≤ (
number of neurons k
) (2CgradCbiasCM ) k,
where the expectation is over the distribution of weights and biases.

heading: G PROOF OF THEOREM 3
text: We first prove the following proposition
Proposition 9. For a compact m-dimensional submanifold M in Rn, m,n ≥ 1 and m < n let S ⊆ Rn be a compact fixed continuous piecewise linear submanifold with finitely many pieces and given any U > 0. Let S0 = ∅ and let Sk be the union of the interiors of all k-dimensional pieces of S \ (S0 ∪ ... ∪ Sk−1). Denote by T the -tubuluar neighbourhood of any X ⊂M such that
T (X) = { y|dM (y,X) < and y ∈M } ,
where ∈ (0, U), dM is the geodesic distance between the point y and set X on the manifold M , we have
volm(T (S)) ≤ d∑
k=n−m
volk(Sk ∩M)ωn−k n−kCk,κ,U ,
where Ck,κ,U > 0 is a constant that depends on the average scalar curvature κ(Sk∩M)⊥ and U , and ωn−k is the volume of the unit ball in Rn−k.
Proof. Define d to be the maximal dimension of linear pieces in S. Let x ∈ T (X ∩M). Suppose x /∈ T (X ∩M) for all k = n −m, ..., d − 1. Then the intersection of a geodesic ball of radius around s with S is a ball inside Sd ∩M . Using the convexity of this ball, with respect to the manifold M (Robbin et al., 2011), there exists a point y in Sd ∩M such that the geodesic γ : [0, 1]→M with γ(0) = y and γ(1) = x is perpendicular to Sd ∩M at y. Formally, TSd∩MM at y is perpendicular to ˙γ(0) ∈ TM at y. Let B (N∗(Sd ∩M)) be the union of all the balls along the fiber of the submanifold Sd ∩M . Therefore, we have
volm(T (S ∩M) ≤ volm(B (N∗(Sd ∩M)) + volm(T (S≤d−1 ∩M)), (11)
where S≤d−1 := ∪d−1k=0Sk. We also note that
volm(B (N∗(Sd ∩M)) = volm+d−n(Sd ∩M)voln−d(B ((M ∩ Sd)⊥)),
where B ((M ∩ Sd)⊥) is the average volume of an ball in the submanifold of M orthogonal to M ∩ Sd. This volume depends on the average scalar curvature, κ(M∩Sd)⊥ of the submanifold (M ∩ Sd)⊥. As shown by Wan (2016), for a fixed point x ∈ (M ∩ Sd)⊥
voln−d(B (x, (M ∩ Sd)⊥)) = ωn−d n−d ( 1− κ(x)(M∩Sd)⊥
n− d+ 2 2 +O( 4)
) ,
where ωn−d is the volume of the unit ball of dimension n− d, B (x, (M ∩Sd)⊥) is the geodesic ball of radius in the manifold (M ∩ Sd)⊥ centered at x and κ(M∩Sd)⊥(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 k ∈ {n−m,n−m+ 1, ..., d}, then we have a smallest Ck,κ,U such that
volk(B (x, (M ∩ Sk)⊥)) ≤ Ck,κ,U k. (12)
The above inequality follows from assumption A5. Using the above inequalities 11, 12 and repeating the argument d− 1− n+m times we get the result of the proposition.
We also note that Ck,κ,U increases monotonically with U , this also follows from the volume being monotonically increasing and positive for > 0. Finally, we can now prove Theorem 3. Let x ∈M
be uniformly chosen. Then, for all ∈ (0, U), using Markov’s inequality and Proposition 9, we have
E[distanceM (x,Bf ∩M)] ≥ Pr(distanceM (x,BF ∩M) > ) = (1− Pr(distanceM (x,BF ∩M) <= ))
≥ (1− nin∑
k=nin−m
volk(Sk ∩M)ωn−k nin−kCnin−k,κ,U )
≥ (1− nin∑
k=nin−m
Cnin−k,κ,U (CgradCbiasCM {#neurons})k ) .
Note that as we increase U the constants Cn−k,κ,U increase, although not strictly, for all k. To find the supremum of the expression on the right hand side, of the last inequality, in ∈ (0, U) we multiply and divide the expression by CgradCbiasCM#neurons to get the polynomial
pU (ζ) = ζ ( 1− ∑nin k=nin−m Cnin−k,κ,Uζ k )
CgradCbiasCM#neurons ,
where ζ = CgradCbiasCM#neurons and ζ ∈ (0, U ′) where U ′ = UCgradCbiasCM#neurons. Let dM be the diameter of the manifold M , defined by dM = supx,y∈M distanceM (x, y). We assume that dM is finite. Taking the supremum over all U ∈ (0, dM ] or U ′ ∈ (0, d′M ], where d′M = dMCgradCbiasCM#neurons, gives us the constant CM,κ
CM,κ = sup U ′∈(0,d′M ] { sup ζ∈(0,U ′) {pU (ζ)}}.
Since dM is finite the constant above exists and is finite. We make a note on the existence of this constant CM,κ in the absence of the constraint that the diameter of manifold M is finite. As U increases the constants Cnin−k,κ,U also increase and are all positive. The solution for p ′ U (ζ) = 0, ζ > 0, which we denote by ζU , is unique and keeps decreasing as U increases. The uniqueness of the solution follows from the fact that the coefficients Cnin−k,κ,U are all positive. We also note that pU (ζU ) need not be equal to supζ∈(0,U ′){pU (ζ)} because ζU need not lie in (0, U ′). In all such cases supζ∈(0,U ′){pU (ζ)} = pU (U ′). Given the polynomial pU (ζ) above if we can assert that there exists a CU , and the corresponding CU ′ , such that for all U > CU , and corresponding U ′ > CU ′ , we have supζ∈(0,U ′){pU (ζ)} = pU (ζU ) < ∞ and for all 0 < U ≤ CU we have supζ∈(0,U ′){pU (ζ)} = pU (U ′) <∞. Therefore, CM,κ exists and is finite if the previous assertion holds, proving this assertion is beyond the scope of our current work and particularly challenging.
Finally, taking the average over distribution of weights gives us the inequality
E[distanceM (x,Bf ∩M)] ≥ CM,κ
CgradCbiasCM#neurons ,
where CM,κ is a constant which depends on the average scalar curvature of the manifold M . This completes the proof of Theorem 3.

heading: H TOY SUPERVISED LEARNING PROBLEMS
text: For the two supervised learning tasks with different geometries (tractrix and sphere), we uniformly sample 1000 data points from each 1D manifold to come up with samples of (xi, yi) pairs. We then add Gaussian noise to y. We train a DNN with 2 hidden layers, with 10 and 16 neurons in each layer and a single linear output neuron, for a total of 26 neurons with piecewise linearity, using the PyTorch library. The optimization is performed using the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 0.01. We ensure a reasonable fit of the model by reducing the test time mean squared error (see Figure 12). We then calculate the exact number of linear regions on the respective domains by finding the points where z(x) = bz for every neuron z and x is on the 1D manifold. We do this by adding neurons, z, one by one at every layer and using the SLSQP (Kraft, 1988) to solve for |z(x)− bz| = 0. We then split a 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,
by sampling directly from θ and t, to measure average distance to the nearest linear boundaries. The experiment was run on CPUs, from training to counting of 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 PyTorch, except for SLQSP for which we used sklearn.
H.1 VARYING nIN
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 a sphere. The only difference is that the input dimension varies, nin.

heading: I HIGH DIMENSIONAL DATASET
text: We utilise the official implementation of pretrained StyleGAN generator to generate curves of images that lie on the manifold of face images. Specifically, for each curve we sample a random pair of latent vectors: z1, z2 ∈ Rk, this gives us the start and end point of the curve using the generator g(z1) and g(z2). 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 z1 and z2 in the latent space that are evenly spaced and generate an image from each one of them. Therefore, the ith image is generated as: xi = g(((100−i)×z1+i×z2)/100), 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 in the video here: https://drive.google. com/file/d/1p9B8ATVQGQYoiMh3Q22D-jSaI0USsoNx/view?usp=sharing.
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× 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 on metfaces dataset, was approximately 36 GPU hours on a Titan RTX GPU that has 24 GB memory. This was run on an on demand cloud instance. We chose hyperparameters by trial and error, targeting a better fit for the training data.

heading: J CODE, DATA AND LICENSES
text: All the code used for our experiments (except the StyleGAN2 code) is enclosed in the folder exp/. The instructions to run all the experiments are enclosed in exp/readme.txt. We plan on releasing the code as an open github repository under the MIT License (https://opensource.org/ licenses/MIT). The files changed on the github repository for the official implementation of StyleGAN2 (https://github.com/NVlabs/stylegan2-ada-pytorch) are enclosed in the folder stylegan2-ada-pytorch. The instructions to run the experiments are documented in stylegan2-ada-pytorch/readme.txt.
Finally, the images we used to sample linear regions on a curve’s piecewise approximation on the manifold of face images, for the MetFaces experiment, are in the zip file https://drive.google. com/file/d/1x5t-sc9NlW5N_ZBXUM0WcfX-toUXa85L/view?usp=sharing.

heading: K BROADER IMPACT STATEMENT
text: 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 our 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 in deep learning that uses excessive compute creates barriers for smaller labs and individuals from training state of the art models.

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

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.

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. 

This paper theoretically characterizes the number of linear regions of ReLU neural networks at initialization. Compared to existing results, the authors take the data manifold into consideration, and the number of linear regions is measured on the data manifold. Moreover, for uniformly random sampled data on a compact manifold, the expected (geodesic) distance to the linear boundary is analyzed.  To further support the theory and also extend to the behavior through the training process, the paper provides synthetic data and real data experiments. There are indications of the number of linear regions does not deviate significantly from their initialization and is faithful to the data manifold dimension.