Asymptotics of Wide Networks from Feynman Diagrams
Authors: Ethan Dyer
Guy Gur-Ari
Venue:  (2020)

Abstract: Understanding the asymptotic behavior of wide networks is of considerable interest. In this work, we present a general method for analyzing this large width behavior. The method is an adaptation of Feynman diagrams, a standard tool for computing multivariate Gaussian integrals. We apply our method to study training dynamics, improving existing bounds and deriving new results on wide network evolution during stochastic gradient descent. Going beyond the strict large width limit, we present closed-form expressions for higher-order terms governing wide network training, and test these predictions empirically.


Published as a conference paper at ICLR 2020
ASYMPTOTICS OF WIDE NETWORKS FROM FEYNMAN DIAGRAMS
Ethan Dyer & Guy Gur-Ari'
Google
Mountain View, CA
Sedyer, @googgg.ooocooooooooooooooomm
ABSTRACT
Understanding the asymptotic behavior wide networks of considerable interest. In this work, we present general method for analyzing this large width behavior. The method is an adaptation Feynman diagrams, standard tool for computing multivariate Gaussian integrals. We apply method study training dynamics, improving existing bounds and deriving new results on wide network evolution during stochastic gradient descent. Going beyond the strict large width limit, we present closed-fon expressions for higher-order terms governing wide network training, and test these predictions empirically.
INTRODUCTION
Neural networks achieve remarkable performance on a wide array machine learning tasks, yet a complete analytic understanding of deep networks remains elusive. One promising approach is to consider the large width limit, in which the number of neurons one or several layers taken to be large. In this limit one use mean mean-field approach to better understand the network's properties at initialization (Neal (1996); Lee et al. (2018)) 8)), as well as its training dynamics (Daniely (2017); Jacot al. (2018) 8)). Additional related works cited below.
Suppose that fxx) is the network function evaluated at an input x. Let us denote the vector of model parameters by 0, whose elements are initially chosen be i.i.d. Gaussian. In this work we consider class of functions we call correlation functions, obtained by taking the ensemble averages of f, its products, and its derivatives with respect the parameters 8, evaluated on arbitrary inputs. Here are a few examples of correlation functions.
(1)())) 0f(22)
((()))
(f(2)
82 (x)))) d0r ago s(xa))
Ey [f(x))((22)
ΣE,
Eo
Σ $4.20
Eo
(1)
06
O0"
Correlation functions often show up in the study of wide networks. For example, the first correlation function in (1) plays a central role in the Gaussian Process picture of wide networks (Lee et al. (2018)), and has been used to diagnose signal propagation in wide networks (Pennington et al. (2017)). The second example in (1) is the ensemble average of the Neural Tangent Kernel (NTK), which controls the evolution of wide networks under gradient flow (Jacot al. (2018)), and the third example shows up when computing the time derivative of the NTK with MSE loss.
While correlation functions can be computed analytically in some special cases (Cho & Saul (2009)), they are not analytically tractable in general. In this work, we present a method for bounding the asymptotic behavior of such functions at large width. many cases of interest, the bound we obtain is tight. Derivation of the method relies on Feynman diagrams (Feynman (1949)), technique for calculating multivariate Gaussian integrals, and specifically on the Hooft expansion ('t Hooft (1974)). However, applying the method is straightforward and does not require any knowledge of Feynman diagrams.
The method presented here is general- seneral-purpose tool that be added to researcher's toolbox. It allows a researcher to quickly identify ways in which network behavior and training
Motivation.
"Atthors listed alphahetically.

---

Published as a conference paper at ICLR 2020
dynamics simplify large width, for example by deriving which quantities vanish in this limit. As we demonstrate, using this method one is able to dramatically cut down on the amount of effort required to derive several key results related to wide networks, well as to go beyond the infinite width limit and investigate ordinary neural networks.
Our contribution.
1. We present general method for bounding the asymptotic behavior of correlation functions. The method is an adaptation of Feynman diagrams to the case wide neural networks. The adaptation involves novel treatment of derivatives of the network function, element that is not present in the original theoretical physics formulation.
2. We apply the method to the study wide network evolution under gradient descent. We improve existing results for gradient flow (Jacot al. (2018)) by deriving tighter bounds, and extending the analysis to the case of stochastic gradient descent (SGD). Going beyond the infinite-width limit, network evolution, and present explicit formulas for the first order correction. To our knowledge, this is the first time this correction has been calculated.
present formalisn for deriving finite-width corrections to
3. As additional applications of our method, in Appendix E.2 we show that in the large width limit the SGD updates are linear in the learning rate, and in Appendix E.3 we discuss finite width corrections the spectrum of the Hessian.
Limitations of our approach. The main result of this paper is a conjecture. We test our predictions extensively using numerical experiments, and prove the conjecture in some cases, but we do not have proof that applies to all the cases we tested, including for deep networks with general non- non-linearities Furthermore, our method can only be used derive asymptotic bounds at large width; does not produce the width-independent coefficient, which is often of interest.
Related work. For additional works on wide networks, including relating them to Gaussian pro- cesses, de G. Matthews al. (2018); Novak et al. (2;19); Maariga-Alonso et al. (2019); Yang (2019); Pennington & Bahri (2017); Pennington & Worah (2018); Schoenholz et al. (2017); Xiao et al. (2018); Chen al. (2018); Daniely al. (2016); Lee et al. (2019); Du al. (201 8b;a); Allen-Zhu et al. (2018). For additional works discussing the training dynamics of wide networks see Geiger al. (2019a), Arora et al. (2019). For a previous of diagrams in this context, see Pennington & Worah (2017). The Neural Tangent Hierarchy presented in Huang & Yau (2019), published during the completion of this version, has significant overlap with the recursive differential equations (10) presented below.
The rest of the paper is organized as follows. In Section we present our main conjecture and supporting evidence. In Section 3 we apply the method to gradient descent evolution of wide networks, and in Section we present details on Feynman diagrams, which is the basic technique used in our proofs. We conclude with Discussion. Proofs, additional applications, and details can be found in the Appendices.
Note: An earlier version of this work appeared in the ICML 2019 workshop, Thcoretical Physics for Deep Learning (Dyer & Gur-Ari (2019)).
CORRELATION FUNCTION ASYMPTOTICS
In this section we present our main result: a method for computing asymptotic bounds on correlation functions of wide networks. We present the result conjecture, supported by analytic and empirical evidence.
2.1 NOTATION
Let f(x) E IR be the network output of deep network with d hidden layers and input a Rr.,.
defined by
f(x) -n=nn-'/4 -1/20T (
on 1/2 (U)))))
(2)
2

---

