Complexity of Linear Regions in Deep Networks

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 (Shalev-Shwartz 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 $\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 1-4). Figure 2 shows how the complexity of these pieces, which we refer to as linear regions, changes in a deep ReLU net with two-dimensional 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.

Theorem 3 also allows us to conclude that, at initialization, the average distance from a sample point to the nearest region boundary is bounded below by a constant times the reciprocal of the number of neurons (see Corollary 5).

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 §C-D.

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 feed-forward networks with arbitrary connectivity, though we do not go into details in this work, for the sake of clarity of exposition.

Consider the simple case of a $\operatorname{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:

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 non-trivial lower bound for the number of linear regions:

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 $\operatorname{ReLU}$ but note that it holds for any piecewise linear, continuous activation function (see Theorems 3 and 6).

Let $\mathcal{N}$ be a network with piecewise linear activation with input and output dimensions of $\mathcal{N}$ both equal $1$. Suppose the weights and biases are randomly initialized so that for each neuron $z$, its pre-activation $z(x)$ has bounded mean gradient

where $T$ is the number of breakpoints in the non-linearity of $\mathcal{N}$ (for ReLU nets, $T=1$). The same result holds when computing the number of linear regions along any fixed $1$-dimensional curve in a high-dimensional input space.

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 pre-activation $z(x)$ of a neuron $z$ satisfies $\left|z^{\prime}(x)\right|=\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 non-degenerate distribution of weights and biases and with any input dimension. If $\left\lVert\nabla z(x)\right\rVert$ and the bias distribution $\rho_{b_{z}}$ are well-behaved, 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 5-6 show experiments that give empirical verification of this heuristic.

2 Higher-Dimensional Regions

For networks with input dimension exceeding $1,$ there are several ways to generalize counting linear regions. A unit-matching heuristic applied to Theorem 1 suggests

Experiments

We empirically verified our theorems and further examined how linear regions of a network change during training. All experiments below were performed with fully-connected networks, initialized with He normal weights (i.i.d. with variance $2/\text{fan-in}$) 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 $95-98\%$.

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:

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

Throughout training, the number of regions does not deviate significantly from the number of neurons in the network, staying within a small constant of the value at initialization, in keeping with our intuitive understanding of Theorem 3 described informally around Theorem 1 above.

The number of regions actually decreases during the initial part of training, then increases again. We explore this behavior further in other experiments below.

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.

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 $\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 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 (, $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.

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 Shalev-Shwartz 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).

Formal Statement of Results

More precisely, we set $\mathcal{B}_{\mathcal{N},0}:=\emptyset$ 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\cdots\cup\mathcal{B}_{\mathcal{N},k-1}\}$ so that in a neighborhood of $x$ the set $\mathcal{B}_{\mathcal{N}}\backslash\{\mathcal{B}_{\mathcal{N},0}\cup\cdots\cup\mathcal{B}_{\mathcal{N},k-1}\}$ coincides with a co-dimension $k$ hyperplane.

Theorem 3 holds under the following assumption on the distribution of weights and biases:

of $\mathcal{B}_{\mathcal{N},k}$ inside $K$ is, in the notation (6),

the function $\rho_{b_{z_{1}},\ldots,b_{z_{k}}}$ is the density of the joint distribution of the biases $b_{z_{1}},\ldots,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 $\mathcal{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 pre-activations $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.

where $C>0$ depends only on $\mu$ but not on the architecture of $\mathcal{N}$ and $n_{j}$ is the width of the $j^{th}$ hidden layer. Moreover, we also have similar lower bounds

with $C^{\prime}>0$ depending only on the distribution $\mu$ of the weights in $\mathcal{N}$.

We prove Corollary 7 in Appendix D. Let us state one final corollary of Theorem 3

We prove Corollary 8 in §E. The basic idea is simple. For every $\epsilon>0,$ we have

with the probability on the right hand side scaling like

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

Appendix A Formal Statement of Results for General Piecewise Linear Activations

The analog of Theorem 3 for general $\phi$ is the following.

and write $\rho_{b_{z_{1}},\ldots,b_{z_{k}}}$ for the density of the joint distribution of the biases $b_{z_{1}},\ldots,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 $\mathcal{N}$ so that each neuron $\widehat{z}$ along this path is open at $x$ (i.e. $\phi^{\prime}(\widehat{z}(x)-b_{\widehat{z}})\neq 0$).

of $\mathcal{B}_{\mathcal{N},k}$ inside $K$ is, in the notation of (6),

where $Y_{z_{1},\ldots,z_{k}}^{(\xi_{i_{1}},\ldots,\xi_{i_{k}})}(x)$ equals

multiplied by the indicator function of the event that $z_{j}$ is good at $x$ for every $j.$

Note that if in the definition (11) of $\phi$ we have that the possible values $\phi^{\prime}(t)\in\{q_{0},\ldots,q_{T}\}$ do not include , then we may ignore the event that $z_{j}$ are good at $x$ in the definition of $Y_{z_{1},\ldots,z_{k}}^{(\xi_{i_{1}},\ldots,\xi_{i_{k}})}.$

where $T$ is the number of breakpoints in the non-linearity $\phi$ of $\mathcal{N}$ (see (11)) and

We prove Corollary 7 in §D and state a final corollary of Theorem 3:

where, as before, $T$ is the number of breakpoints in the non-linearity $\phi$ of $\mathcal{N}$.

We prove Corollary 8 in §E. The basic idea is simple. For every $\epsilon>0,$ we have

with the probability on the right hand side scaling like

Appendix B Outline of Proof of Theorem 6

We remark here that $\mathcal{O}=\emptyset$ if in the non-linearity $\phi$ there are no linear pieces at which the slopes on $\phi$ equals (i.e. $q_{j}\neq 0$ for all $j$ in the definition (11) of $\phi$). If, for example, $\phi$ 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}}.$

