Implicit bias of gradient descent for mean squared error regression with wide neural networks
Authors: Hui Jin
Guido Montufar
Venue:  (2021)
Keywords: Implicit bias
overparametrized neural network
cubic spline interpolation
spatially adaptive smoothing spline
effective capacity

Abstract: We investigate gradient descent training of wide neural networks and the corresponding implicit bias in function space. For 1D regression, we show that the solution of training a width-$n$ shallow ReLU network is within $n^{- 1/2}$ of the function which fits the training data and whose difference from initialization has smallest 2-norm of the second derivative weighted by $1/\zeta$. The curvature penalty function $1/\zeta$ is expressed in terms of the probability distribution that is utilized to initialize the network parameters, and we compute it explicitly for various common initialization procedures. For instance, asymmetric initialization with a uniform distribution yields a constant curvature penalty, and thence the solution function is the natural cubic spline interpolation of the training data. While similar results have been obtained in previous works, our analysis clarifies important details and allows us to obtain significant generalizations. In particular, the result generalizes to multivariate regression and different activation functions. Moreover, we show that the training trajectories are captured by trajectories of spatially adaptive smoothing splines with decreasing regularization strength. 

Under review as conference paper at ICLR 2021
IMPLICIT BIAS OF GRADIENT DESCENT FOR MEAN SQUARED ERROR REGRESSION WITH WIDE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate gradient descent training of wide neural networks and the correspond- ing implicit bias in function space. For ID regression, show that the solution of training a width-n shallow ReLU network is within -112 of the function which fits the training data and whose difference from initialization has smallest 2-norm of the weighted second derivative with respect to the input. The curvature penalty function 1/C is expressed in terms of the probability distribution that is utilized to initialize the network parameters, and we compute it explicitly for various common initialization procedures. For instance, asymmetric initialization with a uniform distribution yields constant curvature penalty, and thence the solution function is the natural cubic spline interpolation of the training data. While similar results have been obtained in previous works, our analysis clarifies important details and allows us to obtain significant generalizations. In particular, the result generalizes to multivariate regression and different activation functions. Moreover, we show that the training trajectories are captured by trajectories of spatially adaptive smoothing splines with decreasing regularization strength.
Keywords. Implicit bias, overparametrized neural network, cubic spline interpolation, spatially adaptive smoothing spline, effective capacity.
INTRODUCTION
Understanding why neural networks trained in the overparametrized regime and without explicit regularization generalize well in practice is an important problem (Zhang et al. (2017). Some form of and specifically the
capacity control different from network size must at play (Neyshabur et al. 20144) |
implicit bias of parameter optimization has been identified to play key role (Neyshabur et al. (017). By implicit bias we mean that among the many hypotheses that fit the training data, the algorithm selects one which satisfies additional properties that may be beneficial for its performance
data.
Jacot et al. (018)) and Lee et al. (2019) showed that the training dynamics of shallow and deep wide neural networks is well approximated by that of the linear Taylor approximation of the models at suitable initialization. Chizat et al. 2019) observe that model can converge to zero training loss while hardly varying its parameters, phenomenon that can be attributed to scaling of the output weights and makes the model behave as its linearization around the initialization. Zhang et al. (2019) consider linearized models for regression problems and show that gradient flow finds the global minimum of the loss function which is closest to initialization in parameter space. This type of analysis connects with trajectory based analysis of neural networks (Saxe et al.) 2014). Oymak and Soltanolkotabi (201)) studied the overparametrized neural networks directly and showed that gradient descent finds global minimizer of the loss function which close the initialization. Towards interpreting parameters in function space, [Savarese et al.) (2099) and Ongie et al. (2020) studied infinite-wide width neural networks with parameters having bounded norm, in ID and muliiddimensional input spaces, respectively. They showed that, under standard parametrization, the complexity of the functions represented by the network, as measured by the 1-norm of the second derivative, can be controlled by the 2-norm of the parameters. Using these results, one show that gradient descent with e weight penalty leads to simple functions, [Sahs et al. (2020) relates function properties, such as breakpoint and slope distributions, the distributions of the network parameters.
Lee

---

Under review as conference paper at ICLR 2021
The implicit bias of parameter optimization has been investigated in terms of the properties of the loss function at the points reached by different optimization methodologies (Keskar et al. 2017 Wu et al.) 2017, et al. 2017). In terms of the solutions, Maennel et al. (2018) show that gradient flow for shallow networks with rectified linear units (Rel.U) initialized close to zero quantizes features in a way that depends the training data but not the network size. Williams al. (2019) obtained results for ID regression contrasting the kernel and adaptive regimes, Soudry et al. (2018) show that in classification problems with separable data, gradient descent with linear networks converges a max- margin solution. Gunasekar et al. (2018b) present result on implicit bias for deep linear convolutional networks, andJi and Telg Telgarsky|or 2019) study non-separable data. CCizat and Bach (2020) show that gra- dient flow for logistic regression with infinitely wide two-layer networks yields a max-margin classifier certain space. Gunasekar et al. (a) analyze the implicit bias of different optimization methods (natural gradient, steepest and mirror descent) for linear regression and separable linear classification problems, and obtain characterizations terms of minimum norm or max mar-inn solutions.
In this work, we study the implicit bias of gradient descent for regression problems. We focus on wide ReLU networks and describe the bias function space. In Section 2 we provide settings and notation. We present our main results in Section 3] and develop the main theory in Sections 4 and [5] In the interest of a concise presentation, technical proofs and extended discussions are deferred to appendices.
2 NOTATION AND PROBLEM SETUP
Consider fully connected network with d inputs, one hidden layer of width and a single output. For any given input x E Rd, the output of the network is
f(x,0)= - ø( (W -
where á is a point-wise activation function, W -R ( ER", ((1) ER" and ((2) R are the weights and biases of layer =1222 We write f= vec(U? (W()) }))) for the vector of all network parameters. These parameters are initialized by independent samples of pre-specified random variables W and B in the following way:
W d V1/dW, D / w (0 _ /InnW, 6(2) V1/nB.
More generally, we will also allow weight-bias pairs to be sampled from a joint distribution of (W,B) which we only assume to be Sub-Gaussian. In the analysis of Jacot et al. (2018); Lee et al. (2019). W and B are Gaussian (0),o2). In the default initialization of Py Torch, W and B have uniform distribution L1( ). The setting [ is known as the standard parametrization. Some works (Jacot ct al. 2018 Lee et al. 2019) utilize the so-called NTK parametrization, where the factor /I/n is carried outside of the trainable parameter. If we fix the learning rate for all parameters, gradient descent leads to different trajectories under these two parametrizations. Our results are presented for the standard parametrization. Details on this in Appendix C.3
We consider a regression problem for data ((T,, ,3) 1;) with inputs X' = { and out- puts y = ر For loss function L: R x R + R. the empirical risk of our function is =(0)= ((f
We use full batch gradient descent with a fixed learning rate 7) to minimize L(6). Writing 9₂ for the parameter at time f, and du for the initialization, this defines an iteration
0+1= ( ( ((x,)))
where
((T |T is the vector of network outputs for all training inputs, and V Vxx,0) L is the gradient of the loss with respect to the model outputs. We will use subscript to index neurons and subscript to index time. Let é,, be the empirical neural tangent kernel (NTK) of the standard parametrization at time 0, which is the matrix Ô,, (2,
2

---

Under review as conference paper at ICLR 2021
3 MAIN RESULTS AND DISCUSSION
We obtain a description of the implicit bias in function space when applying gradient descent to regression problems with wide ReLU neural networks. We prove the following result in Appendix D An interpretation of the result and generalizations are given further below.
Theorem (Implicit bias of gradient descent in wide ReLU networks). Consider feedforward network with a single input unit, a hidden layer of n. rectified linear units, and single linear output unit. Assume standard parametrization (I) and that for each hidden unit the input weight and bias are initialized from a
(W,B) B) (2) with joint density Pw.B. Then, for any finite data set (()g,,,))}{ and sufficiently large n. there exist constant u and v so that optimization of the mean square error on the adjusted training data {(z = -u)] by full-batch gradient descent with sufficiently small step size converges to a parameter 0" for which the output function (xx ) (I) attains zero training error. Furthermore, letting ((x) = [x [ Www.s(W.-Win. aW and S= (C) [min, , max;;;], we have (=)))= with high probability over the random initialization Og. where 9" solves following variational problem:
x (the 2-norm over S)
[ ((((z) (g" (z) (x, dr
min (EC
(4)
subject to g(0,) - -. v, M.
Interpretation An intuitive interpretation of the theorem is that at those regions of the input space where ( is smaller, we can expect the difference hetween the functions after and before training to have a small curvature. We may call p= 1/{ curvature penalty function. The bias induced from initialization is expressed explicitly. We note that under suitable asymmetric parameter initialization (see Appendix C.2 is possible to achieve f(-00) = O. Then the regularization is on the curvature of the output func- lion itself. In Theorem we obtain the explicit form of ( for various common parameter initialization procedures. In particular, when the parameters are initialized independently from a uniform distribution on a finite interval. Ç is constant and the problem is solved by the natural cubic spline interpolation of the data. The adjustment of the training data simply accounts for the fact that second derivatives define a function only up to linear terms. In practice we can use the coefficients and b of linear regression
y/ = oz, + b + ej. j = I,....,A4 M, and set the adjusted data as {(z,, } Although Theorem describes the gradient descent training with the linearly adjusted data, this result can also approximately describe training with the original training data. Further details are provided in Appendix L
We illustrate Theorem I Jumericalll in Figure[ more extensively in Appendix[A] In close agree- ment with the theory, the solution to the variational problem captures the solution of gradient descent training uniformly with error of order n -1/2, To illustrate the effect of the curvature penalty function, Figure I also shows the solutions to the variational problem for different values of Ç corresponding to different initialization distributions. We see that at input points where ( is small / peaks strongly, the solution function tends to have lower curvature / be able to use a higher curvature in order to fit the data.
With the presented bias description we can formulate heuristics for parameter initialization either to ease optimization or also to induce specific smoothness priors the solutions. In particular, by Proposition Jny curvature penalty 1/C can be implemented by an appropriate choice of the parameter initialization distribution. By our analysis, the effective capacity of the model, understood as the set of possible output functions after training, is adapted to the size M of the training dataset and is well captured by space of cubic splines relative to the initial function. This is space with dimension of order M independently of the number of parameters of the network.
Strategy of the proof In Section 4 we observe that for a linearized model gradient descent with sufficiently small step size finds the minimizer of the training objective which is closest to the initial parameter (similar to a result by Zhang et al. 2019). Then Theorem Thsoorem4sshows shows that the training dynamics of the linearization of a wide network is well approximated in parameter and function space by that of lower dimensional linear model which trains only the output weights. This property is sometimes taken for granted and we show that it holds for the standard parametrization. although it does not hold for the NTK parametrization (defined in Appendix C.3), which leads to the adaptive regime. In Section [5] for networks with a single input and a single layer of ReLUs, relate the implicit bias of gradient descent in parameter space to an alternative optimization problem. In Theorem 3 we show that the solution of this problem has well defined limit as the width of the network tends to infinity,
3

---

Under review conference paper at ICLR 2021
Reciprocal curvature penally
y= 0.6582x-04885
10
Error
050
054
021
Error
n= 10
nt n==64 640
Solution g to the variational problem
18-
114
10"2
02-
10a Number of neurons
10a
04
-5
-3
Figure 1: Illustration of Theorem Left: Uniform error between the solution g to the variational problem and the functions f(-00") obtained by gradient descent training of neural network (in this case with uniform initialization W (-111),), B ~ (22))), against the number of neurons. The inset shows examples of the trained networks (blue) alongside with the training data (dots) and the solution to the variational problem (orange). Right: Effect of the curvature penalty function on the shape of the solution function. The bottom shows g" for various different shown at the top. Again dots are training data. The green curve is for constant on [-2,2], derived from initialization = ((a)=1/(( +x?)2, derived from W~ (0,1), B~ N (0,1): and orange for ((z) = (0.1 + + derived from W ~ N(0,1), B (0000.)). Theorem shows how to compute Ç for the above distributions.
W~U(-111), B~ B~ (-22)) blue is for
which allows us to obtain variational formulation. Theorem 6 we translate the description of the bias from parameter space to function space. In Theorem we provide explicit descriptions of the weight function for various common initialization procedures. Finally, we can utilize recent results bounding the difference in function space of the solutions obtained from training wide network and its lincarization (Lee et al. 2019 Theorem H.1).
Generalizations Theorem has several generalizations elaborated in Appendix P For multivariate regression, we have the following theorem.
Theorem (Multivariate regression). Use the same network setting as in Theorem / except that the number of input units changes to Assume that for each hidden unit the input weight and bias initialized from sub-Gaue Gauusiansnnn (W,B) where W is d-dimensional random vector and B is a random variable. Then, for any finite data set {(x,,,;) U and sufficiently large n there exist constant vector and constant
the adjusted 1=1 by bylull- full-batch gradient descent with sufficiently small step size converges to parameter 0² for which ((xx0)) attains zero training error. Furthermore, Bald=||W) V W/|[ C -B/ and <(V .c) Pv.c (VV V.C where Pv.c the -n Idd (the 2-norm over R2) with high probability over the random initialization d. where g" solves followigg variational problem:
that optimization of the mean square
training data {X,,-35 (u,,x) - -u) - M
joint density of (V,C). Then we have [x](xx0*)) 9" g")
(R((-A)(4+)/22 (000)/(((g((()))))))))) f(-00))) dVdc
min gEC(R4)
Supp(()
<(V.c)
(5)
subject
-(x))=ツド> j=1,..,, =0, (V.c)
Here R is the Radon transform which is defined by R(f) 6) = S f(x)ds(x), and the power of the negative Laplacian (-A)ld+13/2 is the operator defined in Fourier domain by (-2) =
For different activation functions, have the following corollary.
4

---

Under review as conference paper at ICLR 2021
Corollary 3 (Different activation functions). Use the same setting in Theorem 7 except that use the activation function & instead of ReLU. Suppose that & a Green' 's function of a linear operator L. i.e. Lò = 6, where ó denotes the Dirac delta function. Assume that the activation function is homogeneous of degree k, i.e. ((ax)==)) - ((r)for all a>> Then we can find a function satisfying T.p = 0 and adjust training data {(,,-,;)} ) j=1 {01,11) - p(x;)))==-- After that, the statement in
Theorem Sinooemmholls holds with the variational problem (4) changed
min
dr s.t. g(z,)= u -p(z)), j=1,..,,M
(6)
(ECR(S)
where (()))=(( and 5 (0==sppp((0mmmmmzz,ppp)
Moreover, our method allows us to describe the optimization trajectory in function space (see Appendix N If we substitute constraints ((=,)==)) in 4 by quadratie term Σ/ ()= added to the objectíve, we obtain the variational problem for a so-called spatially adaptive smoothing spline (see AAbamovvihh and Steinberg 1996; Pintore et al. (006). This problem can be solved explicitly and can be shown to approximate early stopping. To be more specific, the solution to following optimization problem approximates the output function of the network after gradient descent training for t steps with learning rate i//n
M Σ (((())) - Mzl 2 1H ((x) (z.0)))
1 - dr.
min (ECF(S)
Related works Zhang et al. (2019) described the implicit bias of gradient descent in the kernel regime as minimizing kernel norm from initialization, subject to fitting the training data. Our result can be regarded as making the kernel norm explicit, thus providing an interpretable description of the bias in function space and further illuminating the role of the parameter initialization procedure. We prove the equivalence in Appendix M Savarese et al. (2019) showed that infinite- winth networks with 2- 2-norm weight regularization represent functions with smallest 1-norm of the second derivative, an example of which are linear splines. We discuss this in Appendix C.4 A recent preprint further develops this direction for two-layer networks with certain activation functions that interpolate data while minimizing a weight norm (Parhi and Nowak 2019). In contrast, our result characterizes the solutions of training from given initialization without explicit regularization, which turn 2-norm of the second derivative and hence correspond to cubic splines. In finishing this work we became aware of recent preprint (Heiss et 2019) which discusses ridge weight penalty, adaptive splines, and early stopping for one-input ReL.U networks training only the output layer. Williams et al. (2019) showed a similar result in the kernel regime for shallow ReLU networks where they train only the second layer and from zero initialization. In contrast, we consider the initialization of the second layer and show that the difference from the initial output function is implicitly regularized by gradient descent. We show the result of training both layers and prove that it can be approximated by training only the second layer in Theorem In addition, we give the explicit form of ( in Theorem 9 while the ( given by Williams et al. (2019) has minor error because of typo in their computation. Most importantly, our statement can be generalized to multivariate regression, different activation functions, training trajectories.
minimize a weighted
4
WIDE NETWORKS AND PARAMETER SPACE
4.1 IMPLICIT BIAS IN PARAMETER SPACE FOR A LINEARIZED MODEL.
In this section we describe how training a linearized network or wide network by gradient descent leads to solutions that are biased, having parameter values close to the values at initialization. First, we consider the following linearized model:
(8) We write w for the parameter of the linearized model, in order to distinguish from the pa- rameter of the nonlinearized model. The empirical loss of the lincarized model is defined by Lim (w)= M (f (zjiinzz,))))) w.)))) The gradient descent iteration for the linearized model is given by
flim (x.ww f(x,0)) (of( Ab)-
wp = 0 w1+1 Vol (2 (o T.
(9)
5

---

Under review as conference paper at ICLR 2021
Next, we consider wide neural networks. According to Lee et al. (2019) Theorem H.1),
sup
with arbitrarily high probability. So gradient descent training of a wide network or of the linearized model give similar trajectories and solutions in function space. Both fit the training data perfectly, meaning flin 50) = f (x' )= and are also approximately equal outside the training data.
Under the assumption that (Vof(X ..))) = M, the gradient descent iterations converge to the unique global minimum that is closest to initialization (Gunasekar et al. 22118a Zhang et al. (211)) which is the solution of following constrained optimization problem (further details and remarks are provided in Appendix E):
min سا - -ull2 s.t. flin (x()))=) =y.
(10)
4.2 TRAINING ONLY THE OUTPUT LAYER APPROXIMATES TRAINING ALL PARAMETERS
From now on we consider networks with single hidden layer of n ReLUs and a linear output (0r,0)>>i (/( x 6,,0 obtained by training the linearized model are close to those obtained by training only the output layer. Hence, by the arguments of the previous section, training all parameters of wide network training only the output layer gives similar functions.
6(2), We show that the functions and parameter vectors
Let 0g- = vec(W")) (1) ( W (2) (2), be the parameter at initialization so that flin (..6g) fo),
After training the linearized network let the parameter be who = vec (LI)) 300) we B:2)). Using
initialization 2 with probability arbitrarily close to 1, W(l) (1) [(1) 0 and w!! T =0 $
Therefore, writing H for the Heaviside function, we have
wr fx ( H(W!!) (1) )) x, W (2) H(W (1) x+ ((W
=0 =
(11)
w Man (2,00) W (1)
|+ z+0,,
(1)
:+11--(11
So when n is large, if we use gradient descent with a constant learning rate for all parameters, then the changes of W(I) 80), ((2) are negligible compared with the changes of (222) So approximately we can train just the output weights, w:2") ; L,...,, and fix all other parameters. This corresponds to smaller linear model. Let W, vee vee : .6 (W(2) ((2)) be the parameter at time t under the
update rule where (1) (T)) (²)) are kept fixed at their initial values, and
W () 22) w = w( V T_lii(a)) (wt).
(12)
Let 8o0 = llim Wp. By the above discussion, we expect that (1, is close to flim (I,Woc). ) In fact, we prove the following for the MSE loss. The proof and further remarks are provided in Appendix D
We relate Theorem training wide network in Appendix[[]
Theorem 4 (Training only output weights vs linearized network). Consider a finite data set
(M). Assume that (1) we use the MSE loss E(G.y) = 111 - -112: (2) inf, Amia (Qw) > O. Let
wi denote the parameters of the linearized model at time t when train all parameters using (9)
and let We denote the parameters at time when we only train weights of the output layer using (1))
we use the same learning rate 1) in these two training processes and 1)
then for any
(
x E R. with probability arbitrarily close to 1 over the random initialization (2).
supl fin (x,,0t) ( (( "),, as -
(13)
Moreover, in terms of the parameter trajectories we have sup, | W. 1|2 = 0(n
sup, -.""" -1110000000 ( ( 1 3/2), sup, 1b,
(2) - -
In view of the arguments in this section, in the next sections we will focus on training only the output
weights and understanding the corresponding solution functions.
Mooe precisely, for any 8>0 0, RC, s.t. with proh. 1 1-5, (
(7! (,16 S Cn-1/2 and (W!'),b8 ()) SC.

---

Under review as conference paper at ICLR 2021
5 GRADIENT DESCENT LEADS TO SIMPLE FUNCTIONS
In this section we provide a function space characterization of the implicit bias previously described in parameter space. According to (TO). gradient descent training of the output weights ( achieves zero
loss, fli (z,, _0) f (z)
- (W: w!!)
2 +b yy f(x,,00). J = I,..,,M,
with minimum || 119p-/12) 1 113. Hence gradient descent is actually solving
min [ W
W ( s.t.
E (2) [W: 2y b,l+ U0 105-f(an
-
--::00a-aa -o) -I.... (14)
To simplify the presentation, in the following we let flln (2x, = by using the ASI trick (see
Appendix C.2). The analysis still goes through without this.
5.1 INFINITE WIDTH LIMIT
We reformulate problem (14p in a way that allows us to consider the limit of infinitely wide networks, with + 0o, and obtain a deterministic counterpart, analogous to the convergence of the NTK. Let An denote the empirical distribution of the samples (W("), b)) so that Non (A) = #/4 m 1 ((W!") M.)). Here A is the indicator function for measurable subsets A in R2. We further consider a function on ?R² R whose value encodes the difference of the output weight from its initialization for hidden unit with input weight and bias given by the argument, on ( =nW -W(?)). Then (14) with ASI can be rewritten as
-
min (w b) dum (w())) b) s.t. f EC(3)))))))
1, dum (W()),) b)-
-yj, (15)
ga
where; ranges from to M. Here we minimize over functions on C(R?). but since only the values on (W bb) are taken into account, we can take any continuous interpolation of a, (W; .b.). i= Now we can consider the infinite width limit. Let μ be the probability measure of (W,B). We obtain continuous version of problem (15) by substituting for uu. Since we know that Hnn weakly converges to μi, we prove that in fact the solution of problem (15) converges to the solution of the continuous problem, which is formulated in the following theorem. Details in Appendix
Theorem 5. Let (w(2) bb) be i.i.d. samples from a pair (W,B) of random variables finite fourth moment. Suppose Hu is the empirical distribution of (W(") bb)) and ā. (W((), ,)) is the solution of 15). Let (W((), be the solution of the continuous problem with μ in place of pn. Then for any bounded (- sup (2. -g(.a)))))) O(n11/2) 1/2) with high probability, where In (I,aa)= Rn (W(() [[ dy (W()) b) is the function represented by network with hidden neurons after training, and g = a ()) x+ du(w(1)) .b) is the function represented by the infinite-width network.
5.2 FUNCTION SPACE DESCRIPTION OF THE IMPLICIT BIAS
Next we connect the problem from the previous section to second derivatives by first rewriting it in terms of breakpoints. Consider the breakpoint c= -b/W(1) of ReLU with weight (1)) and bias
b. We define corresponding random variable C = =BB/W and let v denote the distribution of (W.C)
Then with (1 .c) =1) ()) the continuous version of (15) is equivalently given
/ (WV)) (x, dv(w(1), .c) -c)= (16)
min (2((1)) .c) (w .c) s.t. fg2 TEC(R2) g2
where ranges from 1 to M. Let v/c denote the distribution of C= and twic= the conditional distribution of W given C = Suppose ve has support supp(uc) and density function pe(c).
Herre we assume that (P - = 0 so that the random variable C is well defined. is not an important restric- tion, since neurons with weight (11)) = give constant functions that can be absorbed in the bias of output layer.
7

---

Under review as conference paper at ICLR 2021
Let ((x,)) SRz (W.))))WW( c)}+ dz(W()),) ()), which again corresponds to the output function of the network. Then, the second derivative g" with respect to æ: (see Appendix [] satisfies ,x) w()) (dwic=,(w!1)), Thus ((W()) .c) is closely related to g" and we can try to express (16) in terms of g(,,,)) Since (",,,) determines g(x,7) only up to linear functions, we consider the following problem:
/ (WW()
.)) du(wa),,) c)
min NEC(RP),ERREEE
R22
(17)
subject to wxy+ / 7 (c) (,W()) j=l,..,,M.
Here u,v are not included in the cost. They add linear function to the output of the neural network. If and in the solution of (17) are small, then the solution close to the solution of (T6.. Ongie
et al. (2020) also use this trick to simplify the characterization of neural networks in function space. Next we study the solution of (17) in function space. This is our main technical result.
Theorem 6 (Implicit bias in function space). Assume W and B are random variables with P(W= = 0) =0, O, and let C -B/W. Let u denote the probability distribution of (W,C). Suppose (7, is the solution of 17 and consider the corresponding output fanction
= -x+
[
(x-w)(x--c)))) dv(w .c).
(18)
JR2
Let vc denote the marginal distribution of and assume it has a density function pc. Let B(W+(C)
denote the conditional expectation W22 given C. Consider the function (())
Assume that training data x, E ssupp()) i I.....m. Consider the set S =uppp(())
max
Then (7,085))) satisfies (I, = f x & S for E S it the solution of the following problem:
(x)) dx s.t. hxx)) ((x)
min hEC
j_
(19)
The proof is provided Appendix where we also present the corresponding statement without ASI. We study the explicit form of this function in the next section.
5.3 EXPLICIT FORM OF THE CURVATURE PENALTY FUNCTION
Proposition 7. Let pw.s denote the joint density function of (W,B) and let -B/W so that pC.
the breakpoint density. Then ((z) = ([(22|C==))pcee = W WWW.ssssWWWWWWWWWW Pw.
dW.
The proof is presented in Appendix] J If we allow the initial weight and biases to be sampled from suitable joint distribution, we make the curvature penalty p p=1 arbitrary.
Proposition 8 (Constructing any curvature penalty). Given any function o: - Ry. satisfying Z = JR e co, if we set the density of C as pe(x) e(a) and make W independent of C with non-vanishing second moment, then (B(W2(C==)pe ((CC=())pp)))
(B(W2)pe(z))) x @(x), ER.
Further remarks on sampling and independent variables are provided in Appendix J To conclude this section we compute the explicit form ( for several common initialization procedures.
Theorem 9 (Explicit form of the curvature penalty for common initializations).
(a) Gaussian initialization. Assume that W and B are independent, W W~N(0. and BudB~NO B~N.,00))))) 20 og
Then Ç is given by ((x) न[न +-
(b) Binary-uniform initialization. Assume that W and B are independent, W E (-1,1} and B B~~U(--a,,a with as L. Then Ç constant on L-L,L].
(c) Uniform initialization. Assume that W and B are independent, W ~ u(-aws aw) and
B B~ll(-as,an with as a. 2 L. Then Ç is constant on LL.L].
The proof is provided in Appendix K
Theorem (b) and [c) show that for certain distributions of
(W.B), Ç is constant. In this case problem (19 is solved by the cubic spline interpolation of the data with natural boundary conditions (Ahlberg al. 1967). The case of general Ç is solved by space adaptive natural cubic splines, which can be computed numerically by solving a linear system and theoretically in an RKHS formalism. We provide details in Appendix
8

---

Under review as conference paper at ICLR 2021
6 CONCLUSION AND DISCUSSION
We obtained explicit description of the implicit bias of gradient descent for mean squared error regression with wide shallow ReLU networks. We presented a result for the univariate case and generalizations to multi-variate ReLU networks and networks with different activation functions. Our result can also help us characterize the training trajectory of gradient descent in function space.
Our main result shows that the trained network outputs a function that interpolates the training data and has the minimum possible weighted 2-norm of the second derivative with respect to the input. This corresponds to an spatially adaptive interpolating spline. The space of interpolating splines is a linear space which has a dimension that is linear in the number of data points. Hence our result means that, even if the network has many parameters, the complexity of the trained functions will be adjusted to the number of data points. Interpolating splines have been studied in great detail in the literature and our result allows to directly apply corresponding generalization results to the case of trained networks. This is related to approximation theory and characterizations for the number of samples and their spacing needed in order to approximate functions from given smoothness class to desired precision [Rieger and Zwicknagl 2010; Wendland 2004).
Zhang et (2019) described the implicit bias of gradient descent as minimizing a RKHS norm from initialization. Our result can be regarded as making the RKHS norm explicit, thus providing an interpretable description of the bias in function space. Compared with Zhang al. (2019), our results give precise description of the role of the parameter initialization scheme, which determines the inverse curvature penalty function Ç. This gives us rather good picture of how the initialization affects the implicit bias of gradient descent. This could be used in order to select good initialization scheme. For instance, one could conduct pre-assessment of the data to estimate the locations of the input space where the target function has high curvature, and choose the parameter initialization accordingly. This is an interesting possibility to experiment with, based on our theoretical result.
Our result can also be interpreted in combination with early stopping. The training trajectory is approximated by smoothing spline, meaning that the network will filter out high frequencies which are usually associated to noise in the training data. This behaviour is sometimes referred to spectral bias (Rahaman et al. 2019).
REFERENCES
Felix Abramovich and David M. Steinberg. Improved inference in nonparametric regression using Lu-smoothing splines. Journal of Statistical Planning and Inference, 49(3):327 - 341, 1996. ISSN 0378-3758. doi: htt.:///ww....eee....../aa////// / h/www. www.scciinneeeeeee.cce.. com/
URL http:
J. H. Ahlberg, Edwin N. Nilson, and J. L. Walsh. The Theory of Splines and Their Ap- plications. ISSN. Elsevier Science, 1967. ISBN 9780080955452. URL https
7/books. . goo.looogeeooooooooooooooo le. cowp/bookks.._s711pppppppppppppp
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002. 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pages 2933-2943, 2019.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1019-1028, International Convention Centre, Sydney, Australia, 06-11 1 Aug 2017. PMLR. URL www.s/vv0000
Inttp://proceeddingg www.:innnsm........m............ www..rr....m wttp:///iwwi.......eeeee.///....
winhhib..... html
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1841,, Stockholmsmüssann. Stockholm Sweden, 10-15 Jul 201 Sa. PMLR URL httlhhttp///proo
ngs. ml wwwppp/wassssppeeeeeepppp ptppss/////gggaaaaaaaraaa 18..mml

---

Under review as conference paper at ICLR 2021
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent lin- ear convolutional networks. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchy and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 9461-9471. Curran Associates, Inc., 2018b.
pdd]
Jakob Heiss, Josef Teichmann, and Hanna Wutte. How implicit regularization of neural networks affects the learned function part i. arXiv preprint arXiv:1911.02903: 2019. 2019.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Gamett, editors, Advances in Neural Information Processing Systems 31, pages 8571 8571-8580. Curran Associates, Inc., 2018.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772-1798, Phoenix, USA, 25-28 Jun 2019. PMLR. URL/Ettp://proceeiinn
Second Conference on Learning
mlr www..m.tpp..v///...m.. ji1 html
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017. URL
/ttps://cpenreet http://www.ee....aaaoooo..o.e
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 3572-8583. Curran Associates, Inc., 2019.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes ReLU network features. arXiv preprint 18310.1803.0836, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412:61412..614, 2014.
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint ar05v: 2017.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width ReLU nets: The multivariate case. In International Conference on Learning Representations, 2020. URL
http:/iwwwww....eeeeeeeeeeeeeeee wwt./ id=#1 1NP*HKDH
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning:
Gradient descent takes the shortest path? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4951 49600 Long Beach, California, USA, 09 15 Jun 2019. PMLR. URL ml press/ v v97/oymak 1t..mmml.lmmmmmmmmmmmmmm..mm....
Rahul Parhi and Robert D. Nowak. Minimum "norm" neural networks splines. arXiv preprint arXiv:1910.02333. 2019.
Alexandre Pintore, Paul Speckman, and Chris C. Holmes. Spatially adaptive smoothing splines. Biometrika, 93(1):133-125, 03 2006. ISSN 0006-3444.
doi: 10. 00.1093/biomee/3.11.1 URL
https:://ooi.org/10..
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
Christian Rieger and Barbara Zwicknagl. Sampling inequalities for infinitely smooth functions, with applications to interpolation and machine learning. Advances in Computational Mathematics, 32 (1):103, 2010.
10

---

Under review as conference paper at ICLR 2021
Justin Sahs, Aneel Damaraju, Ryan Pyle, Onur Tavaslioglu. Josue Ortega Caro, Hao Yang Lu, and Ankit Patel. A functional characterization of randomly initialized gradient descent deep ReLU networks, 2020. URLAttoss///peneeeieee wwt. http:/oouunnnBBB111222
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Alina Beygelzimer and Daniel Hsu, editors, Pro- ceedings of the Shcrty-Second Conference on Learning Theory. volume 99 of Proceedings of Machine Learning Research, pages 2667-2690 Phoenix, USA, 25-28 Jun 2019. PMLR. URL http::/procceeee ngs mlm.rr..... press wet99//aaeeeeeeeeee rese 9a. html
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL.ttt:://arxiiii org/ abs 1312. 6120
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Holger Wendland. Scattered data approximation, volume Cambridge university press, 2004.
Francis Williams, Matthew Trager, Danicle Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Processing Systems, pages 8378-8387, 7778-887,2019 2019.
Lei Wu, Zhamxing Zhu, and E Weinan. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: 7706.0029, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, ICLR 2017, 2017. URL/tttps: //tp://aaavvv. wwtp://.ggggbbbbbbaaaabaae 03530
Yaoyu Zhang, Zii-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error induced by initialization in deep neural networks, arXiv preprint arXiv: /


Reviews:
[{"review_id": "otiurR2r5CO", "reviewer": "AnonReviewer6", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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\n1.  Paper Summary \n\nThis work analyzes the implicit bias of gradient descent for wide, 1 hidden layer networks used for regression and provides a characterization of this bias in function space.  At a high level, as network width increases, gradient descent leads to a solution given by a variational problem penalizing the product of the curvature and the square of the second derivative.  The proof of this proceeds as follows: (1) The solution given by gradient descent on the network can be approximated by the solution by gradient descent on a linear model. (2) Under the standard initialization, the solution for the linear model can be approximated by that of a smaller linear model (corresponding to training the last layer).  (3) The implicit bias for this problem is linked to an alternate optimization problem. (4) The solution to this problem is given by solution to the the variational problem as network width goes to infinity.  \n\n######################################################################\n\n2. Strengths\n\n2.1. The results are presented rigorously and the authors consider a number of generalizations involving (1) alternate distributions for weights/biases (2) univariate and multivariate regression (3) alternate nonlinearities. In particular, an extended discussion of generalizations is provided in Appendix O (some of the discussion points in O.3 - O.5 would be nice to include in a conclusion).\n\n2.2. The empirical evidence presented in the main text and Appendix was very useful in providing an intuitive explanation around Theorem 1.  I also particularly liked that the authors provided an interpretation paragraph on page 2, which among other points addressed the reason for involving a linear adjustment to the training data.\n\n2.3. The authors position their results well relative to a large number of related works.  Appendix C clarified a lot of the points regarding related work in the main text especially regarding comparisons between the results of this work and those of Savarese et al. 2019.  \n\n######################################################################\n\n\n3. Minor Limitations\n\n3.1. While I found this to be an interesting and rigorous work, I feel it would be helpful if the authors could provide a bit more intuition around the technical results for the generalizations.  In particular, I found the interpretation and visualizations presented in the work very helpful for understanding the implicit bias described by Theorem 1. However, it would be helpful if the authors could provide a similar intuition for the multi-variate regression setting.\n\n3.2. I found this work a bit difficult to read through due to the several jumps between equation references.  I think one thing that would help improve the readability is adjusting the Appendix such that related equations in the main text are above the related sections in the Appendix.  One example of this is the need to jump back and forth between equations 15, 16, 17 of the main text in Appendix D. \n\n3.3. I feel the authors could present some of the assumptions more clearly in the main text.  As a quick example, I believe the authors assume in equation (9) that grad_(theta) f(X, theta_0) has rank M (as is done in Appendix E), but unless I'm mistaken, this is not clearly stated in the main text, and it would be nice to understand how this rank requirement relates to the width n of the network (or whether this is not an obvious relationship).    \n\n3.4. (Very Minor) I think this work could benefit from a discussion of how the implicit bias identified in this work could connect with generalization.  For example, is there any way to understand which curvature penalties would yield solutions that generalize better? \n\n######################################################################\n\n4. Score and Rationale\n\nI would vote for accepting this paper.  I found the result to be insightful in characterizing the inductive bias of 1 hidden layer fully connected networks used for regression.  The author's present a rigorous analysis, which they complement with a number of empirical and theoretical examples. \n\n\n######################################################################\n\n5. Minor Comments\n\n5.1. (Very minor style recommendation) The current introduction is a nice summary of related work, but I think the paper would be a bit more readable if the main results and discussion were placed in front of these related works and these works were merged with the other related works section. \n\n5.2. (Minor typo) The last sentence of Appendix C.2 appears to be incomplete.  \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eFHL46mBgv", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 analyzes the implicit bias of gradient descent on a wide two-layer network with standard parameterization and initialization and the squared loss. It is first proved that in this setting, gradient descent on both layers is close to gradient descent on the second layer. Then the implicit bias of gradient descent on the second layer is characterized for a 1-dimensional regression problem, which can also be generalized to the high-dimensional case. \n\nI think it is nice to have an explicit characterization of the minimum-kernel-norm solution. Moreover, the observation that gradient descent with the standard parameterization and initialization basically only trains the second layer is also interesting. \n\nHowever, the current presentation also has many limitations:\n1. Theorem 1, 2 and 6 consider gradient descent on an adjusted training set. Specifically, Theorem 1 and 2 claim the existence of u and v, which are used to adjust the training set, but it seems that how to find u and v is not discussed. Moreover, above Theorem 6, it is said that \"If u and v in the solution of (17) are small, then the solution is close to the solution of (16).\" How should we find u and v? Can it be proved that u and v are small?\n2. The function g given by Theorem 1 and 2 are similar to the results presented in (Savarese et al., 2019) and (Ongie et al., 2020). Can you include a detailed comparison with their results and proof techniques?\n3. In Theorem 4, it is assumed that inf_n \\lambda_\\min (\\Theta_n) > 0. However, this can usually be proved in the NTK setting, for example in (Simon S. Du, Xiyu Zhai, Barnabas Poczos, Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks). Can this assumption be proved?\n4. The appendices should be included. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "YdvEh5mmCs", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 presents a function space view of 2-layer ReLU neural networks and the implicit regularization associated with full-batch gradient descent for various initializations of the weights. In past work, it was shown that for very wide neural networks, the *global* minimizer of a loss plus weight decay regularizer corresponds amounts to regularizing the total variation of the second derivative of a function (and related results in higher dimensions). This paper explores the effective regularization associated with performing gradient descent on an *unregularized* squared error loss. The resulting regularizer is akin to a weighted 2-norm of the second derivative, where the weighting function depends on the distribution of the initial weights. This result addresses an important open problem, provides interesting insights into the role of initialization and implicit bias associated with training, and is supported by nice illustrations.  \n\nThe literature review is strong and covers much of the relevant literature. \n\nMuch of the analysis seems to depend on the optimization occurring in the \"kernel regime\". It is unclear when this is or is not a reasonable model. This issue is particularly salient in light of the comparison of the results with the work of Savarese et al. Savarese considers explicit 2-norm weight decay regularization. Although the paper under review considers unregularized losses, there are multiple studies showing that gradient descent initialized near zero induces 2-norm regularization. So a natural thought is that the Savarese result would also extend (with some non-trivial technical work) to unregularized settings with gradient descent. With this in mind, I expected to see the Savarese norm as a special case of the results of the paper under review, but this is not the case. In particular, the function space regularization calculated in Savarese is NOT an RKHS norm, while the paper under review claims the function space regularization they find IS a kernel norm. I would like to see a more detailed discussion of this potential discrepancy. Section C.4 does not make this clear.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NlYk1F1VMC7", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "**Summary**:\nIn this article, the authors characterized the implicit bias of gradient descent-based learning in the setting of wide single-hidden-layer neural networks with ReLU activation. More precisely, it was shown in Theorem 1 that the trained network output is \"close\" to that of the zero-training-error solution that is the \"closest\" to initialization when the number of neurons $n$ is large. In particular, such a \"closest\" solution is defined via the so-called *curvature penalty function* $1/\\zeta$ that depends on the random initialization of the parameters. Theses results were shown in Theorem 1 to hold for *scalar* input with ReLU activation, and then generalized to *multi-dimensional* input with ReLU nonlinearity in Theorem 2 and to general homogeneous activation function in Corollary 3.\n\n**Strong points**:\nThis paper provides a precise characterization of the implicit bias of (full-batch) gradient descent method in training single-hidden-layer NN, by studying the resulting solution in the setting of large network width. The major contribution of this work, I believe, is to provide *explicit* characterization of the impact of the distribution of the random initialization on the resulting solution, which is then connected to cubic spline interpolation.\n\n**Weak points**:\nMy first concern is that the proposed analysis seems somewhat incremental (compared to previous efforts discussed in P4) and fails to provide sufficiently novel insights on the implicit bias of gradient descent: it is good to have the explicit form as in (1) that depends on the random initialization and the second derivative, and I believe it worth more than a single paragraph of discussion and a single figure to illustrate its practical implications, e.g., how does the number of training sample $M$ come into play? Can similar behaviors be empirically observed beyond the single-hidden-layer model, even without proof? how should we choose the initialization scheme in different problems?\n\nMy second concern is the organization of the paper: I do not understand why the authors have chosen to present the long and complex theorems in Section 2 before introducing the models and notations in Section 3, this makes the paper, at least for me, much harder to read and follow. Also, I do not understand why the authors have chosen to present the model and notations in Sec 3.1 and 3.2 in the general context of $L$-hidden-layer neural networks: none of the technical results are concerned with this \"deep\" case and I personally find this only creates unnecessary confusion.\n\n**Recommendation**:\nI find this paper borderline, and according to the weak points mentioned above, I'm more leaning toward a reject.\n\n**Detailed comments**:\n* abstract: \"of the second derivative\": the second derivative of what with respect to what?\n* Theorem 1: \"for which $f(x, \\theta^*)$ attains zero training error\": $f(\\cdot)$ is not yet defined, and it would also be helpful to recall the definition of $C^2(S)$ in (1).\n* Below (9): it would be helpful to clarify the conditions under which Lee et al. (2019, Theorem H.1) hold and if they are compatible with the assumptions for instance in Theorem 1 of the present article.\n* Above (10): \"gradient descent training of a wide network or of the linearized model giveS similar trajectories and solutions in function space\": the argument on the \"trajectory\" is not reflected in the last equation in P5, which only characterizes the network output.\n* Above (10): \"converge to the unique global minimum\": how is the uniqueness ensured here?\n* Above (11) footnote 1: is this a claim? If yes, it would be helpful to point out in which Section of the appendix is this proved.\n* After (11): not sure to understand why the change in $b^{(2)}$ is also negligible compared to that of $W^{(2)}$.\n* Theorem 4: it would be helpful to clarify whether $\\lambda_\\max(\\hat \\Theta_n)$ is of order $O(1)$ with respect to $n$, that is, does $\\eta < \\frac{2}{n \\lambda_\\max(\\hat \\Theta_n)}$ mean the the step size should scale like $O(n^{-1})$ in the $n \\to \\infty$ limit?", "extra_scores": {}, "extra_text": {}}, {"review_id": "BTubA1in0AQ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "Update after the rebuttal: I would like to thank the authors for the detailed reply and for addressing raised issues in the submission. I appreciate the authors' rationale, but the \"standard\" structure of papers makes it is easier to follow. The same for a conclusion, for the authors it may be reiterating the same ideas, but personally I found conclusions the best place where one can quickly get a flavour what has been done in the paper to assess whether it is actually worth spending time reading it in details. Also, they are helpful in cases like this when a reader (me) is outside of the research field of the paper. Regarding discussions, I appreciate that there is discussion for Theorem 1, but there are theorems and propositions stated in the formal language only which would benefit by being repeated in plain English. If they are just technical results required for the main proof, they may be moved to appendix then.\nOverall, I am increasing my score to reflect positive changes in the submission. \n\nThere is a minor mistakes:\n- In the first line of Conclusion: \"obtained aN explicit\"\n\n\n=========================================================================================================\n\n\nThe paper considers the implicit bias (i.e. why neural networks generalise well) in gradient descent learning of wide neural networks for the regression problem. The theoretical results are first stated for wide ReLU network for a 1D regression problem. They are then generalised for multivariate regression and different activation functions. \n\nIt is difficult for me to assess the main content of the paper, as it is outside of my comfort zone. Therefore, this review would be mostly a feedback on overall structure and clarity of the paper. \n\nStrong points:\n* apparent solid and large theoretical analysis\n* addressing the important problem of understanding why the neural networks and gradient descent lead to such successful results in various domains \n\nWeak points:\n* the paper is not friendly for outsiders of the particular research avenue. It is packed with content without too much space to discussion of presented results to the point that the conclusion section is missing in the paper\n* the structure of the paper is very odd which leads to future references that appear only 3 pages afterwards (see details below)\n\nAs mentioned I can't assess the main content of the paper, but with my educational guess I would recommend to reject the paper in the current version. Careful revision is required to make it a complete piece of work (add conclusion and discussion) and make it more accessible for wider machine learning audience.\n\nIn particular, for the above mentioned weak points:\n* I appreciate space constrains, but probably some of the material can be moved to supplementary completely to allow discussions of the main results more. The theoretical findings are mostly presented in the formal language and there is a lack of plain English discussion on what this means and how it affect the bigger picture. And the paper has to have conclusion section and shouldn't end abruptedly\n* It seems that Section 2 and 3 should be swapped as I cannot see the reason why notations and problem formulation are presented after the main results: for those who are inside the field and can understand Section 2 without introduction would not need then introduction in Section 3 at all. And those who do need Section 3 would not understand Section 2 without it. \nThis also leads to these inconvenient future references. E.g., referring in Theorem (1) to eq.(5) that appears 3 pages after that is a questionable choice.\n\nSome other suggestions/concerns:\n1.\tReLU is introduced in the last paragraph in Introduction, but used in the previous paragraph\n2.\tNTK is defined well after it is used for the first time\n3.\tThe last sentence in Section 2 – there was nothing before about different training trajectories\n4.\tNotation clash: in section 2 sigma denotes an activation function (different from ReLU) and in section 3 sigma denotes a parameter of initialisation distribution: Gaussian and uniform\n5.\tAfter eq. (7): “We will use subscript i to index neurons and subscript t to index time”, i is also used for training points.\n6.\tStrictly speaking n in equation between eq. (9) and (10) is not well-defined\n7.\tASI is not defined", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the implicit bias of gradient descent of infinite width 2-layer neural networks with ReLU activation. It is shown that the dynamics of gradient descent to optimize the 2-layer NN converges to the optimization dynamics on the random feature model in the infinite width limit. Then, it is shown that the gradient descent converges the minimal L2 norm solution from the initial parameters which yields regularization on a weighted integration of second order differentiation. Although this type of analysis has been given in the existing work, this paper gives its explicit form in 1-dimension input setting.

This paper reveals an interesting fact about the implicit regularization that would be educationally valuable. On the other hand, I should mention that there is room for improvement in its theoretical contribution and moreover its novelty is rather limited.
1. Although the explicit formulation of the implicit regularization is informative, the minimum norm bias itself is already pointed out by existing work and this work follows the line. Especially, regularization on the second order derivative has been already pointed out by previous work (although they are 1-norm regularization).
2. The logical jump from the original data to the adjusted data is still not convincing. It is explained that some numerical experiments show the linear term is negligibly small, which means the problems (15) and (17) are very close. However, this excuse does not make sense for this kind of "theoretical" work. The logic used here should be clarified to make the theoretical framework complete.

The evaluations by the reviewers indicate that this paper is on the borderline, and I also feel that some more additional strong point would be required so that this paper is accepted. I encourage the authors to go in this direction and make the analysis more detailed so that the theoretical framework would get more completed.

Minor comment:
Theorem 4 overlaps the result given by the following paper [R1]. It is recommended that the relation and novelty compared with that paper is discussed.

[R1] E, W., Ma, C. & Wu, L. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Sci. China Math. 63, 1235–1258 (2020).
Decision: Reject