Wide Neural Networks are Interpolating Kernel Methods: Impact of Initialization on Generalization
Authors: Manuel Nonnenmacher
David Reeb
Ingo Steinwart
Venue:  (2020)
Keywords: overparametrization
generalization
initialization
gradient descent
kernel methods
deep learning theory

Abstract: The recently developed link between strongly overparametrized neural networks (NNs) and kernel methods has opened a new way to understand puzzling features of NNs, such as their convergence and generalization behaviors. In this paper, we make the bias of initialization on strongly overparametrized NNs under gradient descent explicit. We prove that fully-connected wide ReLU-NNs trained with squared loss are essentially a sum of two parts: The first is the minimum complexity solution of an interpolating kernel method, while the second contributes to the test error only and depends heavily on the initialization. This decomposition has two consequences: (a) the second part becomes negligible in the regime of small initialization variance, which allows us to transfer generalization bounds from minimum complexity interpolating kernel methods to NNs; (b) in the opposite regime, the test error of wide NNs increases significantly with the initialization variance, while still interpolating the training data perfectly. Our work shows that -- contrary to common belief -- the initialization scheme has a strong effect on generalization performance, providing a novel criterion to identify good initialization strategies.

Under review as a conference paper at ICLR 2020
WIDE NEURAL NETWORKS ARE INTERPOLATING KERNEL METHODS: IMPACT OF INITIALIZATION ON GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
The recently developed link between strongly overparametrized neural networks (NNs) and kernel methods has opened new way understand puzzling features of NNs, such as their convergence and generalization behaviors. In this paper, we make the bias of initialization on strongly overparametrized NNs under gradi- ent descent explicit. We prove that fully-connected wide ReLU-NNs trained with squared loss are essentially a sum of two parts: The first is the minimum complex- ity solution of an interpolating kernel method, while the second contributes to the test error only and depends heavily on the initialization.
This decomposition has two consequences: (a) the second part becomes negli- gible in the regime of small initialization variance, which allows us to transfer generalization bounds from minimum complexity interpolating kernel methods to NNs; (b) in the opposite regime, the test error of wide NNs increases significantly with the initialization variance, while still interpolating the training data perfectly. Our work shows that contrary common belief the initialization scheme has strong effect on generalization performance, providing a novel criterion to identify good initialization strategies.
INTRODUCTION
Neural networks (NNs) have celebrated many successes over the past decade and achieved state of the art performance across various domains and tasks. From a theoretical standpoint, however, many aspects of neural networks not well understood, as for example illustrated by Zhang et al. (2016). Neural networks seem to contradict classical learning theory as, in many scenarios, they able to fit random labels perfectly while still generalizing well when trained on the true labels. In addition, overparametrized neural networks frequently exhibit even improved test performance when the number of parameters increased further (Belkin al., 2019). NN models thus often seem to avoid overfitting.
Very recently there have been advances in understanding the training and evaluation behavior of neural networks in the infinitely wide limit (Jacot et al., 2018; Hayou et al. 2019) and also in the strongly overparametrized regime (Du al.) 201 8b Li Liang 2018 Allen Silln-ZZuu et al.! 2018 8a), which is close to the infinite limit NN. Both lines of work express the behavior of the neural network terms of the so-called neural tangent kernel (NTK). particular, Du al. (2018b) showed in this way that, under mild conditions, strongly over-parametrized neural networks converge to global minimum of zero training error.
In another line of research, Belkin et al. (0188) suggested a new picture of learning in the over- parametrized regime, introducing an "interpolating kernel method" which successfully learns in this regime. This method selects the least complex function that interpolates all data points perfectly, as opposed to traditional methods which balance the function's 's complexity against its goodness-of It is suggested that this picture of overparametrized learning could help understand neural networks.
overparametrizee NNs are indeed linked to such kernel methods, then zero (or small) training error alone might not tell us much about the test performance, the measure of function complexity could be determined by the NN architecture, initialization, and the optimization method. A bad NN design may lead to unfavorable complexity measure that could result in large generalization gap.

---

Under review as a conference paper at ICLR 2020
The question therefore remains in which way exactly overparametrized neural networks linked to interpolating kernel methods? And how can this connection help us better understand neural networks and their puzzling features?
1 OUR CONTRIBUTIONS
In this paper we answer the first question by making the link to interpolating kernel methods explicit for strongly overparametrized NNs. After that, exhibit two implications for NNs which this connection allows us to draw.
First, for strongly overparametrized ReLU-NNs make the bias explicit that is imposed by the NN initialization and by training with discrete gradient descent steps on the squared loss. We achieve this by decomposing the learned NN function well the test error into two terms: The first term corresponds to a minimum complexity interpolating kemel method, whereas the second term is proportional to the initialized weights and gives non-zero contribution only if the test input is not part of the training set.
Second, we are able bound the difference between NN with standard initialization of small variance and the solution of minimum complexity interpolating kernel method based on the NTK. This bound provides a new way to transfer existing test error bounds from interpolating kernel methods to NNs, and vice versa.
Our third contribution shows that without putting any constraints on the NN initialization, low train- ing error does not imply low test error. This is because the second term in the above test error decomposition grows as a power of the initialization variance, as we show, whereas the first term is independent of this variance. Thus, the test error grows dramatically with increasing initialization variance, despite (close to) zero training error. Our findings provide an additional theoretical way to analyze initialization schemes, besides the existing heuristics and intention to prevent vanishing and exploding gradients (He et al. 2015 Glorot & Bengio 2010).
Our theoretical bounds and insights are nicely corroborated in several experimental settings.
1.2 NOTATION
We consider a supervised learning setting with data D (1),, C BC) x R consisting of N training points, i.e. the inputs come from the bounded d-dimensional ball BY((0) = fa Rd || < 1 We often view the training inputs X = (Z1,..., 2N)² E Nxx and corresponding labels Y (yi,.... "² E IR in matrix form. For any function g with domain Rd, we define g(X) as the row-wise application of g. Similarly, for any set Drest C Rd R of N test points we define Xiest E RNNxx and Yist E MR. We call a dataset consistent x; = Ij implies y/s = yg.
We denote the output of fully- fully-connected NN with L layers and parameters 0 by
1 (x)
" ab!,
Vmz
ht n2(x)= W a(hhhh + ot' for 2,...,
(1)
mm
h2 1²())=
W abt e ER.
m1
where a(h) := max 0} is the ReLU-activation function applied componentwise, denotes the number of neurons layer I, and W' R and b' Rm= are the weights and biases. choose the number of units in each hidden layer to be the same my For simplicity and m = 0' = [W ,b' denotes the vector of weights and biases in layer I, and I = 1, 0= 0 /²1 the vector of all parameters, whose total number is M = Et= + 1)m4- We keep the "initialization variance" o² (equivalently. > 0) as an explicit scalar parameter, that can be varied.
for
We consider one-dimensional outputs in this paper, although this is easy to generalize. Our arguments hold for general fully-connected NNs, in the "wide limit" min -i oc.
2