Under Assumptions $A1$ and $A2$ of Theorem 3, we have, with probability $1,$

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},\ldots,z_{k}$,

The set $\widetilde{S}_{z_{1},\ldots,z_{k}}$ is, intuitively, the collection of inputs at which $z_{j}(x)-b_{z_{j}}$ switches between linear regions for $\phi$ and at which the output of $\mathcal{N}$ is affected by the post-activations of these neurons. Proposition 9 shows that we may represent $\mathcal{B}_{\mathcal{N}}$ as a disjoint union

We prove Proposition 10 in §C.2. The idea is that each $\widetilde{S}_{z_{1},\ldots,z_{k}}$ is piecewise linear and, with probability $1$, at every point at which exactly the neurons $z_{1},\ldots,z_{k}$ contribute to $\mathcal{B}_{\mathcal{N}}$, its co-dimension is the number of linear conditions needed to define it. Observe that with probability $1$, the bias vector $(b_{z_{1}},\ldots,b_{z_{k+1}})$ for any collection $z_{1},\ldots,z_{k+1}$ of distinct neurons is a regular value for $x\mapsto(z_{1}(x),\ldots,z_{k+1}(x))$. Hence,

Proposition 10 thus implies that, with probability $1,$

The final step in the proof of Theorem 3 is therefore to prove the following result.

where $Y_{z_{1},\ldots,z_{k}}^{(S_{i_{1}},\ldots,S_{i_{k}})}$ 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

that the vector of biases $(b_{z_{j}},\,\,j=1,\ldots,k)$ belongs to the image of $dx$ under map $\left(z_{j}(x)-S_{i_{j}},j=1,\ldots,k\right)$ for some collection of breakpoints $S_{i_{j}}.$ The formal argument uses the co-area formula (see (29) and (30)).

Appendix C Proof of Theorem 3

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 $\phi=\operatorname{ReLU},$ then

We begin by proving that $\mathcal{B}_{\mathcal{N}}\subseteq\bigcup_{z}\widetilde{S}_{z}$ by checking the contrapositive

Fix $x\in\left(\bigcup_{z}\widetilde{S}_{z}\right)^{c}$. Note that $Z_{x}^{\pm}$ are locally constant in the sense that there exists $\varepsilon>0$ so that for all $y$ with $\left\lVert y-x\right\rVert<\varepsilon$, we have

Moreover, observe that if in the definition (11) of $\phi$ none of the slopes $q_{i}$ equal , then $Z_{y}^{-}=\emptyset$ 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:

To each path we may associate a sequence of weights:

For instance, if $\phi=\operatorname{ReLU}$, then

and in general only one term in the definition of $q_{\gamma}^{(j)}(x)$ is non-zero for each $z.$ We may write

Note that if $x\in\left(\bigcup_{z}\widetilde{S}_{z}\right)^{c}$, then for any path $\gamma$ through a neuron $z\in Z_{x}^{0}$, we have

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

Thus, since the summand in (21) vanishes identically if $\gamma\cap Z_{y}^{-}\neq\emptyset$, we find that for $y$ in a neighborhood of any $x\in\left(\bigcup_{z}\widetilde{S}_{z}\right)^{c}$ we may write

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,

Thus, for $y$ sufficiently close to $x,$ we have for every path in the sum (22) that

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:

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

