Abstract
It is wellknown that the expressivity of a neural network depends on itsarchitecture, with deeper networks expressing more complex functions. In thecase of networks that compute piecewise linear functions, such as those withReLU activation, the number of distinct linear regions is a natural measure ofexpressivity. It is possible to construct networks with merely a single region,or for which the number of linear regions grows exponentially with depth; it isnot clear where within this range most networks fall in practice, either beforeor after training. In this paper, we provide a mathematical framework to countthe number of linear regions of a piecewise linear network and measure thevolume of the boundaries between these regions. In particular, we prove thatfor networks at initialization, the average number of regions along anyonedimensional subspace grows linearly in the total number of neurons, farbelow the exponential upper bound. We also find that the average distance tothe nearest region boundary at initialization scales like the inverse of thenumber of neurons. Our theory suggests that, even after training, the number oflinear regions is far below exponential, an intuition that matches ourempirical observations. We conclude that the practical expressivity of neuralnetworks is likely far below that of the theoretical maximum, and that this gapcan be quantified.
Quick Read (beta)
Complexity of Linear Regions in Deep Networks
Abstract
It is wellknown that the expressivity of a neural network depends on its architecture, with deeper networks expressing more complex functions. In the case of networks that compute piecewise linear functions, such as those with ReLU activation, the number of distinct linear regions is a natural measure of expressivity. It is possible to construct networks with merely a single region, or for which the number of linear regions grows exponentially with depth; it is not clear where within this range most networks fall in practice, either before or after training. In this paper, we provide a mathematical framework to count the number of linear regions of a piecewise linear network and measure the volume of the boundaries between these regions. In particular, we prove that for networks at initialization, the average number of regions along any onedimensional subspace grows linearly in the total number of neurons, far below the exponential upper bound. We also find that the average distance to the nearest region boundary at initialization scales like the inverse of the number of neurons. Our theory suggests that, even after training, the number of linear regions is far below exponential, an intuition that matches our empirical observations. We conclude that the practical expressivity of neural networks is likely far below that of the theoretical maximum, and that this gap can be quantified.
1 Introduction
A growing field of theory has sought to explain the broad success of deep neural networks via a mathematical characterization of the ability of these networks to approximate different functions of input data. Many such works consider the expressivity of neural networks, showing that certain functions are more efficiently expressible by deep architectures than by shallow ones (e.g. Bianchini & Scarselli (2014); Montufar et al. (2014); Telgarsky (2015); Lin et al. (2017); Rolnick & Tegmark (2018)). It has, however, also been noted that many expressible functions are not efficiently learnable, at least by gradient descent (ShalevShwartz et al., 2018). More generally, the typical behavior of a network used in practice, the practical expressivity, may be very different from what is theoretically attainable. To adequately explain the power of deep learning, it is necessary to consider networks with parameters as they will naturally occur before, during, and after training.
Networks with a piecewise linear activation (e.g. ReLU, hard $\mathrm{tanh}$) compute piecewise linear functions for which input space is divided into pieces, with the network computing a single linear function on each piece (see Figures 14). Figure 2 shows how the complexity of these pieces, which we refer to as linear regions, changes in a deep ReLU net with twodimensional inputs. Each neuron in the first layer splits the input space into two pieces along a hyperplane, fitting a different linear function to each of the pieces. Subsequent layers split the regions of the preceding layers. The local density of linear regions serves as a convenient proxy for the local complexity or smoothness of the network, with the ability to interpolate a complex data distribution seeming to require fitting many relatively small regions. The topic of counting linear regions is taken up by a number of authors (Telgarsky, 2015; Montufar et al., 2014; Serra et al., 2018; Raghu et al., 2017).
A worst case estimate is that every neuron in each new layer splits each of the regions present at the previous layer, giving a number of regions exponential in the depth. Indeed this is possible, as examined extensively e.g. in Montufar et al. (2014). An example of Telgarsky (2015) shows that a sawtooth function with ${2}^{n}$ teeth can be expressed exactly using only $3n+4$ neurons, as shown in Figure 3. However, even slightly perturbing this network (by adding noise to the weights and biases) ruins this beautiful structure and severely reduces the number of linear pieces, raising the question of whether typical neural networks actually achieve the theoretical bounds for numbers of linear regions.
Figure 1 also invites measures of complexity for piecewise linear networks beyond region counting. The boundary between two linear regions can be straight or can be bent in complex ways, for example, suggesting the volume of the boundary between linear regions as complexity measure for the resulting partition of input space. In the 2D example of Figure 1, this corresponds to computing perimeters of the linear pieces. As we detail below, this measure has another natural advantage: the volume of the boundary controls the typical distance from a random input to the boundary of its linear region (see §2.2). This measures the stability of the function computed by the network, and it is intuitively related to robustness under adversarial perturbation.
Our Contributions. In this paper, we provide mathematical tools for analyzing the complexity of linear regions of a network with piecewise linear activations (such as ReLU) before, during, and after training. Our main contributions are as follows:

•
For networks at initialization, the total surface area of the boundary between linear regions scales as the number of neurons times the number of breakpoints of the activation function. This is our main result, from which several corollaries follow (see Theorem 3, Corollary 4, and the discussion in §2).

•
In particular, for any line segment through input space, the average number of regions intersecting it is linear in the number of neurons, far below the exponential number of regions that is theoretically attainable.
 •

