Finite Depth and Width Corrections to the Neural Tangent Kernel

Introduction

Modern neural networks typically overparameterized: they have many more parameters than the size of the datasets on which they are trained. That some setting of parameters in such networks can interpolate the data is therefore not surprising. But it is a priori unexpected that not only can such interpolating parameter values can be found by stochastic gradient descent (SGD) on the highly non-convex empirical risk but that the resulting network function not only interpolates but also extrapolates to unseen data. In an overparameterized neural network $\mathcal{N}$ individual parameters can be difficult to interpret, and one way to understand training is to rewrite the SGD updates

of trainable parameters $\theta=\{\theta_{p}\}_{p=1}^{P}$ with a loss $\mathcal{L}$ and learning rate $\lambda$ as kernel gradient descent updates for the values $\mathcal{N}(x)$ of the function computed by the network:

Relation (1) is valid to first order in $\lambda.$ It translates between two ways of thinking about the difficulty of neural network optimization:

The function space view where the loss $\mathcal{L}$, which is a simple function of the network mapping $x\mapsto\mathcal{N}(x)$, is minimized over the manifold $\mathcal{M}_{\mathcal{N}}$ of all functions representable by the architecture of $\mathcal{N}$ using gradient descent with respect to a potentially complicated Riemannian metric $K_{\mathcal{N}}$ on $\mathcal{M}_{\mathcal{N}}.$

Moreover, the joint statistical effects of depth and width on $K_{\mathcal{N}}$ in finite size networks remain unclear, and the purpose of this article is to shed light on the simultaneous effects of depth and width on $K_{\mathcal{N}}$ for finite but large widths $n$ and any depth $d$. Our results apply to fully connected ReLU networks at initialization for which we will show:

In contrast to the regime in which the depth $d$ is fixed but the width $n$ is large, $K_{\mathcal{N}}$ is not approximately deterministic at initialization so long as $d/n$ is bounded away from . Specifically, for a fixed input $x$ the normalized on-diagonal second moment of $K_{\mathcal{N}}$ satisfies

Thus, when $d/n$ is bounded away from , even when both $n,d$ are large, the standard deviation of $K_{\mathcal{N}}(x,x)$ is at least as large as its mean, showing that its distribution at initialization is not close to a delta function. See Theorem 1.

Moreover, when $\mathcal{L}$ is the square loss, the average of the SGD update $\Delta K_{\mathcal{N}}(x,x)$ to $K_{\mathcal{N}}(x,x)$ from a batch of size one containing $x$ satisfies

where $n_{0}$ is the input dimension. Therefore, if $d^{2}/nn_{0}>0,$ the NTK will have the potential to evolve in a data-dependent way. Moreover, if $n_{0}$ is comparable to $n$ and $d/n>0$ then it is possible that this evolution will have a well-defined expansion in $d/n.$ See Theorem 2.

In both statements above, $\simeq$ means is bounded above and below by universal constants. We emphasize that our results hold at finite $d,n$ and the implicit constants in both $\simeq$ and in the error terms $O(d/n^{2})$ are independent of $d,n.$ Moreover, our precise results, stated in §2 below, hold for networks with variable layer widths. We have denoted network width by $n$ only for the sake of exposition. The appropriate generalization of $d/n$ to networks with varying layer widths is the parameter

which in light of the estimates in (1) and (2) plays the role of an inverse temperature.

A number of articles have followed up on the original NTK work . Related in spirit to our results is the article , which uses Feynman diagrams to study finite width corrections to general correlations functions (and in particular the NTK). The most complete results obtained in are for deep linear networks but a number of estimates hold general non-linear networks as well. The results there, like in essentially all previous work, fix the depth $d$ and let the layer widths $n$ tend to infinity. The results here and in , however, do not treat $d$ as a constant, suggesting that the $1/n$ expansions (e.g. in ) can be promoted to $d/n$ expansions. Also, the sum-over-path approach to studying correlation functions in randomly initialized ReLU nets was previously taken up for the foward pass in and for the backward pass in and .

2. Implications and Future Work

