Disentangling Trainability and Generalization in Deep Learning
Authors: Lechao Xiao
Jeffrey Pennington
Sam Schoenholz
Venue:  (2020)
Keywords: NTK
NNGP
mean field theory
CNN
trainability and generalization
Gaussian process

Abstract: A fundamental goal in deep learning is the characterization of trainability and generalization of neural networks as a function of their architecture and hyperparameters. In this paper, we discuss these challenging issues in the context of wide neural networks at large depths where we will see that the situation simplifies considerably. To do this, we leverage recent advances that have separately shown: (1) that in the wide network limit, random networks before training are Gaussian Processes governed by a kernel known as the Neural Network Gaussian Process (NNGP) kernel, (2) that at large depths the spectrum of the NNGP kernel simplifies considerably and becomes ``weakly data-dependent'', and (3) that gradient descent training of wide neural networks is described by a kernel called the Neural Tangent Kernel (NTK) that is related to the NNGP. Here we show that by combining the in the large depth limit the spectrum of the NTK simplifies in much the same way as that of the NNGP kernel. By analyzing this spectrum, we arrive at a precise characterization of trainability and generalization across a range of architectures including Fully Connected Networks (FCNs) and Convolutional Neural Networks (CNNs). We find that there are large regions of hyperparameter space where networks will train but will fail to generalize, in contrast with several recent results. By comparing CNNs with- and without-global average pooling, we show that CNNs without average pooling have very nearly identical learning dynamics to FCNs while CNNs with pooling contain a correction that alters its generalization performance. We perform a thorough empirical investigation of these theoretical results and finding excellent agreement on real datasets.

Under review as a conference paper at ICLR 2020
DISENTANGLING TRAINABILITY AND GENERALIZATION IN DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
A fundamental goal in deep learning is the characterization of trainability and generalization of neural networks as a function of their architecture and hyper- parameters. In this paper, we discuss these challenging issues in the context of wide neural networks at large depths where we will see that the situation simpli- fies considerably. To do this, we leverage recent advances that have separately shown: (1) that in the wide network limit, random networks before training are Gaussian Processes governed by kernel known as the Neural Network Gaussian Process (NNGP) kernel, (2) that at large depths the spectrum of the NNGP kernel simplifies considerably and becomes "weakly data-dependent", and (3) that gra- dient descent training of wide neural networks is described by kernel called the Neural Tangent Kernel (NTK) that is related to the NNGP. Here we show that the large depth limit the spectrum of the NTK simplifies in much the same way as that of the NNGP kernel. By analyzing this spectrum, we arrive at a precise characterization of trainability and a necessary condition for generalization across a range of architectures including Fully Connected Networks (FCNs) and Con- volutional Neural Networks (CNNs). In particular, we find that there are large regions of hyperparameter space where networks can only memorize the training set in the sense they reach perfect training accuracy but completely fail gener- alize outside the training set, in contrast with several recent results. By comparing CNNs with- and without-global average pooling, we show that CNNs without av- erage pooling have very nearly identical learning dynamics to FCNs while CNNs with pooling contain a correction that alters its generalization performance. We perform thorough empirical investigation of these theoretical results and finding excellent agreement on real datasets.
INTRODUCTION
Machine learning models based on deep neural networks have attained state-of-the-ard performance across dizzying array of tasks including vision (Cubuk al., 2019), speech recognition (Park et al,,, 2019). machine translation (Bahdanau et al., 2014), chemical property prediction Gilmer et al. (2017), diagnosing medical conditions Raghu al. (2019), and playing games Silver et al. (2018). Historically, the rampant success of deep learning models has lacked a sturdy theoretical foundation; architectures, hyperparameters, and learning algorithms are more often than not selected by brute force search Bergstra & Bengio (2012) and heuristics Glorot & Bengio (2010). Recently, signifi- cant theoretical progress has been made on several fronts that have shown promise in making neural network design more systematic. In particular, in the infinite width (or channel) limit, the distribu- tion of functions induced by neural networks with random weights and biases has been precisely characterized before, during, and after training.
The study of infinite networks dates back to seminal work by Neal (1994) who showed that the distribution of functions given by single hidden-layer networks with random weights and biases in the indinite-width limit are Gaussian Processes (GPs). Recently, there has been renewed interest in studying random, infinite, networks starting with concurrent work on "conjugate kernels" (Daniely et al., 2016; Daniely, 2017) and "mean-fiet field theory" (Poole et al., 2016; Schoenholz et al., 2017). The former set of papers argued that the empirical covariance matrix of pre-activations became deterministic in the infinite-widhh width limit and called this the conjugate kernel of the network while the latter papers studied the properties of these limiting kernels along with the kernel describing

---

Under review as a conference paper at ICLR 2020
distribution of gradients. In particular, it was shown that the spectrum of the conjugate kernel of wide fully-connected networks approached a well-defined, data-independent, limit when the depth exceeds certain scale, Ç. Networks with tan/--nolinearrties (among other bounded activations) exhibit a phase transition between two limiting spectral distributions of the conjugate kernel as a function of their hyperparameters with ç diverging at the transition. It was additionally hypothesized that networks were un-trainable when the conjugate kernel was sufficiently close to its limit.
Since then this analysis has been pushed et al.. 2018), recurrent networks (Chen et al., 2018; Gilboa et al., 2019), networks with residual connections (Yang & Schoenholz, 2017), networks with quantized activations (Blumenfeld et al., 2019), the spectrum of the fisher (Karakida et al., 2018), a range of activation functions Hayou et al. (2018), and batch normalization (Yang et al., 2019). In each case, was observed that the spectra of the kernels correlated strongly with whether or not the architectures were trainable. While these papers studied the properties of the conjugate kernels, especially the spectrum in the large-depth limit, branch of concurrent work made a stronger statement: that many networks converge to Gaussian Processes as their width becomes large (Lee et al., 2018; Matthews et al., 2018; Novak et al., 2019b; Yang, 2019). In this case, the Conjugate Kernel was referred to as the Neural Network Gaussian Process (NNGP) kernel.
wide range for architectures such as convolutions (Xiao
Together this work offered a significant advance however, this theoretical progress was limited to networks at initialization or after Bayesian posterior estimation and provided no link to gradient descent. Moreover, there was some preliminary evidence that suggested the situation might be more nuanced than the qualitative link between the NNGP spectrum and trainability might suggest. For example, Philipp al. (2017) showed that deep fully- connected fan/-networks could be trained after the kernel reached its large-depth, data-independent, limit but that these networks did not generalize to unseen data.
understanding of wide neural networks;
In the last year, significant theoretical clarity has been reached regarding the relationship between the GP prior and the distribution following gradient descent. In particular, Jacot al. (2018) along with followup work (Lee et al., 2019; Chizat et al., 2019) showed that the distribution of functions induced by gradient descent for infinite-widtt networks is Gaussian Process with a particular compositional kernel known as the Neural Tangent Kernel (NTK). In addition to characterizing the distribution over functions following gradient descent in the wide network limit, the learning dynamics can be solved analytically throughout optimization.
In this paper, we leverage these developments and revisit the relationship between architecture, hyperparameters, trainability, and generalization in the large-depth limit for variety of neural net- works. In particular, we make the following contributions:
1. We compute the large-depth asymptotics of several quantities related to trainability, includ- ing the largest eigenvalue of the NTK, Amax. and the condition number λ. Amuxx/ /mmin where Amin is the smallest eigenvalue; see Table 1.
2. We introduce the residual predictor A1), namely the difference between the finite depth and infinite depth NTK predictions, which is related to the model's ability to generalize: the network fails to generalize if A (1) is too small.
3. We show that the ordered and chaotic phases identified in Poole et al. (2016) lead to markedly different limiting spectra of the NTK, which further indicates that, as a fune- tion of depth, the optimal learning rates ought to decay exponentially, linearly and remain roughly a constant in the chaotic, order-to-chaos and ordered phases, respectively.
4. We examine the differences in the above quantities for fully-connected networks (FCNs) and convolutional networks (CNNs) with and without pooling and precisely characterize the effect of pooling to these quantities.
5. We provide substantial experimental evidence supporting these claims, includes experi- ments that densely vary the hyperparameters of FCNs and CNNs with and without pooling.
Together these results provide a complete, analytically tractable, and ielausse-iddeeeddeen theory for learning in very deep and wide networks. In addition to being interesting in its own right our theory provides a strong test of the NTK theory. Finally, our results provides clarity regarding the observation that for linear networks the learning rate must be decreased linearly in the depth of the
2

