Finite Depth and Width Corrections to the Neural Tangent Kernel
Authors: Boris Hanin
Mihai Nica
Venue:  (2020)
Keywords: Neural Tangent Kernel
Finite Width Corrections
Random ReLU Net
Wide Networks
Deep Networks

Abstract: We prove the precise scaling, at finite depth and width, for the mean and variance of the neural tangent kernel (NTK) in a randomly initialized ReLU network. The standard deviation is exponential in the ratio of network depth to width. Thus, even in the limit of infinite overparameterization, the NTK is not deterministic if depth and width simultaneously tend to infinity. Moreover, we prove that for such deep and wide networks, the NTK has a non-trivial evolution during training by showing that the mean of its first SGD update is also exponential in the ratio of network depth to width. This is sharp contrast to the regime where depth is fixed and network width is very large. Our results suggest that, unlike relatively shallow and wide networks, deep and wide ReLU networks are capable of learning data-dependent features even in the so-called lazy training regime. 

Published as a conference paper at ICLR 2020
FINITE DEPTH AND WIDTH CORRECTIONS TO THE NEURAL TANGENT KERNEL
Boris Hanin
Mihai Nica
Department of Mathematics Texas A&M University
Department of Mathematics
University of Toronto
College Station, TX 77843, USA bhanin@math. tamu. edu
Toronto, Canada
mni caimath..hh.mmmmmm utoronto.cc
ABSTRACT
We prove the precise scaling, at finite depth and width, for the mean and variance of the neural tangent kernel (NTK) in randomly initialized ReLU network. The standard deviation is exponential in the ratio of network depth to width. Thus, even in the limit of infinite overparamelerization, the NTK not deterministic if depth and width simultaneously tend to infinity. Moreover, we prove that for such deep and wide networks, the NTK has a non-trivial evolution during training by showing that the mean of its first SGD update is also exponential in the ratio of network depth to width. This sharp contrast to the regime where depth fixed and network width is very large. Our results suggest that, unlike relatively shallow and wide networks, deep and wide ReLU networks are capable of learning data-dependent features even in the so-called lazy training regime.
INTRODUCTION
Modern neural networks are 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 a priori unexpected that not only can such interpolating parameter values can be found by stochastic gradient descent (SGD) the highly non-convex empirical risk but also that the resulting network function generalizes to unseen data. In an overparameterized neural network (xr) the individual parameters can be difficult interpret, and one way to understand training is to rewrite the SGD updates
OC 00,"
A0p
A
of trainable parameters = {0p)p=1 with loss and learning rate as kernel gradient descent updates for the values (z) of the function computed by the network:
[8]
AN(x) = - (KK((),)) VC()) = X
Oc KN(I,
ON v,)
(I)
B
Here ((11, 91), ..., (mn m1 } the current batch, the inner product is the empirical lg inner product over B, and KN is the neural tangent kernel (NTK):
P àN
àN
(N(a,x))
Σ
(x').
00, p=1
00,
Relation (1 valid to first order in X. It translates between two ways of thinking about the difficulty of neural network optimization:
(i) The parameter space view where the loss L, a complicated function of 0 e R. #paraetters, is minimized using gradient descent with respect to simple (Fuclidean) metric;

---

Published as a conference paper at ICLR 2020
(ii) The function space view where the loss L, which is simple function of the network map- ping 2' + (z), is minimized over the manifold Mv of all functions representable by the architecture of N using gradient descent with respect to potentially complicated Rie- mannian metric N on MN
remarkable observation Jacot et al. (2188) is that Kv simplifies dramatically when the network depth d is fixed and its width n tends to infinity. In this setting, by the universal approximation theorem (Cybenko 1989, Hornik et al., 1989,, the manifold MN fills out any (reasonable) ambient linear space of functions. The results in Jacot et al. 2018)) then show that the kernel KN in this limit is frozen throughout training to the infinite width limit of its average E| [v]] at initialization, which depends the depth and non- non-linearity of N but not the dataset.
This mapping between parameter space SGD and kernel gradient descent for a fixed kernel can be viewed as two separate statements. First, at initialization, the distribution of KN converges in the infinite width limit to the delta function on the infinite width limit of its mean TE| N. Second, the infinite width limit of SGD dynamics in function space is kernel gradient descent for this limiting mean kernel for any fixed number of SGD iterations. As long as the loss L is well-behaved with respect to the network outputs N (x) and E[ is non-degenerate in the subspace of function space given by values on inputs from the dataset, SGD for infinitely wide networks will converge with probability to a minimum of the loss. Further, kernel method-based theorems show that even in this infinitely overparameterized regime neural networks will have non-vacuous guarantees on generalization (Wei et al., 2018). However, as (Wei al.) 2018) shows, the regularized neural networks at finite width can have better sample complexity the corresponding infinite width kernel method.
But replacing neural network training by gradient descent for a fixed kernel in function space is also not completely satisfactory for several reasons. First, it suggests that no feature learning occurs during training for infinitely wide networks in the sense that the kernel E[K~ Nv] (and hence its asso- ciated feature map) is data-indeeeedent. In fact, empirically, networks with finite but large width trained with initially large learning rates often outperform NTK predictions at infinite width (Aroral et al. 2019). One interpretation is that, at finite width, K evolves through training, learning data- dependent features not captured by the infinite width limit of its mean at initialization. In part for such reasons, it is important to study both empirically and theoretically finite width corrections to KN. Another interpretation is that the specific NTK scaling of weights at initialization (Chizat & Bach, 2ach,,008bb 8b Mei et al. 2019 2018 Rotskoff & Vanden Eijndenn 2018a b) and the implicit small leariing rate limit (Li et al. 2019) obscure important aspects of SGD dynamics. Second, even in the infinite width limit, although KN is deterministic, it has no simple analytical formula for deep networks, since it is defined via layer by layer recursion. particular, the exact dependence, even in the infinite width limit, of KN network depth is not well understood.
Moreover, the joint statistical effects of depth and width on KN 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 KN for finite but large widths n and any depth d. Our results apply to fully connected ReLU networks at initialization for which our main contributions are:
1. In contrast to the regime in which the depth d is fixed but the width n is large, KN is not approximately deterministic at initialization so long as d/n is bounded away from O. Specifically, for fixed input the normalized on-diagonal second moment of K N satisfies
E KNN (z, 2 E [x 2)}²
~ exp(5d/n) (1 O(d/n?))
Thus, when d/n is bounded away from O, even when both n, d are large, the standard deviation of K n xx) is at least large as its mean, showing that its distribution at initialization is not close to delta function. See Theorem
2. Moreover, when L is the square loss, the average of the SGD update AKN (2, to KN (z. x) from a batch of size one containing x satisfies
E E[AKN (Z (2,x)
d² nno
exp(5d/n) (1+ O(d/73)) (1+0(/)2))
E ([N(I,
2

---

Published as a conference paper at ICLR 2020
where no is the input dimension. Therefore, if dl /nno O, the NTK will have the potential to evolve in data-dependent way. Moreover, if no is comparable to n and d/n > then is possible that this evolution will have well-defined expansion in d/n. See Theorem
In both statements above, = means is bounded above and below by universal constants. We em- phasize that our results hold finite d, n and the implicit constants in both and in the error terms ((d/n²) 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 only for the sake of exposition. The appropriate generalization of d/n to networks with varying layer widths is the parameter
B
nJj
which in light of the estimates in (1) and (2) plays the role of an inverse temperature.
1.1 PRIOR WORK
A number of articles (Bietti & Mairal 2019; Dyer & Gur-Ari 2019; Lee et al. 2019 Yang 2019)
have followed up on the original NTK work Jacot al. (2018). Related in spirit to our results is the work Dyer & Gur-Ari (2019), which uses Feynman diagrams to study finite width corrections to general correlations functions (and in particular the NTK). The most complete results obtained by Dyer & Gur-Ari (019) 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 and let the layer widths tend to infinity. In contrast, our results (as well as those of Hanin (2018);
Hanin Nica (2018); Hanin & Rolnick (2018). do not treat d as a constant, suggesting that the 1/n expansions (e.g. in Dyer & Gur-Ari (2019) can be promoted to d/n expansions. Also, the sum-over-pan paver-path approach to studying correlation functions in randomly initialized ReLU nets was previously taken up for the forward pass by Hanin & Rolnick (018)) and for the backward pass by
Hanin (0188) HadjHanin & Nica (2018). We also point the reader to Theorems 3.1 and 3.2 in [Aroa al. (019). which provide quantitative rates of convergence for both the neural tangent kernel and the resulting full optimization trajectory of neural networks at large but finite width (and fixed
depth).
FORMAL STATEMENT OF RESULTS
Consider a ReLU network N with input dimension no, hidden layer widths Ri...... Re--1, and output dimension na = 1. We will assume that the output layer of N is linear and initialize the biases to zero. Therefore, for any input x E R the network N computes N(x) ((4) given by
(0() v, y = ((-((-1)) 200 : ())
i= ==
(2)
where for i 1,...,
(4) = (1/m-1)-1/2W00) w = (2/n,-1) 1/2
w( ag p i.i.d.
(3)
and μ is a fixed probability measure R that we assume has density with respect to Lebesgue measure and satisfies:
μ symmetric around 0, Varlu] = 1,
d'dp(a)) μ4 < oc.
(4)
The three assumptions in (4) hold for virtually all standard network initialization schemes with the exception of orthogonal weight initialization. But believe our results extend hold also for this case but not do take up this issue. The on-diagonal NTK is
d R5-1 ny
ON
d
my
ON
<N( =
Σ
(x)
26 G) (1))
(5)
OW R
1=1
B=1
and we emphasize that although we have initialized the biases to zero, they are not removed from the list of trainable parameters. Our first result is the following:
3

---

Published as a conference paper at ICLR 2020
Theorem (Mean and Variance of NKT Diagonal Init). We have
[I,N(z, = d {
|0:
no
Moreover, we have that E ())) ) is bounded above and below by universal constants times
de ||=11 d 1
d
exp (5,3)
Si # +
Σ
55 -5
2
no
74
5=1
1
times a multiplicative enror (1 + 0 EE #/2 ) In particular, if all the hidden layer widths are
equal (i.e. n4 n. ior l....,d- 1). we have
E (x,x)))
E [x, exp (1+00(()))))
== =dd/n,
where f = means f bounded above and below by universal constants times g.
This result shows that the deep and wide double scaling limit
n₂ d + D0,
lim nidd
00,
72
the NTK does not converge to constant in probability. This is contrast to the wide and shallow regime where n, - oo and d < 3o is fixed.
Our next result shows that when L is the square loss KN (z, .)) is not frozen during training. To state it, fix an input æ E R" to N and define AKN(E) x)) to be the update from one step of SGD with batch of size 1 containing x (and learning rate A).
Theorem 2 (Mean of Time Derivative of NTK on Diagonal at Init). We have that [A- K (x, is bounded above and below by universal constants times
|
-5/ne-0 GE
|
En
Σ
2
exp (533
710
n1
d1 t=i
8=11
i1 11
times a multiplicative error of size (1+0 1 ) where 3 = =i 1/n,, as in Theorem
In particular, if all the hidden layer widths are equal (i.e. n4 n. for I,..., 1), we find
E [[AKN([,,))
dß
exp (53) (1 (3/n)),
B = d/n.
E [x,
no
Observe that when is fixed and n; = n + 0o, the fre-factor in front of exp (5,3) scales like 1 1/n. This is in keeping with the results from Dyer & Gur-Ari (2019) and Jacot al. (201). Moreover, it shows that if d, n, grow in any way so that d0/no = d/nno + 0, the update AK N (z, x) to K KN xx) from the batch {x} at initialization will have mean It is unclear whether this will be true also for larger batches and when the arguments of KN are not equal. In contrast, if ny z n and d/n bounded away from 0, oc, and the no is proportional d, the average update E (z, r)] has the same order of magnitude as [[KN(z))
2.1 ORGANIZATION FOR THE REST OF THE ARTICLE
The remainder of this article is structured as follows. First, we give an outline of the proofs of Theorems D and 2 in d and particularly in 43.1 which gives in-depth but informal explanation of our strategy for computing moments of K K and its time derivative. Next, in the Appendix Section {A] we introduce some notation about paths and edges in the computation graph of N. This
4

---

Published as a conference paper at ICLR 2020
notation will be used in the proofs of Theorems [ and presented in the Appendix Section The computations in exxxlaiin how to handle the contribution to NN and AKN coming only from the weights of the network. They are the most technical and give them in full detail. Then, the discussion in $C and [D show how to adapt the method developed in { to treat the contribution of biases and mixed bias-weight terms in K N, K2 and AKN. Since the arguments simpler in these cases, we omit some details and focus only on highlighting the salient differences.
B
OVERVIEW OF PROOF OF THEOREMS 1 AND 2
The proofs of Theorems and are so similar that we will prove them at the same time. In this section and in :f.1 we present an overview of our argument. Then, we carry out the details in Appendix Sections B
below. Fix an input æ R to N. Recall from (5) that
KN (x, Kw + Kb.
where we' 've set
K
ON
dw (x) (t))
Kb Σ
ON Ob (x)
(6)
weights
binses b
and have suppressed the dependence on 2; N. Similarly, we have
(1,
Aww + 2Awb + Abb.
21
where we have introduced
! ww
Σ
ON
ON
(x)
ON
(x) (N(x) N.)x))
dwdw
Ow
weights
èN
22N dwob
ON
A wb
Σ
(x) -N.)))
dw
ab
weight bias
ON
oN OV
Abb
(x) (N (1) (.)x))
ab
abob
biases b.b'
and have used that the loss on the batch {z} is given by L(x) (N(x) - (z)) for some
target value N.(r). To prove Theorem I we must estimate the following quantities:
B[Kw], [[K]], E[K2], E[K.Kbb, B[K]].
To prove Theorem 2 we must control in addition
E[Aww], E[Awt], E[Abb].
The most technically involved computations will turn out to be those involving only weights: namely, the terms E K.), [E Reae)./AAWW [[Aww]. These terms are controlled by writing each as a sum certain paths y that traverse the network from the input to the output layers. The corresponding results for terms involving the bias will then turn out to be very similar but with paths that start somewhere in the middle of network (corresponding which bias term was used to differentiate the network output). The main result about the pure weight contributions to K n is the following Proposition 3 (Pure weight moments for KN, AKN). We have
E Kw)
|
ng
Moreover,
[[K
d² z
| exp
exp (5,9)
1+0 Σ
B
no
Finally.
| n
E [ww]
~
Σ
5/ne
ا कर
exp (58)
1+0
Σ
T2
b 11 t=i1 1,533
5

---

Published as a conference paper at ICLR 2020
We prove Proposition 3 in
B
below. The proof already contains all the ideas necessary to treat the
remaining moments. In following two Propositions:
C
and D
we explain how to modify the proof of Proposition to prove the
Proposition 4 (Pure bias moments for KN, AK We have
d
B[Kb]
2
Moreover,
d
(1+0
d
E[K]]
E
e
1=
exp
2
i=1
Finally, with probubility 1, we have Aph
Proposition 5 (Mixed bias biashweight moments for KN, AKN).
We have
d Σ
[[
Σ
exp
1+0
no
n2
m
Further, B[Awb] is bounded above and below by universal constants times
|
(110
Σ 1=1=1
E.
Eo
Σ
exp
_
nh
T2d
The statements in Theorems D and that hold for general n, now follow directly from Propositions The asymptotics when = follow from some routine algebra.
3.1 IDEA OF PROOF PROPOSITIONS 3
Before turning to the details of the proof of Propositions 3 below, we give an intuitive explanation of the key steps in our sum-over-patt analysis of the moments of Kw, Kb. ww. Awb, Abb- Since the proofs of all three Propositions follow a similar structure and Proposition is the most compli- cated, we will focus on explaining how to obtain
first moments of K Since the biases are initialized to zero and Kw involves only derivatives with respect to the weights, for the purposes of analyzing Kw the biases play no role. Without the biases, the output of the neural network, N(x) can be express weighted sum over paths in the computational graph of the network:
no Σ
(x)
FA
wi(?),
YET!
where r'l is the collection of paths in N starting at neuron and the weight of a path wt(7) is defined (13) in the Appendix and includes both the product of the weights along 7 and the condition that every neuron in y is open at x. The path begins at some neuron in the input layer of N and passes through a neuron every subsequent layer until ending up at the unique neuron in the output layer (see (1)).. Being product over edge weights in given path, the derivative of wt(y) with respect to weight W. on an edge e of the computational graph of is:
Owt(?) oW.
wt(7) W. (cEn))
There is subtle point here that wt(y) also involves indicator functions of the events that neurons along 7 are open at x. However, with probability 1, the derivative with respect to W, of these indicator functions is identically The details are in Lemma

---

Published as a conference paper at ICLR 2020
Because Kw is a sum of derivatives squared (see (6). ignoring the dependence the network input I, the kernel Kw roughly takes the form
Il wt(7x)
Kw E E 7T BE
W?
where the sum is over collections (71, Y2) of two paths in the computation graph of N and edges in the computational graph of N that lie on both (see Lemma 6 for the precise statement). When computing the mean, E. w. by the mean zero assumption of the weights W. (see 44)). the only contribution is when every edge in the computational graph of N is traversed by even number of paths. Since there are exactly two paths, the only contribution is when the two paths are identical, dramatically simplifying the problem. This gives rise to the simple formula for [E[Kw] (see (3 The expression
lh wt(T))
K2
Σ 7172777761111
E
W W2
for K2 more complex. involves sums over four paths in the computational graph of N in the second statement of Lemma 6 Again recalling that the moments of the weights have mean 0, the only collections of paths that contribute [[K"] are those in which every edge in the computational graph of N is covered an even number of times:
=== (1()))
E
Σ
Σ
E
W2 W2
TE 77-777733774 C1ENLTN
oven 62E78a7a
However, there are now several ways the four paths can interact to give such a configuration. is the combinatories of these interactions, together with the stipulation that the marked edges e 62 belong to particular pairs of paths, which complicates the analysis of B[ We estimate this expectation in several steps:
1. Obtain exact formula for the expectation in 8
Th wt(3k) W2 W2
E
F(,,,1,,2).
where F(T,ed éi, e2) is the product over the layers l = l,..., d in N of the "cost" of the interactions of 71,....74 between layers L and E. The precise formula in Lemma]
2. Observe the dependence of F(T, on e1, e2 only up to a multiplicative constant: F(T, FT).).
The precise relation
(4
This shows that, up universal constants,
K
Σ
F. (1, E [d]
7ir72 togethe at layer
75.74 togethe at layer Eg
Y2 73.73-78.74
This captured precisely by the terms 15,11, 11, defined in 28).
3. Notice that F. (T) depends only on the un-ordered multiset of edges F. F. E Σ4 E determined by T (see (17) for precise definition). We therefore change variables in the sum from the previous step to find
E K
Σ BEX4
(.(())acobian(FFeee... F1,
where Jacobian( E, e2) counts how many collections of four paths r E I have the same ET also have paths 71, 72 pass through é and paths 73. Y4 pass through eg. Lemma gives precise expression for this Jacobian. It turns outs, explained just below Lemma that
even that
Jacobian E,, 62) ~ #loops(EE)
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 and

---

Published as a conference paper at ICLR 2020
4. Change variables from unordered multisets of edges E E E Leen in which every edge is covered an even number of times to pairs of paths E I 2 #loops(B) (Lemma 9p. giving
The Jacobian turns out to be
B[K2]
Σ VErz
F.(V)3 F.(V)3tlloppsV) Hloops(V)
5. Just like F. (V), the term 3#Hooos(V)) is again a product over layers é in the computational graph of N of the "cost" of interactions between our four paths. Aggregating these two terms into a single functional F. (E) and factoring out the 1/ng terms F.(V) we find that:
1 no
(F.()))
E K
where the 1 1/n; terms cause the sum become average collections V of two inde- pendent paths the computational graph of N with each path sampling neurons uniformly random in every layer. The precise result, including the dependence the input æ,, is in (42)
6. Finally, we use Proposition| to obtain for this expectation estimates above and below that match up multiplicative constants.
Figure 1: Cartoon of the four paths 7/, 7/2 Y3, " between layers & and & in the case where there interaction. Paths stay with there original partners ? with "/2 and "s with 744 at all intermediate layers.
&
Figure 2: Cartoon of the four paths 71, 72, 7a, 74 between layers & and &2 in the case where there is exactly one "loop" interaction between the marked layers. Paths swap away from their original part- ners exactly once at some intermediate layer after f,, and then swap back to their original partners before lz.
3.2 CONCLUSION
Taken together Theorems and 2 show that in fully connected ReLU nets that are both deep and wide the neural tangent kernel KN is genuinely stochastic and enjoys non-trivial evolution during training. This suggests that in the overparameterized limit n, d - co with d/n oc), the kernel KN may learn data-dependent features. Moreover, our results show that the fluctuations of both KN and its time derivative exponential in the inverse temperature
d/n.
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 tums out be data-dependent,
8

---

Published as a conference paper at ICLR 2020
results suggest that the double descent curve Belkin al. (2018 2019); Spigler al. (2018)
that trades off complexity vs. generalization error may display significantly different behaviors
depending the mode of network overparameterization.
However, it is also important to point out that the results Hanin
20018: Hanin Nica (2018);
Hanin & Rolnick (2018) show that, at least for fully connected ReLU nets, gradient- based training not numerically stable unless d/n is relatively small (but not necessarily zero). Thus, we conjecture that there may exist "weak feature learning" NTK regime in which network depth and width are both large but < d/n & 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 Chizat Bach (2018b) 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). Even in fully connected networks, the input/outpu Jacobian already displays different spectral statis- ties depending on the non-linearity (Pennington et al. 2017). Moreover, typical ConvNets, are sig- nificantly 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 (the neural tangent kernel for finite depth convolutional networks is studied in part in (Arora et al. 2019 )
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8139-8148, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. arXiv preprint arXiv: 18/2. 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint 19X3v:9903.07577 2019.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernlls. arXiv preprint arXiv: 2019.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems, pp. 3036-3046, 2018a.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv:1812.0773 2018b.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals, and Systems (MCSS), 2(4):303-314, 1989.
Ethan Dyer and Guy Gur-Ari. Asymptotics of wide networks from feynman diagrams. In ICML Workshop on Physics for Deep Learning, 2019.
Boris Hanin. Which neural net architectures give rise to exploding and vanishing gradients? In Advances in Neural Information Processing Systems, 2018.
Boris Hanin and Mihai Nica. Products many large random matrices and gradients in deep neural networks. arXiv preprint arXiv: 181.v91812.05994, 2018.
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture. In Advances in Neural Information Processing Systems, pp. 571-581, 2018
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, 2019.
Kurt Horiik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural nefworks, 2(5):359-366, 1989.

---

Published as a conference paper at ICLR 2020
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571- 8580, 2018.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint 190.:0290..06720 2019.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large 2019.
learning rate in training neural networks. arXiv preprint
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layers neural networks. arXiv preprint arXiv: 1o..//044.00000 2018.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-fiele theory of two-layers neural networks: dimension-free bounds and kernel limit. arXiv preprint (rXiv:/902.000 2019.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Advances in neural information processing systems, pp. 4788 4798, 2017.
Grant Rotskoff and Eric Vanden-Eijnden Parameters interacting particles: long time convergence and asymptotic error scaling of neural networks. In Advances in neural information processing systems, pp. 7146-7155, 2018a.
Grant M Rotskoff and Eric Vanden-Bijnden. Neural networks interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. arXiv preprint arXiv:1805.00915. 2018b.
Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to parmmetratttinnnooonn affects loss landscape and generaliza- tion. arXiv preprint arXiv: (tx./v://1.099600 /800.0666, 2018
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. arXiv preprint arXiv: 18000058,, 2018.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint (eXXi:1902.047000 2019.
A NOTATION
In this section, we introduce some notation, adapted in large part from Hanin & Nica (2018), that will be used in the proofs of Theorems I [ndd]
2 For N, we will write
[n] = nI.
It will also be convenient to denote
[n] := {a E [n]* every entry in appears an even number of times).
Given ReLU network N with input dimension no, hidden layer widths 7i,..., Pa-11 and output dimension ny 1, its computational graph is a directed multipartite graph whose vertex set is the disjoint union Inu] II... ... [[[ma] and in which edges are possible ways of connecting vertices from [n=-1] with vertices from [ma] for i = 1,...,d. d. The vertices are the neurons in N, and we will write for & do. and a [nd]
a)) = neuron number in layer f.
Definition (Path in the computational graph of N). Given 0 S <1 < l2 S d and ai E [[n,, ag E [negl, path y in the computational graph of N from neuron (1) ) to neuron 2222 is collection of neurons in layers ,,,...,f2:
7 (r(())......( -. (f22)
70) [ny], 7(1) an, 7(22) oz-
(10)
10

---

Published as a conference paper at ICLR 2020
Further, will write
z (211...., ;2, 2 are neurons N).
Given collection of neurons
= (z((), z(ln: on)) E 2²
denote by
r = ( 7k)
is a path starting at neuron =(f,.ax,) ,x,)
cading the ourput s(d.1)
Note that with this notation, we have 7/2 I x(f,,a,) for each i 1...., k. For I D we also
[(e) {a [nv] 3j [k] s.t. (c) k).
Correspondingly, we will write
[(O) distinct elements in I(e).
(11)
each edge in the computational graph of is assigned weight We, then associated to a path collection of weights:
(12)
Definition 2 (Weight of path in the computational graph of N). Fix 0 < & S d, and let be path the computation graph of N starting at layer l and ending at the output. The weight of this path at given input to N is
wt(?) = W(d) II
W 1 ( open at x))
(13)
j=t+1
where
( open x) II
(x).
(x)
(v/ >0>>
is the event that all neurons along are open for the input x. Here (0)) is as in 2
Next, for an edge E [n:-1] x [n:] in the computational graph of N will write
E(e)
(14)
for the layer of e. In the course of proving Theorems I and 2 it will be useful associate every I' E (7) an unordered multi-set of edges ET
Definition (Unordered multisets of edges and their endpoints). For n, n,,', set
Σ* (n,,n')) {(a1, $1), (ax, 3x) (aj, 3,) [n] [n'}
to be the unordered multiset of edges in the complete directed bi- bi-paritite graph Kn oriented from [n] to [n']. For every E E (,,,,,, n') define its left and right endpoints to be
L(E) = {a E [n] 3j 1,... s.I. a [,j} R(E) {B E [n
(15)
1: s.t. B B,}.
(16)
where L(E),R(E) R(E) are unordered multi-sets.
Using this notation, for any collection Z (1) 2 (r2)) of neurons and r (Ti...., 7h) 1 define for each f E [d] the associated unordered multiset
(e) = {aa 8) E [me-1, ne] 3j = 1,..., s.t. 7, - 1) = 7,(() = 3}
of edges between layers L and & that are present in r. Similarly, will write
Σ (EE()) ... E(d)) E Σ (no. x.)... (n na) |L E D s.t. E(E) (e), 8 [d]
(17)
for the set of all possible edge multisets realized by paths in r On number of occasions, will also write
{F E ED every edge in F. appears number of times)
Z,even

---

Published as a conference paper at ICLR 2020
and correspondingly
D Z.even = (T E E F²" E x "Zevven
We will moreover say that for path an edge = (a, 3) E [ni-1] [nn] in the computational graph of N belongs to r (written e ?)
7 - 1) = a2 7(1) = 3.
(18)
Finally, for an edge = (a. (3 E [n:-1] x [n:] in the computational graph of N, we set
We W a. We
for the normalized and unnormalized weights on the edge corresponding to (see 3
B PROOF OF PROPOSITION 3
We begin with the well-known formula for the output of ReLU net with biases set to and linear final layer with one neuron:
(Φ)
Σ Fa
wt(?).
(19)
YET!
The weight path wt(?) was defined (33) and includes both the product of the weights along y and the condition that every neuron in open As explained in |A] the inner sum in (19) is over paths 7 in the computational graph of N that start neuron a in the input layer and end at the
output neuron and the random variables W are the normalized weights on the edge of y between layer i and layer i (see (12).. Differentiating this formula gives sum-over-pate expressions for the derivatives of N with respect to both x and its trainable parameters. For the NTK and its first SGD update, the result the following:
Lemma 6 (weight contribution KN and AKN sum-over-paths). With probability 1,
l wl(7k)
Kw =
Σ aE/mg)
II Tan
Σ
Σ
W2
1=1
rET r=(m)77)
where the sum is over collections I' of two paths in the computation graph of N and edges e that lie on both paths. Similarly, almost surely,
II wt(7x)
K2
Σ
Eak II
Σ
Σ erEnnng
W2 W2
ag [E(no)
k=1
(
(=
e2E79:74
and
L wt(7k)
A ww
Σ
II
Tos
Σ
Σ
W2 W2
aE(na]
k=1
ey Trya (e)
22E7p-78 T=(100024)
plus term that has 0.
The notation [no]*, D& E 7, etc is defined in A We prove Lemma in B. below. Let us emphasize that the expressions for K2 and Aww are almost identical. The main difference that in the expression for Aww the second path 72 must contain both and while 74 has no restrictions. Hence, while for K2 the contribution from collection of four paths r (71, 72, 73. 74) the same as from the collection I' (72, 71, 74, 73). for Aww the contributions are different. This seemingly small discrepancy, as we shall see, causes the normalized expectation E BjAww]/El[ / to converge to zero when d < is fixed and π; oo (see the 1/ns factors in the statement of Theorem 2 In contrast, in the same regime, the normalized second moment E /// remains bounded away from zero in the statement of Theorem Both statements consistent with prior results in the literature Dyer & Gur-Ari (2019); Jacot et al. (2018). Taking expectations Lemma yields the following result.
12

---

Published as a conference paper at ICLR 2020
Lemma (Expectation of Kw; K2
Aww as over 2,4 paths). We have,
K[Kw]
Σ
II
Luk
Σ
Σ
H(T,e)
(20)
af Roleeeen
k=1
D osen
(=(m1.1
where
e[) (m1p))
74-1
Similarly,
E[KW] = Σ
Lak
Σ
CrE9t #2E7a14 61,)
Σ
(21)
ac [no]aue
Tel o,
[=(
where
d 2 [r()]l
F(T,,1,e2)
II
1 1 (00--D1-161-1)
=
2 n
P4
1=1
Finally,
B|Aww ww!
Toe
Σ
Σ 1m
F(T,en,
(22)
OE aE(mo]even
k=1
PET (=(
22E12.23
e1
Lemma 7 is proved in B.2 HT, e). We obtain:
The expression 20 simple evaluate due to the delta function in
d Th |101 =
k Σ
Σ
=
|
(23)
(ET) cET i=1 74-1
where in the second-tt -o-ddtst-lstt equality we used that the number of paths in the comutational graph of N from given neuron the input to the output neuron equals Ii=1..... my and in the last equality we used that na This proves the first equality in Theorem
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[T, e1, e1,e2) e2) appearing in 21 and (22) satisfies
FT(T) & F(T,e1,)2) $ FT),),
2ph
where
(())
FT(T)
I
n²_1
M4
(1 111- r(0]-1)
(24)
i=1
For the remainder of the proof we will write
~
E constants C, > 0 depending only s.t.
cg S S Cg.
Thus, in particular,
F(T,)),02) ~ FT).).
The advantage of (T) is that it does not depend on 61, 62. Observe that for every (#1, a2, a3, a4) E [Poler (oolerens we have that either 01 = a2 0j = ag, or aj = a4. Thus, by symmetry, the sum over 141 (77) in 21 and (22 takes only four distinct values, represented by the following possibilities:
(1,1,1,1),
j=1
(1,2,1,2),
j=
aj [no]even
(1,1,2,2),
j=3"
(1,2,2,1),
j=4
13

---

Published as a conference paper at ICLR 2020
keeping track of which paths " begin at the same neuron in the imput layer to N. Hence, since
Σ
JaL II
||>||
||=
( ( [nol 0istag
k=1
mag,
we find
[[K@]
|| /1 (1 [ La Ia);
(25)
and similarly,
ww] || 11 (11= - + 113 + 114),
(26)
where
1 Σ
# fedges e1, e2 |e 2 62 E e ny4
(27)
rer agaeven (R)
(=
11,
Σ DETS
F. (edges e2, lei E 7 e2 E2 73 el # e2)
(28)
agieven (R) (=()1m0)74)
To evaluate I,, 11y let write
T (T) 1 (ra((-1)=7a((-1) (a())=o(1)
I= (1),..))))
a,3= =3=1..... 4
(29)
for the indicator function of the event that paths Tan aa pass through the same edge between layers i 1, in the computational graph of N. Observe that
# fedges e1 ee 71 72, e 23
Σ
T
2
i1,2=1
and
# (edges e2 le E E 72, e2 E 72, E
F2)
T 2,333
11.22=1
11912
Thus, we have
d Σ
1 =
II =
Σ
h1:0==1 $19-12
where
Σ
H5
Σ DErd ayleven (=(2)mm71))
TErL jasen
T=(11-.,74)
To simplify Ijái and 13 observe that FT) depends only on I' o'only via the unordered edge multi-set (i.e. only which edges are covered matters; not their labelling)
h"= (E" (L). E (d) (d)) E 2d Leven
defined in Definition 3 Hence, we find that for j 1,2,3, 4, i, i2 = 1....,d d
Ijaiis =
F.(F)# T Tere r4
ayieven (7))
E==E, r(0)=a, 1=1,2
(30)
71 (((1-1))=y
BEst
evenn (1)
-'=E,
Σ
F rert
ayeeven (77)
(31)
BEST
eyeeeen (t)
14

---

Published as a conference paper at ICLR 2020
The counts in I3 ,1. and +.i.0. have convenient representation in terms of
((E,ú,ū2)) = 1 (e)) .22 11) s.t. (R((()) =1}
(32)
Č(E,ú1,6)) = [ min [R(
(33)
Informally, the event C(E, $1, i2) indicates the presence of "collision" of the four paths in I before the earlier of the layers 1, i2, while C(E, 4 i2) gives a "collision" between layers i 12; see Section
3.1 for the intuition behind calling these collisions. We also write
A(E, 11,22)
+ 6
[LEBGG))
+ -1 [
B(
(34)
6
36
min(11.22 (1 (c st. [t[[R((())]]
st. [[((()))=
Finally, for E E El a,veen (T), we will define
#loops(E)
# [d] [L(E()) 1, [R(())) 2
(35)
That is, loop is created at layer if the four edges in E all begin at occupy the same vertex in layer i but occupy two different vertices in layer We have the following Lemma.
Lemma 8 (Evaluation of Counting Terms in (30 and 31
Suppose E'
La even for some j =
1,2,3,4. For each i,, 12 {l....,d) d),
# r (7..... 74) E 1
ay.even 7/s D
equals
11
1,2
6 #loops( (E) A(E,
(36)
j= 3= 3,4
Similarly,
# rerd
mih r" F0) -0) 1-1.2 -))
aysewen
equals
L (Cl))
j= 1,2
#loopss(E) i(E (2)((,
(37)
3=
We prove Lemma 8 in
B.3
below. Assuming it for now, observe that
< A(E, 1 12) 1
36
and that the conditions L(E(1)) aj the same for 2,3, since the equality it is in the sense of unordered multi-sets. Thus, we find that E[K is bounded above/below by constant times
|
Σ
+
|
Σ
(,,4,
(38)
f1.12=1
RENd even
FENA .geee
Similarly, E [w] is bounded above/below by a constant times
d
|
F.(E66 Hlopps (E) (L ((F
(39)
d1v
EEDa
+[||0|1
Σ
EESR B
E Observe that every unordered multi-set four edge multiset E Zeven can be obtained by starting from some V 2 considering its unordered edge multi-set EV and doubling all its edges. This map from 2 to E is surjective but not injective. The sizes of the fibers is computed by the following Lemma.
15

---

Published as a conference paper at ICLR 2020
Lemma 9. Fix E Leven. The number of V r3 that E 2 EV is 2 ( where as in 35
#loops(V) # [d] V(i 1) 1. = 2].
Lemma is proved in B.4 Using it and that 0 < Ö i1 i2) - 1, the relation (38 shows that
is bounded above/below by constant times
d² Σ F.((33HHorr( (I=11i [(vo)))=1 + (1|=1 || (1(00)=1)))
(40)
Ver
Similarly, [w[ is bounded above/below by a constant times
d
Σ
Σ F.(V)
MO (II=ll 1 [(11))= + (1a11 || |1 =21) (41)
i1-g=1 Ver
f13612
where, in analogy
we have
C(V, (2 [V([]==))-
Let us introduce
d II
R(() = (V) 3 Mooppa()
n2
1=0
( [V00=11/ p1
(ce[d) [[
Since the number of V in (n) with specified (()) equals II n3, we find that that for each x f O, we have
B[K
de & [R.(v)
(42)
|
and similarly,
E A ww
Σ & [
||0||/
1O
$1.12=1
$19612
Here, Eg is the expectation with respect to the probability measure on V (U1, U2) e 2 obtained by taking V1,22 independent, each drawn from the products of the measure ||=]
on [nu] and the uniform measure on [n:], i 1....,dd
We are now a position to complete the proof of Theorems 2nd To do this, we will evaluate the expectations E, above to leading order in >; 1/n, with the help of the following elementary result which is proven as Lemma in Hanin & Nica (2018).
Proposition 10. Let Au, Ai,..., As be independent events with probabilities po..... Pa and Bo...., Ba be independent events with probabilities qo- ...... qa such that
A = 0, Vj = -....,d d.
Denote by Xx the indicator that the event A₁ happens, X; = 1 [A.)) and by Y; the indicator that B; happens, Y; = 1 (B.)- Further, fix for every E 1...., some a; 2 1, K; 2 1 as well as % > O. Define
Z
7
X K.Y.
i=1
Then, i/ 2 1 for every we have:
d
E E
< (1 p.(a - + qK, -1) + P.P.- p.P---.;00---m-11 -1),
(43)
where by convention ao 70
1. contrast, if S 1 for every i, we have:
d
7
II i=1
(1 + pa(a; 1) + P.P:- PoP--10--100(0
(44)
16

---

Published as a conference paper at ICLR 2020
We first apply Proposition 10 to the estimates above for E[K]]. To do this, recall that
3
II i=1
3 (000
Since [V(d) = 1, may also write
3 (V)
1
II
3 (2
(VV---- 3 31
3
i=1
==1
Putting this together with
42 and noting that
d
d II 1=1
I1 2
[V(]
2 (1o1--
1=1
we find that
14 1 1I 6favo))))
E K
|
~
&
II
Since the contribution for each layer in the product bounded above and below by constants, we have that FE[K]/ ||>||| is bounded below by a constant times
d²
d-1
P4 II IIA
&
(45)
no
2
3
2
and above by a constant times
d² &
II 1==2
44 II
1 10M6--1
(46)
3
Here, note that the initial condition given by r and the terminal condition that all paths end at one neuron in the final layer are irrelevant. The expression 455 there precisely EE 1/78-1/n] from
Proposition 10 where X; is the event that [V(i) 1, Y. 0, a 6, 7i = A 44 K; 1. Thus, since for I,...,d- - 1, the probability of X, is 1/m, + O(1n2)) we find that
3 1, and
d² d-1
5 n
+o
))
d²
2
B[K |>||
II
1+
+ n1-1
exp
Σ 144
n
n
no
2=
where in the last inequality we used that conclude
for I 2 0. Since 1/mi+1/na 1, we + x 2 x²-2212
d²
E
/
||01
exp (5.3
1+0
g
B
n
n
When combined with (23 this gives the lower bound in Proposition The matching upper bound
is obtained from (46) in the same way using the opposite inequality from Proposition 10
To complete the proof of Proposition fashion. Namely, we fix 1 < i1 is and write
we prove the analogous bounds for [[Aww] in similar
C(V,ú1,62)
1A
A
( and [V01=1
The set A is the event that the first collision between layers i ig occurs at layer We then have
i2-1
Ex (R
Σ En [
17

---

Published as a conference paper at ICLR 2020
On the event Ac, notice that (V) only depends the layers 1 i because the event A fixes what happens layers i < S Mimicking the estimates (45 (46
1 and layers /
<<<> d
and the application of Proposition I0 and using independence, get that:
& [V(())((
Σ T4 (E(().)
& (1(4)
exp
Finally, compute:
& (1(Ae)) P((e)
exp
nh
n4
nt
Combining this we obtain that w/Aww]/ || is bounded above and below by constants times
Σ n )
Σ
e 5/nr
5/m
exp
no
n2
n4
i fg===1 8=i1
This completes the proof of Proposition 3 below.
modulo the proof's of Lemmas 6 which we supply
B.1 PROOF OF LEMMA 6
Fix an input Te to N. We will continue write as in 2 y( for the vector of pre-activations as layer corresponding to æ. We need the following simple Lemma.
Lemma 11. With probability 1, either there exists that yl 0 or, for every i E [d], [m,] we have yj +0 40.
Proof. The argument is similar to Lemma in Hanin Rolnick 2019). Namely, fix [d]. [n:]. (()) * 0 for every f, then there exists at least one path 7 in the computational graph of the map + Vi contained in the union over all non non-empty subsets of the collection of paths the computational
(i) so that, y > 0 for each L = 1,..., - 1. For event that y = 0 is therefore
graph of x + 0/ of the event that
EII ( = 0.
For each fixed this event defines co-dimension set the space all the weights. Hence, since the joint distribution of the weights has density with respect to Lebesgue measure (see just before the union of this (finite number) of events has measure This shows that on the even that
(7) A for every f, y + O with probability 1. Taking the union over i, completes the proof. D
Lemma shows that for our fixed æ, with probability 1, the derivative of each 5) in 19 vanishes.
Hence, almost surely, for any edge in the computational graph of N
ON aw
Táp
wt(r)
(x)
(47)
W
TEN1
This proves the formulas for KN, 22 To derive the result for AKN, we write
dc
AK
Σ
KN
OW.
oW.
odges
18

---

Published as a conference paper at ICLR 2020
where the loss L on single batch containing only x is (N(x) (=))) We therefore find
ON ON aN
2A
Σ
(N(x) ( (x))..
oW., OW dw,, aw
edges 61.02
Using
47 and again applying Lemma
we find that with probability 1
ON
wt(2))wt(72)
Σ
Σ
La
aw OW c1
We
a=1
NET 01eaE7,e17te
Thus, almost surely
Ih wt(()))
AKN = Σ
II
Tas Σ
Σ
2X
W2 W
ac aE(no] k=l
(T)
E
e2 e2E72:78 c17612
3
I wt(Tk)
(xxx))
Σ aE(no] k=1
II
Fak
Σ (E)
Σ
W W2
61 EM-
e2E1p-7a
61762
To complete the proof Lemma 6 therefore remains check that this last term has mean 0. To do this, recall that the output layer of 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.
B.2 PROOF OF LEMMA 7
Lemma is almost a corollary of of Theorem 3 in Hanin (2018) and Proposition 2 in Hanin & Nica (2018). The difference is that, in |Hanin (2018): Hanin & Nica (2018), the biases in N were assumed to have a non-degenerate distribution, whereas here we' ve set them to zero. The non- degeneracy assumption is really necessary, the necessary modifications.
repeat here the proof from Hanin (0188) with
If 0, then (xx 0 for any configuration of weights since the network biases all vanish. Will We have from Lemma that
therefore suppose that x +f O. Let us first show 200
wt(nw)
E[KN(z, x)]
Σ aE[no]²
Toy Taz
Σ
Σ
E
(48)
W
FET
<ETI
a,even
To compute the inner expectation, write Fj for the sigma algebra generated by the weight layers up and including j. Let us also define the events:
Sy = (z #0}.
where we recall from 2 that x ( are the post-activations in layer j. Supposing first that is not in layer d, the expectation becomes
(1)
(u >0) 1 1
E
>0)
(idd Fa-1 71
W2
72
We have
(d)
(d) 72
Fa-1
71
nd-1
(ddd-1)=ra(d-) (1))=(2)))
Thus, the expectation in (48) becomes
1
(n (oidd-))=((d-1)) times 21 (d)=
W!(!)
(0) 00}
E
W22
E
W (d- 1)
(v
11
Fa-2
19

---

Published as a conference paper at ICLR 2020
(d-1)
Note that given Fa-2, the pre-activations yj Hence,
of different neurons in layer d - are independent.
II k==
W 72
Fa
rild - 1) + 72(d - 1)
w(a-1)
74
1844
1 >0}
Fu-2
E
2003
I W Wile-1)
(3ix
(1 D0}
>0}
Fa-2
n(d 1(d-1) = 72(d 1)
Recall that by assumption, the weight matrix W(d-1) in layer d equal in distribution to (d-1)) This replacement leaves the product I W(d-1) unchanged but changes 1 [041-)>00 >0)
to ( {o)' On the event Sa-1 (which occurs whenever Vhx (d-2) > 0) we have that y/1
(d-l) *
with probability since we assumed that the distribution of each weight has density relative to Lebesgue measure. Hence, symmetrizing over =W(d), we find that
E
d 1)
Fa-2
1 (d (1(d-1)= nd-2 (=((d-2)=ra(d22]
Similarly, if e is in layer i, then we automatically find that y1 1) giving an expectation of 1/n--11f m1()==a(()
72(1 1) and (1) = 72(1),
Proceeding in this way yields
(- 1)(f-1)=12(i-1)
[[KN(z,2)) = Σ
Faz
Σ
8 ==
i=1 n
aE/ng]2
rEr
auenen (i eemm
d
Σ
Fay Toz
12
n4-1
=E(ng]2
rer
which is precisely (0).. The proof' of (1 and 22 are similar. We have
I I wt(7k)
E[KN (2, 2) =
II Iat Σ
Σ
W2 W2
a aE(no]4
rEr e2E73.74
As before let first assume that edges e1, 62 not in layer d. Then,
d-1
II wt(Tw)
Th
(onk
19
>0)
E
Wid) %
Fa-
The the inner expectation is
1
each weight appears an even number of times
P4
n2
In contrast, if f(c1) É(ez), then the inner expectation is
1 f each weight appears an even number times n
Again symmetrizing with respect to + ( and using that the pre-activation of different neurons are independent given the activations in the previous layer we find that, on the event {v (d-2)
0),
12-1r(d11) 1)1
E
W (dd-1)
1) Coh
1>00]
Fa-2
1 f each weight appears
n
where L is the event that [[d - 1)1 = [Td)
= 1 and C1, e2 are not in layer d 1. Proceeding in
this way layer at time completes the proofs of 21) and (22).
20

---

Published as a conference paper at ICLR 2020
B.3 PROOF OF LEMMA g
Fix j = 1,... 4, edges 61,62 with {(ei) S f(e2) in the computational graph of N and E E L evenn The key idea is to decompose into loops. To do this, define
i0 --1, (B) = minfi > 4-11 [LE(O)
[R(E())) - 2}, k 2 I,..., :.....,#loope. #loops
For each i ,,.... . there exists unique &: 1, ................................ #loops(E) that ik 1 S < (F)
We will say that two layers i,j ,,..., d belong the same loop of E if exists 1,..., #loops(E) so that
i (E) S i.j (E).
We proceed layer by layer to count the number of r E 1
eveevn satisfying r(0) 01 and E E. 1) [m,-1]* and we have L(E(t)) 2. Then I 1) is
To do this, suppose we are given some permutation of (011 01,, 022 02) with 01 f az. Moreover, for j = 1,2 there is a unique edge (with multiplicity 2) in E(i) whose left endpoint is (j. Therefore, I(i 1) determines [(i) when 1, then E(i) consists of a single L(E(i)) = 2. In contrast, suppose L(E(i)) -(; (1). In short, r(1) determines r(j) for edge with multiplicity 4, which again determines I(i all belonging
1. If R(E(i))
the same loop of E i. Therefore, the initial condition r(()) aj determines ((1) for all i S i and the conditions e1 E 71, 62 E 72 determine in the loops of F containing the layers of e1, C2
Finally, suppose L(E(1)) = 1 and R(E(1)) = 2 (i.e. i = (EE for some = 1,...., d) and that 6, are not contained in the same loop of E layer i. Then all (2) = 6 choices of r(i) satisfy I(1) R(E(i)), accounting for the factor of 6 #E)) The concludes the proof in the case j = 1. the only difference in the cases j = 2, 3, 4 that if 71 (0) + (2( (and hence 7a(()) + (4)),, then since ((e)) < ((e2) in order to satisfy e1 E 71. 72 we must have that i, (E) < ((e)).
B.4 PROOF OF LEMMA 9
The proof of Lemma D is essentially identical to the proof of Lemma In fact it is slightly simpler since there are distinguished edges e 62 consider. We omit the details.
C PROOF OF PROPOSITION 4
In this section, we seek to estimate E[K,], E[K E[Aph]. The approach is essentially identical
to but somewhat simpler than our proof of Proposition 3 in B We will therefore focus here on
explaining the salient differences. Our starting point is the following analog of Lemma [ which gives sum-over-pane -ver--at expression for the bias contribution Kù to the neural tangent kernel. To state it, let define, for any collection Z (21....,24) E z of is neurons in N
A
(vz>0) = II 1 20)
j=1
to be the event that the pre-activations the neurons 2 are positive. Lemma 12 (Kp as sum over paths). With probability
KB
Σ zez
L1200
Σ II wt(()),
(49)
PEL
where Z Pizzz wt(?) are defined in AA Further, almost surely,
Abb 0.
(50)
The proof of this result is a small modification of the proof of Lemma and hence is omitted. Taking expectations, we therefore obtain the following analog Lemma
21

---

Published as a conference paper at ICLR 2020
Lemma 13 (Expectation of Kb, Kg as sum over paths). We have
B K| = 2 Σ Σ H(T),
H(T)
mm=y
(51)
2
74-1
ZEZ' TEl cvn [=(um))
(=8(2)+1
Moreover,
E|K = E
E
I(T),
2
2=)
TET (2,
((F1)S((2))
where for = (71,...,7)) E T (((2,)),een eevn)
we have
(((2)
2
A(r) = II
1 m( m(')==((1)) n (=22)
II
1 (100)--6))
(52)
ni_1
"=((=:)+1
(m (0(f--))=2(""-010
(1-
The proof identical to the argument used in B.2 to establish Lemma 7 so we omit the details. The relation (51) is easy to simplify:
E[K,]
E Σ ZEZ1 TE ;=((2)+1
II
1 1 d Σ
R4-1
2
[d([2)
2
where we used that the number paths from neuron in layer l to the output of N equals I[ Ti- This proves the first statement in Proposition Next, let us explain how to simplify E[K The key computation is the following
Lemma 14. Fix two neurons 21, 22 with {(21) S ((22) and write (21, ž1, 22, 22). Then,
d
Σ
H(T) = Me(2))
exp
1
1+0
Σ
(53)
[=((=a)+1 m
TEr Z,even
Proof. The proof of Lemma 14
is a simplified version of the computation of [[K2] (starting around 24 and ending the end of the proof of Proposition 3 Specifically, note that for I
(Y....., 74 E Zeven with ((21) < {(22), the delta functions I (>)(t')==x("") (ox (1')))))= (1)
E
in the definition (22) of (T) ensures that 71 "22 go through the same neuron in layer f(22). To
condition on the index of this neuron, recall that we denote by 2(j, B) neuron number 3 in layer
j. We have
{(22)
Σ TET4
AT())
Σ
Σ
II
1
m m((') ((())==2(1"))
H(T)
(x (1((--))=2((-11) f
A=l Thi (1(22))))) +=((+))1
rET4
2 .coon
Σ
H(T),
(54)
71(1a)-1 B=1
rErL
2even
where Z' = (=((((2)), =({=z)), and
d II
201122
H(T)
ni_
Ha
1 1000))r00000
i=f(aa)++1
Since the inner sum in 54 is independent of 3 by symmetry, we find
Ā(())
(1((2))
Σ H(T),
(55)
nH(())1 DELL
PED
evvenn
even
22

---

Published as a conference paper at ICLR 2020
where = 22). The inner sum in (55) is precisely of the terms I, from 27 without counting terms involving edges c1, C2, except that the paths start at neuron layer { The changes of variables from I E I even to E D to V I that used to estimate the I are no far simpler. In particular, Lemma still holds but without any of the A in, i2), C(E, b1, 12), C(E, 81, 12) terms. Thus, find that
Σ
H(T)
2
Σ #(E)6#hoppcE
Σ
H(V) H(V))#loppsV)
BE
VET 2'
where for the second estimate applied Lemma 9 and have written z"H 22). Thus, as in the derivation of (42)
we find that
Σ TER
H(L) & [H.(V)),
((22)
where
H. 2#(1e|d ( (fE(d) [[((-I)=VV[=== 14g
and E the expectation over pairs of paths starting from neurons 1, 22 in layer {(22) to the output of the network for which neurons in subsequent layers are chosen independently and uniformly among all neurons in that layer. This is precisely the expectation we evaluated in the end of the proof for Thus, applying Proposition exaatly in that case, we find that
Proposition 3
Σ
F(T)
exp
5
d
+0
I
)
rEr
seen
((2))
++
14
1++
n
Putting this together with 554 completes the proof of Lemma 14
Lemma 14 combined with Lemma 13
yields
1
1+0
Σ
exp
m
f,1=1
i=f+1
as claimed in the statement Proposition
D PROOF OF PROPOSITION 5
We begin by computing K wl We will use hybrid of the procedures for computing E[ and E K2). Recall from Lemmas and 12 that
2
I wt(1k)
K₁ Σ (Nz200
Σ
II wt(w)),
Kw
Σ
II Fax Σ
Σ
W
ZEZI
rer?z.2)
aE(no]²
rer T=(11.7)
cEM1.72
Therefore, the expectation of the product B[K,Kw] has the following form
Ii wt(rk)
Σ
II
Fas Σ Σ
Σ
E 1 (82200
W?
aE[na]2 Am
ZE2 (ET(2, eE78-74
Here, for neuron Z and (a1,az) [nu]? we've denoted by I4 (Z,2,)) the set of four tuples (f....,,74 74) of paths in the computational graph of N where 71 72 start from Z and 73 74 start at neurons d1 42 respectively. The analog of Lemmas 7 and 13 (with essentially the same proof), gives that the expectation in the previous line equals
|
((2)
d
22-10(1
1 (ms(0==ma))
II M--1 i=((2)1
n My
1=1
23

---

Published as a conference paper at ICLR 2020
which, up to multiplicative constant equals
((2) ||>|² II 1 (1))))=(0))
22-1r(0) tree -1-1001-11)
Gz(T)
P4
(56)
14-1
i=((2)+1 ni_1
1=1
which is independent of e. Thus, find
E Kw]
|
ΣΣ Σ
G2(T)T3,
2m ZEZ1 reT (2.2...))..o
where r (.,,..,, Y4 we recall that (T)) the indicator function of the event that paths pass through the same edge in the computational graph of N at layer i (see (29)).
As before, that the delta functions (())())=x()) ensure that 73: 74 pass through the same neuron in layer ((Z). Thus, may condition the common neuron through which na 74 must pass at layer ((Z) to obtain that [w is bounded above and below by a constant times
|>|| d 7o
||>|||
Σ Σ
Σ
Gz(TTTT,a
ΣΣ
Σ
E @2(TYTaA(T)
i=1 ZEZ' TET (2, (2,21;)).oom
i=
ZEZ
8=1
PET 2i,enon
where 7' = (2, ((()), =((()))) and we have set
22-17(01
Gz(())
II
1 uie ((rG-DD-IrO) D1-IrG) -1)
P4
Th
i=((2)+1
Notice that T3. 1 i < (()). Moreover, for i 2 E(Z) 1, the same argument as in the proof of Lemma 8 shows that the number of I TT3,cwey,
.ewen for which 73, 74 pass through the same edge layer and correspond to the same unordered multiset of edges E equals
#looop((E) (110)))
(o))s(
As in the proof of Proposition 3 observe that Gz(T))T),, depends only on the unordered multiset
of edges ET in I. Thus, find that
d d|l
E[K,Kw]
Σ
(ZZZ)
Σ
Gz(E)6 loops F))
no
ZEZ
RE 2f Jeven
Applying Proposition 10 as in the end of the proof of Propositions 3 and 4 conclude
(1+0
d Σ
Σ
BEEN
(((2)
2
exp
i=1(Z)+1
T4
n
Hence,
d
| nip
Σ
K[
exp
exp
1 1+
i=1 Yhs
To complete the proof of Proposition the proof of Lemma
it remains to evaluate E/Awh)
To do this, we note that, as in
6
we have
I wt(Tn)
Awb
Σ aE|na]" a=(a1 .22)
Tak
Σ 1 182203
Σ
Σ
W2
1=1
ZEZI
TEr (Z.z..).0))
eE
plus term that has mean 0. Therefore, as in Lemma 7 we find
|| Σ EE Σ
E Awwbl
P(T) # (edges belonging to both 72, 73).
n20
2E2' TE2
(2.2..
24

---

Published as a conference paper at ICLR 2020
where
((2)
(--
P(T) = II
II (=(1))+1
(1(0-)))1)))) =1)
7
(r((=1))77a(-11 (7(1)=74(0)
n
i=1
Thus, we have
2 d
E Awl
Σ (E))
{r r even 72(f- 10-s-11))
E===B -1())=a(11)
Yio
i=1
ZEZ
EEE 2 jenen
where (E) is as in 29 the sum is over unordered edge multisets E (see ) and we've set
Z' (Z, (0,
As in Lemma the counting term satisfies
= (0)) # {I 12 2', even 72 ())a)(()))))))))))))
where C(E,i,) was defined in 32) and is the event that there exists a collision between layers j. (i.e. there exists ......J. . E[Aww] at the end of the proof of Proposition 3 we find
so that (()) 1). Proceeding now as in the derivation of
))
E[Awb] ~
exp
Tu
e
1 na
1+0
Σ 1=1
ThE
n2
1,1=1
This completes the proof of Proposition
25


Reviews:
[{"review_id": "rJxfij46tS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the finite depth and width corrections to the neural tangent kernel (NTK) in fully-connected ReLU networks. It gives sharp upper and lower bounds on the variance of NTK(x, x), which reveals an exponential dependence on a quantity beta=d/n, where d is depth, and n is hidden width. This implies that when beta is bounded away from 0, NTK(x, x) is not deterministic at initialization. The paper further analyzes the change of NTK(x, x) after one step of SGD on a single datapoint x, and shows that the change also depends exponentially on beta.\n\nNTK has been a popular subject of theoretical study in deep learning, and it's an important question to understand when and to what extent NTK can capture the behavior of real neural networks. This paper makes partial progress by analyzing the diagonal entries of the NTK in fully-connected ReLU networks. It concludes that NTK(x, x) at initialization is not deterministic, and can change significantly after doing one SGD step on x, when beta is bounded away from 0. While it's nice that the authors obtained precise answers to these two questions, there are some drawbacks that limit the significance of this paper:\n\n1. The entire paper only considers one single datapoint x, so it doesn't apply to the non-diagonal elements NTK(x, x') or the usual SGD with mini-batches containing multiple datapoints. Of course, it's already implied by the current paper that the NTK is not deterministic and can move a lot when beta is large, but it's unclear whether the reverse is true, i.e., what is the regime when the NTK becomes deterministic and frozen when an entire dataset is involved. An answer (even empirically) to this question would make the paper much more complete.\n\n2. The result is also not so surprising given [Hanin, 2018] (and possibly some other papers by the same author) which also obtained a similar exp(beta) dependence using a similar combinatorial approach.\n\n3. Minor issues regarding incorrect or missing references:\n-- \"Further, kernel method-based theorems show that even in this infinitely overparameterized regime neural networks will have non-vacuous guarantees on generalization (Wei et al., 2018).\" The result of Wei et al. is not about kernel method and in particular not NTK.\n-- \"In fact, empirically, networks with finite but large width trained with initially large learning rates often outperform NTK predictions at infinite width.\" The authors should refer to the work of [Arora et al., 2019] which AFAIK is the first paper that provides empirical study of the (convolutional) NTK predictor at infinite width on relatively large datasets like CIFAR-10.\n\n[Hanin, 2018] Which Neural Net Architectures Give Rise to Exploding and Vanishing Gradients?\n[Arora et al., 2019] On Exact Computation with an Infinitely Wide Neural Net\n\n\n--------\nupdate: Thanks to the authors for the detailed reply, which answers most of my questions. I am updating my rating to weak accept in light of this.\n\nRegarding Wei et al.: Their result on NTK is negative, i.e., they aimed to show that NTK is inferior to regularized NN. I find the way you cited this paper a bit weird. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJx2scAsYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is an important contribution to understand finite depth and width corrections to the NTK. The authors show that the diagonal terms of NTK remain stochastic when depth and width approach infinity at the same rate. \n\nNTK [1] is one of the most exciting discovers for extremely over-parameterized NNs in the last year. In the single limit setting, i.e. fixing depth and letting width -> infinity, the [1] showed that the NTK converges in distribution to a deterministic kernel and remained almost unchanged during gradient descent.  This regime is known as the kernel regime or linearized regime, where the training dynamics of the NN is well-approximated by its first order Taylor expansion. \n\nIn this paper, the authors show that in the double limit regime, i.e. depth/width = \\beta and depth, width -> infinity, the diagonal terms of the NTK, as well as the first gradient step, is NOT deterministic. More precisely, they upper and lower bound the second moment of the diagonal terms of NTK (and first gradient step) through the temperature \\beta. Their method builds on the `\"sum-over-path approach\" developed in [3], etc. \n\nOverall, this is a very interesting result, proposing a new scaling limit that gradient descent dynamics can be highly nontrivial (i.e. not in the kernel regime.) and NNs can possibly learn useful representation. \n\nOther comments: \n1. It will be very helpful to have some experiments to support the main theorems in the paper since the proof is quite involved. \n2. How difficult is it to compute the off-diagonals? Is it possible to obtain other statistics of of the NTK, trace, max eigenvalue, etc. \n3. Is it possible to extend the results to other non-linearities, e.g. Tanh? \n\n\n[1]Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- ´\neralization in neural networks. In Advances in neural information processing systems, pp. 8571–\n8580, 2018.\n[2] Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient\ndescent. arXiv preprint arXiv:1902.06720, 2019.\n[3]Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture.\nIn Advances in Neural Information Processing Systems, pp. 571–581, 2018", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJlnf573Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates a novel infinite width limit taking depth to infinite at the same time. This is beyond conventional theoretical studies for infinite width networks where depth is kept finite when the width is taken to be infinite. The main object that paper studies is the neural tangent kernel which is of great interest to the theoretical deep learning community as it describes gradient descent dynamics in a tractable way.\n\nWhile standard NTK becomes deterministic in the infinite width limit, when both depth and width are simultaneously taken to infinity this paper shows that NTK is no longer deterministic. Moreover authors show that gradient descent update induce non-negligible change to the Kernel. \n\nThere are two main limitations of otherwise significant work. One is generality of sums over path method used here beyond ReLU/Fully connected/single input setting. It is a very powerful technique allowing tight upper and lower bound for variation of diagonal entry of NTK. I worry that the method may be too specific to the particular network setting. Still this does not eclipse the strong results it could say for ReLU networks. \n\nSecond limitation is lack of empirical check. I understand it may be non-trivial to simulate double scaling limit and theoretical contribution alone could be significant progress. I still believe that empirical support should be a strong foundation of science of neural networks and this paper would improve even with some toy model implication of simultaneous depth/width limit. One might particularly wonder, for sufficiently deep/wide network that we could train on our computer, can we observe effects of d/n ( or \\sum_i  1/n_i)?\n\nQuestion:\nI did not quite comprehend the alluded connection to double descent curve with data-dependent features in section 3.2. Could you elaborate?\n\nnit : Dyer&Gur-Ari’s workshop paper is from the 2019 ICML workshop instead of 2018. \np3 sentence below eq (5) unnecessary ‘them’ in the end of line.    \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to study the mean and variance of the neural tangent kernel (NTK) in a randomly initialized ReLU network. The purpose is to understand the regime where the width and depth go to infinity together with a fixed ratio. The paper does not have a lot of numerical experiments to test the mathematical conclusions. In the discussion the reviewers concurred that the paper is interesting and has nice results but raised important points regarding the fact that only the diagonal elements are studied. This I think is the major limitation of this paper. Another issue raised was lack of experimental work validating the theory. Despite the limitations discussed above, overall I think this is an interesting and important area as it sheds light on how to move beyond the NTK regime. I also think studying this limit is very important to better understanding of neural network training. I recommend acceptance to ICLR.
Decision: Accept (Spotlight)