Taken together (1) and (2) above (as well as Theorems 1 and 2) show that in fully connected ReLU nets that are both deep and wide the neural tangent kernel $K_{\mathcal{N}}$ is genuinely stochastic and enjoys a non-trivial evolution during training. This suggests that in the overparameterized limit $n,d\rightarrow\infty$ with $d/n\in(0,\infty)$, the kernel $K_{\mathcal{N}}$ may learn data-dependent features. Moreover, our results show that the fluctuations of both $K_{\mathcal{N}}$ and its time derivative are exponential in the inverse temperature $\beta=d/n.$

It would be interesting to obtain an exact description of its statistics at initialization and to describe the law of its trajectory during training. Assuming this trajectory turns out to be data-dependent, our results suggest that the double descent curve that trades off complexity vs. generalization error may display significantly different behaviors depending on the mode of network overparameterization.

However, it is also important to point out that the results in show that, at least for fully connected ReLU nets, gradient-based training is not numerically stable unless $d/n$ is relatively small (but not necessarily zero). Thus, we conjecture that there may exist a “weak feature learning” NTK regime in which network depth and width are both large but $0<d/n\ll 1$. In such a regime, the network will be stable enough to train but flexible enough to learn data-dependent features. In the language of one might say this regime displays weak lazy training in which the model can still be described by a stochastic positive definite kernel whose fluctuations can interact with data.

Finally, it is an interesting question to what extent our results hold for non-linearities other than ReLU and for network architectures other than fully connected (e.g. convolutional and residual). Typical ConvNets, for instance, are significantly wider than they are deep, and we leave it to future work to adapt the techniques from the present article to these more general settings.

Formal Statement of Results

The three assumptions in (4) hold for vitually all standard network initialization schemes. The on-diagonal NTK is

We emphasize that although we have initialized the biases to zero, they are not removed them from the list of trainable parameters. Our first result is the following:

times a multiplicative error $\left(1+O\left(\sum_{i=1}^{d}\frac{1}{n_{i}^{2}}\right)\right)$, where $f\simeq g$ means $f$ is bounded above and below by universal constants times $g.$ In particular, if all the hidden layer widths are equal (i.e. $n_{i}=n$, for $i=1,\ldots,d-1$), we have

This result shows that in the deep and wide double scaling limit

the NTK does not converge to a constant in probability. This is contrast to the wide and shallow regime $n_{i}\rightarrow\infty$ and $d<\infty.$ is fixed.

times a multiplicative error of size $\left(1+O\left(\sum_{i=1}^{d}\frac{1}{n_{i}^{2}}\right)\right)$, where as in Theorem 1, $\beta=\sum_{i=1}^{d}1/n_{i}.$ In particular, if all the hidden layer widths are equal (i.e. $n_{i}=n$, for $i=1,\ldots,d-1$), we find

The remainder of this article is structured as follows. First, in §3 we introduce some notation about paths and edges in the computation graph of $\mathcal{N}$. This notation will be used in the proofs of Theorems 1 and 2, which are outlined in §4 and particularly in §4.1 where give an in-depth but informal explanation of our strategy for computing moments of $K_{\mathcal{N}}$ and its time derivative. Then, §5-§7 give the detailed argument. The computations in §5 explain how to handle the contribution to $K_{\mathcal{N}}$ and $\Delta K_{\mathcal{N}}$ coming only from the weights of the network. They are the most technical and we give them in full detail. Then, the discussion in §6 and §7 show how to adapt the method developed in §5 to treat the contribution of biases and mixed bias-weight terms in $K_{\mathcal{N}},K_{\mathcal{N}}^{2}$ and $\Delta K_{\mathcal{N}}$. Since the arguments are simpler in these cases, we omit some details and focus only on highlighting the salient differences.

Notation

If each edge $e$ in the computational graph of $\mathcal{N}$ is assigned a weight $\widehat{W}_{e}$, then associated to a path $\gamma$ is a collection of weights:

Next, for an edge $e\in[n_{i-1}]\times[n_{i}]$ in the computational graph of $\mathcal{N}$ we will write