---

Under review as a conference paper at ICLR 2020
FC/CNN-F, CNN-P
NTK
Ordered X1 <
Critical X1 =1=1
Chaotic X1 >
Amax
mO(lx)) mq*
md+221g 14" + m1) 3d
o(t)/d
A
(1) rest
o(xi)/d
3/ 10(1)
o(t)/d
x())
O
md+2 + dmo(l-1)
+1
2
A
Obxi)/d
do((-))
do /xi))
Table I: Evolution of the NTK spectra and (0) The NTKs of FCN and CNN-F are essentially the same and the scaling of (1) A (e9), and A (1) for these networks is written in black. Corrections to these quantities due to the addition an average pooling layer with window size d is written in blue.
network Saxe et al. (2013). Here, we note that this is true only for networks that are initialized critically, i.e. on the order-to-chaos phase boundary.
2 BACKGROUND
We summarize recent developments in the study of wide random networks. We will keep our dis- cussion relatively informal; see (Lee et al., 2018; Matthews et al., 2018; Novak al., 2019b) for more rigorous version of these arguments. To simplify this discussion and as a warmup for the main text, we will consider the case of FCNs. Consider a fully-connected network of depth L where each layer has a width (!) and an activation function o R R. In this work we will take & erf however, most of the results will hold for wide range of non-linearities though specifics such as the phase diagram- can vary substantially. For simplicity, we will take the width of the hidden layers infinity sequentially: ((1) -> oo....,NN(I))
oc. The network is parameterized by weights and biases that we take to be randomly initialized with w(()) ij b()) ~ NO0 1) along with hyperparameters, Twe and σ that set the scale of the weights and biases. Letting the pre-activations
in layer due to an input æ be given by 2. (z), the network is then described by the recursion,
(++
(x)
One
w w(( 0(2)) (x)) + tob Ky
0 O-Is
(1)
VNU
Notice that as OO) co. the sum ends up being over large number of random variables and we can invoke the central limit theorem to conclude that the {z] (2((+1) [ein] are i.i.d. Gaus- sian with zero mean. Given dataset of m points, the distribution over pre-activations can therefore be described completely by the covariance matrix between neurons in different inputs
x(()) (x, = E|2 (x)=²" (z'))- Inspecting Equation 75, we see that (x++1)xx,)) can be com- puted in terms of (2()) (1)) (x,x') as
(((+1) (z, x') 0
+o oZ + +oū
(2)
for T, an appropriately defined operator from the space of positive semi-definite matrices to itself.
Equation 2 describes a dynamical system on positive semi-definite matrices K(ar,²'). It was shown in Poole al. (2016) that fixed points, K (I,,x'), of these dynamics exist such that lim 100) (z, x') = X inputs x and x'. The values of q" and o* are determined by the hyperparameters, au and σb. How- ever Equation 2 admits multiple fixed points (e.g. c* = 0, 1) and the stability of these fixed points plays significant role in determining the properties of the network. Generically, there are large regions of the (a σb) plane in which the ixed-point structure is constant punctuated by curves, called phase transitions, where the structure changes.
with XC (x, = q" [82,," + c²(1 62,=:) independent of the
3

---

Under review as a conference paper at ICLR 2020
The rate at which K(xx, 2²) approaches departs (z, 2²) can be determined by expanding Equa- tion 2 about its fixed point, o'(x,x') = x(x,,') - 1C (z. x') to find'
(x,2²) (x. (x,x'
(3)
which exhibits exponential convergence to or divergence from the fixed-point as 5K((1) (a,, x²) ~ x(x, x'y where x(x, x') =
Since (r,,,, x²) does not depend on x or a' it follows that x') will take on a single value, Xe*, whenever * x'. If Xe- > 1 then the fixed point is unstable and, as discussed above, there will be another fixed point that becomes stable, if Xe* < then the fixed point is stable, and if Xe- 1 then the hyperparameters lie at a phase transition. As was shown in Poole et al. (2016), there is always a fixed-point at c" = 1 whose stability is determined by X1. This defines the order-to-chaos transition. Note, that Xe- can be used to define depth-scale, &e- - log(xe)) that describes the number of layers over which KC() approaches K
This provides precise characterization of the NNGP kernel at large depths. As discussed above, cent work (Jacot et al., 2018; Lee et al., 2019; Chizat et al., 2019) has connected the prior described by the NNGP with the result of gradient descent training using quantity called the NTK. To con- struct the NTK, suppose we enumerate all the parameters in the fully-connected network described above by 0,, The finite width NTK is defined by Ô(x, x²) J(x) where (x) = 0o., 2 (x) the Jacobian evaluated a point x. The main result in Jacot et al. (2018) was to show that in the infinite-widthh limit, the NTK converges to deterministic kernel ( and remains constant over the course of training. As such, at a time during gradient descent training with an MSE loss, the expected outputs of an infinitely wide network, (1(x) E[2,(x)), evolve as
(e = (Id- E -100 uain Yrnin
(4)
(X(st)))) = Orest, train mmin, train (Jd -/ mire Yrain
(5)
for train and test points respectively; see Section in Lee et al. (2019). Here Otest, train denotes the NTK between the test inputs Xtest and training inputs Xuain and Ouain. train is defined similarly. Since Ô converges to O, the gradient flow dynamics of real network also converge to the dynamics described by Equation 4 and Equation 5 (Jacot et al., 2018; Lee et al., 2019; Chizat et al., 2019; Yang. 2019: Arora et al., 2019; Huang& & Yau, 2019). As the training time, t tends to infinity note that these equations reduce to (Xarin)) = Yurin and ju (Xes) = Grest, train O train Yrrain- Consequently call the linear operator
P(O)= Orest, train O O
66)
train, train
the "mean predictor" or "predictor" for short. In addition to showing that the NTK describes net- works during gradient descent, Jacot et al. (2018) showed that the NTK could be computed in closed form in terms of T, T, and the NNGP as,
( (z, x²) (Ct+)
(z, (x,,
where ( is the NTK for the pre-activations at layer-l
3 METRICS FOR TRAINABILITY AND GENERALIZATION AT LARGE DEPTH
We begin by discussing the interplay between the conditioning of Orraintrain and the trainability of wide networks. We can write Equation 4 in terms of the spectrum of O train.train letting O trainttrain U DU as,
(rauia) (Id c -n2i3 ( V
(8)
where X; are the eigenvalues of Ommnn and jice (Xmiiin))) = (TpeiXinnn)) Yimin UY are the mean prediction and the labels respectively written the eigenbasis of Orainnarain- If we order the eigenvalues such that An 2 > Am then it has been hypothesized in c.g. Lee et al. (2019) that the maximum feasible learning rate scales as 17 ~ 2/ No as we verify empirically in section 4. Plugging
Moor precisely, one needs to consider the Jacohian of T operator from positive semi-definite matrices positive semi-definite matrices. We refer the readers Section B of Xiao al. (2018) for more details.
4

---

Under review as a conference paper at ICLR 2020
this scaling for 7 into Equation 8 that the smallest eigenvalue will converge exponentially a rate given by Λ = /o the conditioning number. It follows that if the conditioning number of the NTK associated with neural network diverges then it will become untrainable and so use R as a metric for trainability. We will see that at large depths, the spectrum of mainanii typically features single large eigenvalue, Amax, and then gap that is large compared with the rest of the spectrum. We therefore will often refer to typical eigenvalue in the bulk as Ayest and approximate the condition number as Amax/Aress
In the large-depth limit will see that + converges O* independent of the data distribution. In this case @ ustttain will be rank-1 constant matrix. As such, the mean prediction defined by Equation completely fails to generalize. We define the finite depth correction the infinite depth predictor".
11 Train = (P(O P(())) Yrain-
(9)
By the triangle inequality, the generalization error lower bounded by
IIP()()) - Yeslll2 2 P(())) Yss la || (1) Yrannl
(10)
|P(( train Yemull2 is a constant independent of the test inputs and Equation 10 is large if | (1) Yrain is too small. Therefore, necessary condition for the network to generalize is that there exists some p > 0 such that
| 4) Yiminn 12 2 pll - Y2esll12.
(1I)
As such, we use A (1) as a metric for generalization in this paper.
Our goal is therefore to characterize the evolution of the two metrics (e()) and (1) in I. We follow the methodology outlined in Schoenholz et al. (2017); Xiao et al. (2018) to explore the spectrum of the NTK as a function of depth. We will use this to make precise predictions relating trainability and generalization the hyperparameters (am, 0b, 1). Our main results summarized in Table 1 which
describes the evolution of (t) (the largest eigenvalue of ((!),, Xeest (the remaining eigenvalues), R((), and A (4) in three different phases (ordered, chaotic, and the phase transition) and their depen- dence on m, the size of the training set, the choices of architectures: FCN, CNN-F (convolution with flattening) and CNN-P (convolution with pooling), and size, d, of the window in the pooling layer (which we always take to be the penultimate layer).
We give a brief derivation of these results in Section followed by a more detailed discussion in the appendix. However, it useful to first give a qualitative overview of the phenomenology. In the ordered phase, ( - m(q" - 1xl) and ( + Ixi- At large depths since X1 < 1 follows that (1)) - mqq /(xx1) and so the condition number diverges exponentially quickly. Thus, in the ordered phase expect networks not to be trainable (or, specifically, the at which they learn will grow exponentially in their depth). The predictor scales as lxi which goes to zero at the same rate as the divergence of (0; thus, in the ordered phase networks fail to train and generalize simultaneously. By contrast in the chaotic phase we see that there is gap between X and A and networks become perfectly conditioned and are trainable everywhere. However, in this regime we see that the predictor scales as 1(xe= /x.'.. Since, by definition, in the chaotic phase Xe < 1 and X1 > it follows that ( + 0 over depth & = -1/ log(Xe- /xi). In the chaotic phase networks fail to generalize at a finite depth but remain trainable indefinitely. Finally, notice that introducing pooling modestly augments the depth over which networks can generalize in the chaotic phase but reduces the depth in the ordered phase. We will explore all of these predictions in detail in section 5.
4 LARGE-DEPTI ASYMPTOTICS OF THE NNGP AND NTK
We now give a brief derivation of the results in table 1. To simplify the notation we will discuss fully-connected networks and then extend the results CNNs with pooling (CNN-P) and without pooling (CNN-F). Details of these two cases can be found in the appendix. We will focus on the
PIf (t) diverges to infinity, define P( lim;-4o P()())) If e Irain, trin is singular, we will add diagonal regularizer old into Or trin.
5

---

Under review as a conference paper at ICLR 2020
NTK here since Schoenholz et al. (2017); Xiao al. (2018) contains detailed description of the NNGP in this case. As in sec. 2, we will be concerned with the fixed points of θ as well as the linearization of Equation 7 about its fixed point. Recall that the fixed point structure is invariant within a phase so it suffices to consider the ordered phase, the chaotic phase, and the critical line separately. In cases where stable fixed point exists, we will describe how @ converges to the fixed point. We will see that in the chaotic phase and on the critical line, θ has no stable fixed point and in that case we will describe its divergence. As above, each case the fixed points of O have simple structure with e p" ((1 é* I'd + غ" 11"). To simplify the forthcoming analysis, without a loss of generality, we assume the inputs are normalized to have variance q" As such, we can treat T and T, restricted on (K()), )t, as point-wise functions, since
((K) Ed(u)o(v), (u.v)² ~ ~N
(u,u))~~ [ g" [((m,a))
(12)
Since the dia-oiagonal elements approach the same fixed point at the same rate, we use qub
(!)
(1,,xr and Pab
(1) (0 x') to denote any off diagonal entry of 1C(1) and O respectively. We
will similarly use Lnd and Pas to denote the limits, limy-+ 9ab = Lab = =c"q" and lim Pab =
(1)
Pas pppp. Using the above notation, Equation 7 and Equation 2 become
Jab (1+1)= qq"
11+1) = = T T(4ab)
(0) of
Pab (1+1) (1+1)
(1) qab + o T Pab
(13)
1=11) = = o o p')
(14)
where p() = =0 (x, x) and n0 = (x.) 2). In what follows, we split the discussion into three parts according to the values of XI = T recalling that in Poole et al. (2016); Schoenholz et al. (2017) it was shown that X1 controls the fixed point structure.
4.1 THE CHAOTIC PHASE X1 >
The chaotic phase is so-named because 925/9 < 1 so that similar inputs become more uncorrelated as they pass through the network. In this phase, the diagonal entries of ((1) grow exponentially and the off-diagonal entries converge to a fixed value. Indeed, Equation 14 implies.
Xi
[+1 -1
p(+)) -- + x)xx
D
(15)
X1
which diverges exponentially. To find the limit of the off-diagonal terms, define X = = which was shown to control convergence of the gob and is always less than 1 (Schoenholz et al., 2017: Xiao et al., 2018). Let + oo in Equation 13, we find that
Lab
Lab
Pab 1 1-o2T (2T(
<
(16)
X
The rate of convergence of Pa is (1x²)) (see Section A in the appendix). Since the diagonal terms diverge and the off-diagonal terms are finite it follows that in very deep networks the chaotic phase, (1)))) - ld. Thus, in the chaotic phase, the spectrum of the NTK for very deep networks approaches the diverging constant multiplying the identity. From Equation 4 this implies that optimization in the chaotic phase should be easy since k()) - 1 (provided numerical precision issues from the prefactor do not become problematic). However, computing the mean prediction on test points and noticing that P(O*) Yrain = O we find (see Section B for the derivation),
A Yrain (() Yurain R (rrain
0.
(17)
It follows that in the chaotic phase the networks predictions on unseen data to converge to 0 expo- nentially quickly in the depth. Since Equation 17 decays like (1()())) x(), we expect the network fails to generalize after (EE.) layers, where {. - 1/(log Xe - log x1)
'It has heen observed in previous works Poole et al. (2016); Schoenholz et al. (2017) that the diagonals converge much faster than the off-diagonals for tanh- or erf- networks. *For simplicity, we ignore the polynomial correction in l.

---

Under review as a conference paper at ICLR 2020
In summary, for wide networks, in the chaotic phase the depth increases optimization becomes increasingly easy but the generalization performance degrades and eventually the network fails com- pletely away from the training set after (E..) layers. Therefore, in the chaotic phase, deep network memorizes the training data. We will confirm this prediction for both kernel prediction and neural network training in the experimental results; see Fig 3.
4.2 THE ORDERED PHISE X1 = oa² <:
The ordered phase is defined by the stable fixed point with L/p/9" = 1; in this case, disparate inputs will end up converging the same output the end of the network. In the ordered phase, Equation 14 implies that all the diagonal entries of @ converge to the same value,
q
1000 p==
= 1 1 X1
1
<0
(18)
X1
However, as with the NNGP kernel, the off-diagonal terms of the NTK, Pab will also converge to the value on the diagonal, p". It follows that the limiting kernels have the form O p 11 and K = q p'11T. Thus, the limiting kernels are highly singular and feature only one non-zero eigenvalue. Since the limit is singular, we must linearize the dynamics about the fixed point to gain insight into the limiting behavior of the network. To compute the corrections, let
(1)
obb qab qab
ab = Pub Pab g()) p()) p
(19)
(1) 9" (1) q²
(20)
The diagonal correction can be obtained directly from Equation 18 and we find that e 0 and xi 1+1
g()
i-xi Q- To compute correction of the off-diagonals, we linearize the equation around the fixed point to find that asymptotically (see Section A),
oh
(0) x
5 ah
~
xf
5(0) ab +
+1
1
Pub
ah
(0)
(21)
XI
where X2 - og") While the NNGP and NTK feature the same exponential rate of convergence set by X1. we see that terms in the dff-diagonal terms of the NTK feature polynomial corrections. O has (approximately) two eigenspaces. The first eigenspace comes from the single non-zero eigenvalue at the fixed point and is very close to the DC mode (i.e. all entries of the eigenvector are equal to 1) with eigenvalue
X
max Re (m - 1)(p" - -8(1) + (p' -8(1) mp"
mq
(22)
X1
iee. is the sum of one row, where is the size of the dataset. The second eigenspace comes from lifting the degenerate mero-modes when 1 oc and has dimension (m - 1) with eigenvalue (1) -8 5 = ((x)) + O, which goes to zero exponentially over depth l. The eigenvalues Ayest
of ((()) have a similar distribution with Amax R mg" - (m - 1)c and ( = O(x)). Thus the conditioning number, ,0(), of both (()) and KC()) diverges exponentially as O(xi'1-1) and O(xT') respectively. As discussed above. there is a polynomial correction in the conditioning number the NTK that slightly improves its conditioning. Since O' is singular, we insert diagonal regularization term Id into O train the linear predictor Equation 6, where a a positive constant independent
from and XI. We find A (!) = O₂ (Ixx)): see Section for the derivation. summary, in the ordered phase, & = 11 log x (for simplicity, we ignore the polynomial correction) governs both trainability and generalizability of the predictor.
4.3 THE CRITICAL LINE X1 oZT(gt))
On the critical line both the diagonal and the off-diagonal terms of (!)) diverge linearly in the depth while K(O) converges to q" "11".. From Equation 14 we see immediately that the diagonal terms are given by (1) 9²' and (!)) lq". To compute the correction of the off-diagonals, keep the
7

---

Under review as a conference paper at ICLR 2020
32-5CMP
28-5PO1
28- IE-DDAAN
(a) Chaotic
(b) Ordered
(c) Critical: FCN and CNN-F
284
P 2010-0144 13-0-OW4
2000
206-OU
10 CORP
(d) Critical: CNN-P
(e) Critical: CNN-F and CNN-P
(1) Ordered: Dropout
Figure I: Condition numbers of NTKs and their rate of convergence. Different colors represent images of different size. For example, in the yellow "12-6", "12" represents the size of the dataset and "6" represents the dimension number (6 * 6 3 for FCNand (6, 6,3) for CNN) (a) In the chaotic phase, k()) converges to I for all architectures. (b) We plot x1x=11) confirming K explodes with rate xi/l in the ordered phase. In (c) and (d), the dashed lines representing the condition number (1) and solid lines the ratio between first and second eigenvalues. We see that, on the order-to-chaos transition, these two numbers converge to 2 and 2- (horizontal lines) for FC/CNN-F and CNN-P respectively. In (c), we plot rates of convergence for CNN-P (solid) and CNN-F (dashed), confirming that pooling slows down the convergence of x((1) by factor of d. (f) Adding dropout to the penultimate layer prevents (0))) from divergence in the ordered phase. The legends indicate the rate of the mask with p 1 meaning keeping all activations. Horizontal lines are the limit of ((()) computed in Equation 85 (here m 20 for all curves.)
(1) definition of ab unchanged but define 80) slightly differently to the above as 5(0) Pab iq" to take into account the linear divergence at large depths. Taylor expanding to second order we find,
( ab - 2 + ol )) X2
2 3 + 0(1
(23)
Thus for large (1) has the following form pd la and p = flg + O1). As in the ordered phase, for large it follows that ( essentially has two eigenspaces: one has dimension one and the other has dimension (m -1) 1) with
(m 2)g" 1+ m0L))
2
(1) max
N 3 O(1)
(24)
3
and the condition number (0)) = m+2
+ m0(1-1) - m+2 as 1 - xo. Unlike the chaotic and 2
2
ordered phases, (0)) converges with rate (1-1)). The (C(1) has Amax = mq* + m1)(1 and x R X2 1-1 and the condition number k! diverges linearly with slope mx2/2. A similar calculation gives A O(I-)) the critical line. In summary, ( converges to finite number and the network ought to be trainable for arbitrary depth but the residual predictor A decays polynomially, explaining why critically initialized networks with thousands of layers could still generalize (Xiao et al., 2018).
8

---

Under review as a conference paper at ICLR 2020
Figure 2: Maximal learning rate can be calculated via the Amax. y-axis: accuracy and æ-axis: multiples of Theeory- Each point on the solid (dashed) lines represents the best training (test) accuracy throughout training of one configuration. From blue to purple to red, (aw, 0b) is moving from the order phase the chaotic phase. p is the theoretical prediction.
4.4 REMARKS
We end this section with couple remarks. (1) The above theory holds for CNNs; see Section D. In the large depth setting, the NTK of CNNs without pooling essentially the same as the NTK of FCNs. (2) In the ordered phase, Adding a dropout layer could significantly improve trainability of network. For example, adding dropout to the penultimate layer, the condition number x(() will converge to a finite number rather than diverge exponentially; see (f) Figure and Equation in the appendix.
5 EXPERIMENTS
In this section, we provide empirical results to support the theoretical results in Section 4. Figure is generated using synthetic data and all other plots are generated using CIFAR-10 10 with MSE as the loss function.
Evolution of (!))) (Figure 1). We randomly sample inputs with shapes (m, k2 x 3) for FCN and (m, k, k, for CNN-F/CNN-P, where m E {12, 20) and k {6, 10]. We compute the exact NTK with activation function Erf using the Neural Tangents library (Novak et al., 2019a). We excellent agreement between the theoretical calculation of (!!) in Section (summarized in Table 1) and the experimental results Figure 1.
Maximum Learning Rates (Figure 2 top). In practice, given a set of typpe-parameters of net- work, knowing the range of feasible learning rates is extremely valuable. As discussed above, in the infinite width setting, Equation implies the maximal convergent learning rate is given by
Atheory 2/ 2/> Amax- We argue that Ttheory is good prediction for the maximal convergent learning rate for wide network. To test this statement, we apply SGD to train collection of fully-connected networks on CIFAR-10 10 using
training samples with the following configurations: (1) width: 2048 (2) o = 0.43 fixed, (3) depths: = 5, 10, 20, 40, (4) 10 different values of o., moving from the ordered phase (blue) to the chaotic phase (red) (5) 10 different learning rates 17 = pTttheory: with p E [10-1 10 Overall, we see excellent agreement for depths less or equal to 20 and reasonable good agreement for depth 40. We point out that the degradation of the agreement for larger depth may due to the fact that the finite width NTK becomes more stochastic as the ratio between depth and width increases (Hanin & Nica, 2019). Note that Table tells that, depth increases, Ttheory should decays exponentially and linearly in the chaotic and critical phases resp. and remain roughly constant in the ordered phase.
Trainability vs Generalization (Figure top). Our theoretical result suggests that in the deep chaotic regime (xf is large) training becomes easier but the network can not generalize. On the other hand, the network can generalize but training becomes much more difficult as one moves towards the deep ordered region because x²()) blows up exponentially. To confirm this claim, we conduct an experiment using 16k training samples from CIFAR- 10 with 20 20 different (aw., I) configurations. We train each network using SGD with batch size b = 1024 and learning rate = 0.31)sheory- Deep in the chaotic phase that all configurations reach perfect training accuracy but the network

---

Under review as a conference paper at ICLR 2020
Diweeer
Figure 3: Top: training (left) and test accuracy of FCN using SGD. Bottom: test accuracy of CNN--, CNN-F and the difference. In the blue strip, CNN-F significantly outperforms CNN-P, due to the fact that pooling increases the spectra gap by factor of d.
completely fails to generalize in the sense test accuracy approaches 10%. However, the ordered phase although the training accuracy degrades, generalization improves. The network eventually becomes untrainable after O(1)) layers. In both phases we see that the depth scales, & and &. respectively, perfectly capture the transition from generalizing overfitting.
CNN-P v.s. CNN-F: spatial correction (Figure 3 bottom). We compute the test accuracy using the analytic NTK predictor Equation 5, which corresponds the test accuracy of ensemble of gradient descent trained neural networks taking the width to infinity. We choose 1k training points, fix of and choose 20 20 different (aw. () configurations. We plot the test performance of CNN-P and CNN-F and the performance difference in Fig 3. Remarkably, the performance of both CNN-P and CNN-F are captured by & - log(X1) in the ordered phase and by &. -1/(lo & log & in the chaotic phase. We see that the test performance difference between CNN-P and CNN-F exhibits a region in the ordered phase (a blue strip) where CNN-F outperforms CNN-P by large margin. This performance difference is due the correction term predicted by the A (1) (0.row of Table
CONCLUSION AND FUTURE WORK
In this work, identify several quantities (Amax Àrest: K, and (1) related the spectrum of the NTK that control trainability and generalization deep networks. We offer a precise characteriza- tion of these quantities and provide substantial experimental evidence supporting theoretical results. In future work, we would like to extend our framework to other architectures, e.g., ResNet (with batch-norm), attention model. Understanding the implication of the sub-Fourier modes in the NTK to the test performance of CNN is also an important research direction.
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 1904::900..1990 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint 1XXiv:1409.044 2014.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(Feb):281-305 2012.
10

---

Under review as a conference paper at ICLR 2020
Yaniv Blumenfeld, Dar Gilboa, and Daniel Soudry. A mean field theory of quantized deep networks: The quantization-depth trade-off. arXiv preprint arXiv:1906.00777, 2019.
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical isometry and a mean field theory of RNNs: Gating enables signal propagation recurrent neural networks. International Conference Machine Learning, 2.18.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2019.
Ekin D. Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V. Le. Autoaugment: Learning augmentation strategies from data. The IEEE Conference on Computer Vision and Patlern Recognition (CVPR), June 2019.
Amit Daniely. SGD learns the conjugate kernel class the network. Advances in Neural Infor- mation Processing Systems 30. 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, 2016.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S. Schoenholz, Ed H. Chi, and Jef- frey Pennington. Dynamical isometry and mean field theory of Istms and grus. CoRR, 0bs/1901.0899) 2019, URL http: /ttp://aaae /atxivxivv./////////////////aav/ org/ abs /1999991.000 08987.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'17, pp. 1263-1272. JMLR.org, 2017. URL http:
//dl. acm. :ttp://cttttooo.ccfdddd033000000 33055331 30..:-3333331115311...1 3305512.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. International Conference on Artificial Intelligence and Statistics, pp. 249-256, 2010.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. arXiv preprint arXiv:1909, 00999, 2019.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the selection of initialization and activa- tion function for deep neural networks. arXiv preprint arXiv: /805. 082666 2018.
Jiaoyang Huang and Horng-Tzer Yau. Dynamics of deep neural networks and neural tangent hier- archy. arXiv preprint arXiv:1909.08111 08156, 2019.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. In Advances in Neural Information Processing Systems 31. 2018.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Universal statistics of fisher information in deep neural networks: mean field approach. arXiv preprint / 1806.8006111111 2018.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl- dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations, 2018
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv: 06720, 2019.
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Confer- ence on Learning Representations, 4 2018. URL https:/ /wwp///eeeeeeeeeee/o//e/e. net forum?ids -1-nGgWC-.
Radford M. Neal. Priors for infinite networks (tech. rep. no. crg-tr-94-1). University of Toronto, 1994.
11

---

Under review as a conference paper at ICLR 2020
Roman Novak, Lechao Xiao Jaehoon Lee, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neu- ral tangents: Fast and easy infinite neural networks in python, 2019a. URL http::/ggtthu. com/ httm//googeeneuraltteeea
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A. Abo- lafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes, In International Conference on Learning Representations, 2019b.
Daniel S Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D Cubuk, and Quoc Le. Specaugment: A simple data augmentation method for automatic speech recognition. arXiv preprint www.vv:904.0877000 2019.
George Philipp. Dawn Song, and Jaime G Carbonell. The exploding gradient problem demystified- definition, prevalence, impact, origin, tradeoffs, and solutions. arXiv preprinl arXiv: 171.0577, 2017.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jaseha Sohl-Dickstein, and Surya Ganguli. Expo- nential expressivity in deep neural networks through transient chaos. In Advances In Neural Information Processing Systems, pp. 3360-3368, 2016.
Maithra Raghu, Chiyuan Zhang, Jon Kleinberg, and Samy Bengio. Transfusion: Understanding transfer learning with applications to medical imaging. arXiv preprint arXiv: 1902.07280 2019.
Andrew M Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. International Conference on Learning Representationss 2017
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel. Timothy Lillicrap. Karen Si- monyan, and Demis Hassabis. general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 162(6419):1140-11 140-1144, 2018. ISSN 0036-8075. doi: 10.1 20.1126/science..o https/iience.arb444.... URL 6419/1140.
ence. sci sccienemagg org/ content/362/
Lechao Xiao, Yasaman Bahri, Jascha Sohl- Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of CNNs: How to train 10,000-layer vanilla convo- lutional neural networks. In International Conference on Machine Learning. 2018.
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge chaos. In Advances in Neural Information Processing Systems. 2017.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv: 1902..4700 2019.
Greg Yang. Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel Schoenholz. A mean field theory of batch normalization. arXiv preprint
2019.
12

---

Under review as a conference paper at ICLR 2020
A SIGNAL PROPAGATION OF NNGP AND NTK
Recall that
uab 0= ( + o ((+1)) 9¹
Pab Lab + 0 o (aab) Pab
(11) (1+1)
(25)
-(-11) q- + ou
+o T( p')
(26)
A.1 CORRECTION OF THE OFF-DIAGONALS IN THE CHAOTIC/ORDERED PHASE
Applying Taylor's expansion to the first equation of 25 gives
((+1) T + Eab of
Lab cab の T(in)) + oh ( (1) O
(27)
(112)
(28)
yas + o (Tab) cab + (E (12)
(29)
With Xe = ( we have
aab
(1+1)
ab !
(30)
Similarly, applying Taylor's expansion to the second equation of 25 gives
((+1))
ab = (1 + Xx.2Pab ab + x (1) ab
(1+1)
(31)
where Xc, = (gat). This implies
( ab Xe ab
(0)
(32)
8 X 8(0) +
(1
11
Xc.2
Pub
ab
(0)
(33)
Xe
Note that 50 contains polynomial correction term and decays like Ix.. The correction the fixed points in the ordered phase could be obtained using the same calculation:
(I) cb Xi
(0)
(34)
(1))
Xi
(00) ab
+
1
X2
p
cbb
(
(35)
X1
A.2 CORRECTION OF THE DIAGONASS ON THE CRITICAL LINE.
We have X1 on the critical line. We need to expand the first equation of 25 to the second order
(1) Sab = ca + 2 X2 ah + ((
(I+1)
(03)
(36)
Here we assume T has a continuous third derivative. The above equation implies
(
2
ol 7
abb
(37)
X2
Then
5(1+1)
ah
= (1+1)
lab
o6 + TT + ab Pab - 1q
11) (1) (1)
(38)
Eah
((+1)
+ (xi X2 22 + x3(5x)) 11
(1)
(1q" + ((0) lq+
(39)
Cab
(1+1) + (1 X2c 00 884h + 1g X2c cb
(1)
+ x3( 2lg
1
(40)
2
Plugging Equation 37 into the above equation gives
8(0 ab
= 14" + 01)
(41)
3
13

---

Under review as a conference paper at ICLR 2020
A.3 RELU
We only consider the critical initialization oă = and of = 0. Using the equations in Appendix C of (Lee et al., 2019) gives
2v2 3/2 ((2)22 3T
T( (11-))11-6
(42)
and taking the derivative w.r.t.
1/2 2 T( - = v2 6/2 + O
(43)
π
This is enough conclude (similar to the above calculation)
ob
(1)
=
3π
V2
,21 + olt-)) 3)
(44)
5
- O(1)
3
(45)
Recall that q()) = 1 and p!)) = for Relu network with o = 2. and σb = 0. Therefore
m + 3 1 m0(1),
3 1 + x() + 3
A max
m0(1/l).
(46)
3
A.4 RESIDUAL RELU
We consider the following "continuum" residual network
(((dtt) (1()) (W (zx(1)) b)
(47)
where t denotes the number of layer and dt > 0 sufficiently small and W and b are the weights and biases We also dă 2 (i.e. E[W w 21d) and of 0 (i.e. b b= 0). The NNGP and NTK have the following form
(((++d)) = (C()) - -k(TT(k
(48)
(+++t) (() ddtk(") + 2dt (1))))))))
(49)
Taking the limit dt + 0 gives
( 2T(K((1)
(50)
( x(() + 27 (T(())00
(51)
Using the fact that 90 = 1 (i.c. the inputs have unit variance), we can compute the diagonal terms ( = e¹ and plt) = te'. Let (2) = e c applying the above fractional Taylor expansion to T and
T. have
2V2
(1
ab
(1
00)3 + 0((1 )
(52)
3x
Solving this gives
4ab = (1
(t)
9n²
1-2 + ol1 2))
(53)
2
P + (11)
(54)
Thus the condition number is m/3 + This is the same as the non-residual Relu case discussed above.
B ASYMPTOTIC OF (
To keep the notation simple, we denote Xa = Xurain Ya = Yuains Ord = Orest, train. Oid O train- Recall that
A AY
(P(O (P(==(((0))--))) P((r)) Ya
(0(1) (1)
-1
0is (Ota) )1) Va (55)
Ed
dd
We split our calculation into three parts.
14

---

Under review as a conference paper at ICLR 2020
B.1 CHAOTIC PHASE
In this case the diagonal pd) diverges exponentially and the off-diagonab, Pub converges to bounded constant Pab. Thus P( O. We expand @ about its fixe point
A Y O (1) (0!)) -1 Yd
(56)
(Ota + 0(0%) (p0)d Par Id) 0002)) -1
Yd
(57)
- (ow 0(1))
Pob (117 -ld) + (626/ 20//(0))
ld
Ya
(58)
pll)
-1D))- (0% + +06%))
Pob (117 - Id) + 066 (1)) Yd p(l)
ld
(59)
-p())-1 (0(0%) + 0 /1(1)))) Ya
(60)
In the last equation, we have used the fact 1 = 0 and Or = 0 since Ya is balanced (i.e. containing the same number of positive (+1) and negative (-1) labels.) Therefore
A ( (1) (1(xo/xx)))
(61)
B.2 ORDER-TO-CHAR PHASE
Note that in this phase, both the diagonals and the off-diagonals diverge linearly. In this case
lim
- 1q
1,17
1 3
lim 100
1 lq* - del
=
(62)
Here we use 1a to denote the all '1' (column) vector with length equal to the number of training points in X and defined similarly. Note that the constant matrix B is invertible. By Equation 41
1 3
1 iq"
P(O())
1q"
dd
(63)
(I11 + 0(1/44")) ([1/44")((B (B+
(64)
3
(112 + (B 0(1/4)) 3
(65)
(66)
lim ((00))
(67)
10x
Thus
-
(68)
Ordered Phase In this case 0* is a rank one matrix. We add a diagonal regularization term and defined
(+(0) = Ord (9aa + old
(69)
where σ > 0 is a positive constant independent of the hyper-parameters (aws ob, 1). Let B, =
O* old. Then
(e = ( B, + 0
(70)
= -ig + O, (1
(71)
PP((0') O₂ (5(1))) ab
(72)
15

---

Under review as a conference paper at ICLR 2020
C DROPOUT
In this section, we investigate the effect of adding a dropout layer to the penultimate layer. Let
0 < p S 1 and 7140 (xr) be iid random variables
(x) (x)
{b dw
with probability P
(73)
with probability
p.
For 0 < -- 1,
(1+1) x VNU)
Σ wi(+ 6(2) (x)) (z))(())) tosb
(74)
and for the output layer,
N(L)
[1+ (x)
PVNIL wh (2)))()))))))))))) onb! (((
(75)
where w and 6 are iid Gaussians NO 1). Since no dropout is applied in the first L layers, the NNGP kernel KC()) and @()) can be computed using Equation 2 and Equation 7. Let K.f-1)) 1) and , (1+1) denote the NNGP and NTK of the (L+ 1-th layer. Note that when 1, 1,Ac( x(++1)
and 6 (1++)) ((++)) We will compute the correction induced by p < The fact
pp², if (i + (i,x²) (0, P, if (1xz = (1,x')
Ehy (x)) (f))
(76)
implies that the NNGP kernel (L+
(Schoenholz et al., 2017) is
T (a, x') + if x xtr r'
X((+1) (x, = E[2! (1+1) (x) (1+1)
(2')l
(77)
p
(o2T(1( (z, +o if a ==r'
Now we compute the NTK (1(+1),
which is sum of two terms
dz (2((tt)(z)
(2((Lt)((z')
(2')
az (1+)) (z)
( (02(Lt)((z))
(I²)
(((+)) (I, (I,x²)= =E
+ E
a0(L+1) 00(4+1)
00(SL)
00(5L)
(78)
Here ((L+1) denote the parameters in the (L + 1) layer, namely, w and ((2+22 and (1$L) the
remaining parameters. Note that the first term is in Equation 78 is equal to x: chain rule, the second term is equal to
k((++)) (I, x'). Using the
2
(C)
(x)
(a')
77
w(L+1) (o((+1))((tt))) w((+1) W/lt") (x)) (2))(( (2) (x)))
(L)
20(5L)
00(SL)
J-K=1
(79)
02 (L)
02 (1) (z)
(a)) (x')
E
Σ
おه ()) (4))) (x')
(80)
0O(SL)
0O1sL)
de 00 (x) 00(SL)
(2z) 0z)"0(()) (2')
-
(1 (1))
(1)))))) (x')) Eld(E (z))
(81)
2
OO(SL)
if x xtx
(82)
(1
a z=d.
16

---

Under review as a conference paper at ICLR 2020
In sum, that dropout only modifies the diagonal
O / (x, ( (2,
(83)
0 (2, (2, (2( + +1 (1-1111)) 1/p)03
In the ordered phase, we see
1 jog
lim ( (2, =p"
lim 1000
p (2,2)
p¹
+ (1
(84)
40000
p
p
and the condition number
(m - 1)p² + 1/1² + (1 20/
mp"
lim 10000
K
+1
(85)
( - 1) 0%
1 - 1) - o p
D CONVOLUTIONS
General setup. For simplicity of presentation we consider ID convolutional networks with circular padding as in Xiao al. (2018). We will see that this reduces to the fully-connected case introduced above if the image size is set to one and as such we will see that many of the same concepts and equations carry over schematically from the fully-connected case. The theory of two-dimensional convolutions proceeds identically but with more indices.
Random weights and biases. The parameters of the network are the convolutional filters and biases, w and n1, respectively, with outgoing (incoming) channel index i ()) and filter relative spatial location 3 E [+*] {-k; O,....P k).. As above, will assume Gaussian prior on both the filter weights and biases,
W! U,
(2kk + 1)m 1j.8
= =opp.
wyys ~/0,N(0.1) 1)
(86)
As above, oă and of are hyperparameters that control the variance of the weights and biases respec- tively. nt is the number of channels (filters) in layer 21: + is the filter size.
Inputs, pre-activations, and activations. Let X' denote a set of input images. The network has activations (z) and pre-activations 2 2(x)) for each input image E X C gnnd, with input channel count no E N, number of pixels d E N, where
k
(x) (x) = 2 (=
Dia
1=0 (x)
=
Σ j=1
Wi
W1 +bb
(87)
1>0
@ RR + TR is point-wise activation function. Since we assume circular padding for all the convolutional layers, the spacial size d remains constant throughout the networks until the readout layer.
For each / >> 0, as .n.u + xo, for each E N, the pre-activation converges in distri- bution to d-dimensional Gaussian with mean 0 and covariance matrix K(O), which can be computed recursively (Novak et al., 2019b; Xiao et al., 2018)
(((-1) Ao = (Ao ()+)
(88)
Here K (IC)) (I, x x')a. ofdj... T is non-linear transformation related to its fully- connected counterpart, and A convolution coupled with shift term acting on X'd x X'd PSD matrices
[T (K)) (x,x') = Em-N(O.y (Ø (ua (x)) ó (ua (x'))l
(89)
[A (A()) (x. x') = of + 03 Σ 2k +1
[K] K4 (2,
(90)
'ee will use Roman letters to index channels and Greek letters for spatial location. We use letters i' etc denote channel indices, o, o', to denote spatial indices and 18, S for filter indices.
17

---

Under review as a conference paper at ICLR 2020
D.1 THE NEURAL TANGENT KERNEL
To understand how the neural tangent kernel evolves with depth, we define the NTK of the 1-th hidden layer to be ))))
6 1 (x, V V (z) Vosiz (2¹)
(91)
where 05! denotes all of the parameters in layers at-or-above the l'th layer. It does not matter which channel index i is used because the number of channels approach infinity, this kernel will also converge in distribution to deterministic kemel ((++1) (Yang, 2019), which can also be computed recursively in similar manner to the NTK for fully-connected networks as,
((+1) k(++)) + Ao (T(K1) ) of
(92)
where T is given by Equation 89 with replaced by its derivative d'. We will also normalize the variance of the inputs to q² and hence treat T and T pointwise functions. We will only present the treatment in the chaotic phase to showcase how to deal with the operator A. The treatment of other phases are similar. Note that the diagonal entries of K()) and ( are exactly the same as the fully-comnected setting. We only need to consider the off-diagonal terms. Letting | + oo in Equation 92 we see that all the off-diagonal terms also converge. Let A = oN (AA - oī),, be the normalized convolution operator. Note that A does not mix terms from different diagonals and it (!) suffices handle each off-diagonal separately. Let cab and 8 denote the correction of the j-th diagonal of KC(1) and ( to the fixed points. Linearizing Equation 88 and Equation 92 gives
((+1) xe Xo ab (1+) ab
(93)
ab
8 (1+1) ~ ((AA(
Xa.2 +
Post (
(94)
Xe
(I+1) Next let {Pata be the eigenvalues of A and abbo and ab,a the projection of eab and the a-th eigenvector of A. Then for each a,
8(1) onto
(++1) aba x (1ax)) eaha
(95)
الl) ab.o
~ Paxe(t
(++1) + Xe2 post past ab.a + ab.a
(
(96)
Xe
which gives
ab PaxeCar.a 82 = place
(00) +1 (1+ aabia
=1(11
Xe,2 (0) Cab.a
Pub
(97)
Xe
Therefore, the correction ( - O' propagates independently through different Fourier modes. In each mode, up a scaling factor Pa. the correction is the same as the correction of its FC counterpart. Since the subdominant modes (with |pal < 1) decay exponentially faster than the dominant mode (with Pa = 1), for large depth, the NTK of CNN essentially the same as that of its FC counterpart.
D.2 THE EFFECT OF POOLING AND FLATTENING OF CNNS
attention CNNs. We show in the appendix that the dominant mode in CNNs behaves exactly like the fully-connected case, however we will see that the readout can significantly affect the spectrum. The NNGP and NTK of the I-th hidden layer CNN are 4D tensors xC!)) pixel locations. To perform tasks like image classification or regression, "flattening" and "pooling" (more precisely, global average pooling) are two popular readout strategies that transform the last convolution layer into the logit layer. The former strategy "flattens" an image size (d, .N into a vector in B and stacks a collecconnected layer top. The latter projects the (d. NN) image into a vector of dimension N via averaging out the spatial dimension and then stacks a fully-connected layer top. The actions of "flattening" and "pooling" the image correspond computing the
With the bulk of the theory in hand,
a. (z, z') and (
a 2z) where a, a' E [d] [o. 1,... - 1] denote the
18

---

Under review as a conference paper at ICLR 2020
mean of the trace and the mean of the pixel-to-pixel covariance the NNGP/NT,, respectively, i.e,,
+ Ratten (x, (x,xx)
Σ agd
p (r,
Σ
(z,
(98)
d
d²
a,a'Eld
where ! flatten pool) denotes the NTK right after flattening (pooling) the last convolution. We will also use O fo to denote the NTK of FC. flatten and x are defined similarly.
x!!)
As discussed above, in the large depth setting, all the diagonals 0 (z, x) = pl)) (since the in- puts are normalized to have variance q" for each pixel) and similar to @ all the off-diagonals @ (2, x')) are almost equal (in the sense they have the same order of correction to Pab if exists.)
(1) Without loss of generality, assume all off-diagonals are the same and equal to Pab (the leading correction of Lab for CNN and FCN are of the same order.) Applying flattening and pooling, the NTKs become
+ ( Batten (x, d
1
Σ
@
(z,
1 + 1x4xx
(99)
(1) pool (xr x²) =
1
Σ
(I, = d --- (p -Pab + Pab
(100)
d²
0,a
respectively. As see, ( is essentially the same its FCN counterpart 6 up sub- dominant Fourier modes which decay exponentially faster than the dominant Fourier modes. There- fore the spectrum properties of it and ic are essentially the same for large l.
However, pooling alters the NTK/NNGP spectrum in an interesting way. On the critical line, asymp- totically, (1) (md 2/ and X 24"1/(3d), and x() md+2 + md0O(-1). Here we use blue color to indicate the changes of such quantities against their (
flatten counterpart. Thus pooling decreases (1) roughly by factor of d and increases the condition number by factor of comparing to flattening. In the chaotic phase, pooling does not change the off-diagonals Lab but does slow down the growth of the diagonals by factor of d, i.c. (()) O /d). This sug- gests, in the chaotic phase, there exists a transient regime of depths, where CNN-F hardly perform while CNN-P performs well. In the ordered phase, the pooling does not affect X much but does decrease Arest by a factor of d and the condition number grows approximately like dxi' d times bigger than its flattening and fully-connected network counterparts. This suggests the existence of transient regime of depths, in which CNN-F outperforms CNN-P. This might be surprising because it is commonly believed CNN-P usually outperforms CNN-F.
(2) O(1)
19


Reviews:
[{"review_id": "rJgSrGqM5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the spectra of neural tangent kernels (NTKs) at large depth -- first let width go to infinity, and then let depth go to infinity. At infinite depth the kernel has the form a*identity+b*(all-one matrix), and the paper studies how the large-depth NTK converges to the limit in three cases: chaotic, ordered, and critical line. The paper draws connection between these behaviors with the trainability and generalization of corresponding neural networks. Furthermore, the difference between CNNs with and without global average pooling is studied.\n\nNTK has been a popular subject of research in deep learning theory, and it's an interesting direction to study the NTK in large depth. However, the exposition is confusing and I'm missing some key points of this paper. Therefore I cannot recommend acceptance at this time. See below for detailed comments.\n\n1. I don't really get how the spectrum of large-depth NTK is connected to generalization. At infinite depth, the NTK is just a trivial kernel Theta^*, as noted in the paper. It is claimed that a finite-depth correction Eqn. (7) \"captures the generalization.\" How exactly does it capture the generalization? Generalization appears to be highly dependent on the data distribution. I don't understand how the paper arrives at its conclusions regarding generalization.\n\n2. The paper (esp. Section 3) is written in a way very unfriendly to someone who is not familiar with previous work, with notation, derivations and conclusions buried in paragraphs. I wish there were some theorems clearly and formally summarizing the conclusions.\n\n3. It's unclear whether the studied regime (large depth, probably even larger with) is relevant in practice. Although there are experimental results provided, the CNN experiments are for the infinite-width NTK. It's unclear how they look like for practical networks.\n\n4. There are numerous typos and grammar errors in the paper, even in abstract and introduction.\n\n\n------\nupdate:\nThanks to the authors for the response, especially the clarification about what they mean by generalization. Since the concern about the exposition is still present, I can only update my rating to \"weak reject.\" I hope the authors could further improve the exposition of this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1x-LlrnFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the relation between trainability and generalization ability in deep neural networks. In the theoretical analysis, the authors used the Neural network Gaussian process (NNGP) kernel and Neural Tangent kernel (NTK). The paper clarified that the spectrum of the NTK and NNGP has an important role in investigating the generalization and trainability, i.e., the condition number of the NTK. Some numerical experiments showed an agreement of theory with the practical behavior of learning algorithms. \n\nIn this paper, some existing theoretical results on deep neural networks were combined to extract new insight. Thought the attempt of this paper is interesting, the readability of the paper is not necessarily high. \n\n- In equation (2), the operator T is defined as the kernel K(x,x'). However, the definition seems different from that in equation (8).  The authors need to make clear the definition of T.\n- What is the \"DC\" mode in the sentence above the equation (15)? \n- Is the derivation of the left part in equation (9) straightforward? How was the second term, chi_1 q^* p^(ell), derived?  I'm not sure how the dot{T} was dealt with. The argument below equation (3) should be used? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SkgIDMbRYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the evolution of Neural Tangent Kernel (NTK) at large-depth regimes. By analyzing the conditional number and eigenvalues, they identify three phases of hyper-parameters; 1) In the chaotic phase NTK converges to an identity matrix, which is easy to train but hardly to generalize. 2) In the ordered phase NTK converges to an all-one matrix, which is hard to train but generalizes well. 3) In the critical phase the conditional number converges to a constant. Furthermore, they also analyze the influence of pooling and flattening in CNNs and identify potential regimes where pooling hurts the generalization. They conduct empirical experiments to supporting their theoretical analyses.\n\nHowever, I think this paper is worth of more revisions because many theoretical analyses are unjustified. And some potential typos makes the analyses even more difficult to understand.\n\n1) It looks to me that Eq(2) and Eq(6) are contradictory, where T already contains sigma_w and simga_b in Eq(2) but re-multiplied in eq(6).\n2) The paper analyzes the dynamics by assuming the variances of inputs are q*, which is debatable. The variance q^l also evolves with the depth increases. It is unclear whether the condition number will change if you takes the evolution of q^l into considered.\n3) It is unclear how Eq(9) comes directly from Eq(6), and there aren't any rigorous proofs in the Appendix. Similarly for eq(14).\n4) In the paragraph below Eq(11) the paper states that \\Theta* becomes an all one-matrix. However, Eq(11) states the diagonal converges to q*/(1-xi_1), but the paragraph below Eq(9) states the off-diagonal converges to q*_{ab}/(1- xi_c). Because q*=q*_{ab} as you stated nearby, do you mean xi_1 = xi_c ? \n5) In the first paragraph of Section 3.3, p^l = q* and p^l=l q*. \n6) In the 2nd contribution, you mentioned \"eigenvector correlation\", while I cannot find anywhere else introducing this.\n7) The plots of Figure 1(b) should behave like convex if the kappa really evolves like x_1^l / l. However it is concave. \n8) In the first experiment, you state \"To confirm that the maximal feasible learning rate are ... 2/(lambda_max)\". However, learning rates are never discussed in this paper. It is confusing why this experiment is useful. \n\nGenerally speaking, I think the paper needs careful revisions to support its theoretical analyses. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked 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: The paper investigates the trainability and generalization of deep networks as a function of hyperparameters/architecture, while focusing on wide nets of large depth; it aims to characterize regions of hyperparameter space where networks generalize well vs where they do not; empirical observations are demonstrated to support theoretical results. However, all reviewers agree that, while the topic of the paper is important and interesting, more work is required to improve the readability and clarify the exposition to support the proposed theoretical results.
 
Decision: Reject