# EFFECTS OF DATA GEOMETRY
## IN EARLY DEEP LEARNING

**Anonymous authors**
Paper under double-blind review

ABSTRACT

Deep neural networks can approximate functions on different types of data, from
images to graphs, with varied underlying structure. This underlying structure can
be viewed as the geometry of the data manifold. By extending recent advances
in the theoretical understanding of neural networks, we study how 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.

1 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 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 R[d], 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.

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 the theory of DNNs we refer the reader to Appendix C.

2.1 DATA MANIFOLD AND DEFINITIONS

We use the example of the MetFaces dataset (Karras et al., 2020a) to illustrate how data lies on a low
dimensional manifold. The images in the dataset are 1028 × 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 ⊂_ R[m], to another open subset Y ⊂ _R[k], 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 ⊂ R[k] _is called a smooth m-dimensional submanifold_
_of R[k]_ _(or m-manifold in R[k]) iff every point x ∈_ _M has an open neighborhood U ⊂_ R[k] _such that_
_U ∩_ _M is diffeomorphic to an open subset Ω_ _⊂_ R[m]. 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 : Ω _∩_ R[10] _→_ _M ∩_ R[1028][×][1028][×][3]. This parametrization and its
inverse are unknown in general, and computationally very difficult to estimate in practice.


-----

Figure 1: A visualization of how the 2D surface, here represented by a 2-torus, is embedded in a
larger input space, R[3]. Suppose each point corresponds to an image of the face on this 2-torus. We
can chart two curves: one straight line cutting across the 3D space and another curve that stays on the
torus. The images corresponding to the points on the torus will have a smoother variation in style and
shape whereas there will be images corresponding to points on the straight line that do not belong to
the class of pictures of faces.

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. Let M be an m-manifold in R[k]** _and x ∈_ _M be a fixed point. A vector v ∈_ R[k] _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, S[2] _⊂_ R[3], which is a 2-manifold in R[3].
The tangent space at a fixed point x ∈ _S[2]_ 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.

2.2 LINEAR REGIONS OF DEEP RELU NETWORKS

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 : R[n][in] _→_ R is defined as,

_F_ (x) = WLσ(BL 1 + WL 1σ(...σ(B1 + W1x))), (1)
_−_ _−_

wherethe l[th] _Whidden layer,l ∈_ M[n][l][×][n] B[l][−]l[1] ∈is the weight matrix for theR[n][l] is the vector of biases for the l[th] hidden layer, l[th] hidden layer, nl is the number of neurons in n0 = nin and σ : R → R


-----

is the activation function. For a neuron z in the l[th] layer we denote the pre-activation of this neuron,
for given input x ∈ R[n][in], 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 l[th] 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 ∈ R[n][in] 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
volof a neural networknin 1( _F_ _K)/vol F is thenin(K) (, for a bounded setnin −_ 1)−dimensional volume density of linear regions defined as K R[n][in]. This quantity serves as a proxy for
density of linear regions and therefore the expressive capacity of DNNs. Intuitively, higher density of− _B_ _∩_ _⊂_
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, _F ) =_ min
_B_ neurons z _[|][z][(][x][)][ −]_ _[b][z][|][/][||∇][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)_ # neurons _,_

volnin(K) _≈_ _{_ _}_

h i

meaning the density of linear regions is bound above and below by some constant times the number
of neurons. Secondly, for x ∈ [0, 1][n][in],

E distance(x, BF ) _≥_ _C#{ neurons}[−][1],_
h i

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.

3 LINEAR REGIONS ON THE DATA MANIFOLD

One important assumption in the results presented by Hanin & Rolnick (2019a) is that the input, x,
lies in a compact set K ⊂ R[n][in] 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][n][in] . 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 R[n][in], i.e. M ⊂ R[n][in] 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 “BF as BF,k. More precisely, BF,0 = ∅ and BF,k is recursively defined to be the set of points(nin − _k)−dimensional piece” of_
we definexcoincides with hyperplane of dimension ∈BF \ {B BF,k[′] _F,0[as] ∪[ B]...[F,k] ∪B[ ∩]F,k[M]−[, and note that]1} with the added condition that in a neighbourhood of nin −[ dim(]k. In our setting, where the data lies on a manifold[B]F,k[′]_ [) =][ m][ −] _[k][ (Appendix E Proposition 6). For] x the set B MF,k,_


