Kernel and Rich Regimes in Overparametrized Models
Authors: Blake Woodworth
Suriya Gunasekar
Pedro Savarese
Edward Moroshko
Itay Golan
Jason Lee
Daniel Soudry
Nathan Srebro
Venue:  (2020)
Keywords: Overparametrized
Implicit
Bias
Regularization
Kernel
Rich
Adaptive
Regime

Abstract: A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear predictor, and thus training with gradient descent has the effect of finding the minimum RKHS norm solution.  This stands in contrast to other studies which demonstrate how gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms.  Building on an observation by Chizat and Bach, we show how the scale of the initialization controls the transition between the "kernel" (aka lazy) and "rich" (aka active) regimes and affects generalization properties in multilayer homogeneous models.  We provide a complete and detailed analysis for a simple two-layer model that already exhibits an interesting and meaningful transition between the kernel and rich regimes, and we demonstrate the transition for more complex matrix factorization models and multilayer non-linear networks. 

Under review as a conference paper at ICLR 2020
KERNEL AND RICH REGIMES IN OVERPARAMETRIZED MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear pre- dictor, and thus training with gradient descent has the effect of finding the mini- mum RKHS norm solution. This stands in contrast to other studies which demon- strate how gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. Building on an observation by Chizat and Bach (2018). we show how the scale of the initialization controls the transition between the "kernel" (aka lazy) and "rich" (aka active) regimes and af- fects generalization properties in multilayer homogeneous models. We provide a complete and detailed analysis for simple two-layer model that already exhibits an interesting and meaningful transition between the kernel and rich regimes, and we demonstrate the transition for more complex matrix factorization models and multilayer non-limess networks.
INTRODUCTION
A string of recent papers study neural networks trained with gradient descent in the "kernel regime." They observe that, in certain regime, networks trained with gradient descent behave as kernel meth-
ods (Jacot al. 2018 Daniely et al. 2016 Daniely 2017). This allows one to prove convergence to zero eтror solutions in overparametrized settings (Du et al.] 2018 2019 Allen Zhu et al.] (2018),
and also implies gradient descent will converge to the minimum norm solution (in the correspond- ing RKHS) (Chizat and Bach, 2018 Arora et al., 2019b; Mei et al. 2019) and more generally that models inherit the inductive bias and generalization behavior the RKHS. This suggests that, in a certain regime, deep models can be equivalently replaced by kernel methods with the "right" kernel, and deep learning boils down to a kernel method with a fixed kernel determined by the architecture and initialization, and thus it can only learn problems learnable by some kernel.
This contrasts with other recent results that show how in deep models, including infinitely over- parametrized networks, training with gradient descent induces an inductive bias that cannot be rep- resented as an RKHS norm. For example, analytic and/or empirical results suggest that gradient descent on deep linear convolutional networks implicitly biases toward minimizing the I.p bridge penalty, for on an infinite width single input ReLU implicitly biases towards minimizing the second order tal variations f [= dx of the learned function (Savarese et al. 2019;; and gradient descent on a overparametrized matrix factorization, which can be thought of as a two layer linear network, induces nuclear norm minimization of the learned matrix (Gunasekar et al. 2017) and can ensure low rank matrix recovery (Li et al., 2018). All these natural inductive biases (Lp bridge penalty for p < 1, total variation norm, nuclear norm) are not Hilbert norms, and therefore cannol be cap- tured by a kernel. This suggests that training deep models with gradient descent can behave very differently from kernel methods, and have much richer inductive biases.
2/depth < 1, in the frequency domain (Gunasckar et al. 2018b); weight decay
One might then ask whether the kernel approximation indeed captures the behavior of deep learning in relevant and interesting regime, does the success of deep learning come when learning escapes this regime? In order to understand this, we must first carefully understand when each of these regimes hold, and how the transition between the "kernel" regime and the "rich" regime happens.
Some investigations of the kernel regime emphasized the number of parameters ("widthh") going to infinity as leading this regime. However Chizat and Bach 2018) identified the scale of the model

---

Under review as a conference paper at ICLR 2020
quantity controlling entry into the kernel regime. Their results suggest that for any number of parameters (any width), a model can be approximated by a kernel when its scale at initialization goes to infinity (see details in Section B). Considering models with increasing (or infinite) width, the relevant regime (kernel or rich) is determined by how the sealing at initialization behaves as the width goes to infinity. In this paper we elaborate and expand of this view, carefully studying how the scale of initialization effects the model behaviour for D-homogencous models.
In Section 4 we provide a complete and detailed study for simple 2-homogeneous model that can be viewed as linear regression with squared parametrization, or as a "diagonal" linear neural network. For this model we can exactly characterize the implicit bias of training with gradient descent, as a function of the scale a of initialization, and see how this implicit bias becomes the &g norm in the a - 00 kernel regime, but the & norm in the a -> rich regime. We can therefore understand how, e.g. for a high dimensional sparse regression problem, where it is necessary to discover the relevant features, we can get good generalization when the initialization scale a is small, but not when a is large. Deeper networks corresponds to higher orders of homogeneity, and so in Section 5 we extend our study to a D-homogeneous model, studying the effects of D. In Sections 6 and we demonstrate similar transitions experimentally in matrix factorization and non non-linear networks.
SETUP AND PRELIMINARIES
We consider models f : RP x X' - RR which map parameters w E RR and examples x E X' to predictions f(w, x) E R. We denote the predictor implemented by the parameters w as hw F(w) such that hw (x) = f(w, x). Much of our focus will on models, such a linear networks, which are linear in (but not on the parameters w!), in which case F(w) E X'* is linear predictor and can be represented as a vector Sw with f f(w, x) = (Bw. x). Such models are essentially alternate shall see that change of parametrization is crucial.
parametrizations of linear models, but
In this paper, we consider models that are D-positive homogeneous in the parameters w, for some integer D 2 1, meaning that for any c R,, F(c.w) = c² F(w) and (c-w, = c² f(w, We refer to such models simply as D-homogeneous. Many interesting model classes have this property, including multi-layer ReLU networks with fully connected and convolutional layers, layered linear neural networks, and matrix factorization where 1) corresponds to the depth of the network.
Consider a training set [(x(1), (())) consisting of N examples of input label pairs. For a given loss function f IR R + R, the loss of the model parametrized by w is L(w)= L(F(w)) Em=r ((f(w, x(")), y (1)). We will focus mostly on the squared loss (x y)
()-w)² We slightly abuse notation and use f(w, e R denote the vector of predictions [f(w, x()) )...,.. f(,, f(w,,(()) x( and so for the squared loss we can write L(w) = [lf(w, 1| where y E RN is the vector of target labels.
Minimizing the loss L(w) using gradient descent amounts to iteratively updating the parameters
w(k + 1) w(k) (W))))
We consider gradient descent with infinitesimally small stepsize n, i.c. gradient flow dynamics
(()) = V(W((()..
We are particularly interested in the scale of initialization and capture it through a scalar pa- rameter a E R.. For scale a, we will denote by w.(() the gradient flow path (2) with the initial condition (0) aw,, for some fixed Wa. We use (t) = (t),, and for linear predictors (t) = (t), (t), to denote the dynamics on the predictor F(w) induced by the gradient flow on w.
In many cases, we expect the dynamics to converge to a minimizer of I(()), though proving this happens will not be our main focus. Rather, we are interested in the underdetermined case, N < p, where there are generally many minimizers of L(w). all with f(w, X) = y and L(w) = 0. Our main focus is which of the many minimizers does gradient flow converge to. That is, we want to characterize (oo) = limy-soc (t()) or, more importantly, the predictor ha (2o) = F(wa (2o)) or (co) (no)
converge to, and how these depend the scale a. In underdetermined problems, where there are many zero error solutions, simply fitting the data using the model does not provide enough inductive bias to ensure generalization. But in many cases, the specific solution
2

---

Under review as a conference paper at ICLR 2020
reached by gradient flow (or some other optimization procedure) has special structure, or minimizes some implicit regularizer. and this structure or regularizer provides the needed inductive bias (Gu- nasekar et al. 2018b Soudry et al. 2018 Ji and Telgarsky 2018).
THE KERNEL REGIME
Gradient descent/flow considers only the first-order approximation of the model w.r.t w:
f(w,x) f(w(t),z) + (w w(t), V (w)() x)) + O(l w(t)l²).
(3)
That is, locally around any w(). gradient flow operates the model as if it were affine model
f(w, x) z fo(x) + (w, (w()) (x)) with feature map @wie) (x) V (w((),,xx) (offt)x),
corresponding to
the tangent kernel Kwit) (z, x²)
f x), Vwf(w(t)) x)) (Jacot et al. 2018 Zou et al.
2018 Yang. 2019 Lee et al. 2019). Of particular interest is the tangent kernel at inttaaiittion,
K (w.,t0)=
Kg where we denote Ko Kwa-
The "kernel regime" refers to a situation in which the tangent kernel Kw()) does not change over the course of optimization, and less formally to the regime where it does not change significantly, i.e. where V, k, 2 (w In this regime, training the model is exactly equivalent to training an affine model f(w, x) ((wo/((w x) + (w a--+(bo(x)) with kernelized gradient descent/flow with the kernel Q2(D-1) Kn and a "bias term" of a ((Wo, x). To avoid handling this bias term, and in particular its scaling, Chizat and Bach (2018) suggest using "unbiased" initializations such that F(wo) = 0, so that the bias term vanishes. This can often be achieved by replicating units or components with opposite signs initialization, which is the approach we use here (see Sections 6 for examples and details).
For underdetermined problem with multiple solutions f(w, x) y. unbiased kernel gradient flow (or gradient descent) converges to the minimum norm solution lug = arg (x) || where || is the RKHS norm corresponding to the kernel. And so, in the kernel regime, we will have that h(co)= hK. and the implicit bias of training is precisely given by the kernel.
When does the "kernel regime" happen? Chizat and Bach (0118) showed that for any homogeneous model satisfying some technical conditions, the kernel regime is reached as - 0o. That is, increase the scale of initialization, the dynamics converge to the kernel gradient flow dynamics with the kernel Ko. and we have lim ha )x) = lux- In Sections 4 and 5 we prove this limit directly for specific models, and also demonstrate it empirically for matrix factorization and deep
networks in Sections 6 [and]] 7
In contrast, and we shall see in later sections, the + small initialization limit often leads to very different and rich inductive bias, e.g. inducing sparsity or low-rank structure (Gunasekar et al., 2017 Li 2018 Gunasekar al., 2018b), that allows for generalization in many settings where kernel methods would not. We refer to this limit reached as + 0 as the "rich regime." This regime also referred as the "active" or "adaptive" regime (Chizat and Bach] 2018) since the tangent kernel K (()) changes over the course of training, in sense adapting to the data. We argue that this regime the one that truly allows us exploit the power of depth, and thus the more relevant regime for understanding the success of deep learning.
4 DETAILED STUDY OF SIMPLE DEPTH-2 MODEL
We study in detail a simple 2-homogeneous model. Consider the class of linear functions over X Rd with squared parameterization as follows:
f(w,x x) Σ (w w2 , (Bw: x), where
W+ w_
R and Bw w w (4)
Chizat and Bach did not consider only homogenous models, and instead of studying the scale of initializa- tion they studied scaling the output of the model. For homogeneous models, the dynamics obtained by scaling the initialization are equivalent to those obtained by scaling the output, and so here we focus on homogenous models and scaling the initialization.
3

---

Under review as a conference paper at ICLR 2020
where we use the notation z² for Rd to denote elementwise squaring. We consider initializing all weights equally with Wo 1.
This is nothing but linear regression model, except with an unconventional parametrization. The model can also be thought of as a "diagonal" linear neural network (i.c. where the weight matrices have diagonal structure) with 2d units. A standard diagonal linear network would have d units, with each unit connected to just a single input unit with weights u, and the output with weight vs, thus implementing the model f((u, v), = E; U, But if at initialization |u; |os], their magnitude will remain equal and their signs will not flip throughout training, and so we can equivalently replace both with a single weight w,. yielding the model f(w, x) (w², x).
The reason for using both w+ and w- (or 2d units) is two-fold. First, it ensures that the image of F(w) is all (signed) linear functions, and thus the model is truly equivalent to standard linear regression. Second, it allows for initialization at F(awo) 0 without this being saddle point from which gradient flow will never escape
The model is perhaps the simplest non non-trivial D- D-homogeneous model for D > 1, and we chose for this reason, as it already exhibits distinct and interesting kernel and rich regimes. Furthermore, we can completely understand both the implicit regularization driving this model and the transition between the regimes analytically.
Consider the behavior of the limit of gradient flow 2 as function of the initialization, in the underdetermined < d case where there are many possible solutions X,3 = y. The tangent kernel at initialization is Ko(x, x') Sa² (x, x'), i.e. scaling of the standard inner product kernel, so || x || Thus, in the kernel regime, gradient flow leads to the minimum le norm solution, 3. = arg min xæ=ı [1 Following Chizat and Bach (2018) and the discussion in Section 3 we thus expect that lima-+oc 3a = 3i2. and we also show this below.
In contrast, Gunasekar et al. (017) shows that as imum & norm solution lim (xx) = 3 = arg minx [| This is the "rich regime." Comparing this with the kernel regime, already two very distinct behaviors and, in high di- mensions, two very different inductive biases. In particular, the rich regime's 's bias is not an RKHS norm for any choice of kernel. Can we charactarize and understand the transition between the two regimes as a transitions from very small to very large? The following theorem does just that.
O, gradient flow leads instead to the min-
Theorem 1. For any 0 < a < 20,
(oo))) =Ba = arg min Qa (B) s. XB x3=x =;
(5)
B
where Qa (3) -i (g) and q(2) = So aresinh ( du 2 V4+ x² + arcsinh (
Proof sketch The proof in Appendix A proceeds by showing the gradient flow dynamics on w lead to solution of the form
Ba(oc)= =a² a² (xx (-4X- 4X So0 ra(t)dt) exp 4xX [o ra(()dtt)
(6)
where To (t) (t) y. While evaluating the integral would be very difficult, the fact that
Ba(co) E {a² (exp (-X exp (xTr) : :i })
already provides dual certificate for the KKT conditions for ming Qa (13) s.t. X3=
In light of Theorem D the function Qa (referred to elsewhere as the "hypentropy" function Ghai
al. 2019)) can be understood an implicit regularizer which biases the gradient flow solution towards one particular zero-error solution out of the many possibilities. As a ranges from 0 to 00, the Q. regularizer interpolates between the l and Ea norms, as illustrated (labelled D = 2) have that B,/a² + 0, and so the behaviour of (3) is controlled by the behaviour of g(z) around = 0. In this regime
in Figure 2a which shows the coordinate function g. As +
*Our results can be generalized to non-unitonn con-uniform initialization. "biased initiliation" (i.e. where w- * w+ initialization), the asymmetric parameterization f(Uu, v)), x) E, Min,,, however this complicates the presentation without adding much insight.
4

---

Under review as a conference paper at ICLR 2020
03547
(a) Generalization
(b) Norms of solution
(c) Sample complexity
Figure (a), population error gradient
solution vs. a in the sparse regression problem described in Section 4 In (b). the excess & norm (blue) and excess lz norm (red) of the gradient flow solution, Le. 1 |LLll 2l and [),,,(o))]] (oo)ll, - In (c), the largest such that B. (20) achieves population error at most 0.025 shown. The dashed line indicates the number of samples needed by Bi1-
((2) E + (=))) is quadratic, and (8) E, 83 - 113112. On the other hand when O, 0./a² - is governed by the asymptotic behaviour q(=) ((2 log z) - oc. In this regime Q,) a.
8 log & a² x ||,3]|, + o(1). For any initialization scale a, the function Qa describes exactly how training will interpolate between the kernel and rich regimes. The following Theorems, proven in Appendix as 0 and
B provide a quantitative statement of how the & and & norms are approached respectively:
Theorem 2. For any
a S min { (2(1 (| - .cxp(dd(eelBit.l))) = 11 1 S (1 || l1
a z (2(1+) 2/6) 1| =
11 S 13
Theorem 2 indicates a certain asymmetry between reaching the rich and kernel regimes: polyno- mially large suffices approximate Bi to very high degree of accuracy. On the other hand, exponentially small a is sufficient to approximate 3%,1 and Lemma 2 in Appendix proves that S d-1(1/e) is necessary in order for Qa to be proportional to the & norm, which indicates that must be exceedingly small to approximate 37,1 for certain problems.
This suggestive of an explanation for the difficulty of demonstrating rich regime behavior empiri- cally in matrix factorization problems (Gunasekar et al. 2017, Arora et al.) 2019a). If the initial- ization really needs to be exponentially small, then conducting experiments in this regime may be infeasible for practical reasons.
In order to understand the effects of initialization generalization, consider a simple sparse regres- sion problem, where xx),,..,,xt (N) N I) and y(²) = (3", x(")) + No0, 0.01) where 3 is r*-sparse and its non-zero entries are 1/vr". When N S gradient flow will reach error solution, however, not all of these solutions will generalize the same. With = O(r" log d) samples, the rich regime, i.e. the minimum E norm solution will generalize well. However, even though we can fit the training data perfectly well, we should not expect any generalization in the kernel regime with this sample size (N (dd) samples would be needed that regime), see Figure Ic In this case, to generalize well may require using very small initialization, and generalization will improve as we decrease a. From an optimization perspective this unfortunate because w is a saddle point, so taking - O drastically increases the time needed to escape the saddle point.
training
Thus, there is a tension here between generalization and optimization: a smaller a might improve generalization, but it makes optimization trickier. This suggests that in practice we would want to compromise, and operate just the edge of the rich regime, using the largest a that still allows for generalization. This is borne out in our neural network experiments in Section 7 where standard initialization schemes correspond to being right on the edge of entering the kernel regime, where we expect models to both generalize well and avoid serious optimization difficulties.
The tension between optimization and generalization can also be seen through a tradeoff between and still generalize. In Figure Ic for each sample size
the sample size and the largest N. plot the largest for which the gradient flow solution 3, achieves population risk below

---

Under review as a conference paper at ICLR 2020
No
D+2
0-5
D-18
upoh
302
(a) Regularizer
(b) Approximation ratio
(c) Sparse regression simulation
Figure 2: (a) (=(()) for several values (b) The ratio
/ as function of a, where es
2 (ex)
[1,0,0.... .,..... is the first standard basis vector and la
is the all vector in R This captures the transition between approximating the & norm (where the ratio is 1) and the norm (where the ratio is 1/Vd). (c) sparse regression simulation in Figure using different order models. The y-axis is a (the scale of B3 at initialization) needed to indicates the number samples needed order for PL. to approximate the plant.
the planted predictor accuracy 0.025. The dashed line
some threshold. As N approaches the number of samples needed for 1i to generalize (the vertical dashed line), a must become extremely small. However, generalization is much easier when the number of samples is only slightly larger, and we use much more moderate initialization.
HIGHER ORDER MODELS
In the previous Section, considered 2- 2-homogeneous model, corresponding to simple depth-2 "diagonal" network. Deeper models correspond to higher order homogeneity (a depth- ReLU or linear network D-homogeneous), motivating geneity on the transition between the regimes. We therefore generalize our model and consider:
understand the effect of the order of homo-
Fn(w) = Bw.D w w and fD(w, x) = (
We again consider initializing all weights equally so Wo = As before, this just a linear regres- sion model with an unconventional parametrization. It is equivalent to depth- /) matrix factoriza- tion model with commutative measurement matrices, as studied by Arora et (2019a), and can be thought of as depth-L) diagonal linear network.
We can again study the effect of the scale the initialization a on the implicit bias. Let 3, denote the limit of gradient flow w when initialized at all for the D-homogeneous model. Using the same approach as in Section in Appendix we show:
Theorem 3. For any and
2 3, if gradient flow reaches a solution X(a,p(oc) y. then
(oo) = arg ming Q2(3) s.t. x3=yy
where (?(3)) Σi= (3(/// and qn = hhp is the antiderivative of the unique inverse of 20=190(3.00
hn(z) (1 2) 7
2) m [ 1, 1]. Furthermore, Ba Bi and
lima- Bo,0(20) = B
In the two extremes we see that we again get the minimum & solution the kernel regime, and more interestingly. for any depth D > 2, we get the same minimum & norm solution in the rich regime, as has also been observed by (Aror et al.] (2019a). The fact that the rich regime solution does not change with depth is perhaps surprising, and does not agree from what is obtained with explicit regularization (regularizing ||l||| is equivalent to || 1//2 regularization), nor with implicit regularization on logistic-type loss Gunasekar et al. (0177).
go beyond D = 2, what does change is the interme- diate regime (the regularizer Q! is unique and cannot be obtained with any other order D' * D), well as the sharpness of the transition into the extreme regimes, as illustrated in Figures 2a 2c The most striking difference is that for order > 2 the scale a needed to approximate the E is polynomial rather then exponential, yielding much quicker transition the "rich regime", and
Although the two extremes do not change

---

Under review as a conference paper at ICLR 2020
04
0.
05
033
01
0.
10
10
10 10
12
Figure 3: Regimes in Matrix Completion We generated a 10 x 10 rank-one matrix completion problem
with ground truth M u" "'")" by generating ,²,"" R with i.idd (00 1) entries and observing N = random entries Q2. We fit observed entries by minimizing the squared loss on matrix factorization model F(U, V) = UV with U, V E I2 For different scalings a, we examine the matrix (xx) reached by gradient flow on U, V (solved using python ODE solvers) and plot (i) the reconstruction error on unobserved entries Eiger
M (oo)),)² and (ii) the amount by which the unobserved entries changed during optimization (M)()))()))) (ox)) (0) In (a) we used k 2d and initialized to Uo- Vo aI. In (b) for varying we initialized to Uo al, and Vo- aVo with Un. Vo g with i..d. (((0, 1) entries. For large k. the tangent kernel converges to the kernel corresponding to the Frobenius norm.
allowing opar-optimal sparse regression with reasonable initialization scales. Increasing D further hastens the transition. This might also help explain some of the empirical observations about the benefit of depth in deep matrix factorization Arora et al. (2019a).
DEMONSTRATION IN MATRIX COMPLETION
We now turn to a more complex depth two model, namely a matrix factorization model, and demonstrate similar transitions empirically. Specifically, consider the model over matrix in- puts X E Raxd defined by ((U,V), = (UVT, X). where U, E Rddk This corresponds to linear predictors over matrix arguments specified by F(U,V) = UVT In overparameterized regime with & 2 d, the parameterization itself does not introduce any explicit rank constraints. We consider here a random low rank matrix completion problem where X, ei,, represents an uniform random observation of entry (.. of planted low rank matrix M of rank r* < d: yn (M', X,) Mi.. For underdetermined problems where N < d², there are many trivial global minimizers, most of which are not low rank and hence will not guarantee recovery. As was demonstrated empirically by Gunasekar et al. (017) and also proven rigorously for Gaussian mea- surements by Li et al. (2018), as - 0 gradient flow implicitly regularizes the nuclear norm, which for random measurements leads to recovery of ground truth (Candès and Recht 2009 Recht et al., 2010 these are very different and rich implicit biases that not RKHS norms.
Crucially, the reconstruction results in Gunasekar et al. (211)) and Li et al. (2018) are dependent on initialization with scale Section in order to get unbiased 0 initialization, we consider & 2 2d and initialization of the form (0) = a [U, -U] and (())= = a [Vo. Vol. where Up. Vo E ddxk/2 We will study implicit bias of gradient flow over the factorized parameterization with above initialization.
0. Here we further explore the role of initialization. Similar to
For matrix completion problems with X = cxx-xx the tangent kernel at initialization is given by Kx(X,X)) x :I. Uolixi,
( :)) 1(jx = jxx) (Volix, :]. :ll 1(ix = ix.). This defaults the trivial delta kernel K K(X, X') (X,X')=
1(ix = -xx:) 1 = jxx') for the two special cases (a) Un, Vo have orthogonal columns (e.g. Uo = Vo = 7), or (b) Uo. Vo have independent Gaussian entries and + oc. In these cases, minimizing the RKHS norm of the tangent kernel corresponds to returning a zero imputed matrix (minimum Frobenius norm solution). Figure demonstratts the behaviour of gradient flow updates in the "rich" regime (where for a + recovers the ground truth) and in the "kernel" regime (where for large a, there are no updates to the unobserved entries).
NEURAL NETWORK EXPERIMENTS
In the preceding sections, we intentionally focused on the simplest possible models in which a kernel-to-rich transition can be observed, in order isolate this phenomena and understand it in

---

Under review as a conference paper at ICLR 2020
detail. In those simple models, we were able to obtain complete analytic description of the tran- sition. Obtaining such a precise description in more complex models is somewhat optimistic at this point, as do not yet have satisfying description of even just the rich regime. Instead, we now provide empirical evidence suggesting that also for non-linear and realistic networks, the scale of initialization induces transition into and out of "kernel" regime, and that reach good gener- alization we must operate outside of the "kernel" regime. To track whether we are in the "kernel" regime, we track how much the gradient fw x) changes throughout training. In particular, we define the gradient distance to be the cosine distance between the initial tangent kernel feature map w. (w (0). x) and the final tangent kernel feature map Vw (w.((((T), (w(
we see that also for a non-linear ReLU network, we remain in the kernel regime when the initialization is large, and that exiting from the kernel regime is necessary order to achieve small test error on the synthetic data. Interestingly, when n ~ 1, the models achieve good test error but have smaller gradient distance which, not coincidentally, corresponds to using the out-of-the-box Uniform He initialization. This lies on the boundary between the rich and kernel regimes, which is desirable due to the learning vs. optimization tradeoffs discussed in Section 4 On MNIST data, Figure 4e shows that previously published successes with training overly wide 2 ReLU networks without explicit regularization (e.g. Neyshabur et al.) 2014) relies on the initialization being small, i.e. being outside of the "kernel regime". In fact, the 2.4% test error
In Figures 4a and 4b
reached for large initialization is no better than what can be achieved with a linear model over a random feature map. Turning to a more realistic network. 4f shows similar behavior when training a VGG11-lik- network on CIFARIO.
So far, we attempted to use the best fixed stepsize for each initialization (i.e. achieving the best test error). But as demonstrated in Figures 4c and 4d] the stepsize choice can also have a significant effect, with larger stepsizes allowing one to exit the kernel regime even at an initialization scale where a smaller stepsize would remain trapped in the kernel regime. Further analytic and empirical studies are necessary in order to understand the joint behavior of the stepsize and initialization scale.
DISCUSSION
The main point of this paper is to emphasize the distinction between the "kernel" regime in training overparametrized multi-layered networks, and the "rich" (active, adaptive) regime, show how the scaling of the initialization can transition between them, and understand this transition in detail. We argue that rich inductive bias that enables generalization may arise in the rich regime, but that focusing on the kernel regime restricts us to only what can be done with an RKHS. By studying the transition we also see a tension between generalization and optimization, which suggests we would tend to operate just on the edge of the rich regime, and so understanding this transition, rather then just the extremes, is important. Furthermore, we see that at the edge of the rich regime, the implicit bias of gradient descent differs substantively from that of explicit regularization. Although in our theoretical study we focused on a simple model so that we can carry out a complete and exact analysis analytically, our experiments show that this is representative of the behaviour also in other homogeneous models, and serve as a basis of a more general understanding.
Effect of Width Our treatment focused on the effect of scale on the transition between the regimes, and we saw that, as pointed out by Chizat and Bach, we can observe a very meaningful transition between a kernel and rich regime even for finite width parametric models. The transition becomes even more interesting if the width of the model (the number of units per layer, and so also the number of parameters) increases towards infinity. In this case, we must be careful as to how the initialization of each individual unit scales when the total number of units increase, and which regime we fall in to controlled by the relative scaling of the width and the scale of individual units at initialization. This is demonstrated, for example, in Figure 5 which shows the regime change in matrix factorization problems, from minimum Frobenius norm recovery (the kernel regime) to minimum nuclear norm recovery (the rich regime), a function of both the number of factors ic and the scale of initialization of each factor & As is expected, the scale a at which we see the transition decreases as the model becomes wider, but further study is necessary to obtain complete understanding of this scaling.
A particularly interesting aspect of infinite width networks is that, unlike for fixed-wia wxith networks, it may be possible scale a relative to the width lo such that at the infinitewwidth limit would
8

---

Under review as a conference paper at ICLR 2020
2.30
0.8
0.15
9.25
9.7
0.5
0.14
Sradted disarro
2.5
0.12
3010 pmed
3.25
Dw2
0.4
0.30
Dw55
Dw3
0.08
9.20
0.2
0.64
9.1
0.64
3.50
9.0
0.62
stepsce
(a) Test RMSE scale
(b) Grad distance VS scale
(c) Test RMSE stepsize
0.7
3.0
0.5
2.5
0.3
40
35-
0.3
30
10.9 10a 127
107
0.8
1.0
3.2
1.4
1.6
1.8
2.0
0.000 6,025 0.053 0.075 6,000 0,125 0.150 0.175
(d) Grad distance vs stepsize
(c) MNIST test error vs scale
(f) CIFARIO test error vs scale
Figure 4: Synthetic Data: we generated small regression training set in IR² by sampling 10 points uniformly from the unit circle, and labelling them with a hidden layer teacher network with 3 hidden units. We trained overparametrized depth-D, ReLU networks with 30 units per layer with squared loss using full GD and small stepsize 0.01. The weights of the network set using the Uniform He initialization, and then multiplied by a. The model is trained until = training loss. Shown (a) and (b) are the test error and grad distance vs. the hepth-adjusted scale of the initialization, a when a small constant stepsize is used. for (c) and (d), we fix a near the transition into the kernel regime, and show the test error and grad distance vs. the stepsize. MNIST: we trained a 2epth-2 with 5000 hidden units with cross-entropy loss using SGD until it reached 100% training accuracy. The stepsizes were optimally tuned for each a individually. In (e), the dashed line shows the error of the resulting network vs. a. We repeated the experiment, but froze the bottom layer and only trained the output layer until convergence. The solid line shows the test error of this predictor vs a. CIFARIO: we trained VGGI 1-like deep convolutional network with gross-entropy loss using SGD and small stepsize 10 for 2000 epochs; all models reached 100% training accuracy. In (f), the dashed line shows the final test vs. a. We repeated the experiment freezing the bottom 10 layers and training only the output layer-the solid line shows this model's 's test error. See Appendix B for full details about all of the experiments.
have an (asymptotically) unbiased predictor at initialization limę- F& (w()) 0, or at least a non-exploding initialization lim supp (F = O(1), even with random initialization (without a doubling trick leading to artificially unbiased initialization), while still being in the kernel regime. For two-layer networks with ReLU activation, Arora et al. (2019b) showed that with width k 2 poly(1/ max]=]|as1, fo))))) the gradient dynamics stay in the kernel regime forever.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 1. 1.09922, 2018
Sanjeev Arora, Naday Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:/905. /3655,, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine aineggrained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 2019b.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96)):717-77,, 2009.
Lenaic Chizat and Francis Bach. A note lazy training in supervised differentiable programming. arXiv preprint 1.X.::812..0996, 2018
Amit Daniely. SGD learns the conjugate kernel class of the network. In Advances in Neural Infor- mation Processing Systems, pages 2422-2430, 2017.