•
We find empirically that both the number of regions and the distance to the nearest region boundary stay roughly constant during training and in particular are far from their theoretical maxima. That this should be the case is strongly suggested by Theorem 3, though not a direct consequence of it.
Overall, our results stress that practical expressivity lags significantly behind theoretical expressivity. Moreover, both our theoretical and empirical findings suggest that for certain measures of complexity, trained deep networks are remarkably similar to the same networks at initialization.
In the next section, we informally state our theoretical and empirical results and explore the underlying intuitions. Detailed descriptions of our experiments are provided in §3. The precise theorem statements for ReLU networks can be found in §5. The exact formulations for general piecewise linear networks are in Appendix A, with proofs in the rest of the Supplementary Material. In particular, Appendix B contains intuition for how our proofs are shaped, while details are completed in §CD.
2 Informal Overview of Results
This section gives an informal introduction to our results. We begin in §2.1 by describing the case of networks with input dimension $1.$ In §2.2, we consider networks with higher input dimension. For simplicity, we focus throughout this section on fully connected ReLU networks. We emphasize, however, that our results apply to any piecewise linear activation. Moreover, the upper bounds we present in Theorems 1, 2, and 3 (and hence in Corollaries 4 and 5) can also be generalized to hold for feedforward networks with arbitrary connectivity, though we do not go into details in this work, for the sake of clarity of exposition.
2.1 Number of Regions in 1D
Consider the simple case of a $\mathrm{ReLU}$ net $\mathcal{N}$ with input and output dimensions equal to $1.$ Such a network computes a piecewise linear function (see Figure 4), and we are interested in understanding both at initialization and during training the number of distinct linear regions. There is a simple universal upper bound:
$$\text{max}\mathrm{\#}\{\mathrm{regions}\}\le {2}^{\mathrm{\#}\mathrm{neurons}},$$  (1) 
where the maximum is over all settings of weight and biases. This bound depends on the architecture of $\mathcal{N}$ only via the number of neurons. For more refined upper bounds which take into account the widths of the layers, see Theorem 1 in Raghu et al. (2017) and Theorem 1 in Serra et al. (2018).
The constructions in Montufar et al. (2014); Telgarsky (2015); Raghu et al. (2017); Serra et al. (2018) indicate that the bound in (1) is very far from sharp for shallow and wide networks but that exponential growth in the number of regions can be achieved in deep, skinny networks for very special choices of weights and biases. This is a manifestation of the expressive power of depth, the idea that repeated compositions allow deep networks to capture complex hierarchical relations more efficiently per parameter than their shallow cousins. However, there is no nontrivial lower bound for the number of linear regions:
$$\text{min}\mathrm{\#}\{\mathrm{regions}\}=1,\forall \mathcal{N}.$$ 
The minimum is attained by setting all weights and biases to $0.$ This raises the question of the behavior for the average number of regions when the weights and biases are chosen at random (e.g. at initialization). Intuitively, configurations of weights and biases that come close to saturating the exponential upper bound (1) are numerically unstable in the sense that a small random perturbation of the weights and biases drastically reduces the number of linear regions (see Figure 3 for an illustration). In this direction, we prove a somewhat surprising answer to the question of how many regions $\mathcal{N}$ has at initialization. We state the result for $\mathrm{ReLU}$ but note that it holds for any piecewise linear, continuous activation function (see Theorems 3 and 6).
Theorem 1 (informal).
Let $\mathrm{N}$ be a network with piecewise linear activation with input and output dimensions of $\mathrm{N}$ both equal $\mathrm{1}$. Suppose the weights and biases are randomly initialized so that for each neuron $z$, its preactivation $z\mathit{}\mathrm{(}x\mathrm{)}$ has bounded mean gradient
$$\mathbb{E}\left[\parallel \nabla z(x)\parallel \right]\le C,\mathit{\text{some}}C0.$$  (2) 
This holds, for example, for $\mathrm{ReLU}$ networks initialized with independent, zerocentered weights with variance $\mathrm{2}\mathrm{/}\mathit{\text{fanin}}\mathrm{.}$ Then, for each subset $I\mathrm{\subset}\mathrm{R}$ of inputs, the average number of linear regions inside $I$ is proportional to the number of neurons times the length of $I$
$$\mathbb{E}\left[\mathrm{\#}\{\mathrm{regions}\mathrm{in}I\}\right]\approx \leftI\right\cdot T\cdot \mathrm{\#}\{\mathrm{neurons}\},$$ 
where $T$ is the number of breakpoints in the nonlinearity of $\mathrm{N}$ (for ReLU nets, $T\mathrm{=}\mathrm{1}$). The same result holds when computing the number of linear regions along any fixed $\mathrm{1}$dimensional curve in a highdimensional input space.
This theorem implies that the average number of regions along a onedimensional curve in input space is proportional to the number of neurons, but independent of the arrangement of those neurons. In particular, a shallow network and a deep network will have the same complexity, by this measure, as long as they have the same total number of neurons. Of course, as $\leftI\right$ grows, the bounds in Theorem 1 become less sharp. We plan to extend our results to obtain bounds on the total number of regions on all of $\mathbb{R}$ in the future. In particular, we believe that at initialization the mean total number of linear regions $\mathcal{N}$ is proportional to the number of neurons (this is borne out in Figure 5, which computes the total number of regions on an infinite line).
Theorem 1 defies the common intuition that, on average, each layer in $\mathcal{N}$ multiplies the number of regions formed up to the previous layer by a constant larger than one. This would imply that the average number of regions is exponential in the depth. To provide intuition for why this is not true for random weights and biases, consider the effect of each neuron separately. Suppose the preactivation $z(x)$ of a neuron $z$ satisfies $\left{z}^{\prime}(x)\right=\mathrm{\Theta}(1)$, a hallmark of any reasonable initialization. Then, over a compact set of inputs, the piecewise linear function $x\mapsto z(x)$ cannot be highly oscillatory over a large portion of the range of $z$. Thus, if the bias ${b}_{z}$ is not too concentrated on any interval, we expect the equation $z(x)={b}_{z}$ to have $O(1)$ solutions. On average, then, we expect that each neuron adds a constant number of new linear regions. Thus, the average total number of regions should scale roughly as the number of neurons.
Theorem 1 follows from a general result, Theorem 3, that holds for essentially any nondegenerate distribution of weights and biases and with any input dimension. If $\parallel \nabla z(x)\parallel $ and the bias distribution ${\rho}_{{b}_{z}}$ are wellbehaved, then throughout training, Theorem 3 suggests the number of linear regions along a $1$dimensional curve in input space scales like the number of neurons in $\mathcal{N}$. Figures 56 show experiments that give empirical verification of this heuristic.
2.2 HigherDimensional Regions
For networks with input dimension exceeding $1,$ there are several ways to generalize counting linear regions. A unitmatching heuristic applied to Theorem 1 suggests
$$\mathrm{\#}\{\mathrm{regions}\}=\mathrm{\#}{\{\mathrm{neurons}\}}^{{n}_{\mathrm{in}}},{n}_{\mathrm{in}}=\text{input dim}.$$ 
Proving this statement is work in progress by the authors. Instead, we consider here a natural and, in our view, equally important generalization. Namely, for a bounded $K\subset {\mathbb{R}}^{{n}_{\mathrm{in}}}$, we consider the $({n}_{\mathrm{in}}1)$dimensional volume density
${\mathrm{vol}}_{{n}_{\mathrm{in}}1}\left({\mathcal{B}}_{\mathcal{N}}\cap K\right)/{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K),$  (3) 
where
$${\mathcal{B}}_{\mathcal{N}}=\{x\nabla \mathcal{N}(x)\text{is not continuous at}x\}$$  (4) 
is the boundary of the linear regions for $\mathcal{N}$. When ${n}_{\mathrm{in}}=1$,
$${\mathrm{vol}}_{0}\left({\mathcal{B}}_{\mathcal{N}}\cap K\right)+1=\mathrm{\#}\{\mathrm{regions}\mathrm{in}K\},$$ 
and hence the volume density (3) truly generalizes to higher input dimension of the number of regions. One reason for studying the volume density (3) is that it gives bounds from below for $\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})$, which in turn provides insight into the nature of the computation performed by $\mathcal{N}.$ Indeed, the exact formula
$$\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})=\underset{\mathrm{neurons}\mathrm{z}}{\mathrm{min}}\left\{\leftz(x){b}_{z}\right/\parallel \nabla z(x)\parallel \right\},$$ 
shows that $\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})$ measures the sensitivity over neurons at a given input $x$. In this formula, $z(x)$ denotes the preactivation for a neuron $z$ and ${b}_{z}$ is its bias, so that $\mathrm{ReLU}(z(x){b}_{z})$ is the postactivation. Moreover, the distance from a typical point to ${\mathcal{B}}_{\mathcal{N}}$ gives a heuristic lower bound for the typical distance to an adversarial example: two inputs closer than the typical distance to a linear region boundary likely fall into the same linear region, and hence are unlikely to be classified differently. Our next result generalizes Theorem 1.
Theorem 2 (informal).
Let $\mathrm{N}$ be a network with a piecewise linear activation, input dimension ${n}_{\mathrm{in}}$ and output dimension $\mathrm{1}\mathrm{.}$ Suppose its weights and biases are randomly initialized as in (2). Then, for $K\mathrm{\subset}{\mathrm{R}}^{{d}_{i\mathit{}n}}$ bounded, the average volume of the linear region boundaries in $K$ satisfies:
$$\mathbb{E}\left[\frac{{\mathrm{vol}}_{{n}_{\mathrm{in}}1}\left({\mathcal{B}}_{\mathcal{N}}\cap K\right)}{{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K)}\right]\approx T\cdot \mathrm{\#}\{\mathrm{neurons}\},$$ 
where $T$ is the number of breakpoints in the nonlinearity of $\mathrm{N}$ (for ReLU nets, $T\mathrm{=}\mathrm{1}$). Moreover, if $x\mathrm{\in}{\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}}^{{n}_{\mathrm{in}}}$ is uniformly distributed, then the average, over both $x$ and the weights/biases of $\mathrm{N}$, distance from $x$ to ${\mathrm{B}}_{\mathrm{N}}$ satisfies
$$\mathbb{E}\left[\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})\right]\ge C{\left(\mathrm{\#}\{\mathrm{neurons}\}\right)}^{1},C>0.$$ 
Experimentally, $\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})$ remains comparable to ${\left(\mathrm{\#}\{\mathrm{neurons}\}\right)}^{1}$ throughout training (see Figure 6).
3 Experiments
We empirically verified our theorems and further examined how linear regions of a network change during training. All experiments below were performed with fullyconnected networks, initialized with He normal weights (i.i.d. with variance $2/\text{fanin}$) and biases drawn i.i.d. normal with variance ${10}^{6}$ (to prevent collapse of regions at initialization, which occurs when all biases are uniquely zero). Training was performed on the vectorized MNIST (input dimension 784) using the Adam optimizer at learning rate ${10}^{3}$. All networks attain test accuracy in the range $9598\%$.
3.1 Number of Regions Along a Line
We calculated the number of regions along lines through the origin and and a random selected training example in input space. For each setting of weights and biases within the network during training, the number of regions along each line is calculated exactly by building up the network one layer at a time and calculating how each region is split by the next layer of neurons. Figure 5 represents the average over 5 independent runs, from each of which we sample 100 lines; variance across the different runs is not significant.
Figure 5 plots the average number of regions along a line, divided by the number of neurons in the network, as a function of epoch during training. We make several observations:

1.
As predicted by Theorem 3, all networks start out with the number of regions along a line equal to a constant times the number of neurons in the network (the constant in fact appears very close to 1 in this case).
 2.

3.
The number of regions actually decreases during the initial part of training, then increases again. We explore this behavior further in other experiments below.
3.2 Distance to the Nearest Region Boundary
We calculated the average distance to the nearest boundary for $10000$ randomly selected input points, for various networks throughout training. Points were selected randomly from a normal distribution with mean and variance matching the componentwise mean and variance of MNIST training data. Results were averaged over $12$ independent runs, but variance across runs is not significant. Rerunning these experiments with sample points selected randomly from (i) the training data or (ii) the test data yielded similar results to random sample points.
In keeping with our results in the preceding experiment, the distance to the nearest boundary first increases then decreases during training. As predicted by Theorem 2, we find that for all networks, the distance to the nearest boundary is wellpredicted by $1/\mathrm{\#}\{\mathrm{neurons}\}$. Throughout training, we find that it approximately varies between the curves $0.4/\mathrm{\#}\{\mathrm{neurons}\}$ and $1.5/\mathrm{\#}\{\mathrm{neurons}\}$ (Figure 6(a)). At initialization, as we predict, all networks have the same value for the product of number of neurons and distance to the nearest region boundary (Figure 6(b)); these products then diverge (slightly) for different architectures, first increasing rapidly and then decreasing more slowly.
We find Figure 6(c) fascinating, though we do not completely understand it. It plots the product of number of neurons and distance to the nearest region boundary against the test accuracy. It suggests two phases of training: first regions expand, then they contract. This lines up with observations made in Arpit et al. (2017) that neural networks “learn patterns first” on which generalization is simple and then refine the fit to encompass memorization of individual samples. A generalization phase would suggest that regions are growing, while memorization would suggest smaller regions are fit to individual data points. This is, however, speculation and more experimental (and theoretical) exploration will be required to confirm or disprove this intuition.
We found it instructive to consider the full distribution of distances from sample points to their nearest boundaries, rather than just the average. For a single network (depth 4, width 16), Figure 7 indicates that this distribution does not significantly change during training, although there appears to be a slight skew towards larger regions, in agreement with the findings in Novak et al. (2018). The histogram shows $\mathrm{log}$distances. Hence, distance to the nearest region boundary varies over many orders of magnitude. This is consistent with Figures 1 and 4, which lend credence to the intuition that small distances to the nearest region boundary are explained by the presence of many small regions. According to Theorem 3, this should correlate with a combination of regions in input space at which some neurons have a large gradient and neurons with highly peaked biases distributions. We hope to return to this in future work.
3.3 Regions Within a 2D Plane
We visualized the regions of a network through training. Specifically, following experiments in Novak et al. (2018), we plotted regions within a plane in the $784$dimensional input space (Figure 8) through three data points with different labels ($0$, $1$, and $2$, in our case) inside a square centered at the circumcenter of the three examples. The network shown has depth $3$ and width $64$. We observe that, as expected from our other plots, the regions expand initially during training and then contract again. We expect the number of regions within a $2$dimensional subspace to be on the order of the square of the number of neurons – that is, ${(64\cdot 3)}^{2}\approx 4\times {10}^{4}$, which we indeed find.
Our approach for calculating regions is simple. We start with a single region (in this case, the square), and subdivide it by adding neurons to the network one by one. For each new neuron, we calculate the linear function it defines on each region, and determine whether that region is split into two. This approach terminates within a reasonable amount of time precisely because our theorem holds: there are relatively few regions. Note that we exactly determine all regions within the given square by calculating all region boundaries; thus our counts are exact and do not miss any small regions, as might occur if we merely estimated regions by sampling points from input space.
4 Related Work
There are a number of works that touch on the themes of this article: (i) the expressivity of depth; (ii) counting the number of regions in networks with piecewise linear activations; (iii) the behavior of linear regions through training; and (iv) the difference between expressivity and learnability. Related to (i), we refer the reader to Eldan & Shamir (2016); Telgarsky (2016) for examples of functions that can be efficiently represented by deep but not shallow ReLU nets. Next, still related to (i), for uniform approximation over classes of functions, again using deep ReLU nets, see Yarotsky (2017); Rolnick & Tegmark (2018); Yarotsky (2018); Petersen & Voigtlaender (2018). For interesting results on (ii) about counting the maximal possible number of linear regions in networks with piecewise linear activations see Bianchini & Scarselli (2014); Montufar et al. (2014); Poole et al. (2016); Arora et al. (2018); Raghu et al. (2017). Next, in the vein of (iii), for both a theoretical and empirical perspective on the number of regions computed by deep networks and specifically how the regions change during training, see Poole et al. (2016); Novak et al. (2018). In the direction of (iv), we refer the reader to ShalevShwartz et al. (2018); Hanin & Rolnick (2018); Hanin (2018). Finally, for general insights into learnability and expressivity in deep vs. shallow networks see Mhaskar & Poggio (2016); Mhaskar et al. (2016); Zhang et al. (2017); Lin et al. (2017); Poggio et al. (2017); Neyshabur et al. (2017).
5 Formal Statement of Results
To state our results precisely, we fix some notation. Let $d,{n}_{\mathrm{in}},{n}_{1},\mathrm{\dots},{n}_{d}\ge 1$ and consider a depth $d$ fully connected $\mathrm{ReLU}$ net $\mathcal{N}$ with input dimension ${n}_{\mathrm{in}}$, output dimension $1$, and hidden layer widths ${n}_{j},j=1,\mathrm{\dots},d1.$ As explained in the introduction, a generic configuration of its weights and biases partitions the input space ${\mathbb{R}}^{{n}_{\mathrm{in}}}$ into a union of polytopes ${P}_{j}$ with disjoint interiors. Restricted to each ${P}_{j},$ $\mathcal{N}$ computes a linear function.
Our main mathematical result, Theorem 3, concerns the set ${\mathcal{B}}_{\mathcal{N}}$ of points $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}$ at which the gradient $\nabla \mathcal{N}$ is discontinuous at $x$ (see (4)). For each $k=1,\mathrm{\dots},{n}_{\mathrm{in}},$ we define
$${\mathcal{B}}_{\mathcal{N},k}=\text{the}\mathrm{`}\mathrm{`}({n}_{\mathrm{in}}k)\text{\u2013dimensional piece\u201d of}{\mathcal{B}}_{\mathcal{N}}.$$  (5) 
More precisely, we set ${\mathcal{B}}_{\mathcal{N},0}:=\mathrm{\varnothing}$ and recursively define ${\mathcal{B}}_{\mathcal{N},k}$ to be the set of points $x\in {\mathcal{B}}_{\mathcal{N}}\backslash \{{\mathcal{B}}_{\mathcal{N},0}\cup \mathrm{\cdots}\cup {\mathcal{B}}_{\mathcal{N},k1}\}$ so that in a neighborhood of $x$ the set ${\mathcal{B}}_{\mathcal{N}}\backslash \{{\mathcal{B}}_{\mathcal{N},0}\cup \mathrm{\cdots}\cup {\mathcal{B}}_{\mathcal{N},k1}\}$ coincides with a codimension $k$ hyperplane.
For example, when ${n}_{\mathrm{in}}=2,$ the linear regions ${P}_{j}$ are polygons, the set ${\mathcal{B}}_{\mathcal{N},1}$ is the union of the open line segments making up the boundaries of the ${P}_{j}$, and ${\mathcal{B}}_{\mathcal{N},2}$ is the collection of vertices of the ${P}_{j}.$ Theorem 3 provides a convenient formula for the average of the $({n}_{\mathrm{in}}k)$dimensional volume of ${\mathcal{B}}_{\mathcal{N},k}$ inside any bounded, measurable set $K\subset {\mathbb{R}}^{{n}_{\mathrm{in}}}$. To state the result, for every neuron $z$ in $\mathcal{N}$ we will write
$$z(x):=\text{preactivation at}z,\mathrm{\ell}(z)=\text{layer index of}z$$  (6) 
and ${b}_{z}:=\text{bias at}z.$ Thus, for a given input $x\in {\mathbb{R}}^{{n}_{0}}$, the postactivation of $z$ is
$$Z(x):=\mathrm{ReLU}(z(x))=\mathrm{max}\{0,z(x){b}_{z}\}.$$  (7) 
Theorem 3 holds under the following assumption on the distribution of weights and biases:

A1:
The conditional distribution of any collection of biases ${b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}$, given all the other weights and biases, has a density ${\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({b}_{1},\mathrm{\dots},{b}_{k})$ with respect to Lebesgue measure on ${\mathbb{R}}^{k}$.

A2:
The joint distribution of all the weights has a density with respect to Lebesgue measure on ${\mathbb{R}}^{\mathrm{\#}\text{weights}}$.
These assumptions hold in particular when the weights and biases of $\mathcal{N}$ are independent with marginal distributions that have a density relative to Lebesgue measure on $\mathbb{R}$ (i.e. at initialization). They hold much more generally, however, and can intuitively be viewed as a nondegeneracy assumption on the behavior of the weights and biases of $\mathcal{N}$. Specifically, they are used in Proposition 10 to ensure that the set ${\mathcal{B}}_{\mathcal{N},k}$ consists of inputs where exactly $k$ neurons turn off/on. Assumption (A1) also allows us, in Proposition 11, to apply the coarea formula (29) to compute the expect volume of the set of inputs where a given collection of neurons turn on/off. Our main result is the following.
Theorem 3.
Suppose $\mathrm{N}$ is a feedforward $\mathrm{ReLU}$ net with input dimension ${n}_{\mathrm{0}}\mathrm{,}$ output dimension $\mathrm{1}$, and random weights/biases. Assume that the distribution of weights/biases satisfies Assumptions $A\mathit{}\mathrm{1}$ and $A\mathit{}\mathrm{2}$ above. Then, with the notation (6), for any bounded measurable set $K\mathrm{\subseteq}{\mathrm{R}}^{{n}_{\mathrm{in}}}$ and any $k\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{n}_{\mathrm{in}}\mathrm{,}$ the average $\mathrm{(}{n}_{\mathrm{in}}\mathrm{}k\mathrm{)}\mathrm{}$ dimensional volume $\mathrm{E}\mathit{}\mathrm{\left[}{\mathrm{vol}}_{{n}_{\mathrm{in}}\mathrm{}k}\mathit{}\mathrm{(}{\mathrm{B}}_{\mathrm{N}\mathrm{,}k}\mathrm{\cap}K\mathrm{)}\mathrm{\right]}$ of ${\mathrm{B}}_{\mathrm{N}\mathrm{,}k}$ inside $K$ is
$$\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}({\mathcal{B}}_{\mathcal{N},k}\cap K)\right]$$  (8) 
of ${\mathrm{B}}_{\mathrm{N}\mathrm{,}k}$ inside $K$ is, in the notation (6),
$$\sum _{\begin{array}{c}\mathrm{distinct}\mathrm{neurons}\\ {z}_{1},\mathrm{\dots},{z}_{k}\mathrm{in}\mathcal{N}\end{array}}{\int}_{K}\mathbb{E}\left[{Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right]\mathit{d}x,$$ 
where ${Y}_{{z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}}\mathit{}\mathrm{(}x\mathrm{)}$ is
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel {\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({z}_{1}(x),\mathrm{\dots},{z}_{k}(x))$$ 
times the indicator function of the event that ${z}_{j}\mathit{}\mathit{\text{is good at}}\mathit{}x$ for each $j\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}k$. Here, ${J}_{{z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}}$ is the $k\mathrm{\times}{n}_{\mathrm{in}}$ Jacobian of the map $x\mathrm{\mapsto}\mathrm{(}{z}_{\mathrm{1}}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{)}\mathrm{,}$
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel :=det{\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}\right)}^{1/2},$$ 
the function ${\rho}_{{b}_{{z}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{b}_{{z}_{k}}}$ is the density of the joint distribution of the biases ${b}_{{z}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{b}_{{z}_{k}}$, and we say a neuron $z$ is good at $x$ if there exists a path of neurons from $z$ to the output in the computational graph of $\mathrm{N}$ so that each neuron along this path is open at $x$).
To evaluate the expression in (8) requires information on the distribution of gradients $\nabla z(x)$, the preactivations $z(x)$, and the biases ${b}_{z}.$ Exact information about these quantities is available at initialization (Hanin, 2018; Hanin & Rolnick, 2018; Hanin & Nica, 2018), yielding the following Corollary.
Corollary 4.
With the notation and assumptions of Theorem 3, suppose the weights are independent are drawn from a fixed probability measure $\mu $ on $\mathrm{R}$ that is symmetric around $\mathrm{0}$ and then rescaled to have $\mathrm{Var}\mathit{}\mathrm{[}\mathrm{weights}\mathrm{]}\mathrm{=}\mathrm{\hspace{0.17em}2}\mathrm{/}\mathit{\text{fanin}}$. Fix $k\mathrm{\in}\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{n}_{\mathrm{in}}\mathrm{\}}$. Then there exists $C\mathrm{>}\mathrm{0}$ for which
$\frac{\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}({\mathcal{B}}_{\mathcal{N},k}\cap K)\right]}{{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K)}$  (9)  
$\mathrm{\hspace{1em}}\le \left({\displaystyle \genfrac{}{}{0pt}{}{\mathrm{\#}\{\mathrm{neurons}\}}{k}}\right){({C}_{\mathrm{grad}}\cdot {C}_{\mathrm{bias}})}^{k},$ 
where
$${C}_{\mathrm{bias}}=\underset{z}{sup}\underset{b\in \mathbb{R}}{sup}{\rho}_{{b}_{z}}(b)$$ 
and
$${C}_{\mathrm{grad}}=\underset{z}{sup}\underset{x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}}{sup}\mathbb{E}{\left[{\parallel \nabla z(x)\parallel}^{2k}\right]}^{1/k}\le C{e}^{C{\sum}_{j=1}^{d}\frac{1}{{n}_{j}}}$$ 
where $C\mathrm{>}\mathrm{0}$ depends only on $\mu $ but not on the architecture of $\mathrm{N}$ and ${n}_{j}$ is the width of the ${j}^{t\mathit{}h}$ hidden layer. Moreover, we also have similar lower bounds
$$\left(\genfrac{}{}{0pt}{}{\mathrm{\#}\{\mathrm{neurons}\}}{k}\right){c}_{\mathrm{bias}}^{k}\le \frac{\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}({\mathcal{B}}_{\mathcal{N},k}\cap K)\right]}{{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K)}$$  (10) 
where
$${c}_{\mathrm{bias}}=\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b),$$ 
and
$$\eta =\left(\frac{{sup}_{x\in K}{\parallel x\parallel}^{2}}{{n}_{\mathrm{in}}}+\sum _{j=1}^{d}{\sigma}_{{b}_{j}}^{2}\right){e}^{{C}^{\prime}{\sum}_{j=1}^{d}\frac{1}{{n}_{j}}},$$ 
with ${C}^{\mathrm{\prime}}\mathrm{>}\mathrm{0}$ depending only on the distribution $\mu $ of the weights in $\mathrm{N}$.
Corollary 5.
Suppose $\mathrm{N}$ is as in Theorem 3 and satisfies the hypothesis (14) in Corollary 7. Then, for any compact set $K\mathrm{\subset}{\mathrm{R}}^{{n}_{\mathrm{in}}}$ let $x$ be a uniform point in $K\mathrm{.}$ There exists $c\mathrm{>}\mathrm{0}$ independent of $K$ so that
$$\mathbb{E}\left[\mathrm{distance}(\mathrm{x},{\mathcal{B}}_{\mathcal{N}})\right]\ge \frac{c}{{C}_{\mathrm{bias}}{C}_{\mathrm{grad}}\mathrm{\#}\{\mathrm{neurons}\}}.$$ 
We prove Corollary 8 in §E. The basic idea is simple. For every $\u03f5>0,$ we have
$$\mathbb{E}\left[\mathrm{distance}(\mathrm{x},{\mathcal{B}}_{\mathcal{N}})\right]\ge \u03f5\mathbb{P}(\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})>\u03f5),$$ 
with the probability on the right hand side scaling like
$$1{\mathrm{vol}}_{{n}_{\mathrm{in}}}({T}_{\u03f5}({\mathcal{B}}_{\mathcal{N}})\cap K)/{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K),$$ 
where ${T}_{\u03f5}({\mathcal{B}}_{\mathcal{N}})$ is the tube of radius $\u03f5$ around ${\mathcal{B}}_{\mathcal{N}}.$ We expect that its volume like $\u03f5{\mathrm{vol}}_{{n}_{\mathrm{in}}1}({\mathcal{B}}_{\mathcal{N}})$. Taking $\epsilon =c/\mathrm{\#}\{\mathrm{neurons}\}$ yields the conclusion of Corollary 8.
6 Conclusions and Further Work
The question of why depth is powerful has been a persistent problem for deep learning theory, and one that recently has been answered by works giving enhanced expressivity as the ultimate explanation. However, our results suggest that such explanations may be misleading. While we do not speak to all notions of expressivity in this paper, we have both theoretically and empirically evaluated one common measure: the linear regions in the partition of input space defined by a network with piecewise linear activations. We found that the average size of the boundary of these linear regions depends only on the number of neurons and not on the network depth – both at initialization and during training. This strongly suggests that deeper networks do not learn more complex functions than shallow networks. We plan to test this interpretation further in future work – for example, with experiments on more complex tasks, as well as by investigating higher order statistics, such as the variance.
We do not propose a replacement theory for the success of deep learning; however, prior work has already hinted at how such a theory might proceed. Notably, Ba & Caruana (2014) show that, once deep networks are trained to perform a task successfully, their behavior can often be replicated by shallow networks, suggesting that the advantages of depth may be linked to easier learning.
References
 Arora et al. (2018) Arora, R., Basu, A., Mianjy, P., and Mukherjee, A. Understanding deep neural networks with rectified linear units. In ICLR, 2018.
 Arpit et al. (2017) Arpit, D., Jastrzębski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj, T., Fischer, A., Courville, A., Bengio, Y., et al. A closer look at memorization in deep networks. In ICML, 2017.
 Ba & Caruana (2014) Ba, J. and Caruana, R. Do deep nets really need to be deep? In NeurIPS, pp. 2654–2662, 2014.
 Bianchini & Scarselli (2014) Bianchini, M. and Scarselli, F. On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE Transactions on Neural Networks and Learning Systems, 25(8):1553–1565, 2014.
 Eldan & Shamir (2016) Eldan, R. and Shamir, O. The power of depth for feedforward neural networks. In COLT, pp. 907–940, 2016.
 Hanin (2018) Hanin, B. Which neural net architectures give rise to exploding and vanishing gradients? In NeurIPS, 2018.
 Hanin & Nica (2018) Hanin, B. and Nica, M. Products of many large random matrices and gradients in deep neural networks. Preprint arXiv:1812.05994, 2018.
 Hanin & Rolnick (2018) Hanin, B. and Rolnick, D. How to start training: The effect of initialization and architecture. In NeurIPS, 2018.
 Lin et al. (2017) Lin, H. W., Tegmark, M., and Rolnick, D. Why does deep and cheap learning work so well? Journal of Statistical Physics, 168(6):1223–1247, 2017.
 Mhaskar et al. (2016) Mhaskar, H., Liao, Q., and Poggio, T. Learning functions: when is deep better than shallow. Preprint arXiv:1603.00988, 2016.
 Mhaskar & Poggio (2016) Mhaskar, H. N. and Poggio, T. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829–848, 2016.
 Montufar et al. (2014) Montufar, G. F., Pascanu, R., Cho, K., and Bengio, Y. On the number of linear regions of deep neural networks. In NeurIPS, pp. 2924–2932, 2014.
 Neyshabur et al. (2017) Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. Exploring generalization in deep learning. In NeurIPS, pp. 5947–5956, 2017.
 Novak et al. (2018) Novak, R., Bahri, Y., Abolafia, D. A., Pennington, J., and SohlDickstein, J. Sensitivity and generalization in neural networks: an empirical study. In ICLR, 2018.
 Petersen & Voigtlaender (2018) Petersen, P. and Voigtlaender, F. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 108:296–330, 2018.
 Poggio et al. (2017) Poggio, T., Mhaskar, H., Rosasco, L., Miranda, B., and Liao, Q. Why and when can deep – but not shallow – networks avoid the curse of dimensionality: a review. International Journal of Automation and Computing, 14(5):503–519, 2017.
 Poole et al. (2016) Poole, B., Lahiri, S., Raghu, M., SohlDickstein, J., and Ganguli, S. Exponential expressivity in deep neural networks through transient chaos. In NeurIPS, pp. 3360–3368, 2016.
 Raghu et al. (2017) Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Dickstein, J. S. On the expressive power of deep neural networks. In ICML, pp. 2847–2854, 2017.
 Rolnick & Tegmark (2018) Rolnick, D. and Tegmark, M. The power of deeper networks for expressing natural functions. In ICLR, 2018.
 Serra et al. (2018) Serra, T., Tjandraatmadja, C., and Ramalingam, S. Bounding and counting linear regions of deep neural networks. In ICML, 2018.
 ShalevShwartz et al. (2018) ShalevShwartz, S., Shamir, O., and Shammah, S. Failures of gradientbased deep learning. In ICML, 2018.
 Telgarsky (2015) Telgarsky, M. Representation benefits of deep feedforward networks. Preprint arXiv:1509.08101, 2015.
 Telgarsky (2016) Telgarsky, M. Benefits of depth in neural networks. In COLT, 2016.
 Yarotsky (2017) Yarotsky, D. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103–114, 2017.
 Yarotsky (2018) Yarotsky, D. Optimal approximation of continuous functions by very deep ReLU networks. In COLT, 2018.
 Zhang et al. (2017) Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Appendix A Formal Statement of Results for General Piecewise Linear Activations
In §5, we stated our results in the case of ReLU activation, and now frame these results for a general piecewise linear nonlinearity. We fix some notation. Let $\varphi :\mathbb{R}\to \mathbb{R}$ be a continuous piecewise linear function with $T$ breakpoints $$ That is, there exist ${p}_{j},{q}_{j}\in \mathbb{R}$ so that
$$t\in [{\xi}_{j},{\xi}_{j+1}]\mathit{\hspace{1em}}\Rightarrow \mathit{\hspace{1em}}\varphi (t)={q}_{j}t+{p}_{j},{q}_{j}\ne {q}_{j+1}.$$  (11) 
The analog of Theorem 3 for general $\varphi $ is the following.
Theorem 6.
Let $\varphi \mathrm{:}\mathrm{R}\mathrm{\to}\mathrm{R}$ be a continuous piecewise linear function with $T$ breakpoints $$ as in (11). Suppose $\mathrm{N}$ is a fully connected network with input dimension ${n}_{\mathrm{in}}\mathrm{,}$ output dimension $\mathrm{1}$, random weights and biases satisfying $A\mathit{}\mathrm{1}$ and $A\mathit{}\mathrm{2}$ above, and nonlinearity $\varphi $.
Let ${J}_{{z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}}$ be the $k\mathrm{\times}{n}_{\mathrm{in}}$ Jacobian of the map $x\mathrm{\mapsto}\mathrm{(}{z}_{\mathrm{1}}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{)}\mathrm{,}$
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel :=det{\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}\right)}^{1/2},$$ 
and write ${\rho}_{{b}_{{z}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{b}_{{z}_{k}}}$ for the density of the joint distribution of the biases ${b}_{{z}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{b}_{{z}_{k}}$. We say a neuron $z$ is good at $x$ if there exists a path of neurons from $z$ to the output in the computational graph of $\mathrm{N}$ so that each neuron $\widehat{z}$ along this path is open at $x$ (i.e. ${\varphi}^{\mathrm{\prime}}\mathit{}\mathrm{(}\widehat{z}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{}{b}_{\widehat{z}}\mathrm{)}\mathrm{\ne}\mathrm{0}$).
Then, for any bounded, measurable set $K\mathrm{\subseteq}{\mathrm{R}}^{{n}_{\mathrm{in}}}$ and any $k\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{n}_{\mathrm{in}}\mathrm{,}$ the average $\mathrm{(}{n}_{\mathrm{in}}\mathrm{}k\mathrm{)}$–dimensional volume
$$\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}({\mathcal{B}}_{\mathcal{N},k}\cap K)\right]$$ 
of ${\mathrm{B}}_{\mathrm{N}\mathrm{,}k}$ inside $K$ is, in the notation of (6),
$$\sum _{\begin{array}{c}\mathrm{distinct}\mathrm{neurons}\\ {z}_{1},\mathrm{\dots},{z}_{k}\mathrm{in}\mathcal{N}\end{array}}\sum _{{i}_{1},\mathrm{\dots},{i}_{k}=1}^{T}{\int}_{K}\mathbb{E}\left[{Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}(x)\right]\mathit{d}x,$$  (12) 
where ${Y}_{{z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}}^{\mathrm{(}{\xi}_{{i}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{\xi}_{{i}_{k}}\mathrm{)}}\mathit{}\mathrm{(}x\mathrm{)}$ equals
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel {\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({z}_{1}(x){\xi}_{{i}_{1}},\mathrm{\dots},{z}_{k}(x){\xi}_{{i}_{k}})$$  (13) 
multiplied by the indicator function of the event that ${z}_{j}$ is good at $x$ for every $j\mathrm{.}$
Note that if in the definition (11) of $\varphi $ we have that the possible values ${\varphi}^{\prime}(t)\in \{{q}_{0},\mathrm{\dots},{q}_{T}\}$ do not include $0$, then we may ignore the event that ${z}_{j}$ are good at $x$ in the definition of ${Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}.$
Corollary 7.
With the notation and assumptions of Theorem 6, suppose in addition that the weights and biases are independent. Fix $k\mathrm{\in}\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{n}_{\mathrm{in}}\mathrm{\}}$ and suppose that for every collection of distinct neurons ${z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}$, the average magnitude of the product of gradients is uniformly bounded:
$$\underset{\begin{array}{c}\mathrm{neurons}{z}_{1},\mathrm{\dots},{z}_{k}\\ \mathrm{inputs}x\end{array}}{sup}\mathbb{E}\left[\prod _{j=1}^{k}\parallel \nabla {z}_{j}(x)\parallel \right]\le {C}_{\mathrm{grad}}^{k}.$$  (14) 
Then we have the following upper bounds
$\frac{\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}({\mathcal{B}}_{\mathcal{N},k}\cap K)\right]}{{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K)}$  (15)  
$\mathrm{\hspace{1em}}\le \left({\displaystyle \genfrac{}{}{0pt}{}{\mathrm{\#}\{\mathrm{neurons}\}}{k}}\right){(T\cdot 2{C}_{\mathrm{grad}}{C}_{\mathrm{bias}})}^{k},$ 
where $T$ is the number of breakpoints in the nonlinearity $\varphi $ of $\mathrm{N}$ (see (11)) and
$${C}_{\mathrm{bias}}=\underset{z}{sup}\underset{b\in \mathbb{R}}{sup}{\rho}_{{b}_{z}}(b).$$ 
Corollary 8.
Suppose $\mathrm{N}$ is as in Theorem 3 and satisfies the hypothesis (14) in Corollary 7 with constants ${C}_{\mathrm{bias}}\mathrm{,}{C}_{\mathrm{grad}}$. Then, for any compact set $K\mathrm{\subset}{\mathrm{R}}^{{n}_{\mathrm{in}}}$ let $x$ be a uniform point in $K\mathrm{.}$ There exists $c\mathrm{>}\mathrm{0}$ independent of $K$ so that
$$\mathbb{E}\left[\mathrm{distance}(\mathrm{x},{\mathcal{B}}_{\mathcal{N}})\right]\ge \frac{cT}{{C}_{\mathrm{bias}}{C}_{\mathrm{grad}}\mathrm{\#}\{\mathrm{neurons}\}},$$ 
where, as before, $T$ is the number of breakpoints in the nonlinearity $\varphi $ of $\mathrm{N}$.
We prove Corollary 8 in §E. The basic idea is simple. For every $\u03f5>0,$ we have
$$\mathbb{E}\left[\mathrm{distance}(\mathrm{x},{\mathcal{B}}_{\mathcal{N}})\right]\ge \u03f5\mathbb{P}(\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})>\u03f5),$$ 
with the probability on the right hand side scaling like
$$1{\mathrm{vol}}_{{n}_{\mathrm{in}}}({T}_{\u03f5}({\mathcal{B}}_{\mathcal{N}})\cap K)/{\mathrm{vol}}_{{n}_{\mathrm{in}}}(K),$$ 
where ${T}_{\u03f5}({\mathcal{B}}_{\mathcal{N}})$ is the tube of radius $\u03f5$ around ${\mathcal{B}}_{\mathcal{N}}.$ We expect that its volume like $\u03f5{\mathrm{vol}}_{{n}_{\mathrm{in}}1}({\mathcal{B}}_{\mathcal{N}})$. Taking $\epsilon =c/\mathrm{\#}\{\mathrm{neurons}\}$ yields the conclusion of Corollary 8.
Appendix B Outline of Proof of Theorem 6
The purpose of this section is to give an intuitive explanation of the proof of Theorem 3. We fix a nonlinearity $\varphi :\mathbb{R}\to \mathbb{R}$ with breakpoints $$ (as in (11)) and consider a fully connected network $\mathcal{N}$ with input dimension ${n}_{\mathrm{in}}\ge 1$, output dimension $1$, and nonlinearity $\varphi .$ For each neuron $z$ in $\mathcal{N}$, we write
$$\mathrm{\ell}(z):=\text{layer index of}z$$  (16) 
and set
$${S}_{z}:=\{x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}z(x){b}_{z}\in \{{\xi}_{1},\mathrm{\dots},{\xi}_{T}\}\}.$$  (17) 
We further
$${\stackrel{~}{S}}_{z}:={S}_{z}\cap \mathcal{O},$$  (18) 
where
$$\mathcal{O}:=\left\{x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}\right\begin{array}{c}\forall j=1,\mathrm{\dots},d\exists \text{neuron}z\text{with}\\ \mathrm{\ell}\left(z\right)=j\text{s.t.}{\varphi}^{\prime}\left(z\left(x\right){b}_{z}\right)\ne 0\end{array}\}.$$ 
Intuitively, the set ${S}_{z}$ is the collection of inputs for which the neuron $z$ turns from on to off. In contrast, the set $\mathcal{O}$ is the collection of inputs $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}$ for which $\mathcal{N}$ is open in the sense that there is a path from the input to the output of $\mathcal{N}$ so that all neurons along this path compute are not constant in a neighborhood $x$. Thus, ${\stackrel{~}{S}}_{z}$ is the set of inputs at which neuron $z$ switches between its linear regions and at which the output of neuron $z$ actually affects the function computed by $\mathcal{N}.$
We remark here that $\mathcal{O}=\mathrm{\varnothing}$ if in the nonlinearity $\varphi $ there are no linear pieces at which the slopes on $\varphi $ equals $0$ (i.e. ${q}_{j}\ne 0$ for all $j$ in the definition (11) of $\varphi $). If, for example, $\varphi $ is ReLU, then $\mathcal{O}$ need not be empty.
The overall proof of Theorem 3 can be divided into several steps. The first gives the following representation of ${\mathcal{B}}_{\mathcal{N}}.$
Proposition 9.
Under Assumptions $A\mathit{}\mathrm{1}$ and $A\mathit{}\mathrm{2}$ of Theorem 3, we have, with probability $\mathrm{1}\mathrm{,}$
$${\mathcal{B}}_{\mathcal{N}}=\bigcup _{\mathrm{neurons}z}{\stackrel{~}{S}}_{z}.$$ 
The precise proof of Proposition 9 can be found in §C.1 below. The basic idea is that if for all $y$ near a fixed input $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}},$ none of the preactivations $z(y){b}_{z}$ cross the boundary of a linear region for $\varphi $, then $x\notin {\mathcal{B}}_{\mathcal{N}}.$ Thus, ${\mathcal{B}}_{\mathcal{N}}\subset {\bigcup}_{z}{S}_{z}.$ Moreover, if a neuron $z$ satisfies $z(x){b}_{z}={S}_{i}$ for some $i$ but there are no open paths from $z$ to the output of $\mathcal{N}$ for inputs near $x$, then $z$ is dead at $x$ and hence does not influence $\mathcal{N}$ at $x.$ Thus, we expect the more refined inclusion ${\mathcal{B}}_{\mathcal{N}}\subset {\bigcup}_{z}{\stackrel{~}{S}}_{z}$. Finally, if $x\in {\stackrel{~}{S}}_{z}$ for some $z$ then $x\in {\mathcal{B}}_{\mathcal{N}}$ unless the contribution from other neurons to $\nabla \mathcal{N}(y)$ for $y$ near $x$ exactly cancels the discontinuity in $\nabla z(x).$ This happens with probability $0$.
The next step in proving Theorem 3 is to identify the portions of ${\mathcal{B}}_{\mathcal{N}}$ of each dimension. To do this, we write for any distinct neurons ${z}_{1},\mathrm{\dots},{z}_{k}$,
$${\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}:=\bigcap _{j=1}^{k}{\stackrel{~}{S}}_{{z}_{j}}.$$ 
The set ${\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}$ is, intuitively, the collection of inputs at which ${z}_{j}(x){b}_{{z}_{j}}$ switches between linear regions for $\varphi $ and at which the output of $\mathcal{N}$ is affected by the postactivations of these neurons. Proposition 9 shows that we may represent ${\mathcal{B}}_{\mathcal{N}}$ as a disjoint union
$${\mathcal{B}}_{\mathcal{N}}=\bigcup _{k=1}^{{n}_{\mathrm{in}}}{\mathcal{B}}_{\mathcal{N},k},$$ 
where
$${\mathcal{B}}_{\mathcal{N},k}:=\bigcup _{\begin{array}{c}\text{distinct neurons}\\ {z}_{1},\mathrm{\dots},{z}_{k}\end{array}}{\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\cap {\left(\bigcup _{z\ne {z}_{1},\mathrm{\dots},{z}_{k}}{\stackrel{~}{S}}_{z}\right)}^{c}.$$ 
In words, ${\mathcal{B}}_{\mathcal{N},k}$ is the collection of inputs in $\mathcal{O}$ at which exactly $k$ neurons turn from on to off. The following Proposition shows that ${\mathcal{B}}_{\mathcal{N},k}$ is precisely the “$({n}_{\mathrm{in}}k)$dimensional piece of ${\mathcal{B}}_{\mathcal{N}}$” (see (5)).
Proposition 10.
Fix $k\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}{n}_{\mathrm{in}}\mathrm{,}$ and $k$ distinct neurons ${z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}$ in $\mathrm{N}\mathrm{.}$ Then, with probability $\mathrm{1}\mathrm{,}$ for every $x\mathrm{\in}{\mathrm{B}}_{\mathrm{N}\mathrm{,}k}$ there exists a neighborhood in which ${\mathrm{B}}_{\mathrm{N}\mathrm{,}k}$ coincides with a $\mathrm{(}{n}_{\mathrm{in}}\mathrm{}k\mathrm{)}\mathrm{}$dimensional hyperplane.
We prove Proposition 10 in §C.2. The idea is that each ${\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}$ is piecewise linear and, with probability $1$, at every point at which exactly the neurons ${z}_{1},\mathrm{\dots},{z}_{k}$ contribute to ${\mathcal{B}}_{\mathcal{N}}$, its codimension is the number of linear conditions needed to define it. Observe that with probability $1$, the bias vector $({b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k+1}})$ for any collection ${z}_{1},\mathrm{\dots},{z}_{k+1}$ of distinct neurons is a regular value for $x\mapsto ({z}_{1}(x),\mathrm{\dots},{z}_{k+1}(x))$. Hence,
$${\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k+1}}\right)=0.$$ 
Proposition 10 thus implies that, with probability $1,$
$${\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\mathcal{B}}_{\mathcal{N},k}\right)=\sum _{\begin{array}{c}\mathrm{distinct}\mathrm{neurons}\\ {z}_{1},\mathrm{\dots},{z}_{k}\end{array}}{\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\right).$$ 
The final step in the proof of Theorem 3 is therefore to prove the following result.
Proposition 11.
Let ${z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}$ be distinct neurons in $\mathrm{N}\mathrm{.}$ Then, for any bounded, measurable $K\mathrm{\subset}{\mathrm{R}}^{{n}_{\mathrm{in}}}$,
$\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\right)\right]$  
$\mathrm{\hspace{1em}}={\displaystyle {\int}_{K}}{\displaystyle \sum _{{i}_{1},\mathrm{\dots},{i}_{k}=1}^{T}}\mathbb{E}\left[{Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({S}_{{i}_{1}},\mathrm{\dots},{S}_{{i}_{k}})}(x)\right]dx,$ 
where ${Y}_{{z}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{z}_{k}}^{\mathrm{(}{S}_{{i}_{\mathrm{1}}}\mathrm{,}\mathrm{\dots}\mathrm{,}{S}_{{i}_{k}}\mathrm{)}}$ is defined as in (13).
We provide a detailed proof of Proposition 11 in §C.3. The intuition is that the image of the volume element $dx$ under $x\mapsto z(x){S}_{i}$ is the volume element
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel dx$$ 
from (13). The probability of an infinitesimal neighborhood $dx$ of $x$ belonging to a $({n}_{\mathrm{in}}k)$dimensional piece of ${\mathcal{B}}_{\mathcal{N}}$ is therefore the probability
${\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({z}_{1}(x){S}_{{i}_{1}},\mathrm{\dots},{z}_{k}(x){S}_{{i}_{k}})$  
$\mathrm{\hspace{1em}}\times \parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel dx$ 
that the vector of biases $({b}_{{z}_{j}},j=1,\mathrm{\dots},k)$ belongs to the image of $dx$ under map $\left({z}_{j}(x){S}_{{i}_{j}},j=1,\mathrm{\dots},k\right)$ for some collection of breakpoints ${S}_{{i}_{j}}.$ The formal argument uses the coarea formula (see (29) and (30)).
Appendix C Proof of Theorem 3
C.1 Proof of Proposition 9
Recall that the nonlinearity $\varphi :\mathbb{R}\to \mathbb{R}$ is continuous and piecewise linear with $T$ breakpoints $$ so that, with ${\xi}_{0}=\mathrm{\infty},{\xi}_{T+1}=\mathrm{\infty}$, we have
$$t\in ({\xi}_{i},{\xi}_{i+1})\mathit{\hspace{1em}}\Rightarrow \mathit{\hspace{1em}}\varphi (t)={q}_{i}t+{p}_{i}$$ 
with ${q}_{i}\ne {q}_{i+1}.$ For each $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}},$ write
${Z}_{x}^{+}$  $:=\left\{z\rightz(x){b}_{z}\in ({\xi}_{i},{\xi}_{i+1})\text{and}{q}_{i}\ne 0\text{for some}i\}$  
${Z}_{x}^{}$  $:=\left\{z\rightz(x){b}_{z}\in ({\xi}_{i},{\xi}_{i+1})\text{and}{q}_{i}=0\text{for some}i\}$  
${Z}_{x}^{0}$  $:=\left\{z\rightz(x){b}_{z}={\xi}_{i}\text{for some}i\}$ 
Intuitively, ${Z}_{x}^{+}$ are the neurons that, at the input $x$ are open (i.e. contribute to the gradient of the output $\mathcal{N}(x)$) but do not change their contribution in a neighborhood of $x$, ${Z}_{x}^{}$ are the neurons that are closed, and ${Z}_{x}^{0}$ are the neurons that, at $x$, produce a discontinuity in the derivative of $\mathcal{N}.$ Thus, for example, if $\varphi =\mathrm{ReLU},$ then
$${Z}_{x}^{*}:=\{z\mathrm{sgn}(z(x){b}_{z})=*\},*\in \{+,,0\}.$$ 
We begin by proving that ${\mathcal{B}}_{\mathcal{N}}\subseteq {\bigcup}_{z}{\stackrel{~}{S}}_{z}$ by checking the contrapositive
$${\left(\bigcup _{z}{\stackrel{~}{S}}_{z}\right)}^{c}\subseteq {\mathcal{B}}_{\mathcal{N}}^{c}.$$  (19) 
Fix $x\in {\left({\bigcup}_{z}{\stackrel{~}{S}}_{z}\right)}^{c}$. Note that ${Z}_{x}^{\pm}$ are locally constant in the sense that there exists $\epsilon >0$ so that for all $y$ with $$, we have
$${Z}_{x}^{}\subseteq {Z}_{y}^{},{Z}_{x}^{+}\subseteq {Z}_{y}^{+},{Z}_{y}^{+}\cup {Z}_{y}^{0}\subseteq {Z}_{x}^{+}\cup {Z}_{x}^{0}.$$  (20) 
Moreover, observe that if in the definition (11) of $\varphi $ none of the slopes ${q}_{i}$ equal $0$, then ${Z}_{y}^{}=\mathrm{\varnothing}$ for every $y$. To prove (19), consider any path $\gamma $ from the input to the output in the computational graph of $\mathcal{N}.$ Such a path consists of $d+1$ neurons, one in each layer:
$$\gamma =({z}_{\gamma}^{(0)},\mathrm{\dots},{z}_{\gamma}^{(d)}),\mathrm{\ell}({z}_{\gamma}^{(j)})=j.$$ 
To each path we may associate a sequence of weights:
$${w}_{\gamma}^{(j)}:=\text{weight connecting}{z}_{\gamma}^{(j1)}\text{to}{z}_{\gamma}^{(j)},j=1,\mathrm{\dots},d.$$ 
We will also define
$${q}_{\gamma}^{(j)}(x):=\sum _{i=0}^{T}{q}_{i}{\mathrm{\U0001d7cf}}_{\{{z}_{\gamma}^{(x)}{b}_{{z}_{\gamma}^{(j)}}\in ({\xi}_{i},{\xi}_{i+1}]\}}.$$ 
For instance, if $\varphi =\mathrm{ReLU}$, then
$${q}_{\gamma}^{(j)}(x)={\mathrm{\U0001d7cf}}_{\{{z}_{\gamma}^{(j)}(x){b}_{z}\ge 0\}},$$ 
and in general only one term in the definition of ${q}_{\gamma}^{(j)}(x)$ is nonzero for each $z.$ We may write
$$\mathcal{N}(y)=\sum _{i=1}^{{n}_{\mathrm{in}}}{y}_{i}\sum _{\begin{array}{c}\text{paths}\gamma :i\to \text{out}\end{array}}\prod _{j=1}^{d}{q}_{\gamma}^{(j)}(y){w}_{\gamma}^{(j)}+\mathrm{constant},$$  (21) 
Note that if $x\in {\left({\bigcup}_{z}{\stackrel{~}{S}}_{z}\right)}^{c}$, then for any path $\gamma $ through a neuron $z\in {Z}_{x}^{0}$, we have
$$\exists j\text{s.t.}{z}_{\gamma}^{(j)}\in {Z}_{x}^{}.$$ 
This is an open condition in light of (20), and hence for all $y$ in a neighborhood of $x$ and for any path $\gamma $ through a neuron $z\in {Z}_{x}^{0}$ we also have that
$$\exists j\text{s.t.}{z}_{\gamma}^{(j)}\in {Z}_{y}^{}.$$ 
Thus, since the summand in (21) vanishes identically if $\gamma \cap {Z}_{y}^{}\ne \mathrm{\varnothing}$, we find that for $y$ in a neighborhood of any $x\in {\left({\bigcup}_{z}{\stackrel{~}{S}}_{z}\right)}^{c}$ we may write
$$\mathcal{N}(y)=\sum _{i=1}^{{n}_{\mathrm{in}}}{y}_{i}\sum _{\begin{array}{c}\text{paths}\gamma :i\to \text{out}\\ \gamma \subset {Z}_{x}^{+}\end{array}}\prod _{j=1}^{d}{q}_{\gamma}^{(j)}(y){w}_{\gamma}^{(j)}+\mathrm{constant}.$$  (22) 
But, again by (20), for any fixed $x$, all $y$ in a neighborhood of $x$ and each $z\in {Z}_{x}^{+},$ we have $z\in {Z}_{y}^{+}$ as well. Thus, in particular,
$$z(x){b}_{z}\in ({\xi}_{i},{\xi}_{i+1})\mathit{\hspace{1em}}\Rightarrow \mathit{\hspace{1em}}z(y){b}_{z}\in ({\xi}_{i},{\xi}_{i+1}).$$ 
Thus, for $y$ sufficiently close to $x,$ we have for every path in the sum (22) that
$${q}_{\gamma}^{(j)}(y)={q}_{\gamma}^{(j)}(x).$$ 
Therefore, the partial derivatives $(\partial \mathcal{N}/\partial {y}_{i})(y)$ are independent of $y$ in a neighborhood of $x$ and hence continuous at $x$. This proves (19). Let us now prove the reverse inclusion:
$$\bigcup _{z}{\stackrel{~}{S}}_{z}\subseteq {\mathcal{B}}_{\mathcal{N}}$$  (23) 
Note that, with probability $1,$ we have
$${\mathrm{vol}}_{{n}_{\mathrm{in}1}}({S}_{{z}_{1}}\cap {S}_{{z}_{2}})=0$$ 
for any pair of distinct neurons ${z}_{1},{z}_{2}.$ Note also that since $x\mapsto \mathcal{N}(x)$ is continuous and piecewise linear, the set ${\mathcal{B}}_{\mathcal{N}}$ is closed. Thus, it is enough to show the slightly weaker inclusion
$$\bigcup _{z}\left({\stackrel{~}{S}}_{z}\backslash \bigcup _{\widehat{z}\ne z}{S}_{\widehat{z}}\right)\subseteq {\mathcal{B}}_{\mathcal{N}}$$  (24) 
since the closure of ${\stackrel{~}{S}}_{z}\backslash {\bigcup}_{\widehat{z}\ne z}{S}_{\widehat{z}}$ equals ${\stackrel{~}{S}}_{z}.$ Fix a neuron $z$ and suppose $x\in {\stackrel{~}{S}}_{z}\backslash {\bigcup}_{\widehat{z}\ne z}{S}_{\widehat{z}}$. By definition, we have that for every neuron $\widehat{z}\ne z,$ either
$$\widehat{z}\in {Z}_{x}^{+}\mathit{\hspace{1em}}\text{or}\mathit{\hspace{1em}}\widehat{z}\in {Z}_{x}^{}.$$ 
This has two consequences. First, by (20), the map $y\mapsto z(y)$ is linear in a neighborhood of $x.$ Second, in a neighborhood of $x,$ the set ${\stackrel{~}{S}}_{z}$ coincides with ${S}_{z}$. Hence, combining these facts, near $x$ the set ${\stackrel{~}{S}}_{z}$ coincides with the hyperplane
$$\{xz(x){b}_{z}={\xi}_{i}\},\text{for some}i.$$  (25) 
We may take two sequences of inputs ${y}_{n}^{+},{y}_{n}^{}$ on opposite sides of this hyperplane so that
$$\underset{n\to \mathrm{\infty}}{lim}{y}_{n}^{+}=\underset{n\to \mathrm{\infty}}{lim}{y}_{n}^{}=x$$ 
and
$${\varphi}^{\prime}(z({y}_{n}^{+}){b}_{z})={q}_{i},{\varphi}^{\prime}(z({y}_{n}^{+}){b}_{z})={q}_{i1},\forall n,$$ 
where the index $i$ the same as the one that defines the hyperplane (25). Further, since ${\mathcal{B}}_{\mathcal{N}}$ has codimension $1$ (it is contained in the piecewise linear codimension $1$ set ${\bigcup}_{z}{S}_{z}$, for example), we may also assume that ${y}_{n}^{+},{y}_{n}^{}\notin {\mathcal{B}}_{\mathcal{N}}.$ Consider any path $\gamma $ from the input to the output of the computational graph of $\mathcal{N}$ passing through $z$ (so that $z={z}_{\gamma}^{(j)}\in \gamma $). By construction, for every $n$, we have
$${q}_{\gamma}^{(j)}({y}_{n}^{+})\ne {q}_{\gamma}^{(j)}({y}_{n}^{}),$$ 
and hence, after passing to a subsequence, we may assume that the symmetric difference
$${Z}_{{y}_{n}^{+}}^{+}\mathrm{\Delta}{Z}_{{y}_{n}^{}}^{+}\ne \mathrm{\varnothing}$$  (26) 
of the paths that contribute to the representation (21) for ${y}_{n}^{+},{y}_{n}^{}$ is fixed and nonempty (the latter since it always contains $z$). For any $y\notin {\mathcal{B}}_{\mathcal{N}},$ we may write, for each $i=1,\mathrm{\dots},{n}_{\mathrm{in}}$
$$\frac{\partial \mathcal{N}}{\partial {y}_{i}}(y)=\sum _{\begin{array}{c}\mathrm{paths}\gamma :i\to \mathrm{out}\\ \gamma \subset {Z}_{y}^{+}\end{array}}\prod _{j=1}^{d}{q}_{\gamma}^{(j)}(y){w}_{\gamma}^{(j)}.$$  (27) 
Substituting into this expression $y={y}_{n}^{\pm}$, we find that there exists a nonempty collection $\mathrm{\Gamma}$ of paths from the input to the output of $\mathcal{N}$ so that
$$\frac{\partial \mathcal{N}}{\partial {y}_{i}}({y}_{n}^{+})\frac{\partial \mathcal{N}}{\partial {y}_{i}}({y}_{n}^{})=\sum _{\gamma \in \mathrm{\Gamma}}{a}_{j}\prod _{j=1}^{d}{c}_{\gamma}^{(j)}{w}_{\gamma}^{(j)}$$ 
where
$${a}_{j}\in \{1,1\},{c}_{\gamma}^{(j)}\in \{{q}_{0},\mathrm{\dots},{q}_{T}\}.$$ 
Note that the expression above is a polynomial in the weights of $\mathcal{N}$. Note also that, by construction, this polynomial is not identically zero due to the condition (26). There are only finitely many such polynomials since both ${a}_{j}$ and ${c}_{\gamma}^{(j)}$ range over a finite alphabet. For each such nonzero polynomial, the set of weights at which it vanishes has codimension $1$. Hence, with probability $1,$ the difference $\frac{\partial \mathcal{N}}{\partial {y}_{i}}({y}_{n}^{+})\frac{\partial \mathcal{N}}{\partial {y}_{i}}({y}_{n}^{})$ is nonzero. This shows that the partial derivatives $\frac{\partial \mathcal{N}}{\partial {y}_{i}}$ are not continuous at $x$ and hence that $x\in {\mathcal{B}}_{\mathcal{N}}.$ $\mathrm{\square}$
C.2 Proof of Proposition 10
Fix distinct neurons ${z}_{1},\mathrm{\dots},{z}_{k}$ and suppose $x\in {\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}$ but not in ${\stackrel{~}{S}}_{z}$ for any $z\ne {z}_{1},\mathrm{\dots},{z}_{k}.$ After relabeling, we may assume that they are ordered by layer index:
$$\mathrm{\ell}({z}_{1})\le \mathrm{\cdots}\le \mathrm{\ell}({z}_{k}).$$ 
Since $x\in \mathcal{O}$, we also have that $x\notin {S}_{z}$ for any $z\ne {z}_{1},\mathrm{\dots},{z}_{k}.$ Thus, there exists a neighborhood $U$ of $x$ so ${S}_{z}\cap U=\mathrm{\varnothing}$ for every $z\ne {z}_{1},\mathrm{\dots},{z}_{k}.$ Thus, there exists a neighborhood of $x$ on which $y\mapsto {z}_{1}(y)$ is linear.
Hence, as explained near (25) above, ${\stackrel{~}{S}}_{{z}_{1}}$ is a hyperplane near $x.$ We now restrict our inputs to this hyperplane and repeat this reasoning to see that, near $x,$ the set ${\stackrel{~}{S}}_{{z}_{1},{z}_{2}}$ is a hyperplane inside ${\stackrel{~}{S}}_{{z}_{1}}$ and hence, near $x$, is the intersection of two hyperplanes in ${\mathbb{R}}^{{n}_{\mathrm{in}}}$. Continuing in this way shows that in a neighborhood of $x,$ the set ${\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}$ is equal to the intersection of $k$ hyperplanes in ${\mathbb{R}}^{{n}_{\mathrm{in}}}.$ Thus, ${\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\backslash {\left({\bigcup}_{z\ne {z}_{1},\mathrm{\dots},{z}_{k}}{\stackrel{~}{S}}_{z}\right)}^{c}$ is precisely the intersection of $k$ hyperplanes in a neighborhood of each of its points. $\mathrm{\square}$
C.3 Proof of Proposition 11
Let ${z}_{1},\mathrm{\dots},{z}_{k}$ be distinct neurons in $\mathcal{N},$ and fix a compact set $K\subset {\mathbb{R}}^{{n}_{\mathrm{in}}}$. We seek to compute the mean of ${\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\cap K\right)$, which we may rewrite as
${\int}_{{S}_{{z}_{1},\mathrm{\dots},{z}_{k}}\cap K}}{\mathrm{\U0001d7cf}}_{\left\{\begin{array}{c}{z}_{j}\text{is good at}x\\ j=1,\mathrm{\dots},k\end{array}\right\}}{\mathrm{dvol}}_{{n}_{\mathrm{in}}k}(x)$  (28)  
$={\displaystyle \sum _{{i}_{1},\mathrm{\dots},{i}_{k}=1}^{T}}{\displaystyle {\int}_{{S}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}\cap K}}{\mathrm{\U0001d7cf}}_{\left\{\begin{array}{c}{z}_{j}\text{is good at}x\\ j=1,\mathrm{\dots},k\end{array}\right\}}{\mathrm{dvol}}_{{n}_{\mathrm{in}}k}(x),$ 
where we’ve set
$${S}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}=\{x{z}_{j}(x){b}_{{z}_{j}}={\xi}_{{i}_{j}},j=1,\mathrm{\dots},k\}.$$ 
Note that the map $x\mapsto ({z}_{1}(x),\mathrm{\dots},{z}_{k}(x))$ is Lipschitz, and recall the coarea formula, which says that if $\psi \in {L}^{1}({\mathbb{R}}^{n})$ and $g:{\mathbb{R}}^{n}\to {\mathbb{R}}^{m}$ with $m\le n$ is Lipschitz, then
$${\int}_{{\mathbb{R}}^{m}}{\int}_{{g}^{1}(t)}\psi (x){\mathrm{dvol}}_{nm}(x)\mathit{d}t$$  (29) 
equals
$${\int}_{{\mathbb{R}}^{n}}\psi (x)\parallel Jg(x)\parallel {\mathrm{dvol}}_{n}(x),$$  (30) 
where $Jg$ is the $m\times n$ Jacobian of $g$ and
$$\parallel Jg(x)\parallel =det{\left((Jg(x)){(Jg(x))}^{T}\right)}^{1/2}.$$ 
We assumed that the biases ${b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{j}}$ have a joint conditional density
$${\rho}_{{\mathbf{b}}_{\mathbf{z}}}={\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}$$ 
given all other weights and biases. The mean of the term in (28) corresponding to a fixed $\xi =({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})$ over the conditional distribution of ${b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{j}}$ is therefore
$${\int}_{{\mathbb{R}}^{k}}\mathit{d}\mathbf{b}{\rho}_{{\mathbf{b}}_{\mathbf{z}}}(\mathbf{b}){\int}_{\{\mathbf{z}\mathbf{b}=\xi \}\cap K}{\mathrm{\U0001d7cf}}_{\left\{\begin{array}{c}{z}_{j}\text{is good at}x\\ j=1,\mathrm{\dots},k\end{array}\right\}}{\mathrm{dvol}}_{{n}_{\mathrm{in}}k}(x),$$ 
where we’ve abbreviated $\mathbf{b}=({b}_{1},\mathrm{\dots},{b}_{k})$ as well as $\mathbf{z}(x)=({z}_{1}(x),\mathrm{\dots},{z}_{k}(x))$. This can rewritten as
$${\int}_{{\mathbb{R}}^{k}}\mathit{d}\mathbf{b}{\int}_{\{\mathbf{z}=\mathbf{b}\}\cap K}{\rho}_{{\mathbf{b}}_{\mathbf{z}}}(\mathbf{z}(x)\xi ){\mathrm{\U0001d7cf}}_{\left\{\begin{array}{c}{z}_{j}\text{is good at}x\\ j=1,\mathrm{\dots},k\end{array}\right\}}{\mathrm{dvol}}_{{n}_{0}k}(x).$$ 
Thus, applying the coarea formula (29), (30) shows that the average of (28) over the conditional distribution of ${b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{j}}$ is precisely
$${\int}_{K}{Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\mathit{d}x.$$ 
Taking the average over the remaining weighs and biases, we may commute the expectation $\mathbb{E}[\cdot ]$ with the $dx$ integral since the integrand is nonnegative. This completes the proof of Proposition 11. $\mathrm{\square}$
Appendix D Proof of Corollary 7
We begin by proving the upper bound in (15). By Theorem 3, $\mathbb{E}\left[\mathrm{vol}\left({\mathcal{B}}_{\mathcal{N},k}\cap K\right)\right]$ equals
$$\sum _{\begin{array}{c}\mathrm{distinct}\mathrm{neurons}\end{array}{z}_{1},\mathrm{\dots},{z}_{k}}\sum _{{i}_{1},\mathrm{\dots},{i}_{k}=1}^{T}{\int}_{K}\mathbb{E}\left[{Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}(x)\right](x)\mathit{d}x,$$ 
where, as in (13), ${Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}^{({\xi}_{{i}_{1}},\mathrm{\dots},{\xi}_{{i}_{k}})}(x)$ is
$$\parallel {J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\parallel {\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({z}_{1}(x){\xi}_{{i}_{1}},\mathrm{\dots},{z}_{k}(z){\xi}_{{i}_{k}})$$ 
times the indicator function of the even that ${z}_{j}$ is good at $x$ for every $j.$ When the weights and biases of $\mathcal{N}$ are independent, we may write ${\rho}_{{b}_{{z}_{1}},\mathrm{\dots},{b}_{{z}_{k}}}({b}_{1},\mathrm{\dots},{b}_{k})$ as
$$\prod _{j=1}^{k}{\rho}_{{b}_{{z}_{j}}}({b}_{j})\le {\left(\underset{\mathrm{neurons}z}{sup}\underset{b\in \mathbb{R}}{sup}{\rho}_{{b}_{z}}(b)\right)}^{k}={C}_{\mathrm{bias}}^{k}.$$ 
Hence,
$${Y}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\le {C}_{\mathrm{bias}}^{k}{\left(det\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}\right)\right)}^{1/2}.$$ 
Note that
$${J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}=\mathrm{Gram}(\nabla {z}_{1}(x),\mathrm{\dots},\nabla {z}_{k}(x)),$$ 
where for any ${v}_{i}\in {\mathbb{R}}^{n}$
$$\mathrm{Gram}{({v}_{1},\mathrm{\dots},{v}_{k})}_{i,j}=\u27e8{v}_{i},{v}_{j}\u27e9$$ 
is the associated Gram matrix. The Gram identity says that $det{\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}\right)}^{1/2}$ equals
$$\parallel \nabla {z}_{1}(x)\wedge \mathrm{\cdots}\wedge \nabla {z}_{k}(x)\parallel ,$$ 
which is the the $k$dimensional volume of the parallelopiped in ${\mathbb{R}}^{{n}_{\mathrm{in}}}$ spanned by $\{\nabla {z}_{j}(x),j=1,\mathrm{\dots},k\}.$ We thus have
$$det{\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x){\left({J}_{{z}_{1},\mathrm{\dots},{z}_{k}}(x)\right)}^{T}\right)}^{1/2}\le \prod _{j=1}^{k}\parallel \nabla {z}_{j}(x)\parallel .$$ 
The estimate (14) proves the upper bound (15). For the special case of $\varphi =\mathrm{ReLU}$ we use the AMGM inequality and Jensen’s inequality to write
$\mathbb{E}\left[{\displaystyle \prod _{j=1}^{k}}\parallel \nabla {z}_{j}(x)\parallel \right]$  $\le \mathbb{E}\left[{\left({\displaystyle \frac{1}{k}}{\displaystyle \sum _{j=1}^{k}}\parallel \nabla {z}_{j}(x)\parallel \right)}^{k}\right]$  
$\le {\displaystyle \frac{1}{k}}{\displaystyle \sum _{j=1}^{k}}\mathbb{E}\left[{\parallel \nabla {z}_{j}\parallel}^{k}\right].$ 
Therefore, by Theorem 1 of Hanin & Nica (2018), there exist ${C}_{1},{C}_{2}>0$ so that
$$\mathbb{E}\left[\prod _{j=1}^{k}\parallel \nabla {z}_{j}(x)\parallel \right]\le {\left({C}_{1}{e}^{{C}_{2}{\sum}_{j=1}^{d}\frac{1}{{n}_{j}}}\right)}^{k}.$$ 
This completes the proof of the upper bound in (15). To prove the power bound, lower bound in (15) we must argue in a different way. Namely, we will induct on $k$ and use the following facts to prove the base case $k=1$:

1.
At initialization, for each fixed input $x,$ the random variables $\{{\mathrm{\U0001d7cf}}_{\{z(x)>{b}_{z}\}}\}$ are independent Bernoulli random variables with parameter $1/2.$ This fact is proved in Proposition 2 of Hanin & Nica (2018). In particular, the event $\{z\text{is good at}x\}$, which occurs when there exists a layer $j\in \mathrm{\ell}(z)+1,\mathrm{\dots},d$ in which $z(x)\le {b}_{z}$ for every neuron, is independent of $\{z(x),{b}_{z}\}$ and satisfies
$$\mathbb{P}\left(z\text{is good at}x\right)\ge 1\sum _{j=1}^{d}{2}^{{n}_{j}}.$$ (31) 
2.
At initialization, for each fixed input $x$, we have
$$\frac{1}{2}\mathbb{E}\left[z{(x)}^{2}\right]=\frac{{\parallel x\parallel}^{2}}{{n}_{\mathrm{in}}}+\sum _{j=1}^{\mathrm{\ell}(z)}{\sigma}_{{b}_{j}}^{2},$$ (32) where ${\sigma}_{{b}_{j}}^{2}:=\mathrm{Var}[\mathrm{biases}\mathrm{at}\mathrm{layer}j]$. This is Equation (11) in the proof of Theorem 5 from Hanin & Rolnick (2018).