-----

Figure 2: A circle is an example of a 1D 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
arc from −π to π. In the diagram above, each color in the 2D space corresponds to a linear region.
When the upper half of the circle is flattened into a 1D space we obtain a line. Each color on the line
corresponds to a linear region of the 2D space.

example, the transverse intersection (see Definition E.1) of a plane in 3D with the 2D manifold S[2]
is a 1D curve in S[2] and therefore has dimension 1. Therefore, BF,k[′] [is a submanifold of dimension]
3 2 = 1. This imposes the restriction k _m, for the intersection_ _F,k_ _M to have a well defined_
volume. − _≤_ _B_ _∩_

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 R[n][in] . 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 R[n][in] 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. Let H[m] 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 →** R[k], where k ≤ dim(M ) =
_m, is defined as_

_k(DM_ _H(P_ ))
_Jk,H[M]_ [(][x][) = sup] _H_ _P is a k-dimensional parallelepiped contained in TxM._ _,_
n _H[k](P_ ) o

_where DM : TxM →_ R[k] _is the differential map (see Appendix B) and we use DM_ _H(P_ ) to denote
_the mapping of the set P in TxM_ _, which is a parallelepiped, to R[k]. 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 ⊂_ R[n][in] _and any_
_k = 1, ...., m the average (m −_ _k)−dimensional volume of BF,k inside M_ _,_


E[volm _k(_ _F,k_ _M_ )] =
_−_ _B_ _∩_


E[Yz1,...,zk ]dvolm(x), (2)


_distinct neurons z1,...,zk in F_