---

Under review as a conference paper at ICLR 2020
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In Advances In Neural Information Processing Systems, pages 2253-2261, 2016.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 10V1:88000000 0.000,, 2018.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations, 2019.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points-onling online stochastic gradient for tensor decomposition. In Proceedings The 28th Conference Learning Theory, pages 797-842, 2015.
Udaya Ghai, Elad Hazan, and Yoram Singer. Exponentiated gradient meets gradient descent. arXiv preprint arXiv: (0ti:::99020990000 2019.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159) 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint arXiv:/802.08246, 20.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent linear convolutional networks. arXiv preprint arXiv:/806.0000 804600 2018b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEFE international conference on computer vision, pages 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. arXiv preprint arXiv: 2018.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 010..00000002... 2018.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint 1002::090207722 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in ver-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pages 2-47, 2018.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-frea bounds and kernel limit. arXiv preprint arXiv: 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint 1rXiv:14/2.6614 2014.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-raan solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):771-501 2010.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? arXiv preprint arXiv: 192..00000000000 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. Journal of Machine Learning Research, 19(70), 2018.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1XXY:19022.44660, 2019.
10

---

Under review as a conference paper at ICLR 2020
Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression. 03 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint
2018.
A PROOF OF THEOREM
It is straightforward, given the expression for Qa. to prove that Gr is the minimum Qa solution to XB y. other words, we had been able guess from the beginning that the implicit bias would be governed by Qa. it would have been easy prove this fact. However, key contribution of this work is in developing method for determining what the implicit bias when we not already have good guess.
We will first describe a general approach for deriving the implied regularizer reached at the limit of some gradient flow dynamics which minimize the loss. In particular, our approach will apply whenever solutions the gradient flow dynamics can be written as (t) = fa v(t)) for some (t)).
The first step is to analyze the gradient flow dynamics of Ba and show that
(0a( = y
(a( fx v((o))
for function Ja and some vector v(x)). It is not important for approach to know exactly what ((2)) is. This useful because calculating this v(0o) will often be difficult, even for the simple examples we consider.
The next step is to suppose that there is some function Qa such that
Ba(x)) arg min Qa s.t. x
(10)
B
and to write down the KKT optimality conditions for (TO)
XB
(11)
EV VQa (8") T
Finally, we connect (9) with
11 Specifically, (a( satisties the first KKT condition, and, if
(oo) 3 then by taking v((o) we have
VQa (Baa (co)) = VQa (fa X
(12)
follows that VQ. = (B). Therefore, to derive Qa we simply invert fa and integrate its inverse. We prove Theorems | [nddd] using this method.
Theorem 1. For any < 00,
(oo) Ba = arg min Qa (B) s.t. XB === y.
(5)
where Qa (3) Ei=
and g(=) fe aresinh (#) du 2 /4+ x2 arcsinh (
Proof. We begin by calculating the gradient flow dynamics on w, since the linear predictor Ba (Do) given by F applied the limit of the gradient flow dynamics on w. Recalling that
X X -X],
Wa (t) = = -LW = -V (
= -2X (t) (t
(13)
where the residual r. (1) A w. (1)2 and a o denotes the element-wise product of a and b. It easily confirmed that these dynamics have solution:
(22XT S( (ra((sdss)
w wa (t) = (. exp
(14)
11

---

Under review as a conference paper at ICLR 2020
This immediately gives expression for (t):):
Ba(t) = Wa,+(t)²
(t)-(t)²
(15)
I ra(s)ds) exp [4X] S ra(o)ds)
= a² exp
-4X"
(16)
(44XT / ro(s)ds)
2a sinh
(17)
In addition, this problem satisfies the strict saddle property (Ge al. 2015) (Zhao 2019
Lemma 2.1), therefore gradient flow will converge to zero-error solution, i.e. X 33,00 (20)
y-
Thus, we conclude that Ba (oo) global minimum with zero error, i.e. (,0)(00) = y.
Thus, we have established that
XBo(00)=1 = ( -fa(XTv(o))
(18)
for fz( 2n sinh(z) and v(00) -4 (s)dss This corresponds to from our general
approach detailed above. Continuing from (12) we have that
VQn fo (B) aresinh (3/2a²)
(19)
Integrating this expression completes the proof.
B PROOF OF THEOREM 2
Lemma 1. For any Rd.
a a1 (c, 1 d) = -mii (1, |1 (2 12111) exp (-
2e |181|
guarantees that
a²
|| (1 () I In(1/a2) Q(3/a2) s [|8||, c1+c)
Proof. First, we show that Q(3/a²) Qa (18) Observe that g(x) x arcsin(x/2)) is even because I and arcsin(r/2) are odd. Therefore,
02 a4
Bi 2a
Q(3/03)
Σ
aresinh
(20)
aa
i=1
d
g2
3
Σ
2
4 +
(21)
a
az
1=1
d
1
3
Σ 2
4
+
(22)
at
a
i=1
Qa(13//c)
(23)
12

---

Under review as a conference paper at ICLR 2020
Therefore, we rewrite
a²
a²
In(1/a2) Q(3/22) - in(1/a2)
/a13
(24)
2a²
V4a + B
|3&1| aresinh in(1/22)
[
(25)
in(1/a2)
In(1/a2)
2x²
2a.²
/4a + +3²
In(1/22) |33,1 In
[1&
33
+ V 1 +
(26)
In(1/a?)
In(1/a2)
2n
4x
In
10c1 2
+ V a+ + 82
2a
V4at +
4
+ +9.1|
1+
In In(1/a2)
ln(1/22)
In(1/a2)
(27)
Using the fact that we can bound for a < 1
|a| S V 12 S $|a| + [b]
(28)
In(1/a2) Q13/a9)
Σ
d
2a²
2a²
+ +13,1
1+
In
+ a² +
10:1
2
(29)
In 1n(1/a2)
In ln(1/a2)
In(1/a?)
d
1+ In (1.61 +
+22) a²)
Σ
|8/1|
(30)
In(1/a²)
In (135) + a²)
$ ||
[1+max max sE|d]
1
(31)
In(1/a2)
11 In (11311, + a In(1/az)
$ [1181,
(32)
(33)
So, for any a S min 1, /I1 (2 (11111) # }. then
a²
(++ In (11:31 + a²)
018/a²) < 11
(34)
In(1/a?)
ln(1/22)
1+ In (2118111))
< |1
(35)
In(1/22)
$ || (1 +
(36)
On the other hand, using (27 and (88 again,
a²
d
2a²
|8:| + 2a² In(1/a2)
11 In (18))
Q(3/a²)
+ +18
(37)
1n(1/02)
In (n(1/22)
In(1/a²)
d
|8a1 (1+ In (1331) -
Σ
(38)
In(1/a2)
Using the inequality In(x) 2 this can be further lower bounded by
a²
Q(B/a?)
2 i=1
|33
(39)
In ln(1/22)
ln(1/22)
d
||33|| in in(1/22)
(40)
13

---

Under review as a conference paper at ICLR 2020
Therefore, for any a 2 exp (-21 then
a²
In(1/a2) Q(3/a2) 2 || (1 c)
(41)
We conclude that for a S min (1. v | (2 ) ) exp (-2((²15) ) } that
||3 (1 c) In(1/a2) 2(3/a2) (1+e)
(42)
Lemma 2. Fix any > and 2 max {e, 12 Then for any 2 i- Q(3/a²) * 11131] in the sense that there exist vectors v, w such that
Q ( |101
Q (
(1 +e)
Proof. First, recall that
1
1
1
9
ca2
= 2
4
+
+
ca2
arcsinh
2ca
(43)
1
V4 + 1 + In 2ca²
+
V
11
(44)
ca?
2ca
1
1
20a² V4 + 1 +n
+ In
+
+
(45)
oa2
c022
2
2
Thus,
1
1 In
S ca²9
s 3ca
1 +
In
(46)
ca2
co2
ca
Now, consider the ratio
Q
( E1)
q (=))
(47)
11 Q
[Tella]
dy
azvd
1 a²y 122 Vd
(48)
a2/o
Using 46 we conclude
Q (
-1 In (1)
vā
(49)
Q (T.
3vda² - + In
a3vd
-1 + In (22)
(50)
3vda² - 1 + In
(22 In(d)
In(d) - dv
(51)
6//a² - + Im
a2
14

---

Under review as a conference paper at ICLR 2020
Fix any 0 and d 2 max fe, 12 j. and set d
Then
d
2d
26 6
and
Ind
6
(52)
d
2d
6+
In
20
(53)
2E
6
Iu d
d 2 6d de - 2
(54)
2E
6 d - 2 6d + 2 In
1
In d
(55)
2
= In (d) 6a d Vd 2 6a2 Vd 2+
2 2 In
(56)
a vd
This implies that the second term of (51) is least We conclude that for any 0 and d 2 max {e, 12 a d implies that
(2)0) (1++) e)
le
(57)
@ ( 1 (|1ulla)
14
1
Consequently, for at least one of these two vectors, Q is not proportional the norm up to accuracy O(e) for this value of a.
It is straightforward to confirm that
d Q (2202) 20
(58)
da Q az |dalla)
12
which concludes the proof.
Lemma 3. For any 3 IRd.
a 2 a2(c, (wll2) = v118112 (1+
guarantees that
(1 - +) |1 S 4a a Q(3/a²)) S (1 + |13112
Proof. The regularizer Q can be written
Q(3/a²) = Σ pat
S
aresinh 1 2
di
(59)
iml
Let 002) = /2/0² aresinh (1) dt, then
(0)) = 0
(60)
o'(0) = a²
1
arcsinh
2 =
0
(61)
2a
6"(0)
(62)
a1 V
4
2a
a²
2=0
(63)
8
(4 +
22
3/2
44
1=
3z2
(64)
12
(4 +
2
σ (4 +
)
22
3/2
15

---

Under review as a conference paper at ICLR 2020
Also, note that
12x² - 4
(65)
at2 (4 + =2
6/2
a*
x² + 20
(66)
16a 12
Therefore, by Taylor's theorem, for some & with |4| S |z|
x²
(E)
(x))
24
(67)
40
x²
(T"((E
26 + 20
x2 =1+ 22
(2))
sup 1
(68)
4a
384a
4aa
96a
Therefore, for any 8 Rdd
d
4a 4aa -0(33)118113 11811 = 4a
(B3))
(69)
1a7
4a
(3,))
(70)
4a
B1 + 20 20
18
(71)
96
3 2xx 2 B3
|| max
(72)
96a
Therefore, a 2 v1 11 (1+ ensures
(1 (1-c) |13112 (1
(73)
Theorem 2, For any 0 < <<<d
a S min ( + e) 11192111) expp(d/(ellBizll)) = 113.111 S (1+ E) || ll
a 2 v 2(1+c)(1 2/c) 11 = 113 < (1 +e) |
Proof. We prove the f and & statements separately.
l approximation
First, we will prove that |a. < < 2e) || ll. By Lemma I since S
a1 2 (1 2e) || 1l d). for all with || S (1 2e) || I11 have
|1,11, (1 e < In(1/a2)
Q33/22) |1811, (1+ (
(74)
2 +
16

---

Under review as a conference paper at ICLR 2020
Let B3 be such that X3 y and ||3|| (1 + 2c) 11 l1. Then
2
Q(3/a2)
1
||31|
(75)
In(1/a2)
2 +
(1+ + 2c) ||
(76)
2+c
a²
2+c
(1+ 2c)
In(1/a2) ((9t1/09)
(77)
1 2+c
1 1+2 a²
1 In(1/22) Q(9)1/0²2)
(78)
a²
In(1/a2) Q(311/a?)
(79)
a²
In(1/a2) 2(8a
(80)
Therefore, 3 * Ba. Furthermore, let be any solution X33 = y with ||]|, > >1 + 2c) || l|1-
It is easily confirmed that there exists c E 1) such that the point 3 = (1 - c)B + c satisfies both X,3' = y and ||,811, = (1 + 2e) [| By the convexity of Q, this implies
((3/a²) 2 Q(' /a²) > Qa(3a/a²). Thus a 3 with a large & norm cannot be a solution, even if in(1/a=) Q(B/a²) & I|@|11.
| < (1 + 2x) | ll. we conclude
Since
|.
Q(3./a²)
(81)
In (n(
1
24c
< 1
a²
c In(1/22) ((3)n/a3)
(82)
Z+e
+ 24c
<
||
(83)
2tc
(1 + é) ||
(84)
we will prove that |
First,
< (1+26) |
By Lemma
since a
2
2
|| (12) ) for all B3 with ||,81|2 S (1 (1+22) 26) || ll2 we have
02 Z (1 + 26)
|| 1
c
< 4a 44a Q(3aa3)) < 11111
1 2 e
(85)
2+
Let be such that X,3 = y and ||:1| = (1 + 2c) || Then
4a (((/222) 2
1 2+c
||3112
(86)
1 2+
(1+ + 2c) 1|
(87)
1 2+c
(1+ ++2e))4aQ((iia))
(88)
1 2+c
1 1 2
4a (Q(((i2/aa)
(89)
Itc
4a 232((22/
(90)
4a (3)a
(91)
17

---

Under review as a conference paper at ICLR 2020
Therefore, 3 + Ba. Furthermore, let | be any solution X33 y with ||||| > (1 [1++2:0 2c) ||3 Is
easily confirmed that there exists с E (0, 1) such that the point = - (1-c) satisfies X3' =
y and || (1 + 2c) [| l12- By the convexity of Q, this implies ((3/a²) 2 Q(3' (181/a?))
Q(3i2/a /²)) Thus a 3 with a large & norm cannot be a solution, even 4a 4o Q(3/a²)) 7 113112
Since 8.
||
< +1+ 2e) |1 we conclude
4a 1a²Q(3a/a²)
(92)
1 2+c
4a 2a-2(Bi2/a
(93)
1 2+c
1 + 2+c
<
1|
(94)
1 2+c
(1 + é) 11
(95)
C PROOF OF THEOREM 3
Lemma 4. For the D-homogeneous model (8)
Vt XT S r(F)dr
2-D
S D(D 2)
Proof. For the order-D unbiased model ((t) = w ww the gradient flow dynamics are
dT.
(+((t)
DX r(t) w (-),t), w+(0) a1
(96)
dw+
(+( = DDD S r(r)dr
(97)
Where denotes elementwise multiplication, r(1) x3((1) y. and where all exponentiation is elementwise. Similarly,
dL DX r(() D th (1), w- = al
w (1) dw
(98)
1 D(D 2)X J r(T)dr)
(1) = 2-- -
(99)
First, we observe that V.44 w (t), 2 and V.V, (-))), 2 0. This is because at time 0, w. (0),
= (t))),
w (0), 0; the gradient flow dynamics are continuous; and (t),), and w (t),), 0 = w- (t()), 0.
Consequently.
0. = D 2) XT f r(7)dT
= a-
(100)
0 0 (1) 2-D - -DD-2) x (" r(T)dT)
(101)
2-D < D(D - 2) XT 1-- r(7)dr 2-D
2-2
(102)
which concludes the proof.
18

---

Under review as a conference paper at ICLR 2020
Theorem 3. For any and D 2 3, if gradient flow reaches solution ((a, y, then
(o,)( arg ming (g) S.L. =
where (3) Eig (D(33/a0) and QD = [ hpp the antiderivative of the unique inverse of
h=(2) (1 2) 0-2 (1 2) D-2 1.. Furthermore, C Bi and lima-sox ((0) = 872
Proof. For the order-I) unbiased model [(()) w wh, the gradient flow dynamics are
w(t) dL -DX r(() ow D-1 w(0) = al
dw
-D-2
w(t) = aa- +DD+DDD D(DD S r(())dT
B(t) a 11+aD2DD(D 2)xx S'd r(()dr)
D D-2 D-DDDDDD - 2)x L r(F)dtr)
where X = X - -x] and r(1) = x(((1) - Supposing (11) converges to a zero-error solution, x3((00)= = y3((0)) = aPhp(X (xT(o))(
where v(00) D-2 2) 00 r(T)dr and the function hp is applied elementwise and is defined
(n) (1 =) -.a =) D2
By Lemma 4
1xTT/11_ I 1, so the domain of hD is the interval [-1, 1]. upon which it is monoton- Therefore, there exists inverse mapping
ically increasing from h-(-1) -o to h (1)
ht)(t) with domain |-00, 2o| and range [-1,
This inverse mapping unfortunately does not have simple closed form. Nevertheless, the root of rational equation. Using the approach outlined in Appendix A 12
conclude:
0,( = =] B./0
(t)
Rich regime Next, show that if gradient flow reaches a solution XB,.p y. then lima-so (oo) = Pi for any D. This is implied by the work of Arora et al. (2019a). but include it here for an alternative, simpler proof for our special case, and for completeness" sake.
The KKT conditions for 3 = 3i are X, = y and Ev sign( = X v (where sign(0) = [-11, 1)- The first condition is satisfied by assumption. Define as above. We will demonstrate that the second condition holds too in the limit as a - 0.
First, by Lemma
| VIl S for all and D. Thus, for any coordinates i such that lim, D xc) ]j
O, the second KKT condition holds. Consider now i for which (o.. (co)) As shown above,
lim (Im,D(oO0))) a-70
lim a D (1- [xT2])) [))))= DI a a M))) (1+
(1+
0 (103)
a0
lim a - (1-[XTm [xTv]]] v))) a=
>0
(104)
This and [T < 1 implies lim,- -o [x v/s = 1, and thus the positive coordinates satisfy the second KKT condition. An identical argument be made for the negative coordinates.
19

---

Under review as a conference paper at ICLR 2020
0.25
04
19 - 14G.1
1966
0.3
0.15
02
0.1
0.05
10
10
10'
Figure 5: The plots demonstrate the regimes where gradient flow implicitly minimizes nuclear norm and l norm, respectively.
Finally, we show that if gradient flow reaches a solution X(,c,((oc) y. then lima-+oo ( = Bi2 for any D.
Kernel Regime
First, since X and y are finite, there exists solution 3* whose entries are all finite, and thus all the entries of (oo) which is the Q minimizing solution, will be finite.
The KKT conditions for 3 = Bī2 are X and 3u B = X μ. The first condition is satisfied by assumption. Defining / as above, we have
lim [o,)(
lim a (1 [X u/))) D a (0 (1+ (X ml:) am>
D²x x
(105)
a-000
lim a
[ -|:=0
(106)
D Consequently, defining μ D-2 v, and observing that for small 2,
2D D-2 + 0(:2)
(1- 2) 1-=2)=22 pr (1+2)
(107)
conclude
a (1 1xT vl:) 84 a
X vl))) +4
(a,D(
(1
lim a0000
lim a-3
(108)
X 141
[X T
D
2D [XT v/s + +0[[T Tv13)) 11-2
lim
(109)
a-+0
2D
D-2 [X u/:
1 lim O w/f)
(110)
a00
(111)
Thus, the KKT conditions are satisfied for lima- (oo) = -.72.
D MATRIX EXPERIMENTS
In the appendix, provide additional results similar to those in Section 6 First, in Figure 5 we plot the implicit regularization behavior of gradient flow limits with identity initialization in Figure a[) in "rich" regime (small a) recover the minimum nuclear norm solution N = arg min (M)=z) MM],, while "kernel" regime recovers the minimum Frobenius norm solution Mi = arg (i |M]]
E NEURAL NETWORK EXPERIMENTS
Synthetic Experiments We construct synthetic training set with N 10 points drawn uniformly from the unit circle 2 and labelled by a teacher model with hidden layer of units. We train fully connected ReLU networks with depths 2, 3, and 5 with 30 units per layer to minimize the square loss using full gradient descent with constant stepsize 0.01 until the training loss below 10-9 9 We use Uniform He initialization for the weights and then multiply them by a.
Here, we describe the details of the neural network implementations for the MNIST and CIFAR10 experiments.
20

---

Under review as a conference paper at ICLR 2020
70
0.75
a=
60
1.25
Test error [%6]
a 1.5
50
a 1.75
2.0
Last layer
40
30
20
0
250
500
750
1000
1250
1500 1750 2000
Epoch
Figure 6: Training curves for the CIFARIO experiments
MNIST
Since our theoretical results hold for the squared loss and gradient flow dynamics, here empirically assess whether different regimes be observed when training neural networks following standard practices.
We train fully-connected neural network with single hidden layer composed of 5000 units the MNIST dataset, where weights are initialized as aWo, Wo N 0. - 1in denoting the number of units the previous layer, as suggested by He et al. (2015). SGD with a batch size of 256 used minimize the cross-entropy loss over the 60000 training points, and error over the 10000 test samples are used as measure of generalization. For each value of a, we search over learning rates (0.5, 0.01, 0.05,...) and the which resulted in best generalization.
There is visible phase transition in Figure 4e terms of generalization (=/ 1.4% error for a S 2, and sz 2.4% error for 50), even though every network reached 100% training accuracy and less than 10 cross-entropy loss. The black line indicates the test error (2)7% when training only the output layer of the network, proxy for the performance of linear predictor with features given by fixed, randomly innitallii hidden layer.
CIFAR1O
We trained a VGGI architecture, which as follows: 64-M- 1-----2------56
512-512-M-512 1---5-2----------- (numbers represent the number of channels in convolution layers with no bias, is maxpooling layer, and FC a fully connected layer). Weights were initialized using Uniform He initialization multiplied by No data augmentation SGD with batch size 128 and learning rate 0.0001. All experiments ran for 2000 epochs, and reached 100% train accuracy except when training only the last layer, which reached 50.38% train accuracy with LR = 0.001 (chosen after hyperparameter tuning).
used, and training done using
In addition, approximate the test error in the kernel regime, we experimented with freezing the bottom layers and only training the output layer for both datasets (the solid lines in Figures 4e and 4f
Figure iillustrates some of the optimization difficulties that arise from using smaller a as discussed in Section 4
21


Reviews:
[{"review_id": "Hkgx4G7ZqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the two regimes in the training of overparameterized networks (with small learning rates):\n* kernel regime: the tangent kernel doesn't change much during training. The training behavior is then well approximated by a linear model (Taylor expansion at the initialization). This can happen when the weights are initialized to large values.\n* rich regime: The kernel regime is turned into a rich regime when the assumptions of kernel regimes aren't met.\n\nSpecifically, the paper emphasizes how the scale of initialization controls the transition between the two regimes, which was first pointed out by Chizat & Bach (2018).\n\nMy main concern is that it is unclear what unique contributions are made by the paper, as the theoretical results are not more general than that of Chizat & Bach (2018). The contributions are not clearly stated and I can only see the execution of ideas from Chizat & Bach (2018) and applying them to more concrete examples, which leads to analytical results (for linear networks) in Theorem 1/2. This feels rather incremental. \n\nSome other comments:\n* In experiments it was shown that popular initialization schemes are right on the edge of entering the kernel regime, which is very interesting. How does this change with network widths and different architectures?\n* It's difficult to see what Figure 2b tells because several notations are undefined. What are $e_1$ and $1_d$?\n", "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": "BklE7rOpKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes an inductive bias of the gradient flow for diagonal two-or higher-homogeneous models and characterizes a limit point depending on the initialization scale of parameters. Concretely, the paper shows that the gradient flow converges to an interpolator attaining minimum L1- (or L2-norm) when the scale is small (or large). In addition, these analyses are well verified empirically on MNIST and CIFAR-10 datasets.\n\nQuality:\nThe work is of good quality and is technically sound.\n\nClarity:\nThe paper is well organized and easy to read.\n\nSignificance:\nTo explain the generalization ability of powerful machine learning models that can perfectly learn a training dataset, the implicit bias of the optimization methods and models play key roles when explicit regularization is not adopted. For instance, deep neural networks fall into this scenario. I think this paper makes a better contribution in this line of researches. Although, homogeneous models treated in this study is restricted (essentially linear models) and a theory is limited to the continuous gradient flow, these settings are rather common in this context. In [Gunasekar+(2017)], the convergence to the minimum L1-norm solution was shown for a slightly different model when the scale goes to zero. However, in addition to this property, the paper analyzes arbitrary scales of parameters and shows the convergence to the minimum L2-norm solution when the scale goes to infinity for diagonal homogeneous models.\nIt would be nice if the authors could emphasize the technical difficulty compared to [Gunasekar+(2017)] to strengthen the contribution of the paper.\n\nA few questions:\n- Can this analysis be extended to the setting of early stopping? Toward a better explanation of the generalization performance of deep learning, understanding of the inductive bias of the early stopping before convergence is more important.   \n- A provided theory is limited to linear models essentially. Is it possible to extend a theory to non-linear models?\n\n-----\nUpdate:\nI thank the authors for the response. I am convinced of the difference from [Gunasekar+(2017)] and my review stands. I  would like to keep my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eHz4x6Yr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I really appreciated this paper. It discusses a very complex question (\"Are we learning in a kernel regime, or in a rich regime where features are identified\") by looking at perhaps the simplest model the authors could think of, and then study in detail the model. And how simple it turns out to be: just a linear regression with a twist. All in all, the paper is indeed is a clear demonstration that the differences between\"Kernel\" regime and one where some actual Learning is done can be demonstrated on simple examples. It is also the simplest model where one can observe  a non-trivial inductive bias and 'implicit regularisation'\n\nI do not have much to say on the paper, except that I fully support publication. \n\n\n\n", "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 did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies how the size of the initialization of neural network weights affects whether the resulting training puts the network in a "kernel regime" or a "rich regime". Using a two-layer model they show, theoretically and practically, the transition between kernel and rich regimes. Further experiments are provided for more complex settings.

The scores of the reviewers were widely spread, with a high score (8) from a low confidence reviewer with a very short review. While the authors responded to the reviewer comments, two of the reviewers (importantly including the one recommending reject) did not further engage.

Overall, the paper studies an important problem, and provides insight into how weight initialization size can affect the final network. Unfortunately, there are many strong submissions to ICLR this year, and the submission in its current state is not yet suitable for publication.
Decision: Reject