Published as a conference paper at ICLR 2020
..... Here U E Ru VE R", Wi...., W are weight matrices of dimension and a R + R is the non- con-lincarity.' We denote the vector of all model parameters by 8. At initialization, the elements of 0 are independent Gaussian variables, with each element 0 ~ (0(0,) 1). The corresponding distribution of is denoted by Po-
Let us now define correlation functions, the class of functions that is the focus of this work. These functions involve derivative tensors of the network function. We denote the rank-k derivative tensor by TyI...m (x; f) == 0h
/00m / ... 0000 For k 0 we define T(; = f(x), and still refer to this as a derivative tensor for consistency.
Definition 1. A correlation function is the expectation value of product of derivative tensors, evaluated at arbitrary inputs, where the tensor indices are summed in pairs over all the model parameters. A general correlation function C takes the form
C( Cmm)
Σ
A Mk...Kmmm
...T Tumm Eg [Tr...pe,, (2i)Tpp,++ (22) ...
(Zm)
1+1... 1
Here, 0 S ki S ... S km-1 S Km are integers," 3 m. and kim are even, E Skip is a permutation, and A (x)
p1....pmm (p(cs)(eca)" ""0pttt -1)(tt)))) (1)) We ö to denote the Kronecker delta.
two derivative tensors in correlation function have matching indices that are summed over, we say that they contracted. For example, the correlation function E,, Eg (z) Of (z2))/00)) has one pair of contracted tensors. See (I) for additional examples of correlation functions.
2.2 ASYMPTOTIC BOUNDS ON WIDE NETWORKS
We now present our main conjecture, which allows us to place asymptotic bounds on general correlation functions of wide networks.
Let C(zi...., Im) be correlation function. The cluster graph Gv(V, E) of C is graph with vertices V = {vi,.... :.m) where v; T(x:) for all i, and edges F. = (1us, 05) (T(x)), T(x;)) contracted in C}- Suppose that the cluster graph Gc has nh connected components with even size (even number of vertices), and no components of odd size. Then C(II,..., Imm = On" where
Conjecture 1.
Ro
SC = ne
(4)
We will refer the connected components of a cluster graph Ge the clusters of C. Table lists examples of bounds derived using the Conjecture for several correlation functions. The intuition behind Conjecture comes from the following result for deep linear networks.
Theorem 1. Conjecture holds for correlation functions of networks with linear activations, includ- ing for deep linear networks with biases (affine transformations).
Let us discuss the intuition behind this theorem. Computing correlation functions of deep linear networks amounts to evaluating Gaussian integrals with polynomial integrands in A. One can evaluate such integrals using Isserlis' theorem, which tells us how to express moments of multivariate Gaussian variables in terms of their second moments. For example, given centered Gaussian variables 21, 24.
Eg [1 [4] = E, [2] Eg [232a] + E. [2] [3] Eg [2> + E, [2] Eg [222g]
(5)
Therefore, correlation functions of deep linear networks can be expressed terms of the covariances
Es Use] deg0upp Eg [VVV]] dig, and Eg [w w 61z621. For example, for deep linear network with 2 hidden layers, we have
Eo [f(x))(((2))
- _E V'
of x2
Σ
Eوrō = xF x2
(6)
n²
i.k
We take all layers widths to be equal to n for simplicity, hut our results hold in the more general case where all widths scale linearly with We use μt, v.... denote indices, i.J.... to denote individual weight matrix and weight vector indices,
and a, 3 for input dimension indices.
When ka ka-1s 1, the tensor T(xaa has no derivatives.
3

---

Published as a conference paper at ICLR 2020
Every correlation function of deep linear network can be similarly reduced to of Kronecker delta functions and indth-independent functions of the inputs. The asymptotic large over delta functions, which are tedious to compute by
products
width behavior is determined by these hand. Feynman diagrams are a graphical tool for computing these sums, allowing us to obtain the asymptotic behavior with minimal effort. This tool, which is deseribed in detail in Section is used to prove Theorem 1.
For networks with non-linear activations we further show the following
Theorem 2. Conjecture holds for (1) networks with ReLU activations, where all inputs are set to be equal, and for (2) networks with one hidden layer and smooth activation.
For case (1), the idea behind the proof is put an asymptotic bound the ReLU network in terms of a corresponding deep linear network. For case (2), the basic idea is that each network function contains single over the width, and by keeping track of these sums using Feynman diagrams we are able to bound the asymptotic behavior. We refer the reader to Appendix C for details.
2.3 NUMERICAL EXPERIMENTS
Table lists asymptotic bounds on several correlation functions, derived using Conjecture These are compared against the asymptotic behavior computed using numerical experiments. In addition to the results presented here, we performed experiments using the same correlation functions and experimental setup, but with weights sampled uniformly from }+1} instead of from Gaussian distribution. The results are shown in Appendix A.
In all cases that were tested empirically, found that Conjecture holds. For networks with smooth activations, we found that Conjecture always gives a tight bound. For networks with linear or ReLU activations, always find that the Conjecture holds is not tight. One such case is highlighted in Table 1. In such cases, a tight bound can be obtained for deep linear networks using the complete Feynman diagram analysis presented below.*
upper bound, but that sometimes the bound
Correlation function C
The nn
$C
lin.
ReLU
tanh
Es [((1))((2))]
0,2
0
-0.02
0.003
-0.02
EA ((a)))(
0,4
0
-0.01
0.03
-0.03
Σ, E. (,
1,0
0
0.00
0.00
0.00
En Ea
0,2
-1
-0.98
-1.03
-1.01
Enpo Eo (0.f (e.0f
1,0
-1
-2.01*
-2.01*
-0.98
En.oo Bo (0, (
0,2
-2
-2.05
-2.01
-1.99
Table 1: Examples of bounds on correlation functions obtained from Conjecture 1. The 3 right- most columns list numerical results for fully-connected networks with 3 hidden layers and with linear, ReLU, and tanh activations. The values listed in these columns are the fitted exponents for networks with the corresponding activations. The entries marked with an asterisk are those for which the predicted bound is not tight. The numerical results are obtained by computing the correlation functions for networks with widths 27, 2a, 2 each averaged over 1,000 initializations, and fitting the exponent. Inputs are chosen to be random vectors of dimension 4.
3 APPLICATIONS TO TRAINING DYNAMICS
In this section apply Conjecture to study the evolution of wide networks under gradient flow and gradient descent. We begin by briefly reviewing existing results. Let D,y be a training set of size M,
'For deep linear networks, the proof of Theorem I relies on mapping diagrams to triangulations of 2D surfaces with at least I boundary. There are cases, such as the one highlighted in Table 1, in which all diagrams write down have at least boundaries. In such cases, the full diagrammatic calculation gives tight hound, while Conjecture provides valid upper bound that not tight.
4

---

Published as a conference paper at ICLR 2020
and let L = (L.))D, ((x.y) v) be the MSE loss, with single sample loss {(2,8) = (f(()) y)²
The gradient flow equation is de flow is given by
VoL. The evolution of the network function under gradient
df Σ (e",)")
al(x'.v') 0f
x
dt
Here, O is the Neural Tangent Kernel (NTK), defined by (2), == (zi"( The authors of Jacot et al. (2018) showed that the kernel is constant during training up to O(n O(n-1/3) 1/2) corrections. This leads to dramatic simplification in training dynamics (Jacot al. (2018); Lee et al. (2019)). In particular, for MSE loss the network map evaluated on the training data evolves as f(t) y + -100)) (f(0) y). We will use our technology to derive tighter bound on wiith corrections to the kernel during training and present explicit formulas for the leading correction.
The following result is useful in analyzing the behavior of correlation functions under gradient flow.
Lemma 1. Let C(²) = Eg [T) be a correlation function, where (æ1,..., Tmm) and suppose that = O(n*)) for sc as defined in Conjecture Then Eg dd F(Ø) O( for all
dt
Here we prove the statement for k 1. Appendix D.2 contains proof for the general case.
proof (k: = 1). Let C have ne even clusters and n, odd clusters. Consider Eg (FF()) Tar(a) af(=')
de
- -xp Er'D, Eo a 06 [(x'). Denote by ni (n') the number of even (odd) clusters in this correlation function, which has m' m + 2 derivative tensors. One can check that either (n', n2,)) (ne 1, no) or (n's n',) (ne 1 1, n. + 2). depending whether the Fr.F' derivative is acting on an odd or even cluster in F.6 Therefore, n' + n/ m' S sC.
2
With this result, it is easy understand the constancy of the NTK at large width. The first derivative of the NTK is given by
Eg
d (01, 22)
Σ
Ea
f(r))) 0f(z2) 0f(z')
s(ot)) 00
(x) ++ 22).
(8)
dt
O0
D' p.v
Here, (I1 <> x22) means "add the same term, but exchange 21 and x.2". This correlation function has n, = 0, n. = 2, and m 4, and is therefore O(n by Conjecture 1. By Lemma 1, all higher-order time derivatives of the NTK are O(n-1) ) as well. If we now assume that the time-evolved kernel (() analytic training time 4, and that we are free to exchange the Taylor expansion in time with the
large width limit, then we find that E, [O(I) O D
O(n 1) for any fixed f. This bound, which is tighter than that found in Jacot et al. (2018), was noticed empirically in Lee et al. (2019) as well as in our own experiments, see Figure la.
T Eg
d'O(w)
dia
This analysis can be extended to show that Eg [@(t) {(0)] Onn for SGD as well. The technique similar, and again relies on Conjecture 1. We refer the reader to Appendix E.1 for details. These results improve on existing ones in several ways. Our method applies to the case of SGD as well as to networks where all layer widths are increased simultaneously - a setup that has proven to be difficult to analyze. In addition, the O(z bound we derive on kernel corrections during SGD is empirically tight, and improves the existing bound of -1/22) which was derived for gradient flow (Jacot al. (2018)).
$ 'eere are using condensed notation: (0) and (()) are values initialization, and f. ((), y are treated as vectors in training set space. The kernel e (0) is a square matrix in the same space. 'Here are extending the of the term cluster refer derivative tensors in the integrand itself.
5

---

Published as a conference paper at ICLR 2020
3.1 FINITE WIDTH CORRECTIONS
Next, we will compute the explicit time dependence of θ and f at order O(n under gradient flow. This is the leading correction to the infinite width result. We define the functions O₂ (ar) == f(x) and
O,( Ix) = Σ 10.-1 vs 0f(x,)
s 2.
(9)
00,
30
Notice that O₂ θ is the kernel. easy to check that
dO, 10,........................... dt
Σ Ost1 Rs (f((()) - -)), 8 s21.
(10)
We can use equations (9) and (10) to solve for the evolution of the kernel and network map. Notice that each function O, has s derivative tensors and a single cluster. As result, correlation functions involving operators with larger are increasingly suppressed in width. In particular, E& [dOa/da -' D., Es [Os( = On 2) at all times, using Conjecture and Lemma 1. Thus to solve for f and 6 at (nn we can set O. - 0 for all 8 2 5.
Let us denote the time-evolved kernel by @(t) = ( + (1)) + (( where ()) is the kernel at initialization, and O₃ (f) is the Onn-1) correction with 4, we find
seeking. Integrating equations (10) starting
θ (11, = S dt' EoS (2),
zED.
J di' 1" di" Σ
1 (x1, "'d
(11)
2,''EDu
Here we have introduced the notation Af = c (f y). A detailed derivation can be found in Appendix E.4. There we also evaluate the integrals in (11) in terms of the NTK spectrum.
To obtain the On= correction to the network map (evaluated for simplicity on the training data), we further integrate (10) for s = and find
f(1) fo(() c c6 S at' d' O (t')e -t')e- (f(0) y) + On
(12)
Here we have denote the infinite width evolution by fo(1) = y e -1000) (f(0) - 1). Figures and I compare these predictions against empirical results.
[tan actioacion)
HB2)
6.40
274
Sab311
2.a
3.06
0.30
2-1
vee 23l Impeeee 0013 tas jepeact:
3.00
6.20
21
11P
107
107
10
stegs
strgi
(a) Mean deviation from init.
(b) beyond leading order.
(c) Kernel evolution.
Figure I: Empirical verification of predicted asymptotics. (a) The mean deviation of the NTK from its initial value for a variety of widths and activation functions. The (dashed) matches well with the predicted OOn-1) asymptotics. (b-c) Comparison between the empirical evolution (solid) and the O(n predicted evolution (dashed) for the network function and the kernel. All experiments were performed two-class MNIST, computing single randomly-chosen component of O f. See Appendix A for additional experimental details.

---

Published as a conference paper at ICLR 2020
U
E
V
(a)
(c)
Figure 2: Feynman diagram examples. (a) The Feynman diagram of Eg [f(=) (b)((c) The
Feynman diagrams of E& [f(z)) (x44)] additional, equivalent diagrams are not shown.
4 FEYNMAN DIAGRAMS FOR DEEP LINEAR NETWORKS
In this section we present the Feynman diagram technique, and show how it allows us to compute the asymptotic behavior of correlation functions. We end this section with proof of Theorem for the case of networks with a single hidden layer and linear activations.
Given correlation function C, map it to family of graphs called Feynman diagrams. The graphs are independent of the inputs, and are defined as follows.
Definition 2. Let C( Jm be a correlation function for a network with d hidden layers. The family (CC) is the set of all graphs that have the following properties.
1. There are vertices v1..... U.m, each of degree d 1.1
2. Each edge has type t E (W VJ. Every vertex has edge of each type.
3. If two derivative tensors Tpr.....p (I:). Tyr (x,) contracted k times in C, the graph must have at least k edges (of any type) connecting the vertices v4, Vz-
The graphs in (C) are called the Feynman diagrams C.
Single hidden layer. For the rest of this section we focus networks with a single hidden layer. We refer the reader to Appendix for a full treatment of deep linear networks. For networks with one hidden layer and linear activation, the network output f(x:) = n -11222/Tux Consider the correlation function C(11, = Eg [f (xz)) We have
Din
(2
Ey [VVj (Via Uza] 21
òijōrj 2 22
(13)
As the factors of 1 and 22 are independent of n, we see that C(zi, x2) O(n²). Notice that there are two relevant contributions to this answer: each factor the network function in the integrand contributes n 112 and the summed-over product of Kronecker deltas contributes n. Other details, such as the input dependence, are irrelevant. Feynman diagrams allow us encode only those details that affect the n scaling, ignoring the rest.
The set I'(C) for the correlation function (13) consists of single Feynman diagram, shown in Figure 2a. The asymptotic bound on a correlation function obtained by the following result, which is due to 't Hooft (1974).
Theorem 3. Let C(11...... Im) be correlation functioonn with one hidden layer and linear activation. Then C O(n)) where s max,er(c) L 2
m.. and ly is the number of loops in y.
Let give some intuition for Theorem 3. Each Feynman diagram encodes subset of the terms contributing to the correlation function. To get the asymptotic bound on the correlation function, we sum over the contributions of individual diagrams. We compute the asymptotic behavior of single diagram using the following Feynman rules: (1) each vertex contributes factor of n 1/2 and (2) each loop contributes a factor of n. Therefore, a diagram has I,, loops, its contribution to
For networks with single hidden layer, the number of loops in diagram is equal to the number of connected components. This not true for general deep linear network.
7

---

Published as a conference paper at ICLR 2020
44
V
(a)
(h)
Figure 3: Feynman diagrams for Es (0 z²)] with one hidden layer. The dashed vertical line represents vertices forced by contracted derivatives.
the correlation function scales n/-- Rule (1) is due the explicit n/1 factor in the network definition. Rule (2) follows from applying Isserlis' theorem, as follows. Each covariance factor (such the factor E [VVV,] dig in eq. (13)) corresponds to edge in Feynman diagram. A loop in the diagram corresponds to a sum over a product of Kronecker deltas, yielding a factor of n.
recover the asymptotic behavior (nn²) from Theorem 3. As another example, consider the correlation function C(x1, 222 33, x44 Eg (x))
Returning to our example, the graph in Figure 2a has two vertices and one closed loop,
(x.)]. It has two Feynman diagrams, shown in Figures 2b and 2c, Using the Feynman rules, we find that the disconnected graph represents terms that scale as (nn)), while the connected graph represents terms that scale as O.. Therefore, C(r,, 22, T3, v4) (nn)). This is an example of a more general phenomenon, that connected graphs vanish faster at large n compared with disconnected graphs.
Correlation functions with derivatives. We extend the Feynman diagram technique cor- relation functions that include derivatives f. As a concrete example, consider the correlation function C(r, x/) Eg (0(r, where θ is the kernel defined in Section 3. For single hidden layer, we have
a
T)()) ((()))(())) af(x) [[())) OU;
C(I,I')= Σ Eg
(14)
au. av, av.
The two derivative tensors in this correlation function are contracted: their indices are set to be equal and summed over. Therefore, according to Definition 2, I'(C) includes all diagrams in which the corresponding vertices share at least one edge. The resulting diagrams are shown in Figure 3. The edges forced by the contraction are explicitly marked by dashed lines for clarity, but mathematically they are ordinary edges. We see that in fact there is only one diagram contributing to this correlation function the same one shown in Figure 2a. Following the Feynman rules, we find that IEg [0(z, x²)] = (nn)).
The fact that contracted derivatives should be mapped to forced edges in the Feynman diagrams is proved in Appendix B. The basic reason behind this rule is the relation Σx av, av, aV, aV, σ, E [VV]). Namely, when derivatives act in pairs they yield Kronecker delta factor (6.g). which is equal the factor obtained from a covariance (E [VVV)). While Isserlis' theorem instructs us to sum over all possible covariance configurations (and therefore over all possible edge configurations), a pair of summed derivative leads to particular covariance factor. Therefore, we should only consider graphs that include the edge corresponding this covariance factor.
We are now ready to prove Theorem for the case of single hidden layer with linear activations. A proof for the general case can be found in Appendix B.
Proof (Theorem 1, one hidden layer). Let C(r be correlation function for a network with a single hidden layer and linear activation. Let Gv(V, F) be the cluster graph of C, and let 7(V,"" E') E I(C') be a Feynman diagram. Notice that E C E.. Indeed, E' con- tains an edge corresponding to each pair of contracted derivative tensors in C. and E = {(v,, vy)) (T(),), contracted in CJ. In addition, notice that y only contains connected
'We are not aware of a physics application in which such derivatives are included in Feynman diagram description of correlation functions. Therefore, to our knowledge our treatment of these derivatives is novel both in machine learning and in physies.
8

---

Published as a conference paper at ICLR 2020
components (f.e. loops) with even number of vertices, because every vertex has exactly one edge of each type. Therefore, ny I ne + Bh. where n. is the number of loops in y, and ne (n is the number 2.
of even (odd) components in Gg. The bound is saturated when every even component of Ge belongs to different component of y and pairs of odd components in Ge belong to different components of
y. From Theorem 3, we have that C (n²) where max,er(C) "l S fl Bl.
5 DISCUSSION
Ensemble averages of the network function and its derivatives are an important class of functions that often show up in the study of wide neural networks. Examples include the ensemble average of the train and test losses, the covariance of the network function, and the Neural Tangent Kernel (Jacot al. (2018)). In this work we presented Conjecture I, which allows one to derive the asymptotic behavior of such functions at large width.
For the case of deep linear networks, we presented complete analytic understanding of the Conjecture based on Feynman diagrams. In addition, we presented empirical and analytic evidence showing that the Conjecture also holds for deep networks with non-lineat activations, as well as for networks with non-Gaussian initialization. We found that the Conjecture holds in all cases we tested.
The basic tools presented in this work can be applied many aspects of wide network research, greatly simplifying theoretical calculations. We presented several applications of our method to the asymptotic behavior of wide networks during stochastic gradient descent, and additional applications are presented in Appendix E. We were able to improve upon known results by tightening existing bounds, and by applying the technique to SGD as well as to gradient flow. In addition, we took a step beyond the infinite width limit, deriving closed-fome expressions for the first miith correction to the network evolution. These novel results open the door to studying finite- width networks by systematically expanding around the infinite width limit.
central question in the study of wide networks is whether the infinite width limit is good model for describing the behavior of realistic deep networks (Chizat et al. (2018); Ghorbani et al. (2019); Geiger et al. (2019b)). In this work we take step toward answering this question, by working out the next order in a perturbative expansion around the infinite width limit, potentially bringing closer an analytic description of finite-width networks. We hope that the techniques presented here provide basis to systematically answering these and other questions about the behavior of wide networks.
ACKNOWLEDGEMENTSS
The authors would like to thank Alex Alemi, Yasaman Bahri, Boris Hanin, Jared Kaplan, Jaehoon Lee, Behanm Neyshabur, Sam Schoenholz, Sylvia Smullin, and Jascha Sohl-Dickstein for useful discussion. The authors would especially like to thank Ying Xiao for extensive comments on early versions of this manuscript.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 18/ 1.03962, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019.
Minmin Chen, Jeffrey Pennington, and Samuel S Schoenholz. Dynamical isometry and mean field theory of rnns; Gating enables signal propagation in recurrent neural networks. arXiv preprint arXiv:1806.05394 2018
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. arXiv e-prints, art. arXiv: 1812.07956. Dec 2018.
Youngmin Cho and Lawrence K. Saul.
Kerel methods for deep leam- URL http:://apeet nips. cc/ /aperr// 3628 2628-kernee -method- for-forrdeee coor-deep-ine lea eeeerrnnnng.g.. .ddf.
ing. pp. 342-350, 2009.

---

Published as a conference paper at ICLR 2020
Amit Daniely. Sgd learns the conjugate kernel class of the network. In Advances in Neural Information Processing Systems. pp. 2422-22222222 2430, 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks:
The power of initialization and dual view expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2261 2016.
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference Learning Representations, 2018. URL https::tp... opwnrevieee net/ forum? -ndemmm-----------
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: /8/1 I.03804, 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018b.
Ethan Dyer and Guy Gur-Ari. Asymptotics of wide networks from feynman diagrams. In Theoretical Physics for Deep Learning, ICML Workshop. 2019. URL
http://vvvvv..o.lll.leeeoooo google.......oooooooooooooo.o... com/ http:////wkkbbbRnggggg 2zN http://hhhh.aaao....oooooo.oeo/a Xtt.aa/......tt..yyooaaoooo/a//a
R. P. Feynman. Space time approach to quantum clectrodynamics. Phys. Rev., 76:769-789, 1949.
doi: 10. 10.1103/hhysRe..6.7666 [.99(1949)].
Adria Garriga-Aonsso Carl Edward Rasmussen, and Laurence Aitchison. networks as shallow gaussian processes. In International Conference on Learning Representations 2019. URL www.ttttt//c...... /otp::::///pereevileeee net/ forum? d=Bk s OcKm.
Deep convolutional
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' A'Accoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. arXiv preprint arXiv: /901.01608 2019a.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy learning in deep neural networks: an empirical study. CoRR, abs/1906.08034, 2019b. URL http://arxiv. org/ abs/ 08034.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. arXiv preprint 1rXiv:1901.10159 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of Lazy
Training of Two-layers Neural Networks. arXiv e-prints, art, arXiv: 1996008899) Jun 2019.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in tiny subspace. arXiv preprint arXiv: 18/iv:88//.000 82.04554, 2018.
Boris Hanin and Mihai Nica. Products of many large random matrices and gradients in deep neural networks. arXiv preprint arXiv: 18/2.0999/ 2018.
Jiaoyang Huang and Horn--Tze Yau. Dynamics of deep neural networks and neural tangent hierarchy, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. arXiv e-prints, art. arXiv:1806.0757,, June 2018.
Jachoon Lec, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak. Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. In International Conference on Learn- ing Representations, 2018. URL htt.tttt//pppeeeiiiieeeee// net forum Pid=B1EA-M-O0 oz.
Jachoon 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 Descent. arXiv e-prints, arXiv: 1902.0670.0 Feb 2019.
Radford M. Neal. Priors for Infinite Networks, pp. 29-53. Springer New York, New York, NY, 1996. ISBN 978-1-4612-0745-4 doi: 1-0079978-1-411-0745541 URL https: //ooi. org/o0/gl00oo /10. 1007/978-1-4612-000
10

---

Published as a conference paper at ICLR 2020
Roman Novak, Lechao Xiao, Yasaman Bahri, Jachoon Lee, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jaseha Sohl-dickstein. Bayesian deep convolutional networks with many channels gaussian processes. In International Conference Learning Representations, 2019. URL
httpss: wpwpeeeeeeeeeeeeeeeeeeeeeeeeeeee net wwt.r///oeeermmme forum? d=B1 g30 j0qF7.
Vardan Papyan. Measurements three-level hierarchical structure in the outliers spectrum of deepnet hessians. arXiv preprint urXiv:190/ 19011992044 2019.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pp. 2798-2806, 2017.
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learn- ing. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 2637-2646. Curran Associates, Inc., 2017. URL http: /wwppaaappppppeppeeeepeeeeeeeeee .iis..ipp...... cc/ pacppppr////// G857-nond weellinn---rre randon-naaaaae -attimmmaaiiiiiiii theory for- der--deep-o searning..ple
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of a single-hidden- layer neural network. In Advances in Neural Information Processing Systems, pp. 5410-5419, 2018.
Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. CoRR, 0tbb//711.04735.. 2017. URL httt:://arizs org/
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning; Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint 1rXiv:1706.04444 2017.
Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. correspondence between random neural networks and statistical field theory. arXiv preprint 1rXi::7110.06570, 2017.
Gerard 't Hooft. A Planar Diagram Theory for Strong Interactions. Nucl. Phys., B72:461, 1974. doi: 10.1016/0550-32111 901-0055500-211339995544400 [,337(1973)..
Lloyd N. Trefethen and David Bau. Numerical Linear Algebra. SIAM, 1997. ISBN 0898713617.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. arXiv preprint /ttivv/800.05399 2018.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1rXiv:1902.047700 2019.
A EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
A.I NON-GAUSSIAN INITIALIZATION
In Table we listed asymptotic bounds on several correlation functions, where the model parameters were initialized from Gaussian distribution. Table 2 shows additional results using the same experimental setup, but with weights sampled uniformly from {+1}. We again find good agreement with the predictions of Conjecture
11

---

Published as a conference paper at ICLR 2020
Correlation function C
Re: Ro
SC
lin.
ReLU
tanh
Es [f(z))((a2)
0,2
0.00
0.00
0.02
Eg (1aa)
0,4
-0.07
0.06
-0.02
En Bo (0
1,0
0.00
0.00
0.00
Enp Eo
0,2
-1
-1.02
-1.01
-0.97
Envr Ea [0n]
p (m4)]
1,0
-1
-2.00
-1.99
-2.02
En.o Eo (Opf(a)) jou (1z2) (2s))p (z (1
0,2
-2
-2.05
-2.01
-1.99
Table 2: Examples of bounds on correlation functions obtained from Conjecture 1. The experimental setup is the same in Table I, but the model parameters are sampled uniformly from {=1} instead of from Gaussian distribution. We find good agreement with the theoretical predictoins, and in many cases the bound tight.
A.2 EXPERIMENTAL DETAILS
The experiments in Figure were performed on two-class MNIST, computing a single randomly- chosen component of the kernel Ô Sub-figure (a) uses networks trained for 1024 steps with learning rate 1.0 and 1000 samples per class, averaged over 100 initializations. Each curve in figure (b) represents single instance of the network map evaluated training. The models were trained with 10 samples per class and learning rate 0.1. The input to the network is normalized by the square root of the input dimension as (Jacot al. (2018))
random image over the corse of
f(x) nn=)=
1/2 Ux))))
(15)
B FEYNMAN DIAGRAMS FOR DEEP LINEAR NETWORKS
Feynman diagrams be used to derive asymptotic upper bounds deep linear networks in the large width limit. In this section we describe the method in detail, and use to prove Theorem 1.
B. FEYNMAN DIAGRAMS AND DOUBLE-LINE DIAGRAMS
In this section we build on the results of Section 4 and consider correlation functions of deep linear networks with d hidden layers. The network function was defined in (2), and here we set the activation be the identity. Definition 2 describes how map correlation function graphs called Feynman diagrams. The Feynman diagram method relies on Isserlis' theorem, which allows us to express arbitrary moments of multivariate Gaussian variables in terms of their covariance.
I'(C), a family of
Theorem (Isserlis). Let (Zi...., 21) be centered multivariate Gaussian variable. For any positive integer k.
1
Eg [2t, 2tok
Σ
E [2 2enca)) E (1 ... ... [2e (2 Slo
(16)
2 k!!
TE
Eg 2/,
Zizk-1 0.
(17)
In particular, if the covariance matrix of z the identity then
1
E2 [Zgg
Zigel
Σ
(18)
2k
Using this theorem, a correlation function C can be expressed as a sum over permutations as in (16).
Each term in this sum maps to Feynman diagram in I(C).
12

---

Published as a conference paper at ICLR 2020
W
W
V
(a) Feynman diagram
(b) Double-line diagram
Figure 4: Feynman diagrams for Eg (x')) with 2 hidden layers. Notice that the U, V edges in the Feynman diagram map to single edges in the double-line diagram, while the W edge maps to double edge.
As example, consider the correlation function C(x, x²) Eo (xx)) for network with hidden layers. An explicit calculation gives
n
Din
C(I,I')
Ee [VW]UuaVAWWllii zao's
(19)
n²
k.jikul 0,,
By [V.V]]] Ew [W.. Will Eu (Uja U1s) 2a
(20)
R.j.k,l
xf n
digdek Σ = On
x-
(21)
n
1.1=1
To get from (19) to (20), we applied Isserlis' theorem for every choice of indices i, k. (, a, 3. We find that there is at most one permutation т of the network parameters such that the covariances do not vanish. This is because the covariance of parameters across different layers vanishes identically (for example Eg VWW3 jk
0). Correspondingly, this correlation function has single Feynman
diagram, shown in Figure 4a.
For networks with one hidden layer, saw in Section 4 that the asymptotic behavior is determined by the number of loops in a graph. This observation does not immediately generalize to networks with general depth, because it is not obvious how to count loops in diagrams such the one in Figure 4a. The problem can be traced back to the fact that weight matrices have covariances of the form E [Way sy W&] = 5z involving two Kronecker deltas, but the procedure described far assumes that each covariance (and each edge in the graph) corresponds to single Kronecker delta.
similar question appeared in the context of theoretical physics, and the correct generalization is due to 't Hooft (1974). The idea is to treat each Feynman diagram as the triangulation of a Riemann surface, and to define the number of loops in a graph to the number of faces of the triangulation. In practice, this involves mapping each Feynman diagram to a new double-line diagram: A graph in which each edge corresponds to a single Kronecker delta factor, and loops correspond to triangulation faces of the original diagram.
Definition 3. Letry E [(C) be a Feynman diagram for a correlation function C involving k derivative tensors for network of depth d. Its double-lin graph, DL(7) is graph with kd vertices of degree 2, defined by the following blow-up procedure.
(0) ..... Each vertex (( in y is mapped to d vertices
"....., (0 dd in (T.(7)-
Each edge (u(9, wli)) in y of type U is mapped to single edge u(())
Each edge (w w05) in y of type W is mapped to two edges (vz (1) u ())), (0i+1) o/41)-
(0)
Each edge (1()) ( in ry of type V is mapped to a single edge (v) Ud (i))
The number of faces in y is given by the number of loops in the double-line graph DL(7).
Figure 4 shows the Feynman diagram and corresponding double- -ine diagram for Ep (x) fx')] with 2 hidden layers. We can interpret this Feynman diagram triangulation of the disc: a 2-dimensional
13

---

Published as a conference paper at ICLR 2020
surface with single boundary. The triangulation has 2 vertices, 3 edges corresponding to the edges of the Feynman diagram, and faces correponding to the loops of the double- diagram. Figure shows additional examples of double-line diagrams, and Figure 6 shows the double-line diagrams of a correlation function with derivatives. As explained in Section 4, contracted derivative tensors in correlation function C' map to forced edges in I(C), and these marked with dashed lines the diagrams.
U
U
W
W
W
W
17
V
V
(a)
(b)
Figure 5: Double-line diagrams for IEs (oae)) for deep linear network with hidden layers.
W
W
w!
Figure Double-line graphs describing the expectation value the NTK, E, [+), for a deep linear network with two hidden layers. Crossed edges mark the edges that are forced by contracted derivatives. The derivative can act on either U' V. or W and therefore there are three diagrams. Each diagram has vertices and 2 faces, and therefore the correlation function is Onn)) according to the Feynman rules.
Generally, every Feynman diagram of deep linear network can be interpreted as the triangulation of 2-dimensional manifold with at least one boundary. Intuitively, the presence of the boundary is due to the fact that the U, V weights at both ends of network have only one dimension that scales linearly with the width. As result, in the double-line diagrams the U, V edges become single lines rather than double lines. These 'missing" lines translate into fewer faces the triangulation, and 'missing' faces can be geometrically interpreted as boundaries in the corresponding surface."
The discussion above is summarized by the following result, due to 't Hooft (1974), that describes how the asymptotic behavior of general correlation function can be computed using the Feynman rules for deep linear networks.
Theorem 5. Let C( IIm) be a correlation function of a deep linear network with d hidden I(C') be Feynman diagram. The diagram represents subset of terms that
layers, and let contribute to C, and its asymptotic behavior determined by the Feynman rules: the subset is O(n*)) where 8y = l1 2
dm and by is the number of loops in the double-line diagram DL(7). Furthremore, the correlation function is C O(n"), where maxxer(()) Sy.
The intuition for the formula s. = dm is similar to the single hidden layer case, Theorem 3. The 2
term I,, counts the number of factors of the form Σx....ix Si Biiz Saui, that appear in the dm is due to the explicit n -d22 2
Correlation function after applying Isserlis' theorem. The term normalization of the network function.
One can consider the cyclic model f(x) = =n (d411/22222))1 Tr (VWd-1... (enpll...wwi)) w'
with ID input æ, in which
all the weight tensors Ú, V, W ..... W dd-1 are X n matrices. The Feynman diagram construction for this model is similar to the deep linear case, except that all edges in the Feynman diagram map to double edges in the double-line diagrams. Such diagrams can be interpreted as triangulations of surfaces with no boundaries. Unlike the deep network diagrams, they have no 'missing' loops.
14

---

Published as a conference paper at ICLR 2020
B.2 ASYMPTOTICS OF DEEP LINEAR NETWORKS
We now prove Theorem 1. The theorem follows from the following lemma, again due to 't Hooft (1974), that relates the asymptotic behavior to the number of connected components in Feynman diagram.
Lemma 2. Let C(x,,-..,IIw be correlation function for a deep linear network. Let Cy be the number of connected components of graph 7 T(C). Then C O(n"), where
max Cy (EI(C) 2
(22)
Proof. We prove the result for ID inputs (Din = 1), and it is easy to generalize to arbitrary input dimension. Let T(C) be Feynman diagram and let be connected component of y with by vertices. Notice that we can apply the Feynman rules of Theorem 5 separately to each component y and find bound O(n**), ). Then, y (n**)) where 8, Eye 8yy, and the runs over the
m Eyf and therefore 8y S Cc T connected components of 8yy We will show below that By < 2 which is sufficient to prove (22).
Let us prove the remaining statement about 8yy. The Euler character of the graph 7 with v = Vy vertices, edges and / faces is X = 0
The degree of each vertex in the graph is d 1, and therefore e [d+11c Using Theorem the graph Onn*v' where Sny = = f 2 We therefore find that X 2 Sy, The graph 7 is triangulation of some connected surface with at least one boundary. The Euler character for such a surface is bounded by X S 1, and therefore sy I 1 g O
2"
Let us now prove Theorem 1.
Proof. Let C(II,..., Tm) be a correlation function for deep linear network. Suppose that the cluster graph Gc has ne even size components and n. odd size components. Let y E I(C) be Feynman diagram with cy connected components. We will show that c, S nu + no It then follows m T concluding the proof.
immediately from Lemma 2 that = O(n)) where ne + The
2
Let us derive the bound on Cy. First, all vertices that belong to a given cluster (a component of Gc) will also belong to the same connected component in 7. This is because every edge in Ge also an edge (note that Ge and have the same set of vertices). Therefore, c, ne + nh. Second, note that every connected component of the graph y has an even number of vertices. Indeed, each edge has type f, and each vertex has exactly one edge of each type. Therefore, connected component with v vertices has edges of each type, and so e must be even. follows that the vertices of even clusters can form their own connected components in Feymman diagrams, while odd clusters must be connected in sets of or more to form connected components. The bound on then follows.
For deep linear networks with bias the proof is the same, except we use Lemma 3 below instead of Lemma 2.
B.3 DEEP LINEAR NETWORKS WITH BIAS
In this section we argue that Conjecture holds for deep linear networks with bias. Let us add bias to the definition (2) of deep linear network (setting to be the identity). We choose without loss of generality. The activations z at layer 7 and the network function f are given by
= = U, - 1+1 n 1//2 +1/ 1 1= -.....,d11
(23)
(24)
1
(25)
Here 67....,6d- 6d-1 E R" are biases whose elements are chosen independently from A/ 1) at initialization. The network function can be written
d+1
(k- 1)/2 1)/2 w Wdd2-kkdt1-2
(26)
2=2
15

---

Published as a conference paper at ICLR 2020
b²
b
V
V
W
W
(a) Feynman diagram
(b) Double-line diagram
Figure 7: New Feynman diagrams for E.
with 2 hidden layers and bias.
where we defined 8 U. In the rest of this Section we extend our definitions of Feynman diagrams and double-ling line diagrams to deep linear networks with bias, and then extend several of our results to this case.
Definition 4. Let C( Im) ) be a correlation function for a network with d hidden layers and bias. The family I(C) is the of all graphs that have the following properties.
1. There are verlices 01 , Um, where each vs has degree ka .2....,
2. Each edge has type t. Every vertex of degree h. has one edge of each type {bd+1-k, Wd+2-k ,..., Wdd1,VV
3. If two derivative tensors T pu must have at least edges (of any type) connecting the vertices U/ Vj.
(x.)) (xx), (es),Tri..an Ter..ee (2z) are contracted s times in C, the graph
The intuition behind this definition is that term k in the sum in (26) is equal to the network function of a deep linear network with depth i 1. Correlation functions of such function can be represented diagramatically by including vertices of degree k. To represent the entire sum must consider all diagrams with vertices of varying degree.
We now extend Definition of double-line graphs to accommodate vertices with varying degree. Definition 5. Let
T(C) be Feynman diagram for correlation function C involving derivative tensors for a network of depth d with biases. Its double-line graph, DL(7)) is a graph with vertices of degree 2. defined by the following blow-up procedure.
Each vertex (1) in 7 of degree k; is mapped to k; vertices of ...., U ki-1 in DL(7).
(1)
Each edge (v(9), [00) in y of type W is mapped two edges, (o (i) (1) (vi dd),
(014k d-1 -4k;-d-1) and
( Each edge (olt), vl0) in y of type 1d+1-k, is mapped to single edge (vf ((t)) (notice that K; = kz))
( Each edge (u(9), ((5)) in y of type V is mapped to single edge (1 1zy1)).
As in Definition 3, the number of faces in y is given by the number of loops in the double-line graph DL(r).
Figure is an example of the new single line and double line diagrams that appear in the correlation function Eg (f2) (==)) (f=)f(=.)) for two-hidden-layer network with biases.
Let us now extend Theorem 5 (the Feynman rules) to accomodate bias. The only difference is explicit normalization. Previously, each vertex had degree d + and contributed a factor of n dd2 due to the explicit normalization of the function map. With biases, result of (26), vertex with degree & contributes a factor of (k--1)// 11/2
Theorem 6. Let C( Fm) be a correlation function of a deep linear network with d hidden layers and with biases. Let T(C) be Feynman diagram. The diagram represents subset of
16

---

Published as a conference paper at ICLR 2020
terms that contribute C, and its asymptotic behavior is determined by the Feynman rules: the subset is (nn²)) where Sn - k with kę the degree of the i-th vertex, and by the number of loops in the double- diagram DI,(1). Furthremore, the correlation function C O(ne), where (C)) 8y.
We now introduce the following result, which generalizes Lemma 2 to the case of networks with bias. This Lemma is used above in the proof of Theorem 1.
Lemma 3. Let C(11,.... Jm) be a correlation function for deep linear network with biases. Let Ciy be the number of connected components of a graph ? E ET(C). Then C = Onz)), where
max CET(C)
Cy
(27)
Proof. It is enough to show that each connected component > in y is bounded Onz")) where 8y S " The graph 7 triangulation of a Riemann surface with f faces e edges, and by vertices of degrees ki,...,k, ,,,,, The Feynman rules give
8y
(28)
Using the relation
Eie
2 ki and the definition of the Euler character, X Vuy + f we have 1=
Syy
(29)
2
The diagram 7 is a triangulation of a Riemann surface with at least one boundary, thus x S 1 and Sy
C NON-LINEARITIES
In previous sections we presented the Feynman diagram method for computing the large width asymptotics of correlation functions. In this section we show that the method applies as-is for deep networks with ReLU non-linearities and all-equal inputs, as well as to networks with a single hidden layer, a broader class of lineariiss,,,,s, and arbitrary inputs. Theorem 2 follows immediately from the results presented in this section.
C.1 DEEP NETWORKS WITH RELU NON-LINEARITIES
The following result guarantees that the presence ReLU non-linearities does not change the asymptotic upper bound compared with linear activations, when all inputs the same.
Theorem 7. Let fal be network function of the form (2) with ReLU activation. Let f be network with the same architecture but with linear activation. Let C(#1..... "'.....,mm''.. fai) be correlation function the deep network fai with width n, and let f be deep linear network with the same width and depth. Suppose that all inputs are the same, I1 T2
Km. Then
C(21...., Zmi i fui) OC(( Zmi f))
(30)
Intuitively, we will rely on the fact that for ReLU networks we can, in some cases, treat the binary neuron activations being statistically independent of the weights. This result is due to (Hanin & Nica (2018)). Given this result, we can bound the contribution of the binary activations, and the remaining Gaussian integral is equivalent that found in deep linear network. The proof does not work for correlation functions with non-equal inputs, because in that case the independence result of Hanin & Nica (2018) longer holds.
Proof. We can write the network function
fa(x)) n -//2////1//0 (pb
(31)
(² - j=
(32)
17

---

Published as a conference paper at ICLR 2020
Here, H is the Heaviside step function acting elementwise on its vector argument. We now introduce the construction from Hanin & Nica (2018). Let e¹,7², .7,, j = l,.... be diagonal matrices of dimension n, whose diagonal elements =1-Berouuli(() variables with p z. We define the new variables
Ú==E'U, v== W = - j=
(33)
Let fui be network function with the same architecture as fat but using the re-defined weights. We define
fal(x) 1--4/// (.) (x)) ('(xUx
(34)
= =n -n 10 (² == -W p² := , ;= -......,
(35)
j=1....,
(36)
(37)
The following was shown Hanin Nica (2018).
1. fut and ful are equal in distribution.
2. (D), p. 1, , d' are independent of {U, V, W ..... Wd-1).
3. (z) = ,,...,d} are independent of each other for fixed æ. The diagonal entries of each diagonal matrix (z) are independent, and take the values {0, 1} with probability 1
Now, the correlation function can be written
C( Tmi i fui) = Eg [F(z1,.... Imi fui) = Eo.n. [F(e..... Emi fui)
(38)
The second equality follows from the fact that ful - ful. Let us assume for now that the correlation function has contracted derivatives. The we have
C(a Tmi ful)
Bo.n.
[aa((a1) ... fui (Zm)
(39)
Dmn
m
d-1
m
1)
m
E
II
W ba ser
EE
II
Un
Ei
(40)
n2dm/2
Here, - 161,1....
mm and o
{a1..... am and
m II J=1|=1
m
Ex =
Ply, D
Dty, (Iv))
II
x
(41)
In writing the equation (40) we used the facts that D,p are independent of the parameters, and that parameters in different layers are independent. We now Theorem 4 (Isserlis), which says that each of the expectation values over products of V. Wi, and U elements is equal to a sum over permutations, where each term is product over Kronecker delta functions the covariance matrices of the parameters.
Dm Σ ΣΣ
C(a1...., Rmi C fui)
A
Eg,a
(42)
m2dm/22
Here, A is product of Kronecker delta functions. The precise form of this object will not be important for purpose, though it can be easily derived using Theorem 4. can now bound the correlation function as follows.
Dun ΣV
(C fai)l S
Σ
E
(43)
n ddm/2
&
Din
Fmnax n dvn/
Σ
Σ
(44)
Emuxx
CCV, f[
(45)
18

---

Published as a conference paper at ICLR 2020
B and v E RPn is the all-ones vector. The diagonal elements of p', Dx(x) are identical variables. Therefore, E only takes (1) number of values in the large width limit. Note that each of these values are independent of n,, and therefore Emax O(1). We managed to bound the correlation function for fal in terms of the correlation function for the corresponding linear network f with fixed imputs. The asymptotics of the linear-network correlation function do not depend on the inputs, and therefore this concludes the proof.
Here, Emax = max
C.2 SINGLE HIDDEN LAYER NETWORKS
For networks with single hidden layer, defined by
fa( Σ VolluTa) ==1
x),
(46)
we can extend our asymptotic analysis to smooth non- non-lincarities, We will show Theorem that for any correlation function C, we have
C(21...., Emi fui) = O(C( Zmi f)),
(47)
where f a deep linear network of equal width and sufficient depth. Therefore, computing the asymptotics using Feynman diagrams for deep linear networks yields bound on networks with single hidden layer and smooth non-linearities
Before delving into the proof of this claim, consider a few simple examples. Let us begin with the correlation function Eo (f((())
Es (nn(s))s(((()
Σ n 1.j
Ea (VVo(UF()O(UU(
(48)
n n
E. (o(UT ()T z')1 O(1)
(49)
Here used two facts. First, the weights VÚ are unaffected by the non- non-linearity, so can carry the V integral. Second, the summand in the last equation, [o( (U? x')], is independent of both and because U; are i.i.d. variables.
Next, consider the following correlation function. For simplicity, here we set the input dimension to be Di, 1, and set all inputs to this does not change the asymptoties.
de
Su
3h 0.
Eg
Σ
Es
ful
dt
OU OU, OV.
J.k
Ea [V, Vi, a (U,, )o (Ui, )a' (U:))o(Uis))
n²
Eg ('',,,))'((
n
On
(50)
In the last line, we again used the fact that the summands are equal and independent of n. In general, a correlation function C(Ii,..., Imi fm) can be reduced to the form
K
C m2
(c)
(51)
Fi.ntra
s(a) tiuutrs
= Eu [(oltt (U.f ( (U? x ...x
( (fatt1- (UT
tr Fo (m+1--k,)) (f (nT (mm) ((i), Im)
(52)
19

---

Published as a conference paper at ICLR 2020
This form is obtained by carrying out the Vi integrals, well as all the sums that can be trivially carried out due to the presence of Kronecker deltas. Here, the a sum represents a sum over all K terms that appear from performing the V; integrals using Isserlis' theorem; (()) denotes the l-th derivative of the non- non-linearity; kg is the number of o (U? x) factors sharing the i, index; Ja E Sm is a permutation; and F(a) is a function whose exact form is not important for us. We will denote by Tmax the maximum number of index sums appearing in (51), namely ''ax max Ta-
Our approach to establishing the asymptotic scaling will be to first bound the maximum number of index sums appearing in any in our correlation function, written in the form (51), and then to argue that the summands are bounded by an n-independent constant.
Let introduce family of diagrams, (C)), which different in general than the Feynman diagrams. A given diagram g E (C) is constructed as follows.
Definition 6. Let C( Im, fni) be a correlation function, where fut is the output of a network with one hidden layer, defined in (46). The family I (C)) the set of all graphs that have the following properties.
Each derivative tensor in is mapped to a vertex in the graph.
Each edge has type that corresponds to one of the weight vectors U or V.
Each vertex has exactly edge of V type.
If two derivative tensors are contracted in C, the graph must have least one edge (of any rype) connecting the corresponding vertices for each contraction.
The reason for introducing this graphical structure is that allows us to make two important statements. we define Eg the number of connected components in a graph g e (C) and Emax max then the following holds.
1. The maximal number of sums appearing in a correlation function of the form (51) is mmax-
2. Čmax Cmax. where Cmax is the maximal number of connected components in the family of Feynman diagrams corresponding correlation function C(21, zm fa), where fa is deep linear network with d hidden layers, and d is large enough that none of the derivative tensors vanish."
These two results, combined with a bound on the summands occurring in ClEi, Tmi fat) will establish the bound (47).
Lemma 4. A correlation C has Tiax Čmar-
Proof. Each vertex corresponds derivative tensor, Ty.....u which contains a single sum over paired U, and Vú indices. If two vertices are connected by one or more edges, there a Kronecker delta factor that sets the corresponding indices to be equal (due either to derivative contraction, or to V covariance), reducing the number of sums by one. The result is that any connected component of graph g E ['(C") corresponds to a single sum, and the total numer of index sums corresponding to particular graph is Eg. the number of connected components. As a result, the maximum number of sums corresponding to the collection of graphs (C(C') is Čmux-
Lemma 5. The maximal number of connected components, Emax over the collection of graphs ('(C) corresponding to Clz Emi fui) is bounded by the maximal number of components, Cmaxo over the collection ICC) corresponding C(Z Imi fa) of Feynman diagrams, where fa is deep linear network of sufficient depth d.
Proof. Let (Ti.)) be the number of even(odd) clusters in the cluster graph Ge of C( Zmi Sa). The cluster graph, Ge a subgraph of any graph g E ['(C). We can thus think about the embedding of even and odd clusters into g. In any graph g IC(C), even cluster may belong to its own connected component, while for odd clusters there must be an even number of them in any connected
Note that any derivative tensor of f that has rank greater than d vanishes.
20

---

Published as a conference paper at ICLR 2020
component. This is because even (odd) cluster contains (odd) number of factors of V, which must be paired up in any connected component. We find that
no 2
Cmax = The +
Cmax
(53)
The last inequality was used below Lemma 2 in the proof of Theorem 1.
Theorem 8. Let C( Imi fui) be correlation function for one hidden layer network. Let Cmax be the maximal number of connected components over the collection of graphs T(C) corresponding to C( Emi Sa), where fa(x) is deep linear network map, with with depth greater than or equal to the maximum number of derivatives appearing in any single derivative tensor in C. Then C' O(n²) where Cmax 2 Furthermore.
C(ai. Fmi fnt) = (CC(I Tmi f)).
(54)
Proof. The correlation function in (51) can be bound as
K Σ
Fmm Smi)
Σ Fleeee
s(a) tennettr
(55)
m/
For fixed inputs, Sh....... can take at most (()) different values as function of its indices, and the values are independent of n. This is because the variables U, are identical. We define smax as the maximum value of (5(a) lemmas we can then write.
st....... as function of a and the indices. Combining this with the above
C(r,,.... Tmm fai)l S KS S Smn m/2
(56)
The result of the theorem follows from Lemma 2.
D CORRELATION FUNCTION ASYMPTOTICS
In this section we prove several general results about correlation function asymptotics in the large width limit. Throughout this section, assume that Conjecture holds.
D.1 VARIANCE ASYMPTOTICS
Conjecture can be used to bound the variance of the integrands that appear inside correlation functions.
Es ... Fmml be correlation function, and let Ge be the cluster graph of C with n. even components and n. odd components. Assume Conjecture holds such that C O(n*0), where sc n. ne -. Then Vara [.) 2522s))
Lemma 6. Let C(I1,...,
Proof. To bound the variance, it is enough to bound the correlation function
Ö(1 F2m) EE [Fo(z1..... (f........,,,..........
Im m Fo (Fmm F2m))
(57)
because Vara [F' (2 xm,..,,,,, S Č( Ims TI.... F.). The correlation function Ö has 2n. even clusters and 2n, odd clusters. follows from Conjecture that Ò O(n2cc).
As corrolary, notice that if C O(n*) according Conjecture 1, then typical realizations of the integrand will also be On**). In other words, the asymptotic bound of Conjecture holds for typical initializations, not just in expectation.
Table shows empirical results for the variance of several functions. In all cases we find that we prove tight bound below in
the bound of Lemma holds. For En Vara Appendix E.1 for deep linear networks.
21

---

Published as a conference paper at ICLR 2020
Function
Te: Ro
2sc
lin.
ReLU
tanh
Varg (f())
0,2
0
-0.08
-0.00
-0.02
Vare (oan)
0,4
0
-0.03
0.02
-0.05
Σn Varo (0
1,0
0
-1.01
-1.02
-0,99
Ene Vars (100) Eypo Varo [z, (0. Envio Vary (0,f(an) (00
0,2
-2
-2.1
-2.13
-2.14
1,0
-2
4.002
-4.1
-3.05
0,2
-4
-4.09
-4.14
-4.01
Table 3: Bounds on variances obtained from Lemma 6, where the predicted exponent is 2sc- compared with empirical results. The predicted exponent 2sc, and the right-most columns list the empirical exponents. The experimental setup is the same that of Table 1.
D.2 GRADIENT FLOW
The following results are used in the gradient flow calculations Section 3.
Lemma 7. Let G' be graph with m' vertices, n'e even components, and n', odd components. Let G be a subgraph of G' with m vertices, The even components, and n. odd components. Then s(Be, Doy m) 2 s(n',, n'g m²) where s(a, b, a
Proof. It is enough to show that s(ee, Ro; m) does not increase we (1) add a vertex to G, or (2) add an edge to G, because G' can be obtained from G by performing such operations finitely many times. Adding a vertex to changes The + Tl. no + n. + and m + m + leaving s(n,, No, m)
unchanged. Next, if we add an edge to G' then m does not change, and there are possibilities for how ne and n. change.
1. The edge connects even components. Then ne ト The no + no. and s(n No, m) decreases by 1.
2. The edge connects two odd components. Then + me + 1, + no - 2, and s(ne; Noy m) does not change.
3. The edge connects an even component and an odd component. Then nee + nh 1, no + no. and s(He, foo m) decreases by 1.
4. The edge connects two vertices that belong to the same component. In this case ne. Ro. and (n,,, Roy m) do not change.
We now prove Lemma giving the scaling of time derivatives of correlation functions at initialization. We prove the result for polynomial loss functions. Extension to general loss functions requires interchanging the large width limit and the Taylor expansion of the loss, which we do not discuss.
proof (Lemma 1). Notice that
= Eg (I
t F( Im)
dé(x', v/) 0f(x')))
Eg
Σ (D'
F(r Imm
dth
Of
00
D0
(58)
On the right-hand side we have a linear combination ΣA C.CA of correlation functions CA. where the coefficients depend on the training set labels. Here used the polynomial loss assumption. For each correlation function C',, its integrand can be obtained from F by finitely many operations of the form (1) multiply the integrand by f (zx) for some input v, and (2) act with pair of contracted
22

---

Published as a conference paper at ICLR 2020
derivatives two of the derivative tensors. In the cluster graph representation, these two operations
correspond to (1) adding vertex, and (2) adding an edge. Therefore, the cluster graph Ge of
C' = Eg [F] is subgraph of the cluster graph Gca of each one of the correlation functions CA. By Lemma 7 we have that CA ((n*c) for all A, and therefore the bound applies to EEg [d F/dt"] well.
as
D.3 STOCHASTIC GRADIENT DESCENT
In this section we show that the asymptotics of correlation function do not change under stochastic gradient descent (SGD) updates. Let C( [m,) Rg (f. ] be correlation function, where F9 is the integrand which explicitly depends on the parameters A. Under a single SGD step, the parameters time t. Let P. denote the distribution of parameters at step t, where Po is the initial distribution. We define the evolved correlation function at step to be
updated as 0++1 0g n V (.))),, where L is the mini-batch loss at
Ce(Ei,..., Im) == PE [F((II....,..
(59)
We have the following
Theorem 9. Let C correlation function for a network with linear activations, and assume that Conjecture 1 holds, namely C Onnec) where se is defined in the Conjecture. If C. is the evolved correlation function after SGD steps, then C. = O(n*0).
Proof. Notice that
C++1 E@-Pe+ Fel Eenp, [Fa-nvr(()]]
(60)
The integrand Fa can be written product of derivative tensors of the form Ta -y (2; 0), with contracted derivatives. Suppose that the network has d hidden layers. Then under an SGD step, we have
T Tu (z: v))((()
d+1
Σ
Σ
aL,
0L, Tn (x;
(61)
k!
00m
00
0=0
PL...Me
d+1
(-n)*
θh. oh,
Σ
Σ
0f(z1) 0f(z
k=0
Σ (z1 ... . (ar(2')) (4)) in wie P
(62)
Here DB is the mini-batch, and æy are mini-batch samples. The k sum is truncated because higher- order derivatives of vanish.
We can now see how taking a gradient descent step affects the cluster graph. After taking step, each derivative tensor in C. is replaced by sum (over k ./..... 2²))) Each term in the combination of these sums is a correlation function, whose cluster graph is subgraph C. Therefore, by Lemma C. = O()*)).
We note that for general activation functions the sum in (62) may be infinite. In this case, complete the proof we would need to show that the infinite sum obeys the same bound as each individual term in the sum. We leave this for future work.
E APPLICATIONS
Here we present several applications of our Feynman diagram method for computing large width asymptotics. We assume throughout this section that Conjecture holds.
23

---

Published as a conference paper at ICLR 2020
E.1 NEURAL TANGENT KERNEL
In this section we prove Two results regarding the NTK at large width. We show that the kernel converges in probability, and that during gradient descent it is constant up O(n corrections. Theorem 10. The Neural Tangent Kernel θ of a deep linear network converges in probability in the large width limit, and its variance is O ).
Conjecture is not sufficient for proving this theorem, as we need to use a more detailed Feynman diagram argument. Therefore, we only prove the theorem for the case of deep linear networks.
Proof. First, we will show that Var(o) O( On- Given model function f. the variance is given by
Var(O(z,=>)]
A(x, x')
B (xx,
(63)
(x) (x') (x) (x)))
A(x,²')= Σ
E
(64)
p
00p-
00,
00,
(x) of (x))
Ta (z) of
B(x, x²) =
E
(65)
00,
00
00,
00,
Here f())= = -... f(4) = we introduced the superscripts so we can easily refer to individual factors. The crux of the argument is that the set of Feynman diagrams representing the expression (63) includes only connected graphs. Assuming this is the case, according to the bound (22) these diagrams will all scale as (2 4)/2) = O(n 1) and so will the variance, completing the proof. To why only connected graphs contribute, notice that
Aax, .²) includes all diagrams in which the vertices corresponding to f(), f(2) share an edge, and also the vertices f f(4) share an edge (due to the explicit derivatives);
B(x, a²) includes all diagrams in which all edges either between f(1), ((2) between f(3), f()..
Therefore, in the full expression (63), the only remaining diagrams (i.e. the diagrams that do not cancel between the two terms) are those that include
an edge connecting ,
edge connecting f(3), f()), and
edge connecting one of f0,, to one of f(3), f(4).
These diagrams are all connected graphs, and this completes the proof that Var(e) = (n
Here and above have established that Var = O(n-1) and E [+] O(n)). More generally, let us consider a random variable O equal to the product of ʃ and its derivatives, where the derivatives indices fully summed in pairs. As will now show, if E [0] ( and Var(O) = On- then (1) the limit lim,,+0o E [O] exists, and (2) O converges in probability to this limit. In particular, the NTK an example of such a random variable, and so this will conclude the proof that the NTK converges in probability.
First, consider the mean. There is finite number diagrams contributing to E [O), and each has well-defined n scaling. Therefore, we can write
Amax
E E
Ck n
(66)
k=0
for some values of kmax 2 0 (integer) and co. .I.... large limit,
R. We see that the mean has well-defined
lim [ Co
(67)
24

---

Published as a conference paper at ICLR 2020
Next, let us show that O E [O] converges in probability using Chebyshev's inequality. Indeed, by the variance assumption there exists > 0 such that
Var
ē
P(JO - E [0] c) S
+ 0.
(68)
NE²
Combining the facts that - E [0] >p 0 and E [0] + co. we find that O converges in probability to co-
Next, we show that the large width NTK is constant during training, and compute the asymptotics of the higher-order terms. The following argument is phrased for deep linear networks. More generally, the argument holds for deep networks with smooth non-linear activations under the additional assumption that the large width limit and Taylor series can be exchanged (note that for such networks, the network function is analytic in the weights).
Theorem 11. Let fx) be the network output of a deep linear network with MSE loss Let O2(2, x') be the Neural Tangent Kernel at SGD step t, for some inputs 2, x'. Then in the large width limit, the kernel constant in expectation, and
Eg-Po [0,(x, x²) - Ou(o, x') O( =
(69)
Vare~P. [0r(I, x') - 10((x22)) Onn
(70)
On 1) It then follows from Theorem 9 that Es-P, [0++1(2, (1(xx (n for all t, and therefore
Proof. It is enough to show that Eg~ (2, -
Ep-Po (0,(r, x') - 00(2,
Σ
Ra-Po 10++1 (z,' (71)
concluding the proof. We have
Eg-po (0,(x,2') 00(xxxx))=
Σ
d+1
(-n)&tt
Σ
Eawpo
Σ
aL
aL Tupn...pe (x)
T
k!ll
08m
0g
k.1=0
a
k+11
0L
OL 00 T
Tu (2²)
00
(72)
The fact that the kt, I sums are truncated at df + follows from using linear activations, as higher-order
derivatives of the network function vanish in this case. All terms in the over k. 7 include tensor product of the form 2y.R, T Tu (x) in (2') (..) with either h 2 1 or 2 1, where (..-) stands for additional derivative tensor factors. Therefore, all terms in the k, / sum are correlation functions that have cluster of size at least 3, including 7(x), T(x'), and least
other tensor contracted through the μr or V11 index. It follows from the Conjecture that each term in the sum is O(n 1). Lemma then implies that the variance of these updates is O(n 2).
E.2 WIDE NETWORK EVOLUTION IS LINEAR IN THE LEARNING RATE
In this section we prove that, at large width, the NTK determines the evolution of the network function not just for continuous- time gradient descent but also for discrete-ting -erreett--imeeeeee gradient descent. A similar result holds for stochastic gradient descent, using a stochastic kernel." !f Again we prove the deep linear case explicitly, but the result holds for deep networks with smooth non-linear activations under the additional assumption that the large width limit and Taylor series can be exchanged.
The perspective presented here helps understand the results of (Lee et al. (2019)) where it was observed empirically that linearized evolution is good description of wide networks even for relatively large learning rates.
25

---

Published as a conference paper at ICLR 2020
Theorem 12. Let f() be the network output of a deep linear network, and let fo(z) be the evolved function after gradient descent steps, defined by 0141 = 8, L(Or). In the large width limit, each gradient descent step update of ft. is linear in the learning rate n). Furthermore,
de )la("', +O(n
Es f((x))
E
Eg x
(73)
Here, Oo is the NTK at initialization and & is the single-sample loss at time t.
Proof. For a deep linear network, under single gradient descent step we have
d+1
8 f((x)
aL.
Eg (f++1(x) fe(x)] =
Σ
Eg
(74)
k!
20m ... 000h
00m
00mk
k=1
Ai Me
dl, (E,('')'))
n
Eg
11(x, x²)
0f
(al. E
8 [(())
0L.
0L
Σ
E.
(75)
k!
00m
00th
00m
08th
First, consider the sum over in (73). Each term in the sum is a correlation function for which the cluster graph contains a connected subgraph of size at least 3, and is therefore (n by Lemma 7 and Theorem 1. In the remaining (n) term, by the same argument as Theorem 11 we can replace O, = O + O(n ")) in the correlation function. The result is equation (73).
As mentioned above, we note that the proof goes through when using stochastic gradient descent updates, with the difference that in (73) we should sum over mini-bated samples instead of over the entire training set.
E.3 SPECTRAL PROPERTIES OF THE NTK AND THE HESSIAN
With an eye towards understanding the structure of the loss landscape at large width and as another example use case of approach, investigate the relation between the spectra of the Hessian, and the NTK.
Among other observations, present argument that for network with d hidden layers and MSE loss, the top Din ordered eigenvalues of the Hessian, (Hi are related to those of the kernel X by
- -{ O(n 1/2) d =1 .d>1 1
( -
(1)
Eg
(m-
(76)
The remaining Hessian eigenvalues vanish at large width O(n-1/2) for one hidden layer networks and O(n for deeper networks." 12 This is experimentally corroborated in Figure 9.
The Hessian of general loss takes the form,
82 v) 0f(x) 0f(x)
0l(x, v) 0² f() 0f 80 00
Hav
Σ (x.
(77)
0f2 00k
80"
A
B
The moments of H are useful way to understand its spectrum. As in other examples that we have seen, traces of powers of B lead to connected diagrams with higher and higher numbers of vertices, and scale as increasingly negative powers of More explicitly, traces involving powers of B contain multiple contracted derivative tensors. As a result, taking the average of these traces over the
O(n for the top Din eigenvalue differences and O(x-1/2) for the remaining eigenvalues in the one hidden layer case. We can gain insight into this improved scaling through the perspective of degenerate eigenvalue perturhation theory (Trefethen & Bau (1997)). but this is outside the scope of the current presentation.
Empirically actually find the even stronger bound Bg [((*] {
26

---

Published as a conference paper at ICLR 2020
U
V
Figure 8: A prototypical diagram corresponding to Eg [Tr (B²)]
weight distribution leads to correlation functions where the associated cluster graph, Gc, contain subgraphs with at least three connected vertices. By Lemma and Conjecture these correlation functions vanish infinite width. For example E&g [Tr (AB)) = ((1/n). There single exception is (1). Thus most moments of the Hessian
to this, can be easily seen in figure 8, Egg [Tr(B²*] equal moments of A in expectation."
E, Tr (AAT))
m + 2 ,m= + O(1nn)
Eg (T (H"))]
E. Tr [A9)]
+ Es [Tr (B²)]
(78)
What's 's more, we can relate moments of A to those of the kernel, as both are built out two logit derivatives. Explicitly,
Tr(A4 = Tr((M))").
(79)
and so the moments of the Hessian are also related to those of the kernel." 14
Eg [Tr ((MO)*)
m + 2 m O(1nn)
Es Tr (H*))
Eg Tr ((M)) + Eo Tr (B²)]
(80)
Here, we have defined,
Plllaa 0f
M M x6)
8ab
(Fas ya) Dic-
(81)
For the case of MSE loss. we can go even further. In that case, M (Far = Sub and B decays to zero during training. We thus have,
Esg Tr (O")
+ 2 m = 2 + +(1/))
Initially:
Eg TT (H")))
Eg Tr (0²) + E. Tr (B²)
(82)
At late times:
EA Tr (H**)) Ea (Tr (Om))
Vm.
These results indicate that the only difference between the spectra of the Hessian and the NTK come
from B and that B must have eigenvalues which scale as 1/ ddimBB) As dim( B) = O(n) for one hidden layer networks and O(?²) for deep networks we are left with the relation (76) between the eigenvalues of θ and H. As the network trains, the difference between these eigenvalues gets even
smaller. These results are confirmed experimentally in Figure 9 and Figure 10.
Multi-class, This story can be generalized multi-class neural network maps. In this case the logit is a map fa Di - IR Nams and the NTK has two class indices.
(x)(x) 0 (xx)
θ AB AAB(Zz (x,x') = 80
(83)
001
Expression (80) relating the moments of the Hessian to the NTK still holds in this context provided take Tr ((M))") Tr (B)) with the more general matrix,
al(Ia. Ma) MAB(T,, 2b) 6ab 0F20fB
(Fa, Ha) Dir.
(84)
For the first moment in linear ReLU networks, Tr Br
"Here we have argued for relations relating the mean of moments. It is not too difficult see that these relations will also hold for typical realizations. This follows from Lemma
27

---

Published as a conference paper at ICLR 2020
Top eigenvalue differences
Top digmmbas
200 v. dil.
St Isope i -3.581 561
1
2.14
2
1000
712
430
2nd
Eqpervazzee
(a) Hessian and NTK e.v. difference.
(b) Degenerate spectrum.
Figure 9: (a) The mean difference between the top eigenvalues of the NTK and the Hessian at initializations for a two hidden layer ReLU network of varying width match well with the predicted O(n behavior. The mean taken over 100 instances per width on two-class MNIST with 10 images per class. (b) The top 10 eigenvalues of both the Hessian and the NTK for a two-layer ReLU network of width 2048 trained on a three-class subset of MNIST. The top eigenvalues match well and show aspects of the repeated Nelass structure predicted large width. The eigenvalues of H computed using the lanczos algorithm.
Momert Gifanue
Average eigenvalue of i matrix
eganaaue odoge
07
(Dues-Tbari Tourit
30h
30-1
12/1
20122
sand
22114
Monmenta
(a) Relative moment differences
(b) Second moment of B
Figure 10: Relation between the spectrum of the Hessian and NTK. (a) The first 4 moments of H and θ for two hidden layer ReLU networks. At initialization the first third and fourth moments numerically similar, while the relative difference of the second moment is O(1). After training all moments are numerically close. (b) The root mean square eigenvalue of the matrix shows good agreement with the predicted /T. fall off for single hidden layer ReLU networks. Experiments were performed on ReLU networks trained on two-class MNIST with 100 images per class, Moments of the NTK were computed exactly, while moments of the Hessian and B were computed by randomly sampling 1000 vectors and using Hutchinson's 's trick.
28

---

Published as a conference paper at ICLR 2020
At large width, the NTK approaches the identity matrix in class space, Q + No 8 8AB Tr (e) (Jacot et al. (2018)). This implies that the NTK spectrum consists of Nelass repeated copies. This has consequences for the spectrum of the Hessian at large width. For instance, for the case of MSE error also implies Nelass repeated copies of the Hessian spectrum (See Figure 9b). It is intriguing think this could serve path towards understanding the emergence of the Nelass (or Nelas 1) large eigenvalues and corresponding subspace observed in the Hessian spectrum (Sagun et al. (2016; 2017); Gur-Ari et al. (2018); Ghorbani et al. (2019); Papyan (2019)).
E.4 HIGHER-ORDER NETWORK EVOLUTION
In this section we will explain how to compute higher-order corrections to training dynamics. In principle, this prescription allows to compute model dynamics as expansion in 1/n to arbitrary order. We apply this explicitly to compute the (1//n) training dynamics. In Figure 11, we present experimental confirmation of our predictions for the evolution of the NTK. In the main text, presented these results for the special case of gradient flow with MSE loss.
So far have mostly been using diagrammatic techniques to understanding the leading order scaling of correlation functions. It is interesting to try and understand finite width networks by asking how training dynamics are modified beyond the leading order asymptotics. There are three clear sources of corrections to the leading behavior.
1. The initial kernel, Oo. receives finite width corrections.
2. The linear (in learning rate) update for the network function, equation (73), is modified away from infinite width.
3. The kernel is not constant at finite width.
The first source of corrections is automatically taken into account in typical empirical settings, as the finite-width On can be computed explicitly. The other sources of corrections non-trivial, and will be the focus of this section. We begin by explaining how to take into account the non-constancy of the kernel order by order in 1/n, while maintaining the continuous time approximation. Next, back away from the continuous time limit and write down the full discrete evolution. We introduce a method to compute arbitrary order corrections, and explicitly work out the corrections order 1 /nn for MSE loss.
E.4.1 CONTINUOUS TIME.
Continuous time evolution of the model function in neural networks is governed by the differential equation
df(x;)
Σ 22) al(x'. (at De
(85)
dt
0f
As we have discussed length, in the large width limit, this equation simplifies and O(t) is asymp- totically constant (Jacot et al. (2018)). Our goal is to move beyond this leading behavior at large width and solve (85) brder-by-order in 1 /nn expansion. In Section we deseribed how compute the (n--1) corrections for the case of MSE loss. Here we explain how to handle corrections more generally well as giving a more detailed discussion of the MSE case.
The network map f and kernel, θ are members of the following family of operators.
= Σ 00,-1 (ZI..... 1z-1;t) (f(z.;t)
2 2,
(86)
09,
a0,
with 0₂ := f. Here, as above, O₂ = ② is the kernel. With a general loss function, these operators satisfy. d0, d0, ... Fzit) dt
06 00
Σ
Os41(21..., I,, d'
s 1.
(87)
0f
(0' DD)
29

---

Published as a conference paper at ICLR 2020
Equations (86) and (87). Give infinite tower of first order ODEs, the solution of which gives the time evolution of the network map and the kernel.
df df(1;;))
al(x.v) v)
E (r.y)eD
((11, x;
dt
0f
d ( x2;
(x y)
Σ (a.y)E
Os(01, x2, 22;
dt
0f
d0 (2r, x²;))
06(x, v) Os(2i,
Σ
(88)
dt
0f
(n.y)eDrr
Solving this infinite tower is not feasible. we wish to work to a given order in an expansion in 1/n, however, there is dramatic simplification, which makes solution possible. Firstly, truncate these equations. To see this note that the operators O2 contain s contracted derivative tensors. As a result, by Lemma 7 and Conjecture 1, correlation functions involving the operators, O, satisfy
O
even
Eg (O, T. :.: F);
(89)
71
8 odd
where F(ž;t) is arbitrary additional contribution the integrand.
Thus, if we wish to work to solve for the time evolution to corrections which scale as O(n we can truncate the tower at 2r and set O2r (t) be equal its initial value. Note that the leading order solution, (85), is the result of this procedure with r = 1 and the results presented in the main text for the On -1 evolution correspond to 2.
The truncation provides dramatic simplification, however it is not immediately clear how to solve even the truncated di differential equations (87). We now describe how to organize the perturbative expansion of the operators (t) (including and Q) in such a way that the differential equations become tractable.
The central idea is to write each operator, Oa()), as expansion.
Os rxit)
(2I.....
(90)
where each order ( captures the O(n evolution of O., For example,
f(mi:)) = (0) (x): (z):)) +... 0(21, (00) (x1, ( (I) +...
0g(11,02,40 2yi 0 (1 Tgi 0 22)
(r1, 0zg +
(91)
The notation ! means both that any correlation function containing O O(n and, by Lemma 6, that typical realizations of the operators scale as On--r).
Once the operators O, are organized in this way, solving the differential equations (85) is tractable. As the differential equations describing the evolution of !rr)) for r > 0 only depend on the time dependent solutions of 1"1)), can iteratively solve for the ! order by order. For example, in Section 3, we used the leading order solution for f and θ to solve for (1).
In principle this procedure can be extended to arbitrary order in 1/n. Before going onto explain the finite step corrections to this procedure, we reproduce the results of section in more detail.
Note that in Section 3 used the altemate notation θ for (1)
30

---

Published as a conference paper at ICLR 2020
MSE continuous time example.
The MSE loss is,
L MSF
Σ (f(x) ya)
(92)
2 (e.y)EDer
As such the update equation simplifies to,
df(x; 1)
Σ
(()
(93)
dt
The leading order solution to equation (93) is exponential, kernel evolution,
( (1) = y + -00 (So -y)
(94)
0 (t) Oo.
(95)
Here we are using a condensed notation where fo == (0)) O = (()) Equation (94) is a vector equation with fo. f()) (t), and y are vectors over the training set and the leading order kernel Op is square matrix over the same space.
As discussed above to study the ((1/n) evolution, we can truncate the set of equations (87) at 4, and set (t) = O (t) O2(0) up to corrections which scale O(n 2).
Moving up a rung (87), we have
dOg(x1 22, 23:
Σ
22, (f(z;)) y)
(96)
dt
(a.y) Da
To solve for 0 (1), i.e neglecting 3 corrections, we can plug in the leading order approxima- tions, (t) and ft)).
d 11) 22, Fs:t)
Σ (m.
01(21, #s,
(1;) -1)
(97)
dt
This gives,
0 (1) (I), 22; = 02,01,
1' di'
Σ
(2)))(1;) -vy) v)
(2.
(98)
Using the explicit form of (1) we can write,
0 (Z: ( = O2(ā:)) Eo, (0, (1-' - ( v))
(99)
Here we are again using a condensed notation. == (2)) fo and are vectors over the training set while O₂ a square matrix, and O (z: 0) also vector over the training set, with the value O4 x;; 0) on the point x' E Dir-
Moving one more step up the ladder gives
+ (11, θ 2z, + (01, + O(n
( (01, = L/dv dt' Σ (f (1)
(x;)))
(100)
(x.9)ED..
Plugging in 00 and using the cigenddecompossttion of θ, to perform the integrals gives,
e0)) - Σ (0s(E:0)-&)(A) é,) [1-e-tA)
1
A
Σ 1
--
((A++90)
+
(00 @) - EG)
d +
(101)
31

---

Published as a conference paper at ICLR 2020
(() folt) (n 1024)
(n 1024)
Ladh 1-b1
0.010
bub 1-11
0.034
Iisor hl
Rssor L-bl
Ola") pordiction
0.006
D pcediction
0.002
0.004
0.002
0.000
10P
10
10a
steps
steps
(a) Evolution of network map.
(b) Evolution of NTK.
f(0 folt)
126)
e(1)
(n 128)
0.04
tank: 2
1-h
0.10
fank 2-al
bunk
Ineer hh
Ireer L-hl
0.03
Oj pordiction
peediction
0.02
0.04
0.01
0.02
0.00
10²
102
10P
10'
10
10a
10
steps
stepe
(c) Evolution of network map for
network.
(d) Evolution of NTK for
network.
Figure 11: Single instance evolution for randomly selected element of the NTK and network map. Theoretical predictions at OO are represented by dashed lines, while the true network evolution is shown in solid. (a-b) Wide networks show excellent agreement with predictions. (c-d) Predictions match reasonably well even down modest widths. All plots correspond single training runs on 2-class MNIST with 10 samples per class. The learning rate is 0.1 for all runs. All runs reach training accuracy 1.
Here, have introduced the eigenvectors, é, which are vectors over the training dataset and eigenvalues X; of the initial kernel, O6. The vector म = (æ1, x22 as θ depends on two inputs. Oz 0) vector over the dataset while O+ 0) is square matrix and Aʃo over the training data.
y vector
Finally, can plug in the expression (100) into (93) and give the sub-leading behavior for f(1)
df;r;) dt
Σ
(z,x't)) (f(x'tt) y) (nn
(102)
(e.))ED+,
f(I) - - Oot
(So 9)
(103)
This completes the full O(n-1) time dependance. This prediction for the ((1/n) time dependence is confirmed experimentally in Figure 11.
Note, one consequence (101) that the ((1/n) corrections to go to constant at late times.
( = lim (1) = - Σ (0a(z:0) ê.) + Σ M (Z) a.) e2)
(104)
And the asymptotic evolution of Af(t is again constant kernel evolution, but with corrected kernel.
f(t) + ((++te)) (fo v)
(105)
32

---

Published as a conference paper at ICLR 2020
It is worth noting that these predictions are quite detailed, giving the full time dependence, rather than just the overall scaling with width. In deriving these results and in the discrete time analysis below, we implicitly make assumption that can control the discrete time corrections in the continuous time case that f()). (t) and all the O₂ (t) are differentiable. This relies on being able to differentiate through the activation function. For non-smooth activations such as ReLUU this assumption is suspect, and indeed the evolution is more subtle in the ReLU case and a full analysis left future work. For this reason we present experimental results for networks with smooth activation functions.
E.4.2 DISCRETE TIME.
With the 1/n corrections to continuous time evolution under our belts, it is possible to also keep track of corrections coming from the discrete update step. The essential point, that it is possible solve iteratively, order by order in 1/n is not changed. To see this we can look at how the update equations modified. Beginning with the network output update equation, have,
de, (e, 33) x') (x(x,
f((()))
-
Σ
05
(x' Dit
+ 1
f((z)
n
8 f((x)
Σ
g gi
Σ
ge 98 g +
(106)
00
3!
20 30 age
pup
In Section E.2 argued that the (1)²) terms vanish at large width. In more detail, each factor of the gradient, gr,, contains a contracted derivative tensor. Thus, the cluster graph for correlation functions involving the 112 term will always contain three contracted vertices and thus the correlation functions will scale as On -)) The ry2 term will give four vertices, and thus also scale as O(1/n). the r7 contribution will be O and so on.
Just as in the continuous time case this equation is still solvable order by order in 1/n. What we mean by solvable is the following. All terms on the RHS appearing with fo are already higher order as result of their derivative structure. This means, just as in the continuous case, we can use the lower order solution of f. the gradient terms on the RHS to solve for f. on the LHS.
Similarly, the update equation for θ receives discrete time modifications.
06 v)
n
O 00, x22)
1141 x2) (1(21, = Σ x2)
Σ Ja
ge gt
0f 2
0ANDAN
(107)
Here we have adopted a notation where, में = (II,.... ........,). v.). Just as for f. increased powers in rj increasingly suppressed in n and we can iteratively solve this equation using solutions leading orders in solve for sub-leading behavior.
More generally the tower of differential equations defined recursively in (87) becomes
OsH1e(T,x') 06(x', v/tt)
(7)+1(7) Oz:((T)= =
Σ
0s
(x' DED
000+.t1 00,, 000g ... 80 Iu.
Σ
9p
2 1. (108)
2=2
As in the continuous time case, a given order in n, we can truncate this tower and use lower order solutions to solve for the time evolution up to the desired order. To ground this discussion in concrete use case, we again walk through the 1/n corrections for MSE loss, now discrete time.
MSE discrete time example.
For discrete time evolution, the leading order behavior of the model map is
S (1 '70o)' (So - y)
(109)
0 Op
(110)
33

---

Published as a conference paper at ICLR 2020
At next order proceed by solving the truncated set of equations in (108). The first equation, for Oag still gives a constant solution,
(1)
4:4 = O4:0-
(111)
Here, both the discrete and continuous time terms that would appear on the RHS are (11/n²). Next, we must solve for O3 The discrete time update is,
03:+1 - (z) = -1
Σ (e',g))De
24 1/)
7 2
Σ pe
8 3z (T)
Di gi +
(112)
To order 1/n we can drop the order 1/2 and higher terms, as they contain expressions with 5 or more contracted derivative tensors. Thus this order, we are left with the discrete analogue of (96).
O3.441 (T) O3 (3)=
E Oze(E,x))(((()))) v²)
(113)
(#' (e
which we get the discrete version of (98),
( = 0z.((7) - Σ Σ
Osa(T, x') (on(xe)) -²))
(114)
1'=1 0'=1 (d'rt))
Explicitly, this takes the form
O @ (i) 03 (T) (3) (05'(1 (1-''11116)) 1)0) - -11- (So y))
(115)
Here we have adopted notation similar to above, where (z: is a vector over the training dataset.
So far, this procedure has been a discrete analogue what we have done in the continuous time case, however as we move on to compute è and ff we will have to keep track of the novel corrections, which vanish in continuous time. Explicitly, at order 1/n the discrete update for O₂ is given by,
2 (7) 0 (z) = - Σ
old (i, x') (110) (x') -5y 5²)
e 0fu(z') 0f((=")
+ 2
Σ
Σ
v/) (f:" v²)
z' aa wy uy Di ue 00.00" Og
00"
(116)
This can be summed to give 0!",
To move up to the neural network map itself there is one additional complication. The O( /n) term, fz()(z) af.("") 0f((z") in (106) has non trivial time dependence. We can deal with this just as Ener 38"0000 d8t 0g0
we have been doing, by taking an extra time derivative and integrating. Defining.
(z 0f((22) @f((za)
(117)
00"000
D0v
00"
We have
(z) (+) 7
Σ
80 (01.1.00T)
v5)
(118)
d0p
8gu
with the solution,
001, (7) afo
(1) = (1)
Σ
(0,1 (1 1700 - (01-770)))11 (119)
30" 00k
34

---

Published as a conference paper at ICLR 2020
This can in turn be plugged into the update equation for fi-
(2) f((x) 11 Σ (al( + 6:"² (z, xa) (fe(ze) yal
$12
o 11 (za) Va) (f( 3/b)
+
2
"
Σ
8 fo())
@f((r.) a a5o(ae)
(fi(za) - ya) (ft(zs) - yb) (fe(2e) Me)
3! 0,b,c
00
00.
ag
00r
(120)
Here (Ia: va) are elements of the training set Der and summed over. This equation can be solved to give st
f( = 9)
(('+2)) - n)on) (1--no))((+t))
- (1 m706)" A + Disc.]
(121)
p=1
Where Disc; contains the discrete derivative updates at (11/n).
Disc, 172
Σ (Fa vb) (fe(xa) ya) (Je(Ira) ybb
17²
fo
ffo(=.) (z((zs) ff((z) (f((Fa) Va) (f((m)) - y6) (Filze) Uo)
3!
80 00 00
a0
000
a,b,c
(122)
These expressions may look fairly intimidating. The key point is that all terms in the summand in (I (116) and thus (121) are known functions of time and initial data, just as in the continuous time setting.
35


Reviews:
[{"review_id": "SJxzoDYLcS", "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 proposes a new tool based on Feynman diagrams to analyze wide networks (e.g., feed-forward networks with one or more large hidden layers or CNNs with a large number of filters).\n\nThe main contributions of the paper are:\n- a new method (using Feynman diagrams) to bound the asymptotic behavior of correlation functions (ensemble averages of the network functions and its derivatives). The method is presented as a conjecture.\n- tighter bounds for gradient flow of wide networks\n- an extended analysis of SGD for wide networks\n- a formalism for deriving finite-width corrections\n\n\nThe study of (infinitely) wide networks has been active over the last few years. A better understanding of wide networks could, amongst other things, shed light on recent empirical results related to over-parametrized networks.  As such, improving our theoretical understanding of wide networks and especially properties of finite-width networks, which is what this paper explores, seems significant and potentially very impactful.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byl5H39iqS", "reviewer": "AnonReviewer4", "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 a positive review. Feel free to skip to the feedback.\n\nSUMMARY OF PAPER\nThis paper explains how to use cluster graphs to easily compute the asymptotic behaviour of any given correlation function (Definition 1) for deep linear networks. By \"asymptotic behaviour\" I mean that it upper-bounds correlation functions by c·n^s, where s is a nonnegative integer given by the particular cluster graph, and c a \"constant\" (which I think depends on the particular input, x, to correlation function, among other things).\n\nThe authors then conjecture (Conjecture 1) that these bounds transfer to deep nonlinear networks, and that they are tight:\n- Appendix C proves that these upper bounds also hold for deep ReLU networks, and 1-hidden-layer networks with smooth nonlinearity. This is also mentioned in page 3.\n- Section 2.3 empirically shows that these bounds are pretty tight. (in terms of the exponent, none of the theory here gives a value for the constant c)\n\nThe tool provided above is the main result. The authors then use it to provide some results about wide networks  \n- They give a different proof that for large width, the Neural Tangent Kernel stays constant during training. This is because its derivative wrt. time as a function of width n is O(n^-1), and thus 0 for n->infinity.\n- Using the ease of calculation from the tool, they approximate the change in the NTK over training time for any network. They do this using its value at initialization + a term that depends on n^-1. These results are numerically verified in Figure 1.\n- They present numerical evidence for the accuracy of this approximation to the change in NTK over time. \n\nThe authors spend the last 2 pages explaining how cluster graphs derive from Feynman diagrams (FDs), and why these help compute asymptotics.\n\nWHY I AM ACCEPTING THIS PAPER\n\nThe paper adapts FDs and cluster graphs, which is a potentially very useful tool for other wide-network researchers, and could accelerate research in this whole sub-field. It also shows their power by providing a surprisingly large amount of novel theoretical results.\n\nFEEDBACK\n\nAt a very high level, there is only one thing that I think isn't made quite clear by the presentation, and it should be. If I understand correctly, Feynman diagrams (or cluster graphs) are only used here to calculate correlation functions for deep *linear* networks. Then, other results establish that the width-dependent asymptotic behaviour for linear networks holds as-is for nonlinear networks, and these results with FDs constitute Conjecture 1. There are proofs for ReLU and 1-layer smooth networks, mentioned in pg. 3; and the experiments in the paper support it for common nonlinear deep networks as well. I think that asymptotics for linear networks transfer to nonlinear ones is an interesting result, which doesn't depend on FDs.\n\nWhat follows are details.\n\nIt is unclear to me whether cluster graphs are as \"powerful\" as FDs, i.e. whether the bound at the end of the Proof in page 8 is always saturated. Are there some cases in which you need to use FDs to get a tighter upper bound?\n\nIn Table 1 you should say that the values under \"lin. ReLU tanh\" are the fitted exponent s_C. This is not explained. Perhaps you  can mark the only 2 cases (in the 5th row) where the bound is not tight. It would be nice to know how much error remains between the fitted c·n^(s_C) and the empirical values.\n\nPlease explain x1 <-> x2 in eq. 8\n\nIn figure 1b, consider adding the finite-width limit prediction for the training dynamics. You have already done so for the prediction of the NTK during training in figure 5c, you could indicate it in the same way in 5b.\n\n\nTypos:\n\nFigure 2 caption: feynman -> Feynman\n\npg 8. anlytic evicence -> analytic", "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": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BJefC4YVqr", "reviewer": "AnonReviewer3", "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": "The paper investigates the asymptotic behavior of correlation functions of wide networks. The main part of the work revolves around Conjecture 1 which assesses how the correlation function scales depending on the number of connected components of even/odd size of the constructed cluster graph. The authors then study training dynamics of wide networks under gradient flow and (stochastic) gradient descent and present empirical evidence to support their claims.\n\nWhile I am no expert in this particular area, the paper is fairly well written and the main concepts and ideas are outlined nicely in most places. I do have some comments, though, wrt. the notation and the relevance of certain results:\n\n(1) In 2.1. the authors state the def. of a deep LINEAR network, however, the activation functions are non-linear. Could you be more clear what you mean by linear in your setting? \n\n(2) What are the vertices in Conjecture 1? v_i = T(x_i), right? I think it's clear from the context (i.e., the definition of edges), but this could be written more precisely.\n\n(3) What is the actual relevance of the ORDER of the correlation function in Conjecture 1 and the relevance of the cluster graph. Can the authors motivate this more clearly, or provide some more intuition on this construction?\n\n(4) What does the notation x_1 \\leftrightarrow x_2 in Eq. 8 mean?\n\n(5) Thm. 3 - Apparently, the expression for C only depends on the #loops in \\gamma. Is this independent of the number of connected components (especially, since Conjecture 1 explicitly hinges on #connected components)?\n\n(6) Does the analysis equally hold if you consider affine maps (Ax + b ) instead of linear operations Ax? \n\nOverall, the paper presents some quite interesting results, but the authors could be more clear on the relevance of those results and its implications. Non-expert readers are left with having to figure this out on their own. In my point of view, this would make the paper much stronger.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission presents bounds on the training dynamics (including gradient evolution) for deep linear (and in some cases nonlinear) networks as a function of the width of the layers or number of convolutional layers. The work also presents experimental results that provide evidence that the bounds are tight.

Strengths:
The work provides interesting insights into these training dynamics, particularly for the wide-but-not-infinite setting, which is less studied.
The work also adapts cluster graphs and Feynman diagrams to derive these bounds, which could be useful tools for researchers in this field.

Weaknesses:
The validity and applicability of some of the results for nonlinear networks was not entirely clear at first but has been clarified in the revision.

The reviewer consensus was to accept this submission.

Decision: Accept (Spotlight)