---

Under review as a conference paper at ICLR 2020
Our parametrization together with standard normal initialization W 0y NO 1) is the so-called NTK parametrization (e.g. Du et al. (2018b)) a forward pass this is equivalent to the standard parametrization (setting 0/ ym: 1 in Eq. with the weights and biases initial- ized at variances o²/ //m and o², respectively (He et al. 2015). During gradient training the two parametrizations are equivalent up to a parameter-dependent scaling factor of the learning rate (Lee) et al. 2019).
We consider the squared error loss E(D. v) = ---1 =////2 and train by minimizing the empirical risk
(D) = Σ
11 NN (X) - 112//2
(x,0)ED
using gradient descent (GD). That is, starting from the initialization 0 = fu the weights are updated according to the discrete iteration 0(+1 = 8, ((() for t = 0, ....., where 1) is a learning rate.
We connect NNs to interpolating kernel methods w.r.t. two specific kernel functions that are defined for any initialization 0 Bg of NN (1) The first kernel Vp Rd Rd - IR is associated with training only the last layer 8² of NN (Lee al. 2019).
where <bxx) = VoL ANN (x) o=00 E RII(m+1)
(3)
is the corresponding feature map. The second is the so-called neural tangent kernel (NTK)
$
Rd x Rd + R associated with training all NN parameters (Jacot et al. 2018 Lee et al. 2019).
.NN (<x,2') (===))=(())((()))) ((z))(z') where o(x) Vefe
0=
RRIM
(4)
again represents the feature map. The "minimum complexity interpolating kernel method" fits a consistent training set D perfectly, using a function of minimum kernel norm w.r.t. kernel K:
fim arg min || JEHK
subject Y == f(X),
where H. is the reproducing kernel Hilbert space (RKHS) associated with K (Belkin et al, (2188);; also App. B). Additionally, we denote the solution of fully converged fully-connected ReLUU NN trained with gradient descent, squared loss and random initialization by fNN, We denote the test losses for these two predictors by Lmmet fmeeh
fmmeeh (Xtes) Yesall (/ff//NN /(Niest for meth NN, int.
RELATED WORK
There are two main lines of research related to our work. The first line investigated in which way strongly overparametrized NNs, where the number m of units per hidden layer scales polynomially with the number N of training data points, converge to arbitrary small training error during training.
The first papers to investigate this for 1 hidden layer were Daniely (2017). Li & Liang 2018 and
Du et al. (2018b). Later, AAllen-Zhn Zhu et al. (2018a), Allen-Zhu et al. (2018b). Zou et al. 2018 and
Du al. 20) Sa) extended the work to deeper networks, CNNs and RNNs (Goodfellow al.. 2016).
[i& Liang (018)) mostly focus on the cross entropy loss, whereas Du et al. (2018b) focuses on the squared error as we do here. Additionally, Du al. (2018b) the first work connect the training behaviour of finite NNs (not only in the limit of infinite width m) to the NTK-kernel introduced by Dacot al. (0018). This connection is important for our work. In a similar vein, Arora et al. (019b) developed data dependent generalization bounds based on the fact that the weights do not move far from their initialization, as shown in the above works. Furthermore, Arora et al. (2019a) experimentally evaluate the generalization behaviour of the infinite width solution of NNs in the NTK-limit.
Most of these contributions focus on showing that the training loss converges to global minimum or that the training dynamics is close to a trajectory that converges to zero training loss. We build upon these works, but in contrast our focus is the connection between the test error of trained NN and the error of an interpolating kernel method. We achieve this by resolving the implicit bias that the initialization and gradient descent (GD) has the test loss. The initialization bias the training loss is minor compared to the test loss. The most related work to ours is by Zhang et al. 2019). They investigate similar issue we do but use different method to weaken the effects
3

---

