We prove the precise scaling, at finite depth and width, for the mean and variance of the neural tangent kernel (NTK) in a randomly initialized ReLU network. The standard deviation is exponential in the ratio of network depth to width. Thus, even in the limit of infinite overparameterization, the NTK is not deterministic if depth and width simultaneously tend to infinity. Moreover, we prove that for such deep and wide networks, the NTK has a non-trivial evolution during training by showing that the mean of its first SGD update is also exponential in the ratio of network depth to width. This is sharp contrast to the regime where depth is fixed and network width is very large. Our results suggest that, unlike relatively shallow and wide networks, deep and wide ReLU networks are capable of learning data-dependent features even in the so-called lazy training regime. Modern neural networks are typically overparameterized: they have many more parameters than the size of the datasets on which they are trained. That some setting of parameters in such networks can interpolate the data is therefore not surprising. But it is a priori unexpected that not only can such interpolating parameter values can be found by stochastic gradient descent (SGD) on the highly non-convex empirical risk but also that the resulting network function generalizes to unseen data. In an overparameterized neural network N (x) the individual parameters can be difficult to interpret, and one way to understand training is to rewrite the SGD updates ∆θ p = − λ ∂L ∂θ p , p = 1, . . . , P of trainable parameters θ = {θ p } P p=1 with a loss L and learning rate λ as kernel gradient descent updates for the values N (x) of the function computed by the network: Here B = {(x 1 , y 1 ), . . . , (x |B| , y |B| )} is the current batch, the inner product is the empirical 2 inner product over B, and K N is the neural tangent kernel (NTK): Relation (1) is valid to first order in λ. It translates between two ways of thinking about the difficulty of neural network optimization: (i) The parameter space view where the loss L, a complicated function of θ ∈ R #parameters , is minimized using gradient descent with respect to a simple (Euclidean) metric; (ii) The function space view where the loss L, which is a simple function of the network mapping x → N (x), is minimized over the manifold M N of all functions representable by the architecture of N using gradient descent with respect to a potentially complicated Riemannian metric K N on M N . A remarkable observation of Jacot et al. (2018) is that K N simplifies dramatically when the network depth d is fixed and its width n tends to infinity. In this setting, by the universal approximation theorem (Cybenko, 1989; Hornik et al., 1989) , the manifold M N fills out any (reasonable) ambient linear space of functions. The results in Jacot et al. (2018) then show that the kernel K N in this limit is frozen throughout training to the infinite width limit of its average E[K N ] at initialization, which depends on the depth and non-linearity of N but not on the dataset. This mapping between parameter space SGD and kernel gradient descent for a fixed kernel can be viewed as two separate statements. First, at initialization, the distribution of K N converges in the infinite width limit to the delta function on the infinite width limit of its mean E[K N ]. Second, the infinite width limit of SGD dynamics in function space is kernel gradient descent for this limiting mean kernel for any fixed number of SGD iterations. As long as the loss L is well-behaved with respect to the network outputs N (x) and E[K N ] is non-degenerate in the subspace of function space given by values on inputs from the dataset, SGD for infinitely wide networks will converge with probability 1 to a minimum of the loss. Further, kernel method-based theorems show that even in this infinitely overparameterized regime neural networks will have non-vacuous guarantees on generalization (Wei et al., 2018) . But replacing neural network training by gradient descent for a fixed kernel in function space is also not completely satisfactory for several reasons. First, it suggests that no feature learning occurs during training for infinitely wide networks in the sense that the kernel E[K N ] (and hence its associated feature map) is data-independent. In fact, empirically, networks with finite but large width trained with initially large learning rates often outperform NTK predictions at infinite width. One interpretation is that, at finite width, K N evolves through training, learning data-dependent features not captured by the infinite width limit of its mean at initialization. In part for such reasons, it is important to study both empirically and theoretically finite width corrections to K N . Another interpretation is that the specific NTK scaling of weights at initialization (Chizat & Bach, 2018b; a; Mei et al., 2019; 2018; Rotskoff & Vanden-Eijnden, 2018a; b) and the implicit small learning rate limit (Li et al., 2019) obscure important aspects of SGD dynamics. Second, even in the infinite width limit, although K N is deterministic, it has no simple analytical formula for deep networks, since it is defined via a layer by layer recursion. In particular, the exact dependence, even in the infinite width limit, of K N on network depth is not well understood. Moreover, the joint statistical effects of depth and width on K N in finite size networks remain unclear, and the purpose of this article is to shed light on the simultaneous effects of depth and width on K N for finite but large widths n and any depth d. Our results apply to fully connected ReLU networks at initialization for which our main contributions are: 1. In contrast to the regime in which the depth d is fixed but the width n is large, K N is not approximately deterministic at initialization so long as d/n is bounded away from 0. Specifically, for a fixed input x the normalized on-diagonal second moment of K N satisfies Thus, when d/n is bounded away from 0, even when both n, d are large, the standard deviation of K N (x, x) is at least as large as its mean, showing that its distribution at initialization is not close to a delta function. See Theorem 1. 2. Moreover, when L is the square loss, the average of the SGD update ∆K N (x, x) to K N (x, x) from a batch of size one containing x satisfies where n 0 is the input dimension. Therefore, if d 2 /nn 0 > 0, the NTK will have the potential to evolve in a data-dependent way. Moreover, if n 0 is comparable to n and d/n > 0 then it is possible that this evolution will have a well-defined expansion in d/n. See Theorem 2. In both statements above, means is bounded above and below by universal constants. We emphasize that our results hold at finite d, n and the implicit constants in both and in the error terms Under review as a conference paper at ICLR 2020 2 ) are independent of d, n. Moreover, our precise results, stated in §2 below, hold for networks with variable layer widths. We have denoted network width by n only for the sake of exposition. The appropriate generalization of d/n to networks with varying layer widths is the parameter which in light of the estimates in (1) and (2) plays the role of an inverse temperature. Taken together Theorems 1 and 2 show that in fully connected ReLU nets that are both deep and wide the neural tangent kernel K N is genuinely stochastic and enjoys a non-trivial evolution during training. This suggests that in the overparameterized limit n, d → ∞ with d/n ∈ (0, ∞), the kernel K N may learn data-dependent features. Moreover, our results show that the fluctuations of both K N and its time derivative are exponential in the inverse temperature β = d/n. It would be interesting to obtain an exact description of its statistics at initialization and to describe the law of its trajectory during training. Assuming this trajectory turns out to be data-dependent, our results suggest that the double descent curve Belkin et al. (2018; 2019); Spigler et al. (2018) that trades off complexity vs. generalization error may display significantly different behaviors depending on the mode of network overparameterization. However, it is also important to point out that the results in Hanin (2018); Hanin & Nica (2018); Hanin & Rolnick (2018) show that, at least for fully connected ReLU nets, gradient-based training is not numerically stable unless d/n is relatively small (but not necessarily zero). Thus, we conjecture that there may exist a "weak feature learning" NTK regime in which network depth and width are both large but 0 < d/n 1. In such a regime, the network will be stable enough to train but flexible enough to learn data-dependent features. In the language of Chizat & Bach (2018b) one might say this regime displays weak lazy training in which the model can still be described by a stochastic positive definite kernel whose fluctuations can interact with data. Finally, it is an interesting question to what extent our results hold for non-linearities other than ReLU and for network architectures other than fully connected (e.g. convolutional and residual). Typical ConvNets, for instance, are significantly wider than they are deep, and we leave it to future work to adapt the techniques from the present article to these more general settings. . Since the number of V in Γ 2 ( n) with specified V (0) equals , we find that so that for each and similarly, Here, E x is the expectation with respect to the probability measure on V = (v 1 , v 2 ) ∈ Γ 2 obtained by taking v 1 , v 2 independent, each drawn from the products of the measure We are now in a position to complete the proof of Theorems 1 and 2. To do this, we will evaluate the expectations E x above to leading order in i 1/n i with the help of the following elementary result which is proven as Lemma 18 in Hanin & Nica (2018). Proposition 10. Let A 0 , A 1 , . . . , A d be independent events with probabilities p 0 , . . . , p d and B 0 , . . . , B d be independent events with probabilities q 0 , . . . , q d such that Denote by X i the indicator that the event A i happens, X i := 1 {Ai} , and by Y i the indicator that B i happens, Then, if γ i ≥ 1 for every i, we have: where by convention α 0 = γ 0 = 1. In contrast, if γ i ≤ 1 for every i, we have: We first apply Proposition 10 to the estimates above for we find that Since the contribution for each layer in the product is bounded above and below by constants, we have that 2 is bounded below by a constant times and above by a constant times Here, note that the initial condition given by x and the terminal condition that all paths end at one neuron in the final layer are irrelevant. The expression (45) is there precisely 3 ≤ 1, and K i = 1. Thus, since for i = 1, . . . , d − 1, the probability of X i is 1/n i + O(1/n 2 i ), we find that where in the last inequality we used that 1 + x ≥ e When combined with (23) this gives the lower bound in Proposition 3. The matching upper bound is obtained from (46) in the same way using the opposite inequality from Proposition 10. To complete the proof of Proposition 3, we prove the analogous bounds for E[∆ ww ] in a similar fashion. Namely, we fix 1 ≤ i 1 < i 2 ≤ d and write The set A is the event that the first collision between layers i 1 , i 2 occurs at layer . We then have On the event A , notice that F * (V ) only depends on the layers 1 ≤ i ≤ i 1 and layers < i ≤ d because the event A fixes what happens in layers i 1 < i ≤ . Mimicking the estimates (45), (46) and the application of Proposition 10 and using independence, we get that: Finally, we compute: Under review as a conference paper at ICLR 2020 Combining this we obtain that E[∆ ww ]/ x 4 2 is bounded above and below by constants times This completes the proof of Proposition 3, modulo the proofs of Lemmas 6-9, which we supply below.
The neural tangent kernel in a randomly initialized ReLU net is non-trivial fluctuations as long as the depth and width are comparable. 
{"src": "scitldr-AIC_train", "paper_id": "SJgndT4KwB"}