for the layer of $e.$ In the course of proving Theorems 1 and 2, it will be useful to associate to every $\Gamma\in\Gamma^{k}(\vec{n})$ an unordered multi-set of edges $E^{\Gamma}.$

to be the unordered multiset of edges in the complete directed bi-paritite graph $K_{n,n^{\prime}}$ oriented from $[n]$ to $[n^{\prime}].$ For every $E\in\Sigma^{k}(n,n^{\prime})$ define its left and right endpoints to be

where $L(E),R(E)$ are unordered multi-sets.

for the set of all possible edge multisets realized by paths in $\Gamma_{Z}^{k}.$ On a number of occasions, we will also write

We will moreover say that for a path $\gamma$ an edge $e=(\alpha,\beta)\in[n_{i-1}]\times[n_{i}]$ in the computational graph of $\mathcal{N}$ belongs to $\gamma$ (written $e\in\gamma$) if

Finally, for an edge $e=(\alpha,\beta)\in[n_{i-1}]\times[n_{i}]$ in the computational graph of $\mathcal{N}$, we set

for the normalized and unnormalized weights on the edge corresponding to $e$ (see (3)).

Overview of Proof of Theorems 1 and 2

and have suppressed the dependence on $x,\mathcal{N}.$ Similarly, we have

and have used that the loss on the batch $\{x\}$ is given by $\mathcal{L}(x)=\frac{1}{2}\left(\mathcal{N}(x)-\mathcal{N}_{*}(x)\right)^{2}$ for some target value $\mathcal{N}_{*}(x).$ To prove Theorem 1 we must estimate the following quantities:

To prove Theorem 2, we must control in addition

We prove Proposition 3 in §5 below. The proof already contains all the ideas necessary to treat the remaining moments. In §6 and §7 we explain how to modify the proof of Proposition 3 to prove the following two Propositions:

up to a multiplicative error of $1+O(d/n^{2}).$ When $d/n$ is small, this expression is bounded above and below by a constant times

Thus, since Propositions 3 and 4 also give

where the weight of a path $\operatorname{wt}(\gamma)$ was defined in (10) and includes both the product of the weights along $\gamma$ and the condition that every neuron in $\gamma$ is open at $x$. The path $\gamma$ begins at some neuron in the input layer of $\mathcal{N}$ and passes through a neuron in every subsequent layer until ending up at the unique neuron in the output layer (see (7)). Being a product over edge weights in a given path, the derivative of $\operatorname{wt}(\gamma)$ with respect to a weight $W_{e}$ on an edge $e$ of the computational graph of $\mathcal{N}$ is:

There is a subtle point here that $\operatorname{wt}(\gamma)$ also involves indicator functions of the events that neurons along $\gamma$ are open at $x.$ However, with probability $1$, the derivative with respect to $W_{e}$ of these indicator functions is identically at $x.$ The details are in Lemma 11.

Obtain an exact formula for the expectation in (18):

Observe that the dependence of $F(\Gamma,e_{1},e_{2})$ on $e_{1},e_{2}$ is only up to a multiplicative constant:

The precise relation is (24). This shows that, up to universal constants,

This is captured precisely by the terms $I_{j},II_{j}$ defined in (27),(28).

Notice that $F_{*}(\Gamma)$ depends only on the un-ordered multiset of edges $E=E^{\Gamma}\in\Sigma_{even}^{4}$ determined by $\Gamma$ (see (14)). We therefore change variables in the sum from the previous step to find

where a loop in $E$ occurs when the four paths interact. More precisely, a loop occurs whenever all four paths pass through the same neuron in some layer (see Figures 1 and 2).

Finally, we use Proposition 10 to obtain for this expectation estimates above and below that match up multiplicative constants.

Proof of Proposition 3

We begin with the well-known formula for the output of a ReLU net $\mathcal{N}$ with biases set to and a linear final layer with one neuron:

The weight of a path $\operatorname{wt}(\gamma)$ was defined in (10) and includes both the product of the weights along $\gamma$ and the condition that every neuron in $\gamma$ is open at $x$. As explained in §3, the inner sum in (19) is over paths $\gamma$ in the computational graph of $\mathcal{N}$ that start at neuron $a$ in the input layer and end at the output neuron and the random variables $\widehat{W}_{\gamma}^{(i)}$ are the normalized weights on the edge of $\gamma$ between layer $i-1$ and layer $i$ (see (9)). Differentiating this formula gives sum-over-path expressions for the derivatives of $\mathcal{N}$ with respect to both $x$ and its trainable parameters. For the NTK and its first SGD update, the result is the following:

where the sum is over collections $\Gamma$ of two paths in the computation graph of $\mathcal{N}$ and edges $e$ that lie on both paths. Similarly, almost surely,

Lemma 7 is proved in §5.2. The expression (20) is simple to evaluate due to the delta function in $H(\Gamma,e).$ We obtain:

where in the second-to-last equality we used that the number of paths in the comutational graph of $\mathcal{N}$ from a given neuron in the input to the output neuron equals $\prod_{i=1,\ldots,d}n_{i}$ and in the last equality we used that $n_{d}=1.$ This proves the first equality in Theorem 1.

It therefore remains to evaluate (21) and (22). Since they are so similar, we will continue to discuss them in parallel. To start, notice that the expression $F(\Gamma,e_{1},e_{2})$ appearing in (21) and (22) satisfies

For the remainder of the proof we will write

The advantage of $F_{*}(\Gamma)$ is that it does not depend on $e_{1},e_{2}.$ Observe that for every $a=(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})\in[n_{0}]_{even}^{4}$, we have that either $\alpha_{1}=\alpha_{2}$, $\alpha_{1}=\alpha_{3}$, or $\alpha_{1}=\alpha_{4}$. Thus, by symmetry, the sum over $\Gamma_{even}^{4}(\vec{n})$ in (21) and (22) takes only four distinct values, represented by the following possibilities:

keeping track of which paths $\gamma_{1},\ldots,\gamma_{4}$ begin at the same neuron in the input layer to $\mathcal{N}.$ Hence, since

To evaluate $I_{j},\,II_{j}$ let us write

for the indicator function of the event that paths $\gamma_{\alpha},\gamma_{\beta}$ pass through the same edge between layers $i-1,i$ in the computational graph of $\mathcal{N}$. Observe that

To simplify $I_{j,i_{1},i_{2}}$ and $II_{j,i_{1},i_{2}}$ observe that $F_{*}(\Gamma)$ depends only on $\Gamma$ only via the unordered edge multi-set (i.e. only which edges are covered matters; not their labelling)

defined in Definition 3. Hence, we find that for $j=1,2,3,4,\,i_{1},i_{2}=1,\ldots,d,$

The counts in $I_{j,*,i_{1},i_{2}}$ and $II_{j,*,i_{1},i_{2}}$ have a convenient representation in terms of

Informally, the event $\widehat{C}(E,i_{1},i_{2})$ indicates the presence of a “collision” of the four paths in $\Gamma$ before the earlier of the layers $i_{1},i_{2}$, while $C(E,i_{1},i_{2})$ gives a “collision” between layers $i_{1},i_{2}$; see Section 4.1 for the intuition behind calling these collisions. We also write

Finally, for $E\in\Sigma_{a,even}^{4}(\vec{n})$, we will define

That is, a loop is created at layer $i$ if the four edges in $E$ all begin at occupy the same vertex in layer $i-1$ but occupy two different vertices in layer $i.$ We have the following Lemma.

Suppose $E\in\Sigma_{a_{j},even}^{4}$ for some $j=1,2,3,4.$ For each $i_{1},i_{2}\in\{1,\ldots,d\},$

We prove Lemma 8 in §5.3 below. Assuming it for now, observe that

Observe that every unordered multi-set four edge multiset $E\in\Sigma_{even}^{4}$ can be obtained by starting from some $V\in\Gamma^{2}$, considering its unordered edge multi-set $E^{V}$ and doubling all its edges. This map from $\Gamma^{2}$ to $\Sigma_{even}^{4}$ is surjective but not injective. The sizes of the fibers is computed by the following Lemma.