Under review as a conference paper at ICLR 2020
of non-zero initialization and also do not quantify the impact of initialization on generalization but give evidence for such an effect. The recent contribution Lee et al. (2019). building upon Lee et al. 2017), Matthews al. (2018) and Neal (1996). explicitly solves the training dynamics and shows that the solution in the trained infinite model seems to be similar to a Gaussian Process, even though its covariance is not the Bayesian posterior of simple prior. The solution of their continuous training time analysis is similar to the linearized model in the proof of our Thm. 2 We perform a discrete-time analysis, as in actual NN training, instead of the vontinuous-time (ODE-like) analysis of other works. Woodworth et al. (2019) uses a continuous time analysis as well to focus on the effect of noise in the gradients. [Borovykh (2019) investigates the effect of the scaling between the "deep" and the "kernel" regime.
The second line of related work introduces interpolating kernel methods and the idea of an over- parametrized learning regime which does not suffer from overfitting even though the number of parameters be much larger than the number of training samples. This line of work was mainly introduced by Belkin et al. (2018)) and the follow-up works Ma et al. (2017) 7); Belkin et al. (201 8c The main idea is, instead of regularizing the function while trying to fit the data points well, to regularize (the complexity of) function that perfectly interpolates all data points. This newly identified overparametrized learning regime challenges the conventional thinking about the bias- variance-tradeofff (Vapnik) (003)) from the underparametrized regime. Belkin et al.) (2019) introduces a houble-dip picture to describe the transition between the two regimes. [iing & Rakhhin (2018) have derived generalization bounds for these interpolating kernel methods using novel techniques. Using our explicit link to NNs, this will provide an alternative to NN generalization bounds like margin or PAC-Bayes-biid connection between overparametrized NNs and interpolating kernel methods has been suggested in
bounds (c.g.. Bartlett al. (2017): Neyshabur et al. (2017)) While
the papers above, the link has not been made explicit a rigorous way, to the best of our knowledge.
The implicit bias of (stochastic) gradient descent (SS)D) and random initialization on the trained NN has been the topic of many previous works, e.g. Soudry et al. (2018); Glorot & Bengio (0100); Daniely et al. (2016); |Rahaman et al. (2088): Oymak & Soltanolkotabi (2018), which all elucidate certain aspects of the implicit bias. Our work is unique in that it investigates the effect (implicit bias of (S)GD and random initialization)
the test error of trained NNs, exhibiting NNs where despite always vanishing training error- the test error can be either very good or arbitrarily large. Without gradient descent training and in deterministic fashion, such examples have been constructed in (Mücke& & Steinwart 2019).
LINKING WIDE NNS AND INTERPOLATING KERNEL METHODS
We now develop the link between strongly overparametrizee neural networks and minimum com- plexity interpolating kernel methods mathematically. We first illustrate the main idea with the sim- pler case where only the last NN layer is trained, before extending the result to general NN training.
3.1 PARADIGMATIC LINEAR CASE: TRAINING ONLY THE LAST NN LAYER
As the NN function fNN(2) (x) 1 is linear in the parameters 0L of the last layer, the associated fea- tures vxx) = Vo
PNN (xr) le, and corresponding kernel Vi from (3) do not depend on the last-layer
initialization 0/: (but depend on the other layers 8) gl:h.-1), and fø (z) = (8" (xx) holds exactly for all 0 and x. Starting NN gradient descent at Of = 0, we get the following simple link:
Theorem Let J be the fully converged solution of fully-connectedd strongly overparametrized ReI.U-NN i with layers, where only the last layer 0² = [W b²) has been trained, using gradient descent under squared loss consistent dataset D, after it had been initialized at 0 = 0, and all other layers have been kept at their random initialization ~ (O, 1). Then it holds that
fd (x*) = -fi (x*)
Vxx"" E Rdd
where fig is the minimum complexity interpolating kernel solution 5 of w.r.f. kernel VV
3
Proof. Abbreviating the last-layer parameters by 0 = 04 and using the aforementioned linearity fo(x) = (0, (x)) 9, the gradient descent update rule reads:
0e+1 0. vp/ (1)(())))))))) Y)-
4

---