_where Yz1,...,zk is Jm,H[M]_ _k_ [(][x][)][ρ][b]1[,...,b]k [(][z][1][(][x][)][, ..., z][k][(][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 dimension m ≤ _nin and therefore the m−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(_ _F,k_ _M_ ) _# neurons_
_−_ _B_ _∩_ (2CgradCbiasCM )[k],

_volm(M_ ) _≤_ _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:_

_CM,κ_
E[distanceM (x, _F_ _M_ )]
_B_ _∩_ _≥_ _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 R[k] 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.

3.1 INTUITION FOR THEORETICAL RESULTS

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](https://en.wikipedia.org/wiki/Coarea_formula)
[2https://en.wikipedia.org/wiki/Smooth_coarea_formula](https://en.wikipedia.org/wiki/Smooth_coarea_formula)


-----

(a) (b)

Figure 3: The tractrix (a) and circle (b) are plotted in grey on the x-y plane, which are the 1D input
data manifolds. The target function is in blue, on the z-axis, and periodic in nature.

vectors upon projection to the tangent plane more than others, 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.

4 EXPERIMENTS

4.1 SUPERVISED LEARNING ON TOY DATASET

To empirically corroborate our theoretical results, we calculate the number of linear regions and
average distance 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 : (−π, π) → R[2] 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 : R[1] _→_ R[2] 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 ofsince changing the architecture also changes Cgrad. Although this variation in Cgrad is quite low in CM × Cgrad,
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.


-----

Figure 4: Graph of number of linear regions for
tractrix (blue) and sphere (orange). The shaded
regions represent one standard deviation. Note
that the number of neurons is 26 and the number
of linear regions is comparable but different for
both the manifolds.

Figure 6: We observe that as the dimension nin is
increased, while keeping the manifold dimension
constant, the number of linear regions remains
proportional to number of neurons (26).

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 regions proportionally. The number of hidden units
for three layer networks are in the legend along
with the data manifold.


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.

Figure 7: We observe that as the dimension nin is
increased, while keeping the manifold dimension
constant, the average distance varies very little.

Figure 9: We observe that the log density of number of linear regions is lower on the manifold
(blue) as compared to off the manifold (green).
As training progresses, in contrast to previous
examples with generalization, the log density decreases.


-----

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 R[n][in] 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 R[n][in]. We provide implementation details in_
Appendix H.

4.3 METFACES: HIGH DIMENSIONAL DATASET

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 : R[k] _→_ R[n][in] . 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.

5 DISCUSSION AND FUTURE WORK

There is significant amounts of work in both supervised and unsupervised learning settings for
non-Euclidean data (Bronstein et al., 2017). Despite these empirical results most theoretical analysis
remains agnostic to data geometry, with 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.


-----

6 REPRODUCIBILITY STATEMENT

We offer the following details for all the experiments we have performed: hyperparameters, sample
sizes, GPU-hours, CPU-hours, code, neural network architectures, python libraries, input sizes, and
external code bases. We also provide the code with instructions on running it in the readme.txt
in the exp/ folder of the supplementary material. Specifically, for Sections 4.1 and 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.

REFERENCES

Zeyuan Allen-Zhu, Y. Li, and Zhao Song. A convergence theory for deep learning via overparameterization. ArXiv, abs/1811.03962, 2019.

M. Anthony and P. Bartlett. Neural network learning - theoretical foundations. 1999.

Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for
deep nets via a compression approach. ArXiv, abs/1802.05296, 2018.

Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient
descent for deep linear neural networks. ArXiv, abs/1810.02281, 2019a.

Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix
factorization. In NeurIPS, 2019b.

D. Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S.
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 L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear vc-dimension bounds for piecewise
polynomial networks. Neural Computation, 10:2159–2173, 1998.

P. P. Brahma, Dapeng Oliver Wu, and Y. She. Why deep learning works: A manifold disentanglement
perspective. IEEE Transactions on Neural Networks and Learning Systems, 27:1997–2008, 2016.

Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estimation.
_ArXiv, abs/2003.13913, 2020._

M. Bronstein, Joan Bruna, Y. LeCun, Arthur Szlam, and P. Vandergheynst. Geometric deep learning:
Going beyond euclidean data. IEEE Signal Processing Magazine, 34: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.13478, 2021.

Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem.
_ArXiv, abs/2008.11245, 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/1908.01842, 2019.

Alexander Cloninger and Timo Klock. Relu nets adapt to intrinsic dimensionality beyond the target
domain. ArXiv, abs/2008.02545, 2020.

G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control,
_Signals and Systems, 2:303–314, 1989._

Simon Shaolei Du, Wei Hu, and J. Lee. Algorithmic regularization in learning deep homogeneous
models: Layers are automatically balanced. In NeurIPS, 2018.

C. Fefferman, S. Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. arXiv: Statistics
_Theory, 2013._


-----

Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. ArXiv,
abs/1805.09112, 2018.

Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová. Modelling the influence of
data structure on learning in neural networks. ArXiv, abs/1909.11500, 2020.

I. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, S. 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.6544, 2015.

Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial
examples. CoRR, abs/1412.6572, 2015.

Alfred Gray. The volume of a 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 in Mathematical Physics, 376:287–322, 2018._

B. Hanin and D. Rolnick. Complexity of linear regions in deep networks. ArXiv, abs/1901.09021,
2019a.

B. Hanin and D. Rolnick. Deep relu networks have surprisingly few activation patterns. In NeurIPS,
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 on graph-structured data.
_ArXiv, abs/1506.05163, 2015._

K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2:359–366, 1989.

Arthur Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in
neural networks. In NeurIPS, 2018.

Tero Karras, S. Laine, and Timo Aila. A style-based generator architecture for generative adversarial
networks. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp.
4396–4405, 2019.

Tero Karras, Miika Aittala, Janne Hellsten, S. Laine, J. Lehtinen, and Timo Aila. Training generative
adversarial networks with limited data. ArXiv, abs/2006.06676, 2020a.

Tero Karras, S. Laine, Miika Aittala, Janne Hellsten, J. Lehtinen, and Timo Aila. Analyzing and
improving the image quality of stylegan. 2020 IEEE/CVF Conference on Computer Vision and
_Pattern Recognition (CVPR), pp. 8107–8116, 2020b._

Kenji Kawaguchi, L. Kaelbling, and Yoshua Bengio. Generalization in deep learning. ArXiv,
abs/1710.05468, 2017.

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. _CoRR,_
abs/1412.6980, 2015.

Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
_ArXiv, abs/1609.02907, 2017._


-----

Dieter Kraft. A software package for sequential quadratic programming. Tech. Rep. DFVLR-FB
_88-28, DLR German Aerospace Center — Institute for Flight Mechanics, 1988._

S. Krantz and Harold R. Parks. Geometric integration theory. 2008.

Daniel Kunin, Javier Sagastuy-Breña, S. Ganguli, Daniel L. K. Yamins, and H. Tanaka. Neural mechanics: Symmetry and broken conservation laws in deep learning dynamics. ArXiv,
abs/2012.04728, 2020.

Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha SohlDickstein, and Jascha Sohl-Dickstein. Wide neural networks of any depth evolve as linear models
under gradient descent. ArXiv, abs/1902.06720, 2019.

Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric,
geometry, and complexity of neural networks. ArXiv, abs/1711.01530, 2019.

L. Loveridge. Physical and geometric interpretations of the riemann tensor, ricci tensor, and scalar
curvature. 2004.

H. Mhaskar and T. Poggio. Deep vs. shallow networks : An approximation theory perspective. ArXiv,
abs/1608.03287, 2016.

Federico Monti, D. Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M.
Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. 2017
_IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5425–5434, 2017._

Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear
regions of deep neural networks. In NIPS, 2014.

V. Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In
_ICML, 2010._

Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nathan Srebro. A pac-bayesian
approach to spectrally-normalized margin bounds for neural networks. ArXiv, abs/1707.09564,
2018.

Jonas Paccolat, Leonardo Petrini, Mario Geiger, Kevin Tyloo, and Matthieu Wyart. Geometric
compression of invariant manifolds in neural networks. Journal of Statistical Mechanics: Theory
_and Experiment, 2021, 2020._

Dominique Perraul-Joncas and Marina Meila. Non-linear dimensionality reduction: Riemannian
metric estimation and the problem of geometric discovery. arXiv: Machine Learning, 2013.

Ben Poole, S. Lahiri, M. Raghu, Jascha Sohl-Dickstein, and S. Ganguli. Exponential expressivity in
deep neural networks through transient chaos. ArXiv, abs/1606.05340, 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 on Computer Vision and Pattern
_Recognition (CVPR), pp. 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/1606.05336, 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 ICML, 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. ArXiv, abs/1706.04454, 2018.

Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics
of learning in deep linear neural networks. CoRR, abs/1312.6120, 2014.


-----

Johannes Schmidt-Hieber. Deep relu network approximation of functions on a manifold. ArXiv,
abs/1908.00695, 2019.

Thiago Serra, Christian Tjandraatmadja, and S. Ramalingam. Bounding and counting linear regions
of deep neural networks. In ICML, 2018.

Uri Shaham, Alexander Cloninger, and Ronald R. Coifman. Provable approximation properties for
deep neural networks. ArXiv, abs/1509.07385, 2015.

Samuel L. Smith and Quoc V. Le. A bayesian perspective on generalization and stochastic gradient
descent. ArXiv, abs/1710.06451, 2018.

Weijie J. Su, Stephen P. Boyd, and Emmanuel J. Candès. A differential equation for modeling
nesterov’s accelerated gradient method: Theory and insights. In 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, abs/1509.08101,
2015.

Joshua B. Tenenbaum. Mapping a manifold of perceptual observations. In NIPS, 1997.

Z. Wan. Geometric interpretations of curvature. 2016.

Tingran Wang, Sam Buchanan, Dar Gilboa, and John Wright. Deep networks provably classify data
on curves. ArXiv, abs/2107.14324, 2021.

Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon.
Dynamic graph 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 S. Yu. A
comprehensive survey on graph neural networks. IEEE Transactions on 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/1611.03530, 2017.

Liu Ziyin, Tilman Hartwig, and Masahito Ueda. Neural networks fail to learn periodic functions and
how to fix it. ArXiv, abs/2006.08195, 2020.

A ASSUMPTIONS

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 R[k].

**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.


-----

B ADDITIONAL BACKGROUND ON MANIFOLDS

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


_g11(x)_ _. . ._ _g1n(x)_
. .
.. ... ..
_gn1(x)_ _. . ._ _gnn(x)_


_Gx = [gij(x)] =_


is symmetric and invertible. The inner product of u, v ∈ _TxM is then defined by ⟨u, v⟩M = u[T]_ _Gxv._
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 [g[ij](x)]. Building on this definition of the metric
tensor the Ricci curvature tensor is defined as


_n_ _∂2gij_ _∂[2]gib_

_Rij =_ + _[∂][2][g][ab]_ _g[ab]_
_−_ [1]2 _∂xa∂xb_ _∂xi∂xj_ _−_ _∂xj∂xa_ _−_ _∂x[∂][2]i[g]∂x[jb]a_

_a,b=1_

X  

_n_

1 _∂gac_ _∂gbd_ _∂gjd_ _∂gjb_

+ + _[∂g][ic]_ _g[ab]g[cd]_

2 _∂xi_ _∂xj_ _∂xa_ _∂xb_ _−_ _[∂g]∂x[ic]a_ _∂xd_

_a,b,c,d=1_

X  

_n_

_∂gjc_

+ _[∂g][ic]_ _g[ab]g[cd]._

_−_ 4[1] _∂xi_ _∂xj_ _−_ _[∂g]∂x[ij]c_

_a,b,c,d=1_

X  


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. S[2], deviates from a d − 1 sphere in the flat space, e.g. R[3]. 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


_g[ij]Rij._
_i,j=1_

X


_C =_


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

_[∞]_
_H_ _[m](S) := sup_ inf (diam Ui)[d] _S_ _i=1[U][i][,][ diam][ U][i]_ _[< δ]_ _._
_δ>0_ _|_ _⊆∪[∞]_

_i=1_

n X o

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
_→_ _∈_


-----

(a) (b)

Figure 10: The geodesic circle on S[2] (blue region in (a)) does not have the same area as the flat
circle (b), both of radius ϵ. One can imagine cutting the blue top off the sphere’s surface and trying to
"flatten" it. Such an effort will lead to failure, if the material of the sphere does not "stretch", since
the geodesic ball, on S[2], cannot be mapped to a circle in R[2] in a distance preserving manner. Thus,
the area of the two blue regions in (a) and (b) vary. This deviation in the area spanned by the two
spheres, despite their radii being the same, is proportional to the scalar curvature.

_H_ _γ 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 R[k] 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 R[k] that correspond to this set P .

C RELATED WORK

There have been various approaches to explain the efficacy of DNNs in approximating arbitrarily
complex functions. We briefly touch upon two such promising approaches. Broadly, the theory of
DNNs can be viewed from two lenses: expressive power (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).

D PROOF SKETCH

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.


-----

E PROOF OF THEOREM 1

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 ∈_ R[n][in]|z(x) − _bz = 0}._
We also have

_O :=_ _x ∈_ R[n][in] _|∀j = 1, ..., L ∃_ neuron z with l(z) = j s.t. σ[′](z(x) − _bz) ̸= 0_ _._

Further, n o
_Sz := Sz ∩O._
We state propositions 9 and 10 by Hanin & Rolnick (2019a) as we apply them to prove Theorem 1,
relabeling them as needed. f
**Proposition 4. (Proposition 9 by Hanin & Rolnick (2019a)) Under assumptions A1 and A2, we**
_have, with probability 1,_
_BF =_ _Sz._

_neurons z_

[

f

By extending the notion of Sz to multiple neurons we have


_Sz1,...,zk :=_


_Szj_ _,_
_j=1_

\

e


meaning that the set _Sz1,...,zk is, intuitively, the collection of inputs in R[in]_ 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 &

[e]
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 R[n][in]. 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, S[2], intersect in the ambient
space R[3]. 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 S[2]_ at a point p but does not intersect tranversally it
coincides exactly with the tangent plane of S[2] at point _p_ = S[2] _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 everydimensional submanifold in x ∈_ _BF,k ∩_ _M there exists a neighbourhood in which R[in]._ _BF,k coincides with an m −_ _k_

_Proof.neighbourhood of From Proposition 5 we already know that x, with probability 1, for any x BF,kB is aF,k_ _ninM −. Let this hyperplane be denoted byk-dimensional hyperplane in some_
_Pk. This is an n −_ _k dimensional submanifold of R ∈[n][in]. 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[e]z1,...,zk ∩ _M_ ). (3)
X

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 R[n][in],_

E _volm_ _k_ _Sz1,...,zk_ _M_ = E _Yz1,...,zk_ (x) _dx,_
_−_ _∩_ _M_
h  i Z h i

_where Yz1,...,zk_ (x) equals e
_Jm,H[M]_ _k_ [(][x][)][ρ][b]1[,...,b]k [(][z][1][(][x][)][, ..., z][k][(][x][))][,]
_times the indicator function of the event that zj, for j = 1, ..., k, is good at x for every j and_
_Hk : R[n][in]_ _→_ R[k] _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[e]z1,...,zk _M_ ) over the distribution
of weights and biases. We can rewrite this expression as _∩_
ZSz1 _,...,zk ∩M_ **1zj is good at xdvolm−k(x).** (4)

The map Hk is Lipschitz and C [1] 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 :_
R[n][in] _→_ R[k] is C [1] and M ⊆ R[n][in] is an m−dimensional C [1] manifold in R[n][in], then


_g(x)Jk,H[M]_ _k_ [(][x][)][d][vol][m][(][x][) =]


_M_ _∩Hk[−][1](y)_ _g(y)dvolm−k(y)dvolk(x),_ (5)


R[k]


for every H[m]-measurable function g where Jk,H[M] _k_ [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

R[k][ b][d][vol][k][(][b][)] **z=b** _M_ **1zj is good at xdvolm−k(x),** (6)

Z Z{ _}∩_

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

_Yz1,...,zk_ (x)dx.
_M_

Z

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:


volm−k _Sz1,...,zk_ _M_
_∩_
 i
e


_Yz1,...,zk_ (x) _dx,_ (7)
i


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.


-----

F PROOF OF THEOREM 2

To prove the upper bound in Theorem 2 we first show that the (determinant of) Jacobian for the
function Hk : M → R[k], 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 : R[k] _→_ _TxM is_
an orthogonal projection onto the orthogonal complement of the kernel of the differential DM _Hk._
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 →** R[k] _such that Hk(x) = [z1(x), ..., zk(x)][T]_ _and the differential_
_DM_ _Hk is surjective at x then_

_Jk,H[M]_ _k_ [(][x][) =] det(Gram(φHk (∇z1(x)), ..., φHk (∇zk(x)))), (8)

_where φHk : R[n]_ _→_ R[k] _is a linear map and Gram denotes the Gramian matrix.p_

_Proof. We first define the orthogonal complement of the kernel of the differential DM_ _Hk. For a_
manifold M ⊂ R[n] and a fixed point x we have that TxM is a m−dimensional hyperplane. If we
choose an orthonormal basis e1, ..., en of R[n] 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 ∈ R[k] 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 R[n] and function Hk : M → R[k] we have that
_DM_ _Hk : TxM →_ R[k] at a fixed point x is linear function. Therefore we can write DM _Hk(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 DM _Hk for a fixed point x ∈_ _M is_

ker(DM _Hk) =_ _z_ _Az = 0 and z_ _TxM_ _._
_|_ _∈_
n o

Since we can create a canonical basis for the space ker(DM _Hk) starting from the basis e1, ..., em in_
_R[n]_ using the Gram-Schmidt process given the matrix A we have that for any y ∈ _R[n]_ we can project
it orthogonally onto ker(DM _Hk). The orthogonal complement of ker(DM_ _Hk) is therefore defined_
by

ker(DM _Hk)[⊥]_ = _a_ _a_ _z = 0 for some z_ ker(DM _Hk) and a_ _TxM_ _._
_|_ _·_ _∈_ _∈_
n o

Similar to the previous argument, we construct a canonical basis starting from e1, ..., em for
ker(DM _Hk)[⊥]_ and therefore we can denote the orthogonal projection onto ker(DM _Hk)[⊥]_ 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 ∈ R[n] 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 R[n].

Finally, from lemma 5.3.5 by Guillemin & Pollack (1974) we have that

_Jk,H[M]_ _k_ [(][x][) =][ H][k][(][D][M] _[H][k][(][P]_ [))][/][H][k][(][P] [)][,]

for any parallelepiped P contained in (ker(DM _Hk))[⊥]. Arguing similar to the proof of lemma 5.3.5_
by Guillemin & Pollack (1974) we get that


det((A)[T] _A) =_


_Jk,H[M]_ _k_ [(][x][) =]


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

_k_
Π[k]j=1[ρ][b]zj [(][b][1][, ..., b][k][)][ ≤] sup = Cbias[k] _[.]_
neurons z _[ρ][b][z]_ [(][b][)]
 

Hence,
_Yz1,...,zk ≤_ _Cbias[k]_ _[J]k,H[M]_ _k_ _[.]_

From Proposition 8 we have that Jk,H[M] _k_ [is equal to the][ k][-dimensional volume of the paralellopiped]
spanned by φx( _zj(x)) for j = 1, ..., k. Therefore, we have_
_∇_

_Jk,H[M]_ _k_ _j=1[||][E][∇][z][j][(][x][)][|| ≤||][E][||][k][Π][k]j=1[||∇][z][j][(][x][)][||][,]_ (9)

_[≤]_ [Π][k]

where ||E|| denotes the matrix norm which is defined as

_||E|| = sup_ _||Ey||_ _y ∈_ R[k], ||y|| = 1 _._
n o

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,_

_k_
E Π[k]j=1[||∇][z][j][(][x][)][||] _≤_ _Cgrad_ _,_ (10)
h i  

where,

_Cgrad = sup_ sup _C_ _j=1_ _nj1_ _,_
_z_ _x∈R[n][in]_ [E][[][||∇][z][(][x][)][||][2][k][]][1][/k][ ≤] _[Ce]_ [P][d]

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_
n

such that _Ex_ _C_ _x_ _S_
_||_ _|| ≥_ _∀_ _∈_
o

Therefore, combining equations 10, 9 and result from Theorem 1 we have


E[volm _k(_ _F,k_ _M_ )] number of neurons
_−_ _B_ _∩_

volm(M ) _≤_ _k_



(2CgradCbiasCM )[k],


where the expectation is over the distribution of weights and biases.

G PROOF OF THEOREM 3

We first prove the following proposition

**Proposition 9. For a compact m-dimensional submanifold M in R[n], m, n ≥** 1 and m < n let
_S ⊆_ R[n] _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_ _,_
_|_ _∈_
n o

_where ϵ ∈_ (0, U ), dM is the geodesic distance between the point y and set X on the manifold M _, we_
_have_

_d_

_volm(Tϵ(S)) ≤_ _k=Xn−m_ _volk(Sk ∩_ _M_ )ωn−kϵ[n][−][k]Ck,κ,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 R[n][−][k]._
_−_


-----

(a) (b)

Figure 11: We illustrate how vectors project differently on tangent planes of two different manifolds:
circle (a) and tractrix (b). In case of the tractrix the tangents (and the projection of vectors onto them)
are on the inside of the tractrix whereas for the sphere the tangents are always on the outside of the
sphere. Since the projections of vectors onto the tangent space are an essential aspect of our proof we
end up with the term CM, which quantifies the “shrinking” of these vectors upon projection, in the
inequalities for Theorems 2 and 3

_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∩M_ _M at y is perpendicular →_
tosubmanifoldγ(0) ∈ _T SMd at yM. Let. Therefore, we have Bϵ(N_ _[∗](Sd ∩_ _M_ )) be the union of all the ϵ balls along the fiber of the
_∩_

volm(Tϵ(S _M_ ) volm(Bϵ(N (Sd _M_ )) + volm(Tϵ(S _d_ 1 _M_ )), (11)
_∩_ _≤_ _[∗]_ _∩_ _≤_ _−_ _∩_

where S _d_ 1 := _k=0[S][k][. We also note that]_
_≤_ _−_ _∪[d][−][1]_

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 −_ _[κ][(]n[x][)][(][M]d + 2[∩][S][d][)][⊥]_ _ϵ[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_ ) <= ϵ))
_−_ _nin_ _∩_


_k=nin_ _m_ volk(Sk ∩ _M_ )ωn−kϵ[n][in][−][k]Cnin−k,κ,U

X− 

_nin_

_Cnin−k,κ,U_ (CgradCbiasCM _ϵ{#neurons})[k][]_
_k=Xnin−m_


_≥_ _ϵ(1 −_

_≥_ _ϵ(1 −_


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

_ζ_ 1 _k=nin_ _m_ _[C][n]in[−][k,κ,U]_ _[ζ]_ _[k][]_
_−_ [P][n][in] _−_
_pU_ (ζ) = _,_
 _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 [=]
_dM_ _CgradCbiasCM_ #neurons, gives us the constant CM,κ

_CM,κ =_ _U_ _[′]∈sup(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

_CM,κ_
E[distanceM (x, Bf _M_ )]
_∩_ _≥_ _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.

H TOY SUPERVISED LEARNING PROBLEMS

For the two supervised learning tasks with different geometries (tractrix and sphere), we uniformly
sample 1000 data points from each 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,


-----

Figure 12: The test errors for the cases where data is sampled from the tractrix (blue) and the circle
(green). We see that the tractrix converges slower but the magnitude of the errors remains comparable
as training progresses across the two manifolds.

by sampling directly from θ 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.

I HIGH DIMENSIONAL DATASET

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:g(z2). We then generate 100 images to approximate a curve connecting the two images on the image z1, z2 ∈ R[k], this gives us the start and end point of the curve using the generator g(z1) and
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
_i[th]_ 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.](https://drive.google.com/file/d/1p9B8ATVQGQYoiMh3Q22D-jSaI0USsoNx/view?usp=sharing)
[com/file/d/1p9B8ATVQGQYoiMh3Q22D-jSaI0USsoNx/view?usp=sharing.](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.


-----

J CODE, DATA AND LICENSES

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/](https://opensource.org/licenses/MIT)
[licenses/MIT). The files changed on the github repository for the official implementation of](https://opensource.org/licenses/MIT)
[StyleGAN2 (https://github.com/NVlabs/stylegan2-ada-pytorch) are enclosed in](https://github.com/NVlabs/stylegan2-ada-pytorch)
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 man[ifold of face images, for the MetFaces experiment, are in the zip file https://drive.google.](https://drive.google.com/file/d/1x5t-sc9NlW5N_ZBXUM0WcfX-toUXa85L/view?usp=sharing)
[com/file/d/1x5t-sc9NlW5N_ZBXUM0WcfX-toUXa85L/view?usp=sharing.](https://drive.google.com/file/d/1x5t-sc9NlW5N_ZBXUM0WcfX-toUXa85L/view?usp=sharing)

K BROADER IMPACT STATEMENT

Although DNNs have been highly effective in approximating arbitrarily complex functions the reason
behind their effectiveness remains open. Similarly, the cases and theoretical reasons for where
they fail to approximate or introduce bias remain underexplored. Our work is unique in the sense
that it looks at both data and model together when estimating the approximation capabilities of the
model. Our empirical results are also close to the theoretical predictions which enables us to be more
confident of our assertions. The negative impact and ethical concern that 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.


-----