3.
At initialization, for every neuron $z$ and each input $x,$ we have
$$\mathbb{E}\left[{\parallel \nabla z(x)\parallel}^{2}\right]=2.$$ (33) This follows easily from Theorem 1 of Hanin (2018).

4.
At initialization, for each $1\le j\le {n}_{\mathrm{in}}$ and every $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}$
$$\mathbb{E}\left[\mathrm{log}\left({n}_{\mathrm{in}}{\left(\frac{\partial z}{\partial {x}_{j}}(x)\right)}^{2}\right)\right]=\frac{5}{2}\sum _{j=1}^{\mathrm{\ell}(z)}\frac{1}{{n}_{j}}$$ (34) plus $O\left({\sum}_{j=1}^{\mathrm{\ell}(z)}\frac{1}{{n}_{j}^{2}}\right)$, where ${n}_{j}$ is the width of the ${j}^{\text{th}}$ hidden layer and the implied constant depends only on the ${4}^{\text{th}}$ moment of the measure $\mu $ according to which weights are distributed. This estimate follows immediately by combining Corollary 26 and Proposition 28 in Hanin & Nica (2018).
We begin by proving the lower bound in (15) when $k=1.$ We use (31) to see that $\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}1}\left({\mathcal{B}}_{\mathcal{N}}\cap K\right)\right]$ is bounded below by
$$\left(1\sum _{j=1}^{d}{2}^{{n}_{j}}\right)\sum _{\mathrm{neurons}z}{\int}_{K}\mathbb{E}\left[\parallel \nabla z(x)\parallel {\rho}_{{b}_{z}}(z(x))\right]\mathit{d}x.$$ 
Next, we bound the integrand. Fix $x\in {\mathbb{R}}^{{n}_{\mathrm{in}}}$ and a parameter $\eta >0$ to be chosen later. The integrand $\mathbb{E}\left[\parallel \nabla z(x)\parallel {\rho}_{{b}_{z}}(z(x))\right]$ is bounded below by
$\mathbb{E}\left[\parallel \nabla z(x)\parallel {\rho}_{{b}_{z}}(z(x)){\mathrm{\U0001d7cf}}_{\{\leftz(x)\right\}\le \eta}\right]$  
$\mathrm{}\ge \left[\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b)\right]\mathbb{E}\left[\parallel \nabla z(x)\parallel {\mathrm{\U0001d7cf}}_{\{z(x)\le \eta \}}\right],$ 
which is bounded below by
$$\left[\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b)\right]\left[\mathbb{E}\left[\parallel \nabla z(x)\parallel \right]\mathbb{E}\left[\parallel \nabla z(x)\parallel {\mathrm{\U0001d7cf}}_{\{\leftz(x)\right\}>\eta}\right]\right].$$ 
Using CauchySchwarz, the term $\mathbb{E}\left[\parallel \nabla z(x)\parallel {\mathrm{\U0001d7cf}}_{\{\leftz(x)\right\}>\eta}\right]$ is bounded above by
$${\left(\mathbb{E}{\left[\parallel \nabla z(x)\parallel \right]}^{2}\mathbb{P}\left(\rightz(x)>\eta )\right)}^{1/2},$$ 
which using (33) and (32) together with Markov’s inequality, is bounded above by
$$\frac{2}{{\eta}^{1/2}}{\left(\frac{{\parallel x\parallel}^{2}}{{n}_{\mathrm{in}}}+\sum _{j=1}^{\mathrm{\ell}(z)}{\sigma}_{{b}_{j}}^{2}\right)}^{1/2}.$$ 
Next, using Jensen’s inequality twice, we write
$\mathrm{log}\mathbb{E}\left[\parallel \nabla z(x)\parallel \right]$  $\mathrm{}\ge {\displaystyle \frac{1}{2}}\mathbb{E}\left[\mathrm{log}\left({\parallel \nabla z(x)\parallel}^{2}\right)\right]$  
$\mathrm{}={\displaystyle \frac{1}{2}}\mathbb{E}\left[\mathrm{log}\left({\displaystyle \sum _{j=1}^{{n}_{\mathrm{in}}}}{\left({\displaystyle \frac{\partial z}{\partial {x}_{j}}}(x)\right)}^{2}\right)\right]$  
$\mathrm{}\ge {\displaystyle \frac{1}{2}}\mathbb{E}\left[\mathrm{log}{\left({n}_{\mathrm{in}}^{1/2}{\displaystyle \frac{\partial z}{\partial {x}_{j}}}(x)\right)}^{2}\right]$  
$\mathrm{}={\displaystyle \frac{5}{4}}{\displaystyle \sum _{j=1}^{\mathrm{\ell}(z)}}{\displaystyle \frac{1}{{n}_{j}}}+O\left({\displaystyle \sum _{j=1}^{\mathrm{\ell}(z)}}{\displaystyle \frac{1}{{n}_{j}^{2}}}\right),$ 
where in the last inequality we applied (34). Putting this all together, we find that exists $c>0$ so that
$$\mathbb{E}\left[\parallel \nabla z(x)\parallel {\rho}_{{b}_{z}}(z(x))\right]\ge c\left[\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b)\right],$$ 
where
$$\eta \ge 4\left(\frac{{\parallel x\parallel}^{2}}{{n}_{\mathrm{in}}}+\sum _{j=1}^{d}{\sigma}_{{b}_{j}}^{2}\right){e}^{\frac{5}{4}{\sum}_{j=1}^{d}\frac{1}{{n}_{j}}+O\left({\sum}_{j=1}^{\mathrm{\ell}(z)}\frac{1}{{n}_{j}^{2}}\right)}.$$ 
In particular, we may take
$$\eta =\left(\frac{{sup}_{x\in K}{\parallel x\parallel}^{2}}{{n}_{\mathrm{in}}}+\sum _{j=1}^{d}{\sigma}_{{b}_{j}}^{2}\right){e}^{C{\sum}_{j=1}^{d}\frac{1}{{n}_{j}}}$$ 
for $C$ sufficiently large. This completes the proof of the lower bound in (15) when $k=1$. To complete the proof of Corollary 7, suppose we have proved the lower bound in (15) for all $\mathrm{ReLU}$ networks $\mathcal{N}$ and all collections of $k1$ distinct neurons. We may assume after relabeling that the neurons ${z}_{1},\mathrm{\dots},{z}_{k}$ are ordered by layer index:
$$\mathrm{\ell}({z}_{1})\le \mathrm{\cdots}\le \mathrm{\ell}({z}_{k}).$$ 
With probability $1,$ the set ${S}_{{z}_{1}}\subset {\mathbb{R}}^{{n}_{\mathrm{in}}}$ is piecewise linear, codimension $1$ with finitely many pieces, which we denote by ${P}_{\alpha}$. We may therefore rewrite ${\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\cap K\right)$ as
$$\sum _{\alpha}{\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{2},\mathrm{\dots},{z}_{k}}\cap {P}_{\alpha}\cap K\right).$$ 
We now define a new neural network ${\mathcal{N}}_{\alpha}$, obtained by restricting $\mathcal{N}$ to ${P}_{\alpha}.$ The input dimension for ${\mathcal{N}}_{\alpha}$ equals ${n}_{\mathrm{in}}1,$ and the weights and biases of ${\mathcal{N}}_{\alpha}$ satisfy all the assumptions of Corollary 7. We can now apply our inductive hypothesis to the $k1$ neurons ${z}_{2},\mathrm{\dots},{z}_{k}$ in ${\mathcal{N}}_{\alpha}$ and to the set $K\cap {P}_{\alpha}.$ This gives
$\mathbb{E}\left[{\displaystyle \sum _{\alpha}}{\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{2},\mathrm{\dots},{z}_{k}}\cap {P}_{\alpha}\cap K\right)\right]$  
$\mathrm{\hspace{1em}}\ge {\left(\underset{z}{inf}\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b)\right)}^{k1}\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}1}\left({P}_{\alpha}\cap K\right)\right].$ 
Summing this lower bound over $\alpha $ yields
$\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}k}\left({\stackrel{~}{S}}_{{z}_{1},\mathrm{\dots},{z}_{k}}\cap K\right)\right]$  
$\mathrm{\hspace{1em}}\ge {\left(\underset{z}{inf}\underset{\leftb\right\le \eta}{inf}{\rho}_{{b}_{z}}(b)\right)}^{k1}\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}1}\left({\stackrel{~}{S}}_{{z}_{1}}\cap K\right)\right].$ 
Applying the inductive hypothesis once more completes the proof. $\mathrm{\square}$
Appendix E Proof of Corollary 8
We will need the following observation.
Lemma 12.
Fix a positive integer $n\mathrm{\ge}\mathrm{1}$, and let $S\mathrm{\subseteq}{\mathrm{R}}^{n}$ be a compact continuous piecewise linear submanifold with finitely many pieces. Define ${S}_{\mathrm{0}}\mathrm{=}\mathrm{\varnothing}$ and let ${S}_{k}$ be the union of the interiors of all $k$dimensional pieces of $S\mathrm{\backslash}\mathrm{(}{S}_{\mathrm{0}}\mathrm{\cup}\mathrm{\cdots}\mathrm{\cup}{S}_{k\mathrm{}\mathrm{1}}\mathrm{)}$. Denote by ${T}_{\epsilon}\mathit{}\mathrm{(}X\mathrm{)}$ the $\epsilon \mathrm{}$tubular neighborhood of any $X\mathrm{\subset}{\mathrm{R}}^{n}\mathrm{.}$ We have
$${\mathrm{vol}}_{n}\left({T}_{\epsilon}(S)\right)\le \sum _{k=0}^{n}{\omega}_{nk}{\epsilon}^{nk}{\mathrm{vol}}_{k}\left({S}_{k}\right),$$ 
where ${\omega}_{d}\mathrm{:=}\mathit{\text{volume of ball of radius}}\mathit{}\mathrm{1}\mathit{}\mathit{\text{in}}\mathit{}{\mathrm{R}}^{d}\mathrm{.}$
Proof.
Define $d$ to be the maximal dimension of the linear pieces in $S.$ Let $x\in {T}_{\epsilon}(S).$ Suppose $x\notin {T}_{\epsilon}({S}_{k})$ for all $k=0,\mathrm{\dots},d1.$ Then the intersection of the ball of radius $\epsilon $ around $s$ with $S$ is a ball inside ${S}_{d}\cong U\subset {\mathbb{R}}^{d}$. Using the convexity of this ball, there exists a point $y$ in ${S}_{d}$ so that the vector $xy$ is parallel to the normal vector to ${S}_{d}$ at $y$. Hence, $x$ belong to the normal $\epsilon $ball bundle ${B}_{\epsilon}({N}^{*}({S}_{d}))$ (i.e. the union of the fiberwise $\epsilon $balls in the normal bundle to ${S}_{d}$). Therefore, we have
$${\mathrm{vol}}_{n}\left({T}_{\epsilon}(S)\right)\le {\mathrm{vol}}_{n}({B}_{\epsilon}({N}^{*}({S}_{d})))+{\mathrm{vol}}_{n}\left({T}_{\epsilon}({S}_{\le d1})\right),$$ 
where we abbreviated ${S}_{\le d1}:=\overline{{\bigcup}_{k=0}^{d1}{S}_{k}}.$ Using that
${\mathrm{vol}}_{n}({B}_{\epsilon}({N}^{*}({S}_{d})))$  $={\mathrm{vol}}_{d}({S}_{d}){\mathrm{vol}}_{nd}({B}_{\epsilon}({\mathbb{R}}^{nd}))$  
$={\mathrm{vol}}_{d}({S}_{d}){\epsilon}^{nd}{\omega}_{nd}$ 
and repeating this argument $d1$ times completes the proof. ∎
We are now ready to prove Corollary 2. Let $x\in K={[0,1]}^{{n}_{\mathrm{in}}}$ be uniformly chosen. Then, for any $\epsilon >0$, using Markov’s inequality and Lemma 12, we have
$\mathbb{E}\left[\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})\right]$  
$\mathrm{\hspace{1em}}\ge \epsilon \mathbb{P}(\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})>\epsilon )$  
$\mathrm{\hspace{1em}}=\epsilon (1\mathbb{P}(\mathrm{distance}(x,{\mathcal{B}}_{\mathcal{N}})\le \epsilon ))$  
$\mathrm{\hspace{1em}}=\epsilon \left(1\mathbb{E}\left[{\mathrm{vol}}_{{n}_{\mathrm{in}}}\left({T}_{\epsilon}\left({\mathcal{B}}_{\mathcal{N}}\right)\right)\right]\right)$  
$\mathrm{\hspace{1em}}\ge \epsilon \left(1{\displaystyle \sum _{k=1}^{{n}_{\mathrm{in}}}}{\omega}_{{n}_{\mathrm{in}}k}{\epsilon}^{{n}_{ink}}\mathbb{E}\left[{\mathrm{vol}}_{{n}_{ink}}({\mathcal{B}}_{\mathcal{N},k})\right]\right)$  
$\mathrm{\hspace{1em}}\ge \epsilon \left(1{\displaystyle \sum _{k=1}^{{n}_{\mathrm{in}}}}{({C}_{\mathrm{grad}}{C}_{\mathrm{bias}}\epsilon \mathrm{\#}\{\mathrm{neurons}\})}^{k}\right)$  
$\mathrm{\hspace{1em}}\ge \epsilon \left(1{C}^{\prime}{C}_{\mathrm{grad}}{C}_{\mathrm{bias}}\epsilon \mathrm{\#}\{\mathrm{neurons}\}\right)$ 
for some ${C}^{\prime}>0.$ Taking $\epsilon $ to be a small constant times $1/({C}_{\mathrm{grad}}\mathrm{\#}\{\mathrm{neurons}\})$ completes the proof. $\mathrm{\square}$