Under review as a conference paper at ICLR 2020
This iteration can be solved explicitly using induction and the binomial theorem (Shah al. 2018):
E(- (A ()(())))))))))) (Y (XX)00
01 = 00 + xX)²"
(8)
= (X)) (x (x(X)(()))) [1- - (11 -
where (x(X)((X) denotes the pseudoinverse. If the learning rate satisfies " 2/Amax (X) such that gradient descent converges, we get (x-mm(X)xxx in the limit + oe the spectral radius is smaller than one and the term in square brackets can be simplified to 1. To be precise this holds since D is consistent and we are in the strongly over- parametrized regime, so that Y (and (())))) lies in the range of 2b( [[ x)" almost surely (over the random initialization بb on which t depends), see also Du et al. 2018b).
-
Setting 9g = 0 as presupposed, we obtain the following predictor at full convergence (t = oo):
(>²) = (0.c (xxx)) 1>(x" (xx)=))))((())))))(()) ()) (((X))x(x)")
(9)
The same value do can be obtained as the solution to the following least squares interpolation:
xx arg arg min |01| subject Y == xx())
(10)
This can in turn be written minimizing the RKHS norm of an interpolation function w.r.t. the kernel from Eq. (3) (for details on this see App-
cint
arg min Ilfll
subject to Y Y= f()..
(11)
JEHo
The claim has thus been proven by deriving the explicit solution 9 and showing it to equal fint
3.2 GENERAL CASE: TRAINING THE FULL NEURAL NETWORK
In the case of training the full NN, we want to follow similar steps as in Sect. 3.1 first approximate (NN (x) affine-linearly by f around its initialization 0 Oo. using recent results on wide NNs (Du et al. 2018b). We further drop the requirement that any components of 0, must vanish; note, e.g., that the suggestive requirement Og
For this, we
(analogous Sect. 3. would, for L > 1, lead to vanishing features o(x) Vafe NN Veff"(z)), o, and a degenerate kernel & = 0. Nonzero 8g will however result in an initialization bias f! as we will see (Eq. (14).
Theorem
Let f ANN be the fully converged solution of a strongly overparametrized ReLU-NN ( with L layers, each with m neurons, where all layers 0 have been trained using gradient descent under squared loss on a consistent dataset after random initialization On ~ [0, 1). Then there exists a N E IN such that for all NN with m 2 N and Vx" E (0) it holds with probability at least 28 over the initialization that
of
1
1N Fi (x)))
+0
(12)
81/2
m2
where fin is the minimum complexity interpolating kernel solution
of D w.r.t. kernel & (
For the proof of Thm. we describe here especially those steps which are new compared to Thm. The first property we need the approximate linearity of the NN in its parameters during the whole gradient training. This is the reason why we restrict to strongly overparametrized fully-connected NNs. For such networks, a combination of the works (Jacot et al. (0018) : Du et al. (2018b); Lee 0. stays close to the
et al. (2019) shows that the solution tg of the training dynamics initialization dg. and the deviation from a linear model vanishes with growing width m:
Lemma 1 (Lee et al. (2019); Du et aL 2018b)) Denote the linearization of NN ( around its (x) + (o)N(())) (0 (0-00). Further, for t 2 0, let O2 and 0, be the parameters obtained by gradient descent training starting from Og with sufficiently small step size of the full NN and its linearisation respectively. Then, there exists some N E NN such that for all m 2 N it holds with probability least 1 8 over the initialization that: sup, JNN (x) flim (z))²
initialization Og by fli
JNN
b.
((1/m) for all x: E (0).
5

---

Under review as a conference paper at ICLR 2020
Similar linearisation hold for strongly overparametrized RNNs and CNNs as well, not only for cully-con NNs. The theorem proves that for every sufficiently wide NN the lincarised solu- tion is close to the trained full NN. For more detailed analysis of the dependence of N on the width m, variance a and 5 we refer to Lee et al. 2019): Du et al. (2188). Using this result, we continue our analysis with flln which can rewrite
(x))
J0g
(0 0o, (f(x))
(J0 (x) (Po: ((x))) + (0, 6(x)) were ((x) - Vele (a:)leo the feature vector defined in Eq. 4. Similar to the proof of Thm. gradient descent on f with the loss function ( Y 1/ (1x(X ( (x)))) leads to the final (L + oo) parameter and sufficiently small step size < 2/Amax
G 00 + "(x)" (6(X))(X))) (Y SNN ( (X)), resulting in the function
(x)( for (I) +
(Y - (X)). (X)).
(13)
13 and thereby fAN, to the solution far of the interpolating model, two steps remain to be done. First we show that the two summands in Eq. (13) which are not proportional to the labels Y can be simplified into single form for cully-connected ReLUUNNN: this can be done by showing fe, (x) = & (0n, (())) (see Lemma 2 for more details). Secondly, we can bound this single expression from above in terms of the initializaiin variance (Lemma 3 for proofs see Appendix.
To connect Eq.
The term proportional to Y is then identified with fint.
Lemma 2 For a fully-connected ReLU-NN NNN (Eq. 1 with L layers. the trained linearized version flin from Eq. (3 can be written as follows:
(x) = (lz))(()))))))) (xx))(())(((xxxxx)))))) -
Og- (14)
Thus, the trained (NN()) (x) + 011 mm) decomposes essentially into the two terms of Eq. 149 (for x E (0))
As (x) - f())()) S O(L//m), the expression 14 holds for the trained fNN in the wide limit m D0 well. This technical result enables all of our results in Thms, and
Eq. (4p can be understood intuitively (in the case of a consistent D): The first term makes the model interpolate the training data D perfectly (X) = Y), independently of the initialization 8o whereas the second term vanishes on the training data x: = X and thus only contributes to test inputs x x². The second term furthermore depends on the initialization lo, more precisely on the component of 0, that is orthogonal to the feature manifold spanned by the data D, i.e. orthogonal to ((x)))=- =xX)] is the projector onto the kernel
the range of o(X)". Note that [1 ((( X of ((X), about which the dataset D does not give any information.
Lemma 3 For a fullly-connected ReLU-NN ANN, it holds for all x E (0) with probability at least 0ol - x" v8
1 - 8 over the initialization Gg that [ (1
As in the proof of Thm. I (see Eqs. 9 ITT) the first part of the decomposition in Eq. 14 is
fist. By Lemma 3 we see that for small o² the distance between flin and fint becomes small with high probability, and plin and fNN are close too because of m >> N. The triangle inequality gives the desired result. Thus, strongly overparametrized neural networks initialized with small variance and trained under gradient descent correspond to solutions of a minimum complexity interpolating kernel method.
If fi (ax)) < |f (x*)- - ( (=")-f""(>"
4 IMPLICATIONS FOR NEURAL NETWORKS
Now that we have established the link between NNs and interpolating kernel methods, we show two implications this has for the test loss of neural networks. First, we derive an upper bound on the NN test loss, which in the regime of small NN initialization variance allows us to transfer generalization bounds from interpolating kernel methods to neural networks. Second, a lower bound on the NN test loss gives in the regime of large NN initialization variance examples of NNs, trained under gradient descent after random initialization, that generalize badly despite (close to) zero training loss.

---

Under review as a conference paper at ICLR 2020
4.1 TRANSFERRING GENERALIZATION BOUNDS TO NEURAL NETWORKS
From Thm. 2 it is now almost straightforward connect the test error of the interpolating kernel method to the test error (w.r.t. squared loss) of the neural network.
Theorem 3 Let f8N be the fully-come colvereede solution of strongly overparanetrized NN 1 with L layers and m hidden units per layer and initialization variance o², where all layers have been trained using gradient descent under squared loss consistent dataset D after random initializa- tion Og ~ N (0,1 1). Then it holds with probability at least 24 over the random initialization that
NN lest
VVL Liss + at /v8 O(1/mm).
To prove this theorem we use the fact that - (z) S O(L//m) holds uniformly for all E (0) and that [l (Xust) f' (Xuat x1x))l1 112 I 00"1/0 holds with high probability; the last fact follows the same way as in the proof of Lemma instead applying Markov's 's inequality to the squared deviation for single test point x, applying it to averaged sum of squared deviations over all test points. Then, we make use the triangle incquality and evaluate the square to prove the desired result. This inequality formalism to the other and gives us a new grip on finding bounds on the test eπror for NNs. Good generalization bounds minimum complexity interpolating models have been established in (Liang & RRkhlin (2018). On the other hand, [Belkin et al. (2018)) showed that conventional bounds in the underparametrrieed regime might be of little for minimum complexity kernel methods.
enables
transfer bounds for the test error from one
4.2 ZERO NN TRAINING ERROR ALONE DOES NOT IMPLY SMALL TEST ERROR
In the past many people trained neural networks with the goal achieve a low training error with the hope that this might also result in a low test error. The initialization was merely thought as necessity to converge faster to low training enror training dynamics. We now show with our analysis that random initialization alone is not enough, but instead we need certain constraints the initialization to be able to give generalization bounds.
give favourable starting point for the
Before we prove this let us derive some simple properties. Let ((x, be the feature vector of NN initialized with NTK prraeerramttiznaionn with initialization variance Then it is easy to that ((I,o) = o (x, because of the homogeneity of the derivative w.r.t constants. Fur- ther we define J(Xrest, σ) := |l (Xua) (1 ((X) (X))) J( (Xiaa) = J(Xieu, 1). With this notation, we can show the following theorem:
/ and
Theorem 4 Let JNN be the fully- colve-co solution of strongly overparametrized NN ① with L layers and m hidden units per layer and initialization variance d², where all layers have been trained using gradient descent under squared loss on a consistent dataset 'D after random initial- ization Go (N, Then holds with probability at least 5 over random initialization VINN lest
(( - 0(1//m)
test
For general datasets D. it is highly likely that (Xies,) o) * O. To prove the statement decomposition of Lemma 2 Now instead making the variance small to bound the second term can the homogeneity of (2 a)) to show that J[Xeeu,, o) - J (XXes)) Now using twice the reverse triangle inequality we and the lemma 1 get the desired result.
the
Now looking at the expression of Thm. and using again the homogeneity of & we can that / V does not change when changing because the different factors cancel out and the term corresponding to the linear approximation should also not impact the result too much as long we choose m large and do not increase a significantly. Respecting this constraint we can now easily increase the variance to make the second term as large as we want. Thus, by increasing we are able to increase the test loss arbitrarily while not changing the training error at all because the second term in our decomposition does contribute during training time. This shows that without considering an explicit initialization the training error of a NN might tell us very little about the actual test loss. Thus, our results underline the importance of finding good initialization strategies.

---

Under review as a conference paper at ICLR 2020
5 EXPERIMENTS
In this section we give experimental evidence for our theoretical findings: the influence of NN initialization on the generalization performance of fully-trained wide NNs (Sect. as well as the link to interpolating kernel methods in the first place (Sect. 3).
We perform experiments (Fig. D in three different setting (1) A toy experiment, fitting 2D- dataset with N = 10 datapoints sampled uniformly from f(x) = exp(-1|z|13), - with a NN of I hidden layer (L = 2) with m 10000 neurons; here, the "wide NN" requirement m > N is satisfied to the highest degree. (2) Fitting N = 100 MNIST digits O and 1 by a single-hidden-layer network with m 4000 hidden units. In line with our framework and with other works on wide NNs (e.g.. (Du et al. 2018b] Arroa et al.] 2019b)), we fit these classification labels using squared error loss. (3) Fitting MNIST digits O and with 2 hidden layers (L = 3) of m 1500 neurons each. The reason for using small training sets is to maintain the overparametrization limit m > N.
In each setting we vary the variance o² of the NN initialization, performing always 10 repetitions. We stop training at the same "close to zero" training loss for all o², chosen in each setting so small that empirically the test loss remains almost constant (while the training loss is decreasing further).
The left panels (Fig. 1 show the test losses of the trained NN vs. the linearization f of the ini- tialized NN (Lemma D]. at different NN initialization variances o². Both curves are very close, confirming the basic premise that the approximation of wide NNs by linear models is quite accurate for our NNs, even though we are not in the guaranteed overparametrized regime (e.g.. m 2 O(N)) from Du al. (20T8b). The approximation better for the two MNIST experiments, where we actually further from the this regime, whereas the larger repetition variances for the 2D bump are due to sampling the training inputs from a small volume of low dimension.
Most strikingly, the test loss of the trained NN depends heavily on its weight initialization Og even though all NNs have been trained the same low training error. This is shown by the increase at larger initialization variance o². Via the link to flin, this can be understood from the test behavior of strongly overparametrized linear models flim with big initialization 0g (Eq, (4) and Sect. 4.2).
The right panels underline this behavior predicted by our theory quantitatively: The test error of trained ReL.U-NN as well our our analytical lower bound on it (Thm. { both behave big a² like @()²L) (see also Eq. (12), with I. the number of layers. This in particular shows how one can find natural examples of (overparametrrized) NNs, i.c. initialized randomly and trained by gradient descent, that interpolate the training data perfectly, yet with arbitrarily large test error.
In the regime of small a² on the other hand, the right panels confirm Thm. 3 namely that the test error is close to the (low) test error of the interpolating kernel method for (Eq. (5)). Note that its test error in the figures is almost constant in o², as fill does not depend directly on the weight initialization &, but on the (many and random) NN features Φ(z), which via the kernel & only determine function smoothness. This is more reasonable modeling behavior than that of wide NNs. initialized at large o².
6 DISCUSSION
In this paper we make the bias explicit that is imposed by gradient descent and random initialization on fully-connected strongly overparametrized NNs. We achieve this by decomposing a gradient descent-trained network with (close to) zero training error into an interpolating kernel term and a second term that vanishes on training inputs but not on test inputs.
Because this second term is independent of the training labels but depends strongly on the initializa- tion, it is favorable for good generalization to reduce its impact. This can be achieved by choosing the variance of the NN initialization to be sufficiently small, as we have shown. On the other hand, too small an initialization variance limits the expressivity of the NN and its features.
Our work furthers the practical understanding of modern NNs by utilizing recent theoretical ad- vances in strongly overparametrized NNs. particular, we saw that the initialized weights are not merely a starting point for training, but significantly influence the performance of the NN trained to
Mooe details the settings needed reproduce the experiments can he found in Appendix
8

---

Under review as a conference paper at ICLR 2020
Try experiment 120 Gauss bumpo
Try experiment 120 Caussion tump)
100
Lower Sound
Warrpliitng tamalimatos
20
100
50
10
32"
10 Vortace
VaH BRA0
MKIST L-1 Nidden leyer
MMET with L-11 hildlen
Truined los
Sgmaa"2.
Linustied Solatin
Hdtrpokiting Namml mathod
30-
MNIST hidden
MNIST hidden
Trained 16
Sgrra"... Is
Lineatted Solution
10
Warrpoliting kamal mathod
Tol
10
30
10-2
Figure 1: Experiments on the 2D bump f(x) exp(-1|x|13) (top row) and on MNIST with L = and layers, respectively (last two rows). Left panels: The test error of trained wide NNs as well as their linearized versions increases significantly with the NN initialization variance o² despite training all NNs to the same very low training error. This is explained by the theory in Sect. 4.2 as the linearized approximation of our NNs is quite accurate (see also Sect. 3). Right panels: Quantitatively, at big a the NN test loss as well as its lower bound both grow as (()2L) (Thm. 4
At small o². on the other hand. the NN test error is close to that of the interpolating kernel method iint (Eq. 5)) confirming Thm.
zero empirical error. Similarly, focussing the first term of our decomposition, Seamiing-theoretinn results on interpolating kernel methods lead to better understanding of puzzling features of NNs.
Our work provides intuition for the "essentially barriers" phenomenon first observed in Draxler et al. (2018); Garipov et al. (2018): When scaling all initialization weights Op by common contin- uous factor (like r), all of the finally trained NNs JNN connected continuously and their training етrоr stays at (close to) zero. This is because & changes by only scalar factor o²!, which conti- nously changes the second (test) term in the linearization fNN se flin (Eq, 14) but cancels out of the first (training) term. It would be interesting for further work to investigate varying Og more generally the hypersurface of zero training loss, which induces non-scalar changes in +
The connection of NNs with minimum complexity interpolating kernel methods opens up more directions for future research. An important next step would be to go from strongly overparametrized NNs to merely overparametrized NNs, where the (infinitesimal) kernel dynamics effected by NN training is to be understood in addition to fixed-kernel interpolation. Further, the connection remains to be made explicit for CNNs and RNNs, well for other (classification) loss functions, whose strict minimization often requires infinite weights. For SGD at least, instead full gradient descent, the basic decomposition into training part and its orthogonal component (Eq. 14 remains valid.
9

---

Under review as a conference paper at ICLR 2020
Another direction needed to fully leverage the link NNs made explicit in Sect. 4.1 is understand better the properties e.g. the generalization behavior (Liang & Rakhlim 2018) of interpolating kernel methods, whose close connection to large modern-day NNs we have highlighted in this paper.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- paramcterization. arXiv preprint arXiv: 0.3962,, 2018a.
Zeyuan Alue Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. arXiv preprint arXiv: 12065, 2018b.
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 Xrviv: /955, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprini arXiv: 2019b.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky.
margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in Neural Information Processing Systems, pp. 2300-2311, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. arXiv preprint
2018b.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? arXiv preprint arXiv:1806.0er. 2018c.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-
learning practice and the classical varinnari trade-off. Proceedings of the National Academy of Sciences, 116(32):15499-15888 2019.
Anastasia Borovykh. The effects of optimization on generalization in infinitely wide neural net- works. ICML Workshop, 2019.
Amit Daniely, Sgd learns the conjugate kernel class of the network. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems 30. pp. 2422 2430. Curran Associates, Inc., 2017. URL httt:://papers. nips. wwwppppppp..pp.r...ppppppppppppp 6836 agd learns tee---hhecooo-e cinte-coojugatee
cfaeellllass------- thee pdf
network
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, pp. 2253-2261, 2016.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht. Essentially no barri- ers in neural network energy landscape. arXiv preprint arXiv:1803.00885 2018
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. 2019.
arXiv preprint
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 101.11//1100.44 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv: 1810.00544 2018b.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pp. 8789-8798, 2018.
10

---

Under review as a conference paper at ICLR 2020
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Goodfellow, Yoshua Bengio, and Aaron Courville. Deep leurning. MIT press, 2016.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. Training dynamics of deep networks using stochastic gradient descent via neural tangent kernel. arXiv preprint arXiv: 33554, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 857 1- 8580, 2018.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.00165; 2017.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jaseha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. arXiv preprint
2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can gener- alize. arXiv preprint arXiv: 2018.
Siyuan Ma. Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. arXiv preprint arXiv:1712.06559, 2017.
Alexander G de Matthews, Mark Rowland, Jiri Hron, Richard Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint 1804 2018.
Nicole Mücke and Ingo Steinwart. Global minima of dons: The plenty pantry. 1rXiv:1905.10686 2019.
arXiv preprint
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to speraially-normalizeedd margin bounds for neural networks. arXiv preprint arXiv:1707.09550 2017.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterrized nonlinear learning: Gradient descent takes the shortest path? arXiv preprint arXiv: 2018
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin. Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. arXiv preprint 100608/400 2018.
Vatsal Shah, Anastasios Kyrillidis, and Sujay Sanghavi. Minimum norm solutions do always generalize well for parameterize problems. arXiv preprint 1rXiv:1811.07000 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-287)) 2018.
11

---

Under review as a conference paper at ICLR 2020
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint arXiv:1906.0588 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16/ 2016.
Yaoyu Zhang, Zhi-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error induced by initialization in deep neural networks. arXiv preprint arXiv:1905.07777, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterrzed deep relu networks. arXiv preprint 1rXiv:1811. 1.08888, 2018.
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A MINIMUM 2-NORM SOLUTION
Let us consider an affine linear model f(x) = (())6, where ((x) is our feature map and 0 our weights. We want choose the weights solution of the following problem:
0 subject to Y = x(X)0
min 2
First, we use the method of Lagrange multipliers and define the following Lagrange function
|00 - x² (#(X)6-) Y)
[(0, 2
Taking the derivative with respect to 8 and setting it to zero gives fT X (X). Now plugging this into the Lagrangian we get
((A) = - (xxx
Minimizing this term with respect to À we get À = (X(X))(x))) Y. Inserting this relation we
get
i xx) (X(X)0(X))) "
CONNECTING THE INTERPOLATION ATING MINIMUM 2-NORM SOLUTION TO THE MINIMUM RKHS-NORM INTERPOLATING KERNEL METHOD
Building upon the previous section we now want to show that a linear predictor where the weights are the solution of minimum 2-norm interpolation with feature map ((x) is equivalent a minimum complexity interpolating kernel method with
1 arg min | JEHK
subject to Y = f(X),
2
Hx
were the kernel the RKHS is given by K(x, y) = (0(x), p(y)) and the same function used for the linear ansatz in the minimum 2-norm solution.
We can find the solution the minimum complexity interpolating kernel method by minimizing following Lagrangian:
((S,))= 1
|
+ (X-)))(
Hi
Because the RKHS-Norm is bounded by definition (for non degenerate data) we can use the repre- senter theorem (f = -E a; ((;,)...) with as E R) and the reproducibility of the kernel to arrive
1
C(a, A) aaa " X)a + X (Y K(X,X)a)
Now taking the derivative with respect to a we get a X. Inserting this into our Lagrangian we get
((A) = - X XXX
This Lagrangian is equivalent to the Lagrangian of the minimal two norm solution the dual rep- resentation and due to the convexity of the problem the solutions must also be equivalent.
LEMMA
In this section want to give the proof for lemma 2. Let NN be fully-connected NN defined in the notation section. For simplicity we switch from the NTK initialization to the He et al. (2015) initialization. The proof is equivalent in both parametrizations.. The only difference that we
13

---

Under review as a conference paper at ICLR 2020
suppress some of the scaling factors in the initialization of the weights. We again assume ReLU- activation function. Before showing the actual lemma we will first show the following expression which we will use to proof the lemma
fW (x) - 1 - (W, Vwf(x))
(15)
were the scalar product is defined as the Serteett-Shhmii-rrodue with (A, B) Ir [A* B and W = diag(WL...., W1) is the diagonal matrix with all the weigh matrices on the diagonal. We restrict ourselves to networks without biases but the proof with biases is almost identical.
To prove the lemma we can first proof that Al f1.... L} we have Jw; this statement is true easy to see that the formula above is also true.
NNN (x) (W, Vw.f(z)). If
A ReLU Network can be written in the following way
N (x) = (el
(16)
where (n)(0) is the diagonal matrix with the step function on the diagonal corresponding to the components of (x) 2 O. Now, we can define a(WLa, x) == Wohh--1o2ooW.-1..h.e and b(W11. == (2 to get
A (x) aaWaaWWL L. Wib((W.,
a (0) = 0. Defining the derivative of the a(W))
Using the fact that m()))m stepfunction at the step to be zero is also done in most of the standard frameworks like tensorflow. Additionally, the region where the stepfunction jumps is d dimensional subspace and thus the expression holds almost everywhere anyway. Now, since our weights do not move much and only neglectable number change the step function we can just define this derivative be zero. The derivative of b( (W:1, .)) with respect to Wi is clearly zero because it does not depend on Wi.
because we define
Using this we can see that almost every
a W (x)
(Wi, Vw, NN (o))
Σ (Wi)
a(W.,,, = NN (x),
((W)
Applying this result L-times we have get that almost everywheee NN (x) (W, Vw f(z)). Thus, get almost everywhere
So - (0o, { (0)))())) +(x))
1
and therefore also
N (z) (x)))(
(x)
((x)
do
L
D LEMMA
In this section we want to show the statement of lemma 3. We want to show that
( (T)) (1
PP L
( Gol < 026. 1-8
First, let us focus on the operator (1- (x (1- properties of projection operator (symmetric and equal to its square). Thus, all the eigenvalues are either zero or one. The operator projects A -ddimensional vectors into a N N-dimensional subspace and then back to the M M-dimensional space. Thus, it has N eigenvalues which are and all the rest are zero. Now, looking at the whole operator we see that has M - N eigenvalues which are one and the rest are zero. Therefore, we can neglect the projection operator because this will only make our result larger due to the neglected dimensions which would be projected out.
The second term has the
Using this and the formula have derived in th proof for lemma we get almost everywhere
1
L (xx (D (xxx))(( -xx)) Aul - (B(x)0)) = |f (x))
14

---

Under review as a conference paper at ICLR 2020
Now, we use Markov's inequality to arrive
P (()
0o
11.800 (x))
/8
2 1 -
To start of we can again Thus, the only thing that is left to do is to show that E [Jir (x)] S م²و write the Neural Network as product of matrices
AN (x) = WI (0.0000
We use a similar approach as Du & Hu 2019) and generalize this approach to non-linear networks. We make of the fact that for for random matrix A Rd with i.i.d. .N(0, entries and
arbitrary non-zero vector Rd: /0 the distribution of ||AA||| is Xás distributed. Additionally, it is
|-]
easy to that |lAa2 Aual
(00))20000000 1... (
thus get 2 I 10000 W1 Wial?
1. Defining Z,
E [1 (x)]²] - E[Z, Zz] , o²L
Inserting the result for E [20 [o)] we get
1 (x) (1- - (X)
Bol < <0///o -
L
E DETAILS ON OUR EXPERIMENTS
In this section we want to talk about how we conducted the experiments. Since the experimental settings are not very complicated this should be more than enough to easily reproduce our results.
As described in the experimental section we used three different setting to investigate the dependence of the Neural Network solution the initialization variance. We used standard He et al. (2015)- initialization which is, as mention the notation section, equivalent to the NTK- TTK-ppramettrzztion and standard normal initialization when rescale the learning rate. Since we choose the theoretical value
A (*(X) for the learning rate the settings are equivalent. For all experiments we use Tensorflow with ReLU-activation functions, set the bias initially to zero and train with GD.
1.9
For all networks we use low number of training data points to make sure that we are in or close to the over over-paranne paramarrmtreeeed regime. This is necessary to assure the validity of the linearisation.
The first Network for the 2D exponential Bump a single hidden layer NN with 10000 hidden units. We use 10 training data points and 300 testing points. We train 10 networks for each variance value
and until the training loss drops first bellow a loss of 10 5 The final training loss of the curves
plotted in the experimental section can be seen in figure 2
We choose the stopping point for the training error in such a way that even though the training loss still decreasing further the test loss almost constant.
Toy experiment (2D Goussaa bump)
10-1
9.995 x 19
9.99 x 10-
Training Loek
9,985
9.875 10--
9.97 10
9,985 x 10
9.96 10
10
Variance
Figure 2: Benchmark experiment with a 2D-Gaussian Bump
For the single layer MNIST network we use 4000 hidden units and for the two layer network two layers of each 1500 hidden units. We use 100 training samples of O and labelled examples of the
15

---

Under review as a conference paper at ICLR 2020
training set and 100 samples from the test set to calculate the test error. For the MNIST Network train the networks to reach a training error smaller than 10 The plot of the final training errors that corresponds to the curves in the Experimental section shown in figure 3
SN with L=1 hioden layer
MNIST with L-2 hidden layer's
10
loss
9.89975 X-1977xx10
9,9995 10"
Traning Loda
2.0994 10
9,99925 x10
9.599 x 10-5
9.999 x0
3.9988 x
9.99255
Varlence
Veriene
Figure 3: Experiments with MNIST for a NN with and 2 hidden layers
16


Reviews:
[{"review_id": "SkxT3DtpKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "\n[Summary]\nThis paper studies the impact of initialization noise on the theories of wide neural networks in the Neural Tangent Kernels (NTK) regime. The paper proves that the difference between the trained neural net and the kernel interpolator (with the NTK) can be bounded by O(\\sigma^L + 1/\\sqrt{m}), where \\sigma^2 is the initializing variance of each individual weight entry. Relationships between the generalization error of these two functions are derived from the above bound.\n\n[Pros]\nThe general message that this paper conveys is interesting -- the initial network f_{\\theta_0}(x), which is typically omitted (or made small by making \\sigma small) in NTK analyses, can deviate the converged NN from the kernel interpolator in terms of generalization error.\n\n[Cons]\nThere are fundamental mistakes in the statements/proofs of Theorem 2, 3, 4:\n-- Theorem 2: the statement is “whp over W, the bound … holds uniformly for x”. The proof relies on Lemma 3, whose statement is also uniform over x, but the proof applies the Markov inequality *for a single x* and is thus valid only for a single x. (As it’s Markov, it seems not sensible to apply the union bound upon it.)\n\n-- Theorem 3: the difference between L^NN_test and L^int_test should be on the order of (\\sigma^L + 1/\\sqrt{m}) rather than it squared. To bound the difference in squared loss we have a^2 - b^2 <= O(1) * |a-b| (if a, b are bounded by O(1)). We don’t have a^2 - b^2 <= |a - b|^2.\n\n-- Theorem 4: J(X_test) as defined is a vector whose dimension grows with the number of test data points, where the theorem requires it to be a scalar. Indeed the treatment of test data as a fixed matrix (rather than samples from a distribution) is already a bit atypical.\n\n***\n\nI have read the authors' rebuttal and the other reviews, and I'm glad to see the issues with Theorem 3 and 4 pointed out above are fixed in the revision. However, I also agree with the other reviewers that the paper in the present stage has not yet demonstrated sufficient technical contributions, and thus I am keeping my original evaluation.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJerMupf5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 solution of neural network training in the NTK regime. The trained network can be written as the sum of two terms --- the first is the minimum RKHS norm interpolating solution, and the second term depends on the initialization. When the initialization scale is small, the second term almost vanishes, but when the initialization scale is large, it's likely that the second term becomes very large, leading to worse generalization.\n\nThe technical contribution of this paper is pretty low. The most important formula is (14), which only appears in the second half of the paper (the first half of the paper is almost all known results). The bounds in later part of the paper are also straightforward. Moreover, another paper https://arxiv.org/abs/1905.07777 already studied the same question and showed that non-zero output can increase the generalization error.\n\n\n-----------\nupdate:\nI have read the authors' response. My assessment stays the same since I still think that the technical contribution of this paper is quite limited.\n\nAlso there is a negative effect of using small init, which the authors might have overlooked: when the init is smaller, you'd need a larger width for the NN to be in the NTK regime. See e.g. \"Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang. ICML 2019\".", "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 read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1g_B4n6FS", "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 considers the impact of initialization bias on test error in strongly overparameterized neural networks. The study uses tools from recent literature on the generalization of overparameterized neural networks, i.e. neural tangent kernels and interpolating kernel method, to provide useful insights on how the variance of weights initialization affects the test error. I have a few questions about theoretical results, but the paper has a convincing experiment that supports its theoretical claims. Addressing the following points will improve the exposition of the paper. \n1. Please provide a little hint on how Lemma 2 rewrites the equation (13) for linearized function for easier readability without referring to the Appendix.\n2. In the case of cross-entropy error, would the effect be similar? Could this be verified with a similar experiment as for MSE?\n3. To what extent this result is observed in not as strongly overparameterized settings? In other words, it would be interesting to see what happens if you fix the architectural choice while increasing the number of training parameters, how long does the test error effect persist?\n\nMinor remark:\n- a few typos are present on pages 4, 5, 7, 8", "extra_scores": {"experience_assessment": "I have read many papers in 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": {}}, {"review_id": "BJxSSJytqS", "reviewer": "AnonReviewer4", "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 overparameterized fully-connected neural networks trained with squared loss. The authors show that the resulting network can be decomposed as a sum of the solution of a certain interpolating kernel regression and a term that only depends on initialization. Based on this, the authors also derive a generalization bound of deep neural networks by transferring it to a kernel method. My major concern about this paper is the novelty and significance of its results:\n\nIn terms of connection to NTK, It seems that the connection between neural networks trained with squared loss and the result of NTK-based kernel regression has already been well-studied by \n\nArora, Sanjeev, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. \"On exact computation with an infinitely wide neural net.\" arXiv preprint arXiv:1904.11955 (2019).\n\nwhich is a missed citation. Without a clear explanation on the difference between the submission and this paper above, I don’t think this paper is ready for publication.\n\nIn terms of generalization, it is also very difficult to judge whether this paper's result is novel. In fact this paper misses almost all citations on generalization bounds for neural networks. Moreover, the generalization bound given in this paper does not seem to be very complete and significant, since the authors do not show when can L_{test}^{int} be small. To demonstrate the novelty and significance of the result, the authors should at least compare their generalization result with the following generalization bounds for over-parameterized neural networks in Section 4: \n\nAllen-Zhu, Zeyuan, Yuanzhi Li, and Yingyu Liang. \"Learning and generalization in overparameterized neural networks, going beyond two layers.\" arXiv preprint arXiv:1811.04918 (2018).\nCao, Yuan, and Quanquan Gu. \"A generalization theory of gradient descent for learning over-parameterized deep relu networks.\" arXiv preprint arXiv:1902.01384 (2019).\nArora, Sanjeev, 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).\nCao, Yuan, and Quanquan Gu. \"Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks.\" arXiv preprint arXiv:1905.13210 (2019).\n\nOverall, I suggest that the authors should make a clear discussion on the relation of this paper to many existing works mentioned above. As long as the authors can give a convincing demonstration of the novelty and significance of their results, I will be happy to increase my score.\n\nA minor comment: how can the bound in Theorem 3 be derived based on Theorem 2? Should there be a constant factor in the bound?\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves that fully-connected wide ReLU-NNs trained with squared loss can be decomposed into two parts: (1) the minimum complexity solution of an interpolating kernel method, and (2) a term depends heavily on the initialization. The main concerns of the reviewers include (1) the contribution are not significant at all given prior work; (2) flawed proof,  and (3) lack the comparison with prior work. Even the authors addressed some of the concerns in the revision, it still does not gather sufficient support from the reviewers after author response. Thus I recommend reject.
Decision: Reject