since the closure of \widetilde{S}_{z}\big{\backslash}\bigcup_{\widehat{z}\neq z}S_{\widehat{z}} equals $\widetilde{S}_{z}.$ Fix a neuron $z$ and suppose x\in\widetilde{S}_{z}\big{\backslash}\bigcup_{\widehat{z}\neq z}S_{\widehat{z}}. By definition, we have that for every neuron $\widehat{z}\neq z,$ either

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 $\widetilde{S}_{z}$ coincides with $S_{z}$. Hence, combining these facts, near $x$ the set $\widetilde{S}_{z}$ coincides with the hyperplane

We may take two sequences of inputs $y_{n}^{+},y_{n}^{-}$ on opposite sides of this hyperplane so that

where the index $i$ the same as the one that defines the hyperplane (25). Further, since $\mathcal{B}_{\mathcal{N}}$ has co-dimension $1$ (it is contained in the piecewise linear co-dimension $1$ set $\bigcup_{z}S_{z}$, for example), we may also assume that $y_{n}^{+},y_{n}^{-}\not\in\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

and hence, after passing to a subsequence, we may assume that the symmetric difference

Substituting into this expression $y=y_{n}^{\pm}$, we find that there exists a non-empty collection $\Gamma$ of paths from the input to the output of $\mathcal{N}$ so that

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 non-zero polynomial, the set of weights at which it vanishes has co-dimension $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 non-zero. 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}}.$ $\square$

C.2 Proof of Proposition 10

Fix distinct neurons $z_{1},\ldots,z_{k}$ and suppose $x\in\widetilde{S}_{z_{1},\ldots,z_{k}}$ but not in $\widetilde{S}_{z}$ for any $z\neq z_{1},\ldots,z_{k}.$ After relabeling, we may assume that they are ordered by layer index:

Since $x\in\mathcal{O}$, we also have that $x\not\in S_{z}$ for any $z\neq z_{1},\ldots,z_{k}.$ Thus, there exists a neighborhood $U$ of $x$ so $S_{z}\cap U=\emptyset$ for every $z\neq z_{1},\ldots,z_{k}.$ Thus, there exists a neighborhood of $x$ on which $y\mapsto z_{1}(y)$ is linear.

C.3 Proof of Proposition 11

where $Jg$ is the $m\times n$ Jacobian of $g$ and

We assumed that the biases $b_{z_{1}},\ldots,b_{z_{j}}$ have a joint conditional density

given all other weights and biases. The mean of the term in (28) corresponding to a fixed $\xi=\left(\xi_{i_{1}},\ldots,\xi_{i_{k}}\right)$ over the conditional distribution of $b_{z_{1}},\ldots,b_{z_{j}}$ is therefore

where we’ve abbreviated ${\bf b}=\left(b_{1},\ldots,b_{k}\right)$ as well as ${\bf z}(x)=\left(z_{1}(x),\ldots,z_{k}(x)\right)$. This can rewritten as

Thus, applying the co-area formula (29), (30) shows that the average of (28) over the conditional distribution of $b_{z_{1}},\ldots,b_{z_{j}}$ is precisely

Appendix D Proof of Corollary 7

where, as in (13), $Y_{z_{1},\ldots,z_{k}}^{(\xi_{i_{1}},\ldots,\xi_{i_{k}})}(x)$ is

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}},\ldots,b_{z_{k}}}(b_{1},\ldots,b_{k})$ as

is the associated Gram matrix. The Gram identity says that $\det\left(J_{z_{1},\ldots,z_{k}}(x)\left(J_{z_{1},\ldots,z_{k}}(x)\right)^{T}\right)^{1/2}$ equals

The estimate (14) proves the upper bound (15). For the special case of $\phi=\operatorname{ReLU}$ we use the AM-GM inequality and Jensen’s inequality to write

Therefore, by Theorem 1 of Hanin & Nica (2018), there exist $C_{1},C_{2}>0$ so that

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$:

At initialization, for each fixed input $x$, we have

At initialization, for every neuron $z$ and each input $x,$ we have

This follows easily from Theorem 1 of Hanin (2018).

which using (33) and (32) together with Markov’s inequality, is bounded above by

Next, using Jensen’s inequality twice, we write

where in the last inequality we applied (34). Putting this all together, we find that exists $c>0$ so that

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 $\operatorname{ReLU}$ networks $\mathcal{N}$ and all collections of $k-1$ distinct neurons. We may assume after relabeling that the neurons $z_{1},\ldots,z_{k}$ are ordered by layer index:

Summing this lower bound over $\alpha$ yields

Applying the inductive hypothesis once more completes the proof. $\square$

Appendix E Proof of Corollary 8

where we abbreviated $S_{\leq d-1}:=\overline{\bigcup_{k=0}^{d-1}S_{k}}.$ Using that

and repeating this argument $d-1$ times completes the proof. ∎