Fix $E\in\Sigma_{even}^{4}$. The number of $V\in\Gamma_{Z}^{2}$ so that $E=2\cdot E^{V}$ is $2^{\#\text{loops}(V)+{\bf 1}_{\{\left|V(0)\right|=2\}}},$ where as in (35),

Since the number of $V$ in $\Gamma^{2}(\vec{n})$ with specified $V(0)$ equals $\prod_{i=1}^{d}n_{i}^{2},$ we find that so that for each $x\neq 0,$ we have

Here, $\mathcal{E}_{x}$ is the expectation with respect to the probability measure on $V=(v_{1},v_{2})\in\Gamma^{2}$ obtained by taking $v_{1},v_{2}$ independent, each drawn from the products of the measure $\left(x_{1}^{2}/\left\lVert x\right\rVert_{2}^{2},\ldots,x_{n_{0}}^{2}/\left\lVert x\right\rVert_{2}^{2}\right)$ on $[n_{0}]$ and the uniform measure on $[n_{i}],\,i=1,\ldots,d.$

We are now in a position to complete the proof of Theorems 1 and 2. To do this, we will evaluate the expectations $\mathcal{E}_{x}$ above to leading order in $\sum_{i}1/n_{i}$ with the help of the following elementary result which is proven as Lemma 18 in .

Let $A_{0},A_{1},\ldots,A_{d}$ be independent events with probabilities $p_{0},\ldots,p_{d}$ and $B_{0},\ldots,B_{d}$ be independent events with probabilities $q_{0},\ldots,q_{d}$ such that

Denote by $X_{i}$ the indicator that the event $A_{i}$ happens, $X_{i}:={\bf 1}_{\left\{A_{i}\right\}}$, and by $Y_{i}$ the indicator that $B_{i}$ happens, $Y_{i}={\bf 1}_{\{B_{i}\}}$. Further, fix for every $i\in 1,\ldots,d$ some $\alpha_{i}\geq 1,K_{i}\geq 1$ as well as $\gamma_{i}>0$. Define

Then, if $\gamma_{i}\geq 1$ for every $i$, we have:

where by convention $\alpha_{0}=\gamma_{0}=1.$ In contrast, if $\gamma_{i}\leq 1$ for every $i$, we have:

Since $\left|V(d)\right|=1$, we may also write

Putting this together with (42) and noting that

where in the last inequality we used that $1+x\geq e^{x-x^{2}/2}$ for $x\geq 0.$ Since $e^{-1/n_{1}+1/n_{d}}\simeq 1,$ we conclude

When combined with (23) this gives the lower bound in Proposition 3. The matching upper bound is obtained from (46) in the same way using the opposite inequality from Proposition 10.

This completes the proof of Proposition 3, modulo the proofs of Lemmas 6-9, which we supply below. $\square$

With probability $1,$ either there exists $i$ so that $y^{(i)}=0$ or, for every $i\in[d],j\in[n_{i}]$ we have $y_{j}^{(i)}\neq 0.$

Lemma 11 shows that for our fixed $x$, with probability $1,$ the derivative of each $\xi_{j}^{(i)}$ in (19) vanishes. Hence, almost surely, for any edge $e$ in the computational graph of $\mathcal{N}:$

This proves the formulas for $K_{\mathcal{N}},K_{\mathcal{N}}^{2}.$ To derive the result for $\Delta K_{\mathcal{N}},$ we write

where the loss $\mathcal{L}$ on a single batch containing only $x$ is $\frac{1}{2}\left(\mathcal{N}(x)-\mathcal{N}_{*}(x)\right)^{2}.$ We therefore find

Using (47) and again applying Lemma 11, we find that with probability $1$

To complete the proof of Lemma 6 it therefore remains to check that this last term has mean $0.$ To do this, recall that the output layer of $\mathcal{N}$ is assumed to be linear and that the distribution of each weight is symmetric around (and hence has vanishing odd moments). Thus, the expectation over the weights in layer $d$ has either $1$ or $3$ weights in it and so vanishes. $\square$

2. Proof of Lemma 7

Lemma 7 is almost a corollary of of Theorem 3 in and Proposition 2 in . The difference is that, in , the biases in $\mathcal{N}$ were assumed to have a non-degenerate distribution, whereas here we’ve set them to zero. The non-degeneracy assumption is not really necessary, so we repeat here the proof from with the necessary modifications.

If $x=0,$ then $\mathcal{N}(x)=0$ for any configuration of weights since the network biases all vanish. Will therefore suppose that $x\neq 0.$ Let us first show (20). We have from Lemma 6 that

To compute the inner expectation, write $\mathcal{F}_{j}$ for the sigma algebra generated by the weight in layers up to and including $j$. Let us also define the events:

where we recall from (2) that $x^{(j)}$ are the post-activations in layer $j.$ Supposing first that $e$ is not in layer $d$, the expectation becomes

Thus, the expectation in (48) becomes $\frac{1}{n_{d-1}}{\bf 1}_{\left\{\begin{subarray}{c}\gamma_{1}(d-1)=\gamma_{2}(d-1)\\ \gamma_{1}(d)=\gamma_{2}(d)\end{subarray}\right\}}$ times

Note that given $\mathcal{F}_{d-2},$ the pre-activations $y_{j}^{(d-1)}$ of different neurons in layer $d-1$ are independent. Hence,

Recall that by assumption, the weight matrix $\widehat{W}^{(d-1)}$ in layer $d-1$ is equal in distribution to $-\widehat{W}^{(d-1)}.$ This replacement leaves the product $\prod_{k=1}^{2}\widehat{W}_{\gamma_{k}}^{(d-1)}$ unchanged but changes ${\bf 1}_{\{y_{\gamma_{1}}^{(d-1)}>0\}}$ to ${\bf 1}_{\{y_{\gamma_{1}}^{(d-1)}\leq 0\}}$. On the event $S_{d-1}$ (which occurs whenever $y_{\gamma_{k}}^{(d-2)}>0$) we have that $y_{\gamma_{1}}^{(d-1)}\neq 0$ with probability $1$ since we assumed that the distribution of each weight has a density relative to Lebesgue measure. Hence, symmetrizing over $\pm\widehat{W}^{(d)}$, we find that

Similarly, if $e$ is in layer $i,$ then we automatically find that $\gamma_{1}(i-1)=\gamma_{2}(i-1)$ and $\gamma_{1}(i)=\gamma_{2}(i)$, giving an expectation of $1/n_{i-1}{\bf 1}_{\left\{\begin{subarray}{c}\gamma_{1}(i)=\gamma_{2}(i)\\ \gamma_{1}(i-1)=\gamma_{2}(i-1)\end{subarray}\right\}}$. Proceeding in this way yields

which is precisely (20). The proofs of (21) and (22) are similar. We have

As before let us first assume that edges $e_{1},e_{2}$ are not in layer $d$. Then,

Again symmetrizing with respect to $\pm\widehat{W}^{(d)}$ and using that the pre-activation of different neurons are independent given the activations in the previous layer we find that, on the event $\{y_{\gamma_{k}}^{(d-2)}>0\}$,

where $L$ is the event that $\left|\Gamma(d-1)\right|=\left|\Gamma(d)\right|=1$ and $e_{1},e_{2}$ are not in layer $d-1$. Proceeding in this way one layer at a time completes the proofs of (21) and (22). $\square$

3. Proof of Lemma 8

For each $i=1,\ldots,d$ there exists unique $k=1,\ldots,\#\text{loops}(E)$ so that

We will say that two layers $i,j=1,\ldots,d$ belong to the same loop of $E$ if exists $k=1,\ldots,\#\text{loops}(E)$ so that

We proceed layer by layer to count the number of $\Gamma\in\Gamma_{a_{j},even}^{4}$ satisfying $\Gamma(0)=a_{j}$ and $E^{\Gamma}=E.$ To do this, suppose we are given $\Gamma(i-1)\in[n_{i-1}]^{4}$ and we have $L(E(i))=2$. Then $\Gamma(i-1)$ is some permutation of $(\alpha_{1},\alpha_{1},\alpha_{2},\alpha_{2})$ with $\alpha_{1}\neq\alpha_{2}.$ Moreover, for $j=1,2$ there is a unique edge (with multiplicity $2$) in $E(i)$ whose left endpoint is $\alpha_{j}.$ Therefore, $\Gamma(i-1)$ determines $\Gamma(i)$ when $L(E(i))=2.$ In contrast, suppose $L(E(i))=1.$ If $R(E(i))=1,$ then $E(i)$ consists of a single edge with multiplicity $4,$ which again determines $\Gamma(i-1),\Gamma(i)$. In short, $\Gamma(i)$ determines $\Gamma(j)$ for all $j$ belonging to the same loop of $E$ as $i.$ Therefore, the initial condition $\Gamma(0)=a_{j}$ determines $\Gamma(i)$ for all $i\leq i_{1}$ and the conditions $e_{1}\in\gamma_{1},e_{2}\in\gamma_{2}$ determine $\Gamma$ in the loops of $E$ containing the layers of $e_{1},e_{2}.$

4. Proof of Lemma 9

The proof of Lemma 9 is essentially identical to the proof of Lemma 8. In fact it is slightly simpler since there are no distinguished edges $e_{1},e_{2}$ to consider. We omit the details. $\square$

Proof of Proposition 4

to be the event that the pre-activations of the neurons $z_{k}$ are positive.

where $Z^{1},\,\Gamma_{(Z,Z)}^{2},\,\operatorname{wt}(\gamma)$ are defined in §3. Further, almost surely,

The proof of this result is a small modification of the proof of Lemma 6 and hence is omitted. Taking expectations, we therefore obtain the following analog to Lemma 7.

where for $\Gamma=(\gamma_{1},\ldots,\gamma_{4})\in\Gamma_{(Z,Z),even}^{4}$ we have

The proof is identical to the argument used in §5.2 to establish Lemma 7, so we omit the details. The relation (51) is easy to simplify:

Since the inner sum in (54) is independent of $\beta$ by symmetry, we find

where for the second estimate we applied Lemma 9 and have written $Z^{\prime\prime\prime}=(1,z_{2})$. Thus, as in the derivation of (42), we find that

Putting this together with (54) completes the proof of Lemma 14. ∎

as claimed in the statement Proposition 4. $\square$

Proof of Proposition 5

Here, for a neuron $Z$ and $a=(a_{1},a_{2})\in[n_{0}]^{2}$ we’ve denoted by $\Gamma_{(Z,Z,a)}^{4}$ the set of four tuples $(\gamma_{1},\ldots,\gamma_{4})$ of paths in the computational graph of $\mathcal{N}$ where $\gamma_{1},\gamma_{2}$ start from $Z$ and $\gamma_{3},\gamma_{4}$ start at neurons $a_{1},a_{2}$ respectively. The analog of Lemmas 7 and 13 (with essentially the same proof), gives that the expectation in the previous line equals

which, up to a multiplicative constant equals

which is independent of $e.$ Thus, we find

where if $\Gamma=\left(\gamma_{1},\ldots,\gamma_{4}\right)$ we recall that $T_{3,4}^{i}(\Gamma)$ is the indicator function of the event that paths $\gamma_{3},\gamma_{4}$ pass through the same edge in the computational graph of $\mathcal{N}$ at layer $i$ (see (29)).

As in the proof of Proposition 3, observe that $\widehat{G}_{Z}(\Gamma)T_{3,4}^{i}(\Gamma)$ depends only on the unordered multiset of edges $E^{\Gamma}$ in $\Gamma$. Thus, we find that

Applying Proposition 10 as in the end of the proof of Propositions 3 and 4 we conclude

plus a term that has mean $0.$ Therefore, as in Lemma 7, we find

where $T_{2,3}^{i}(E)$ is as in (29), the sum is over unordered edge multisets $E$ (see (14)), and we’ve set

As in Lemma 8, the counting term satisfies

This completes the proof of Proposition 5. $\square$

References