On the Dynamics and Convergence of Weight Normalization for Training Neural Networks
Authors: Yonatan Dukler
Quanquan Gu
Guido Montufar
Venue:  (2020)
Keywords: Normalization methods
Weight Normalization
Convergence Theory

Abstract: We present a proof of convergence for ReLU networks trained with weight normalization. In the analysis, we consider over-parameterized 2-layer ReLU networks initialized at random and trained with batch gradient descent and a fixed step size. The proof builds on recent theoretical works that bound the trajectory of parameters from their initialization and monitor the network predictions via the evolution of a ''neural tangent kernel'' (Jacot et al. 2018).  We discover that training with weight normalization decomposes such a kernel via the so called ''length-direction decoupling''.  This in turn leads to two convergence regimes and can rigorously explain the utility of WeightNorm. From the modified convergence we make a few curious observations including a natural form of ''lazy training'' where the direction of each weight vector remains stationary. 

Under review as a conference paper at ICLR 2020
ON THE DYNAMICS AND CONVERGENCE OF WEIGHT NORMALIZATION FOR TRAINING NEURAL NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
We present proof of convergence for ReLU networks trained with weight normal- ization. In the analysis, we consider over-parameterized 2-layer ReLU networks initialized at random and trained with batch gradient descent and a fixed step size. The proof builds on recent theoretical works that bound the trajectory of parameters from their initialization and monitor the network predictions via the evolution of "neural tangent kernel" (Jacot et 2018). We discover that training with weight normalization decomposes such kernel via the so called "length- denggt-direction decoupling". This in turn leads to two convergence regimes and can rigorously explain the utility of WeightNorm. From the modified convergence make few curious observations including a natural form of "lazy training" where the direction of each weight vector remains stationary.
INTRODUCTION
Dynamic normalization in neural networks is pe-armmetriizaioon procedure between the layers that improves stability during training and leads to faster convergence. This approach was popularized with the introduction of Batch Normalization (BatchNorm) in (0) and has led to a plethora of additional normalization methods, notably including Layer Normalization (LayerNorm) [6] and
Weight Normalization (WeightNorm) 288. WeightNorm was proposed as method that emulates BatchNorm and benefits from similar stability and convergence properties, Moreover, WeightNorm has the advantage of not requiring a batch setting, therefore considerably reducing the computational overhead that is imposed by BatchNorm [16]. WeightNorm is widely used in training of neural
networks and the focus of this work.
Today, normalization methods are ubiquitous in the training of neural nets since in practice they significantly improve the convergence speed and stability in training. Despite the impressive empirical results and massive popularity of dynamic normalization methods, explaining their utility and proving that they converge when training with non-smooth, non-convex loss functions has remained an unsolved problem. In this paper provide sufficient conditions on the data, initialization, and over-pane prraattrettiiiiooonnn for dynamically normalized ReLU networks to converge to a global minimum of the loss function, and rigorously illustrate the utility of normalization methods.
Consider the class of 2-layer ReLU neural networks f TRd IR parameterized by (W.c) c) E R.xd I
f(x: w. Vm
(wo
(1.1)
Here the activation function the ReLU, (s) max(s, 0} 26 m denotes the width of the second layer, and f is normalized accordingly by factor vm. We investigate gradient descent training with WeightNorm for I.Ip, which re-parameterizes the network in terms of (V,g, c) E mR Rm x Rm
as
V(x:V
CaO
Jk
|
V
X
(1.2)
This gives a similar parameterization to 14 that study convergence of gradient optimization of convolutional filters on Gaussian data. We consider the regression task, optimizing with respect the

---

Under review as a conference paper at ICLR 2020
L loss with random parameter initialization and focus the over-parametrized regime, meaning that m > n, where n is the number of training samples.
The neural network function class (1.1) has been studied in many papers including 15 33 36
along with other similar parrpaaameterize architectures 04 23], An exuberant series of recent works prove that ferd-forward ReLU networks converge to zero training error when trained with gradient descent from random initialization. Nonetheless, to the best our knowledge, there are no proofs that ReLU networks trained with dynamic normalization on general data converge global minimum. This is in part because normalization methods completely change the optimization landscape during training. Here we show that neural networks of the form given above converge at linear rate when trained with gradient descent and WeightNorm. The analysis is based on the werrpparameteriaation of the networks, which allows for guaranteed descent while the gradient non-zero.
For regression training, a group of papers studied the trajectory of the networks' predictions and showed that they evolve via a "neural tangent kernel" (NTK) as introduced by Jacot et al. [21]. The latter paper studies neural network convergence in the continuous limit of infinite width over- parameterization, while the works of 3 [5] 27
33 33) analyze the finite width setting. For finite- width over- porraaaeeterized networks, the training evolution also exhibits kernel that takes the form of Gram matrix. In these works, the convergence rate is dictated by the least eigenvalue of the kernel. We build on this fact, and also on the general ideas of the proof of 15 and the refined work of 3
Compared with un-normalized training, we prove that normalized networks follow modified kernel evolution that features a "length-direction" decomposition of the NTK. This leads to two convergence regimes in WeightNorm training and explains the utility of WeightNorm from the perspective of the NTK. In the settings considered, WeightNorm significantly reduces the amount of over-paramee wverpprraetterization needed for provable convergence, as compared with normaaalleeed settings. The decomposition of the NTK also connects to observations of [12] that discuss "lazy training" which refers to training regime where the weights of the network stay close their initialization (see Section G. Further, we present more careful analysis that leads to improved over parameterization bounds as compared with [15].
In this work we rigorously analyze the dynamics of weight normalization training and its convergence from the perspective the neural tangent kernel. We discover WeightNorm training has two regimes with distinct behaviors. The main contributions of this work are:
We prove the first general convergence result for dynamically normalized 2-layer ReLU networks trained with gradient descent. Our formulation does not assume the existence of a teacher network and has mild assumptions on the training data.
We explain the utility of normalization methods via decomposition of the neural tangent kernel. In the analysis we highlight two distinct convergence regimes and give a concrete example of "lazy training" for finite-step gradient descent.
It is shown that finite-step gradient descent converges for all weight magnitudes at initialization and we significantly reduce the amount of over pee-pearaetttiizaionn required for provable convergence as compared with un normalized training.
The paper is organized as follows. In Section we provide background on WeightNorm and derive key evolution dynamics of training in Section We present and discuss our main results, alongside with the idea of the proof, in Section We discuss related work in Section 3 and offer discussion of our results and their implications dynamic normalization training and "lazy training" in Section Proofs are presented in the Appendix.
2
NORGHTNORM
Here we give an overview of the WeightNorm procedure and review some known properties of normalization methods.
Notation We use lowercase, lowercase boldface, and uppercase boldface letters to denote scalars, vectors and matrices resp. We denote the Rademacher distribution as Uf1, -1] and write N (H, Σ) for a Gaussian with mean ii and covariance Σ. Training points are denoted by x X....X, X, E IR and parameters of the first layer by Va E Rdd. We use (xx max(æ, 0). and write ||2,, || for
2

---

Under review as a conference paper at ICLR 2020
the spectral and Frobenius norms for matrices. Amin (A) is used to denote the minimum eigenvalue of a matrix and (. denotes the Euclidean inner product. For a vector v denote the &g vector
norm as ||v|2 and for positive definite matrix S define the induced vector norm ||v|s == vv Sv. x(I
The projections of x onto and u are defined as x
_u x"
uull ). Denote the
|ulli
indicator function of event A as A and for weight vector at time I, vx((), and data point x; we denote a (1) (vx(t) xx2 0)
WeightNorm procedure For single neuron o(w' x)), WeightNorm re-parametrizes the weight W E IRd in terms of v E I3 y E Il as
V 1vll2* (
v ||v12
w(v.g)
(2.1)
This decouples the magnitude and direction of each weight vector (referred as the "length-direction" decomposition). In comparison, for BatchNorm each output x is normalized according to the average statistics in batch. We can draw the following analogy between WeightNorm and BatchNorm if the inputs x, are centered (Exx 0) and the covariance matrix is known (Exx' = S). In this case, batch training with BatchNorm amounts to
(1
= =
x
W
X
W
X
(2.2)
Ex ( xx ww)
W
Sw
From this prospective, WeightNorm special case of (.. with S
22
28
Properties of WeightNorm We start by giving an overview of known properties of WeightNorm that will be used to derive the gradient flow dynamics of WeightNorm training.
For re-parameterizattion (2.1) of network function that is initially parameterized with weight w. the gradient w relates to the gradients V. Vgf by the identities
V.ʃ
|v|22 V V)
vzf= (Vw).
This implies that V. v = 0 for each input x and parameter v. For gradient flow, this orthogonality results in (0)]2 [t)l for all For gradient descent (with step size 7)) the discretization in conjunction with orthogonality leads increasing parameter magnitudes during training 19 28
as illustrated in Figure I
[[v + 1)ll2 = (1) 1 (s)
(2.3)
va(s)
V
(va(0)
(2
V2
Figure 1: WeightNorm updates for gradient flow and gradient descent. For gradient flow, the norm of the weights are preserved, i.e., ||v (0)]l2 (t)]l for all t > 0. For gradient descent, the norm of the weights (s)]l is increasing with s.
Problem Setup We analyze
with WeightNorm training 1.2
so that
4 x
f(x: V,
CAO gb
Vv

---

Under review as a conference paper at ICLR 2020
We take an initialization in the spirit of [77
vx ~ N(0,a21)) Ck U(11,1) and (x( = (1vx(0)ll//a
(2.4)
Where a is the variance of Vi. at initialization. The initialization of gle (0) is therefore taken to be independent of a. We remark that the initialization (2.4) gives the same initial output distribution as in methods that study the un-normalized network class (I.I.. The parameters of the network are optimized using the training data {(x1, MI), ..... (Xn: vn)) with respect to the square loss
Σ (f(x)) - -1)) 2 =11 --ylé. L(f) = 2
(2.5)
where f = (f2,2,....,
and y (3/1, 3/2 ..
EVOLUTION DYNAMICS
We present the gradient flow dynamics of training (2.5 to illuminate the modified dynamics of WeightNorm as compared with vanilla gradient descent. In Appendix we tackle gradient descent training with WeightNorm where the predictions' cvolution vector at is replaced by the finite difference f(s + 1) f(s). For gradient flow, each parameter is updated in the negative direction of the partial derivative of the loss with respect that parameter. The optimization dynamics give
dv di
ÖL
dgk ÖL
(3.1)
OV
di
0gk
We consider the where fix the top layer parameters C during training. In the parameterized regime, the dynamics of c and 9l turn out to be the same.
To quantify convergence, we monitor the time derivative of the i-th prediction, which computed via the chain rule as
af:
-
m Of dvk
+ Of: dg3
0t
Ovv dt
0gn. di
Substituting 3.1 into the i-th prediction evolution and grouping terms yields
af:
Of: OL
0f: OL Oyn 0g
(3.2)
01
OV OVR
TB
The gradients of fü and L with respect to Vk are written explicitly as
0h (t)
6 gx(().
v=(0 La)())
OL OV
(t) = vm Σ (Ji(t) - vi)
C (g)(1) vx(t)*
x
st).
Ov
/m [t)l)l2
[vx(t)]l
Thus (t) in 3.2 can be calculated as
T((1) = 200 - 1Ú) - m
Ch =m((0) 2 [
(xyaco) xx(())
, (1)
m
1=1
Defining the v-orthogonal Gram matrix V(t) as
m
aCH gx())
2 )
(x) x x; xxx00+ (a()),,
Vty(t)
(3.3)
|[v((t]l2
m
we can write TV as
T+( Σ V.r(t (f)(t) vz).
Note that (tt) is the induced neural tangent kernel 21
for the parameters v of WeightNorm training.
While it resembles the Gram matrix H(t) studied in here obtain matrix that is not piece-wise
4

---

Under review as a conference paper at ICLR 2020
constant in since the data points projected onto the orthogonal component of We compute Tg in (32 analogously. The associated derivatives with respect to Ih are
0f (t)
Ck
o (va x.),
aL Oyk
(t)
Σ (b(t)) ==1
1o) [ve(1)l2
Ck
(Vx xz),
Vm [vx(1)]22
and obtain
(g
(1,(1) ws) (IvA())
Ch
o(vx(1) =(va(()"x))ovv((() xv)o(vv((1)xx, x:).
j=1
Given that ch = 1, define Gtt) as
(tv (v) xx,
Giy(t)
(3.4)
m
[t)
hence we can write
Tg()) Σ
G,)00,())))
j=1
Combining Tv and Tg. the full evolution dynamics are given by
df (t) a + G(t) (f(t) y).
(3.5)
di
Denote (C) V() 33.). 3.4 are independent of at (((((((()) y). We note that V(0), G(0), defined
+ G(() and write dr
Observation 1 (a independence). For initialization 2.4 and a > the Gram matrices V(),, G(()) are independent of
This fact is proved in Appendix A When training the neural network in (I.I
without WeightNorm
(see 3 15 (6)). the corresponding neural tangent kernel H(t)) defined by dr kk=1
0y:
-E= 0f: dws 8w de
0f: at
Σド= H))())( - yj) and takes the form
k=1 8w4 Owg
H H2(
Σ k=1
(3.6)
The analysis presented above shows that vanilla and WeightNorm gradient descent are related as follows.
Proposition 1. Define V(0). G(0), and H(O) in and 3.6 respectively. then for all
>> 0,
V(0)+ + H())
Thus, for L,
0f -A())(((())))) - y) = -H(O)(((0)- -). 01
That is. WeightNorm decomposes the NTK in each layer into length and direction component. We refer to this as the "length-direction decoupling" of the NTK, in analogy to (2.1) 1). From the proposition, normalized and un-normalized training kernels initially coincide if a = 1. The utility of normalization methods can be attributed to the modified NTK A()) that occurs when the WeightNorm coefficient, a, deviates from 1. For >> the kernel A(t) is dominated by G(t), and for < 1 the kernel A(t) is dominated by (tt). We elaborate onthe details of this the next section. In practice, by (2.3) training progresses, l|valla grow monotonically, leading larger and transition from the V dodinnate to the G G-dominated regime. our analysis we will study the two regimes a > 1 and < 1 in turn.
5

---

Under review as a conference paper at ICLR 2020
4 MAIN CONVERGENCE THEORY
In this section we discuss our convergence theory and main results. From the continuous flow (3.5). observe that the convergence behavior is described by (t) and G(t). The matrices ((t) and Gtt) are positive semi-definite since they can be shown to be covariance matrices. This implies that the least eigenvalue of the evolution matrix A(t) + V(t) G(t) is bounded below by the least eigenvalue of each kernel matrix,
Amin (A()) 2 max (amin (V(1)/a² Amin (G
For finite-step gradient descent, a discrete analog evolution (3.5) holds. However, the discrete case requires additional care in ensuring dominance of the driving gradient terms. For gradient flow, it is relatively casy to see linear convergence is attained by relating the rate of change of the loss to the magnitude of the loss. Suppose that for all 2 0,
Ain (A) 2 w/2. with w > O.
(4.1)
Then the change in the regression loss is written as
d d [F(()) - - - y) df(() - - ((((((()) y)
di
f(()) - y1.
Integrating this time derivative and using the initial conditions yields
[f(t) - y112 < exp( wt [(0) - -y1l..
which gives linear convergence. The focus of our proof is therefore showing that (4. throughout training.
holds
By Observation we have that V and G are independent of the WeightNNrrm coefficient a (a only appears in the 1/a" scaling of A). This suggests that the kernel A() / V(() G(l) can be split into two regimes: When < 1 the kernel is dominated by the first term + V. and when >> 1 the kernel dominated by the second term G. We divide our convergence result based on these two regimes.
In each regime, 4.. holds the corresponding dominant kernel, V(t) or G(t), maintains a positive least eigenvalue. Having least eigenvalue that is bounded from 0 gives convex-like property that allows us to prove convergence. To ensure that condition (4. is satisfied, for each regime we show that the corresponding dominant kernel is "anchored" (remains close) an auxiliary Gram matrix which we define in the following for V and G.
Define the auxiliary v-orthogonal and v-aligned Gram matrices y G as
V = Ev-N(0,aa)) (x) xy 11 (0)1
(4.2)
G = Evw.N(,.aa) (x) x)) L (0)
(4.3)
For now, assume that * and . are positive definite with least eigenvalue bounded below by w (we give a proof sketch below). In the convergence proof we will utilize ver-parameterizattoo to ensure that (t), Gt)) concentrate to their auxiliary versions so that they are also positive definite with least eigenvalue that is greater than w/2. The precise formulations are presented Lemmas B.4 and B.5 that are relegated to Appendix B
To prove our convergence results we make the assumption that the x,s have bounded norm and are not parallel.
Assumption 1 (Normalized non-parallel data). The data points (1),1),.... (Xn: Un) satisfy (0).
|xx||2 and for each index pair i + j. x, + B.x, for all
In order to simplify the presentation of results, assume that the input dimension d is small, whereby d 2 50 suffices. This is not essential for the proof. Specific details are provided in Appendix[A]
Assumption 2. For data points x, E & assume that d 50.

---

Under review as a conference paper at ICLR 2020
Both assumptions can be easily satisfied by pre-procce pre-ppocessing, e.g., normalizing and shifting the data, and adding zero coordinates needed.
Given Assumption ! V G are shown to be positive definite.
Lemma 4.1. Fix training data points (x1,y1)..... y1)..... (Xn, Bn)} satisfying Assumption
7 Then the
v-orthogonal and v-aligned Gram matrices V and Go defined in (4.2) and (..3) are strictly
positive definite. We denote the least eigenvalues Xmin| ( (Vo)) =: Ao. Amiu
Po-
Proof sketch Here we sketch the proof of Lemma 4.1 The main idea, the same as 15 is to regard the auxiliary matrices V G the covariance matrices of linearly independent operators. For each data point x,, define &b = X 1l (2T3- The Gram matrix Vo is the covariance matrix of {or taken over Rd with the measure N(0, I²).. Hence showing that V is strictly positive definite is equivalent to showing that { are linearly independent. Unlike [[3], the functionals under consideration are not piecewise constant so different construction is used to prove independence. Analogously, a new set of operators, 0z(v) == (x)),, is constructed for
G Interestingly, each Φ; corresponds to dd, dv The full proof is presented in Appendix D As
already observed from evolution (3.5), different magnitudes of lead two distinct regimes that discussed below. We present the main results for each regime.
V-DOMINATED CONVERGENCE
For a < convergence dominated by (tt) and Amin (A(t)) 2 convergence theorem for the V-dominated regime here.
a² Amin (V(t)). We present the
Theorem 4.1 (V-dominated convergence), Suppose neural network of the form (12) is initialized as in 2.4) with a S 1 and that Assumptions ho In addition. suppose the neural network trained via the regression loss 2.5) with targets y sutisfying ||yl| = O(1). If m = (n2² log(n/8) X²).
then with probubility
For iterations s = 0, 1.... K, the evolution matrix A (s) satisfies Amin (Ann(A(s)) (A(s)) 2
Ag 20
2. WeightNorm training with gradient descent of step-size -0(V-Vi)) as
a²
converges linearly
[[((s) - y1 (1
17o 2a
|IP(0) - y112.
The proof of Theorem 4.1 is presented in Appendix C We will provide sketch below. We make the following observations about our V-dominated convergence result.
The required over-paramettrization is independent of a. Further, the dependence of m on the failure probability is log(1 This improves previous results that require polynomial dependence of order 83, Additionally, reduce the dependence the sample size from n. (as appears in (3) to n log(n).
In Theorem smaller leads to faster convergence, since the convergence is dictated by Ao/a².
Nonetheless, smaller a is also at the cost of smaller allowed step-sizes, since = =(a²² 2 V
(|z).
The orf between step-size and convergence speed is typical. For example, this is implied in
Chizat et al. [12), where nonetheless the authors point out that for gradient flow training, the increased
convergence rate not balanced by a limitation on the step-size. The works 4 19 32 define an effective sep-size (adaptive step-size) r/ = n7aa² 2 to avoid the dependence of 17 on a.
G-DOMINATED CONVERGENCE.
For > 1 our convergence result for the class 1.2 is based monitoring the least eigenvalue of G()). Unlike V-dominated convergence, a does not affect the convergence speed in this regime.
Theorem 4.2 (G-dominated convergence). Suppose a network of the form (1.2p is initialized as in (2.4) with a 2 1 and that Assumptions Z hold. In addition, suppose the neural network trained via the regression loss (25)) with targets y satisfying || = O(1). If m ② max {nd log(n/5)/er /))(' o ptg n² log(n/0)/ ()) then with probability 1 5,
1. For iterations =0, ...., K, the evolution matrix A(s) satisfies Amin (A(s)) > 20

---

Under review as a conference paper at ICLR 2020
2. WeightNorm training with gradient descent of step-size 17 = O [[((e]]]
converges linearly
[[((s) - y112 Toll |10(0) -y1
We make the following observations about our G-dominated convergence result, and provide a proof sketch further below.
Theorem 4.2 holds for a 2 so long as m = 22 max {n log(n/8)/16e) n² log(n/0)//88) Taking a /n/Po gives optimal required over-parameterization of order
m lognnoogn//0)
This significantly improves on previous results 15 for un-normalized training that have dependencies of order 4 in the least eigenvalue, cubic dependence in 1/8, and n² dependence in the number of samples n. In contrast to V-dominated convergence, here the rate of convergence (oo is independent of a but the avee-parameterization is a-dependent. We elaborate this curious behavior in the next sections.
Proof sketch of main results The proof of Theorems 4.1 and 4.2 is inspired by a series of works
including B 15 33 36). The proof has the following steps: (I) We show that at initialization V(0), G()) can be viewed as empirical estimates of averaged data-dependent kernels V00 G that strietly positive definite under Assumption
(II) For each regime, we prove that the corresponding kernel remains positive definite if (t) and gx.(t) remain near initialization for each 1 < m. (III) Given a uniformly positive definite evolution matrix A()) and sufficient over- parameterization we show that each neuron, V& (4), 9% (4) remains close to its initialization. The full proof is presented in Appendix B for gradient flow and Appendix for finite-step gradient descent.
While the spirit of the proof is familiar from other works, the different convergence regimes explain the utility of WeightNorm. We elaborate further on this in the discussion.
5 RELATED WORK
Dynamic normalization theory A number of recent works attempt to explain the dynamics and utility of dynamic normalization methods. The original works (20) 28 of BatchNorm and Weight- Norm resp. suggest that dynamic normalization methods improve training by fixing the intermediate layers' output distributions. The works of Bjorck BatchNorm may improve optimization by improving smoothness of the Hessian of the loss, therefore allowing for larger step-sizes with reduced instability. Hoffer et al. [8] showed that the effective step-size in BatchNorm is divided by the magnitude of the weights, this followed the work of WNgrad [32] that introduces an adaptive step-size algorithm based on this fact. Following the intuition of WNGrad, Arora et al. [ proved that for smooth loss and network functions, the diminishing "effective step-size" of normalization methods lead to convergence with optimal convergence rate for properly initialized step-sizes. The work of [22] explains the accelerated convergence of BatchNorm from a Sength--dircttion decoupling" perspective. The authors along with [9] analyze the linear least squares regime, with [22] presenting bisection method for finding the optimal weights. Robustness and regularization of Batch Normalization is investigated in 25 and improved generalization is analyzed empirically. Shortly after the original work of WeightNorm, [35] showed that for a single precptron WeightNorm may speed-up training and emphasized the importance of the norm of the initial weights. Additional stability properties were studied by 34 via mean-fiee -ield analysis. The authors show that gradient instability is inevitable even with BatchNorm the number of layers increases; this is in agreement with [7] for networks with residual connections. The work of [5] suggests initialization strategies for WeightNorm and derives lower bounds on the width to guarantee same order gradients across the layers.
[8] and Santurkar et al. (29 argue that
pver-parametrized neural networks There has been a significant recent literature studying the convergence of un-normalized over-parametrized neural networks. The analysis of the majority of the works relies on the width of the layers. These include 2-layer networks trained with Gaussian inputs and outputs from teacher network [30], (24] and [14] (with WeightNorm). Assumptions on the data distribution are relaxed [5] and the works that followed 3 33 36). Our work is inspired by the
mechanism presented in this chain of works. Wu et
33 extend convergence results adaptive
8

---

Under review as a conference paper at ICLR 2020
step-size methods and propose AdaLoss. Recently, the global convergence of over ver-parameterized neural networks was also extended to deep architectures [ 37 38]. In the aver-parameterized regimes, Arora al. B develop generalization properties for the networks of the form (I.I). In addition, in the context of generalization, Allen-Zhu et al. [ illustrates good generalization for deep neural networks trained with gradient descent. Cao and Gu [10] and [1] derive generalization error bound of gradient descent and stochastic gradient descent for learning over pyer-paramtttiizationn deep ReLU neural networks.
DISCUSSION
In this section we interpret our main results and make a connection of the convergence theory with "lazy training".
Chizat et 12 analyze recent works of werrpparameterized convergence based on the NTK and note that re-scaling the network's ' outputs during gradient flow training leads to fast convergence while at the same time the weights remain close to their initialization. This is interpreted as a "linear solution", meaning that the direction of the weights does not change at training. The authors also refer to this type of convergence as "lazy training".
In our G-dominated convergence, observe new type of "lazy training" that is different from the one presented in [1]] We refer to our G regime as "lazy training" since the directions of the weights remain fairly stationary. Nonetheless, in G-dominated "lazy training", the magnitudes of the weights (gk) change. Moreover, we observe this phenomenon not only in the continuous flow setting but also in the finite step gradient descent setting. Unlike [12] where it is argued that neural networks do not necessarily follow the "lazy training" regime, we believe that G-dominated convergence actually is common but that it emerges at later stages in training, after the weights have adopted their directions in the V-dominated regime and improves stability.
Overall training with WeightNorr leads a gradual transition from V-dominated to the G-dominated regimes. We recall that since the weights grow (see (2.3)). the WeightNorm coefficient a increases during training progressively. The direction of the weights changes rapidly at the earlier stages of training when is small, and G-dominated convergence ensues as grows, leading to improved stability. For a > 1 this allows us to ease the requirements made on the over-parameterization (less is sufficient) and step size (a bigger step size is possible, of order 1 = O (2)) From this perspective, the utility of WeightNorm is attributed to the allowed larger step-sizes and increased stability at the later stages of training (G-dominated), all while maintaining fast convergence the beginning of training (V-dominaedd convergence).
Dynamic normalization is the most common optimization set-up of current deep learning models, yet understanding the convergence of such optimization methods is still an open problem. In this work we present a proof giving sufficient conditions for convergence of dynamically normalized 2-layer ReLU networks trained with gradient descent. To the best of our knowledge this is the first proof showcasing convergence of gradient descent training of neural networks with dynamic normalization and general data, where the objective function is non-smooth and non-convex. The notion of decoupling" clarified by the neural tangent kernel (I) that naturally separates in our analysis into "length", G(!), and "direction"", V())/a2, components. For = 1 the decomposition initially matches normmalaleed training. Yet we discover that in general, normalized training with gradient descent leads to 2 regimes dominated by different pieces of the neural tangent kernel. We note that training typically commences in the V-dominated regime and transitions into the G-dominated regime training proceeds and the magnitude of the weights grow. Our improved analysis is able to reduce the amount of over-parane parameterization that was needed in previous convergence works in the un-normalized setting and in the G-dominated regime, we prove convergence with significantly lower amount of over-parameterization as compared with un-normalized training.
REFERENCES
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In NeurlPS, 2019.
[2] Zeyuan Alle Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parametreeteiz.iioonn In International Conference on Machine Learning, pages 242-252, 2019.

---

Under review as a conference paper at ICLR 2020
[3] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized wo-layer neural networks. In International Conference Machine Learning, pages 322 332, 2019.
[4] Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. In International Conference on Learning Representations, 2019. URL
https::/<ppenree ew net. htt.//ormmmmmmmm
[5] Devansh Arpit and Yoshua Bengio. The benefits of over-paramettrizzaion at initialization in deep ReLU networks, In NewrIPS, 2019.
[6] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. Deep Learning Symposium, N116-2016, 2016.
[7] David Balduzzi, Mareus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? Proceedings of the 34th International Conference on Machine Learning-Voir Meeling- 70, pages 342-350. JMLR. org, 2017.
Volume
[8] Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normalization. In Advances Neural Information Processing Systems, pages 7694-7705, 2018.
[9] Yonggiang Cai, Qianxiao Li, and Zuowei Shen. A quantitative analysis of the effect of batch normalization on gradient descent. In International Conference on Machine Learning, pages 882-890, 2019.
[10] Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXi::/90..0/384, 2019.
[11] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurlPS, 2019.
[12] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In NeurIPS, 2019.
[13] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. 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 1675-1685, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
[14] Simon S. Du, Jason D. Lee, and Yuandong Tian. When is a convolutional filter easy to learn? In International Conference on Learning Representations, 2018. URL httl:/ts////peereiiieee
net het/forum?idde SkA 1EC6W
[15] Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes peer-parameterized neural networks. In International Conference Learning Representations, 2019. /ttp
[16] Igor Gitman and Boris Ginsburg. Comparison of batch normalization and weight normalization algorithms for the large-scale image classification. arXiv preprint arXiv: 1709. 0019908845.. 2017.
[17] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256 2010.
[18] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap large batch training of neural networks. In Advances in Neural Information Processing Systems, pages 1731-1741, 2017.
[19] Elad Hoffer, Ron Banner, Itay Golan, and Daniel Soudry. Norm matters: efficient and accurate normalization schemes in deep networks. In Advances in Neural Information Processing Systems, pages 2164-2174, 2018
[20] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 448 148-456,72 2015.
[21] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
10

---

Under review as a conference paper at ICLR 2020
[22] Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length-direction decoupling in non-convex optimization. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 106-815. PMLR, 16-18 Apr 2019.
[23] Yuanzhi Li and Yingyu Liang, Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pages 8168 8177, 2018.
[24] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pages 597-607, 2017.
[25] Ping Luo, Xinjiang Wang, Wenqi Shao, and Zhanglin Peng. Understanding regularization in batch normalization. arXiv preprint arXiv: /00t://800.000 009,00846, 2018.
[26] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted Boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-IO), pages 807-814, 2010.
[27] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizzaton:: global convergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.00664, 2019.
[28] Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelcrate training of deep neural networks. In Advances in Neural Information Processing Systems, pages 901-909, 2016.
[29] Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normalization help optimization? In Advances in Neural Information Processing Systems, pages 2483-2493, 2018.
[30] Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 3404-3413. JMLR. org, 2017.
[31] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
[32] Xiaoxia Wu, Rachel Ward, and Léon Bottou. Wngrad: Learn the learning rate in gradient
descent. arXiv preprint arXiv: 303.02865. 2018.
[33] Xiaoxia Wu, Simon Du, and Rachel Ward. Global convergence of adaptive gradient methods for over- parameterized neural network. arXiv preprint 1rXiv:1902.07111.
[34] Greg Yang. Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel S. Schoen- holz. mean field theory of batch normalization. In International Conference on Learning Representations, 2019. URI. htt.tttts:::::peeeeeeee
net f 1dd=SyDDMCCCFFF
[35] Yuki Yoshida, Ryo Karakida. Masato Okada, and Shun-ichi Amari Statistical mechanical analysis of online learning with weight normalization single layer perceptron. Journal of the Physical Society of Japan, 8644)2044002, 2017.
[36] Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent for over-parameterized neural networks. In NeurIPS, 2019.
[37] Difan Zou and Quanquan Gu. An improved analysis of training peeeparameterieed deep neural networks. In NeurlPS, 2019.
[38] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterrzeed deep relu networks. Machine Learning, 2019.
11

---

Under review as a conference paper at ICLR 2020
APPENDIX
We present the detailed proofs of the main results of the paper below. 'hee appendix organized follows. We provide proofs the simple propositions regarding the NTK presented in the paper in Appendix A and prove the main results for V-dominated and G-dominated convergence in the settings of gradient flow and gradient descent in Appendices C The proofs for gradient flow and gradient descent share the same main idea, yet the proof for gradient descent has considerate number we prove the lemmas used in the analysis of
of additional technicalities. In Appendices D and Appendices B and respectivel..
A WEIGHTNORM DYNAMICS PROOFS
In this section we provide proofs for Proposition T which describes the relation between vanilla and WeightNorm NTKs and Observation T of the paper.
Proof of Proposition] 1
We would like to show that V(0) + G()) = H()). For each entry, consider
(V(0) + G(O)gy = m
(0)* , xy 1x
1
xx v4(
x, (u))))
m
Note that
(x,, x₃) = (xx v1()
+ x,
(0)
xj
vu(
+ + x xe(
)= vo(())
(xxx100) x,y (x(0)= + (x, (x/1(0) xj vn(0)).
(xx
This gives
(V(0) + G(0)),
Xi x; (0) (0,
m
which proves the claim.
Proof of Observation T We show that the initialization of the network is independent of a. Take a, B 0, and for each k. initialize vh, v
v0 a00, v0 N1)
Then
(0) ( Unif( (in distribution).
( (0)l2
Hence the distribution of each neuron of ve(0) ) initialization is independent of a. Next for gh (0), we note that
(0))l)
[v((
3 1 (0)
Initializing of (0), oh (0) as in (.4).
(0)22
[v)
ge (0)
(0
a
gives
of (0). (0) Xd. and Lf ( (0)
oh (0)[
~O.
~ (..
(0)l
(0)
for all a, 3. This shows that the network initialization is independent of a and is equivalent to the initialization of the un-normalized setting. Similarly, inspecting the terms in the summands of V (0), G(O) shows that they are also independent of a. For
V L (0)
1 (0)
ack (0) (0)
(x) vx(0)=
x, yx(0)=))
12

---

Under review as a conference paper at ICLR 2020
(0)+
the terms ax (0), x; (0)) defined as
are independent of scale, and the fraction in the summand is identically 1.
(1) 1 (0)
x) x).(0)
1=1
is also invariant of scale since the projection onto vector direction vx) is independent of scale.
B CONVERGENCE PROOF FOR GRADIENT F1.WW
In this section we derive the convergence results for gradient flow.
The main results are analogous to Theorems gradient descent the proof' are simplified. In Appendix C (Theorem 4.1 4.2 for finite step gradient descent.
by considering gradient flow instead of we prove the main results from Section 4
We state our convergence results for gradient flow.
Theorem B.1 (V dV-omminteed convergence). Suppose network from the class 1.2 is initialized as in
(.4) with a and that assumptions) hold In addition, suppose the neural network is trained the regression loss (2.3) with target satisfying lo O()). Then WeightNorm training with gradient flow converges at a linear rate, with probability 1 6, as
(r (oggn/))/// Xa).
[f(()) 112 exp(->ot/a2)11FO) 1
This theorem is analogous to Theorem but since here, the settings are of gradient flow there is no mention of the step-size. It is worth noting that smaller a leads to faster convergence and appears to not affect the other hypotheses of the flow theorem. This "un- "un-interuptted" fast convergence behavior does not extend to finite-step gradient descent where the increased convergence rate is balanced by decreasing the allowed step-size.
The second main result for gradient flow for G-dominated convergence.
Theorem B.2 (G-dominated convergence). Suppose a network from the class 1.2 is initialized as in 2.4 with > 1 and that assumptions 7 hold. In addition, suppose the neural net- work trained on the regression loss (2.5) with target y satisfying |lyl = O(1). Then if m = ( max {na log(n/8)/ / "b: n² log(n/d)/pr)) WeighNNorm training with gradient flow con-
verges al lineur rate, with probability - as
[[((t) y1 < exp((Poo)][((0 - -yl13
B. PROOF SKETCH
To prove the results above follow the steps introduced in the proof sketch of Section idea of the proofs for V and G dominated convergence are analogous and lot of the proofs are based of Du et al. [15. We show that in each regime, attain linear convergence by proving that the least eigenvalue of the evolution matrix A(L) is strictly positive. For the V-dominated regime we lower bound the least eigenvalue of (1) as Amin (A()) > Amia mmi(((()) (V()))/a² and in the G-dominated regime we lower bound the least eigenvalue as Amin (A(t)) 2 Amin (t))..
+ The main
)m)))G(t)..
The main part of the proof is showing that Amin (t))), Amin (G)))) stay uniformly positive. We use several lemmas to show this claim.
In each regime, we first show that initialization the kernel under consideration, V(0) G(0). has positive least eigenvalue. This is shown via concentration to an an auxiliary kernel (Lemmas B. B.2). and showing that the auxiliary kernel is also strictly positive definite (Lemma
Lemma B.1. Let (O) and to be defined in (3.3 and (.2 assume the network width m
satisfies m 22(" 1 log(n/8)). Then with probability
6,
X3
A
[V((0) - k
13

---

Under review as a conference paper at ICLR 2020
Lemma B.2. Let G(0) and G be defined as in
3.4 and 4.3 assume satisfies
( 12 log(n/6)) ). Then with probability - 6,
H6
|| GG G Ho
After showing that V(0), G(0) have positive least-eigenvalue we show that V(), G()) maintain this positive least eigenvalue during training. This part of the proof depends on the over-parameeerizaaion of the networks. The main idea is showing that if the individual parameters (+) 9u (4) do not
change too much during training, then Vtt,, G(t) remain close enough to V(0), G(0) so that they
still uniformly strictly positive definite. We prove the results for V ((t and Gtt) separately since each regime imposes different restrictions on the trajectory of the parameters.
B.3 make assumptions the parameters of the network not changing "too much later we show that this holds and is the result of over-parameterization Specifically, over- reee-parameterizaiion ensures that the parameters stay at small maximum distance from their initialization.
For now, in Lemmas B.3
B44
V-dominated convergence To prove the least eigenvalue condition on V(t), we introduce the surrogate Gram matrix (1) defined entry-wise as
m
(1)(1)
vult)
(1)
(B.1)
m
This definition aligns with V(t) if we replace the scaling term (oc 2 Viz(1) by 1.
[f]]l in each term in the sum
To monitor V(t) V(0) consider Vit) V(0) and V(t) V(t) in Lemmas B.3 and B.4 respectively:
Lemma B.3 (Rectifier sign-changes). Suppose v (0). vx) are sampled i..d. as 2.4 In
addition assume we have m 22( (m/8)*/4 // log(n/5)) and [[v - vx(0)]l2 S 96m(m/6)11 R
ado
Then with probability 1 - 8.
IV((t) v(0)222 Ao 8
Lemma B.4. Define
An
ad1
Rg (8n(m/8)1/4
R.
(B.2)
96n(m//)1
Suppose the conditions of Lemma B.3 hold, and that vv=()))v=(0)]1 s R. 11gx (0))22 s R. for all 1 I ke I m. Then with probability 8,
[[V(1) ((0) < A
G-dominated convergence We ensure that G(t) stays uniformly positive definite if the following
hold.
Lemma B.5. Given (0),,, ... (0) generated i...d. in (2.4). suppose that for each k, [[vv<(t)
v (0)ll S
8a(m//)177 =: R,, then with probability 8,
/2mcuo
(G(t)-G(O)]a [G((t) G( < 140
4
After deriving sufficient conditions to maintain a positive least eigenvalue at training, we restate the discussion of linear convergence from Section formally.
14

---

Under review as a conference paper at ICLR 2020
Lemma B.6. Consider the linear evolution di (G(t)
V( (f(tt) y) from (35) Suppose
a²
that Amin (t
V(
> for all times 0 < 5 T. Then
[[f(t) yl12 exp(-wt)]| y12
for all times 0 ST
Using the linear convergence result of Lemma B.6 we can now bound the trajectory of the parameters from their initialization.
Lemma B.7. Suppose that for all 0 S 1 S T, Amin (GI+
2 and (gx(1) - gx:(0) s
Rg S 1/(m/8) Then with probability 1 - over the initialization
(t) (x)]22 4vnlif(0) - yll2
R,
(B.3)
awym m
for each k and all times 0 T.
G(t) 2 v(1)
Lemma B.8. Suppose that for all 0 sts T, Amin
2 2- Then with probability
1 - over the initialization
4/n||f(() - yyl2 Ry
(tx(() 9k (0) s
Vmw
for each k and all times 0 S SIST.
The distance of the parameters from initialization depends on the convergence rate (which depends on Amin (A (t))) and the width of the network m. We therefore able find sufficiently large for which the maximum parameter trajectories are not too large so that we have that the least eigenvalue of (t) is bounded from 0; this proves the main claim.
Before proving the main results in the case of gradient flow, we use two more technical lemmas. Lemma B.9. Suppose that the network initialized as (2.4) and that y E IR" has bounded entries l < M. Then [[f(0) - yll2 I Cv'n log(n/ (8) for some absolute constant C > O.
Lemma B.10 (Failure over initialization). Suppose vi (0) .... (O) are initialized i..d as 2.4 with input dimension d. Then with probability 1 6,
(m/5) 1/d
max KE VT
V& (0)l2
In addition by (2.3 for all 2 0, with probability
8,
(m/5) 1/d
1
max AE(m)
V=(t)ll
a
Remark (Assumption 2p. Predominately, machine learning applications reside in the high dimen- sional regime with d 50. Typically d > 50. This therefore leads to expression (m/8)² //d that is essentially constant. For example, if d = 50, for max [[ 2 10, one would need m/8 2 8000 (the tail of x2 also has a factor of (d/2)! 24/2 which makes the assumption even milder). The term (m/5)2/ /// therefore may be taken as a constant for practicality,
1
C
max AH
(0)l2
While make Assumption 2 when presenting final bounds, for transparency do not Assumption during our analysis and apply it only when we present the final over-paramettrrization results avoid the overly messy bound. Without the assumption the theory still holds yet the pvertparamettrizzatonn bound worsens by a power + 1/(d - 1). This is since the existing bounds can be modified, replacing m with m m
15

---

Under review as a conference paper at ICLR 2020
Proof of Theorem B.1
Note that m = Q n ( implies that Lemma B.1 holds. Further since the gradient flow updates continous (since the time derivative with respect to each parameter may be bounded), there exist small time T for which the parameters are bounded from initialization for < t & and for all 1 s k S m,
(lv())-v<(0]lzz S R.. (1) gu (0) S Rg.
The bounded trajectory above, along with the over- parameterization, ensures that with probability 1 8 over the initialization that Lemma B.4 and that
Amin (G(t) +
1 a² v(t) 2 Amin (V())/a² 2
Ao
2a²
for times 0 S S T. The condition on the eigenvalue the evolution matrix along with the bounded
trajectory of 9u implies that Lemmas B.7 B.8 hold for least times
< T' Define To to be
the first failure point of either Lemmas B.8 B. 7 we have that To 2 T > 0. For < f < To. by
substituting m (1n** (00)/////////// Xg) and using the bound on [[ ylll of Lemma B.9 direct
calculation utilizing Lemma B.7 shows that
(//)/ff(0) yll2
vv (t) vx(0)]l2
< Rv.
vm1
Similarly by Lemma B.8 m ensures that
Vnl(((() < Rg.
y1l2 Vmda
(9%(() g& (0)
The over-parameetriizaioon of m implies that the parameter trajectories stay close enough to initializa- tion satisfy the hypotheses of Lemmas B.3 B.4 and that Amin (A(t)) 2 Amin Att)(((t))/a² 2 2n at
time To. This implies that Lemmas B.7 B.8 both hold at time To which contradicts the definition of To. Therefore we conclude that Lemmas B.7 B.8 hold for & which implies that Lemma B.4 holds for >> 0 hence Lemma B.6 guarantees linear convergence.
Here we consider the case where the convergence is dominated by G. This occurs when a 1. Proof of Theorem [B.2]
Similarly to Theorem B.1 we note that m 12( max {n' log(n/5)/** ug n² log(n/8)/m) im- plies that Lemma B.2 holds. Further since the gradient flow updates are continous (since the time derivative with respect to each parameter may be bounded), there exist small time T for which the parameters are bounded from initialization for 0 t < T and for all 1 S k S
vvx va (0)ll2 S R..
The bounded trajectory above, along with the over- over-varameeeteee parameterizaaiion ensures that with probability 1 over the initialization that Lemma holds and that
Amiu G(t)+
1 a v(t) 2 Amin (G())//²² 140
for times 0 < t. S T. The condition on the eigenvalue of the evolution matrix along with the bounded trajectory gs implies that Lemmas [.7 B.8 hold for least times < 1 < T. Define To to be the first failure point of either Lemmas B.8 B. we have that To > T 0. For 0 t <
To. by substituting m Ω max {n² log(n/ /)/ a Pip n log(n (() ((1) and using the bound on
[[F(0) - yll2 of Lemma B.9 direct calculation utilizing Lemma B.7 shows that
(v yll2
On log(n//) R...
(t) (0)
a m
auovm
Similarly by Lemma
B.8 m ensures that
B.8 VT
[()) yll2
1gx (t) ga (0)
< Ry
Viiuoo
16

---

Under review as a conference paper at ICLR 2020
The over parameterizztion of implies that the parameter trajectories stay close enough h to initial- ization to satisfy the hypotheses of Lemmas B.5 and that Amin (A(t)) 2 (min(G(tt))ee ž /uo22 at time Tg. This implies that Lemmas B.7 B.8 both hold at time To which contradicts the definition of Th Therefore we conclude that Lemmas B.7 B.8 hold for & > which implies that Lemma B.5 holds for >> 0 hence Lemma B.6 guarantees linear convergence with rate po/22.
Note that if a is large, the required complexity is reduced. Taking D2(/n/po) gives the improved bound
n²² log (n/0)
m
HB
C FINITE STEP-SIZE TRAINING
The general technique of proof for gradient flow extends to finite-step gradient descent. Nonethless, proving convergence for WeightNorm gradient descent exhibits additional complexities arising from the discrete updates and joint training with the new parameterization (.2)) We first introduce some needed notation.
Define (RR) as the set of indices k E [m] corresponding to neurons that are close to the activity boundary of ReLU at initialization for a data point x;,
(R) = {kr e [m] v with ||v - vx 12 s R and 1x + 1(v x, 2 0}}.
We upper bound the cardinality of (R)( with high probability.
Lemma C.1. With probability 8, we have that for all
V2mR
VTa + 16log(n/8)
(S)(R))
3
Next review some additional lemmas needed for the proof of Theorems 4.1
4.2 Analogous
Lemmas B.7 B.8 we bound the finite-step parameter trajectories Lemmas
Lemma C.2. Suppose the norm of [[f(s) y1ı2 decreases linearly for some convergence rate during gradient descent training for all iteration steps 0,1,..., K with step-size n
[[((s) 1 I (1- -0)) ((()) y 1 Then for each we have
[ox gx((0) A/T(f(()) yllz
Vmn
for iterations s == K LI.
Lemma C.3. Under the assumptions of Lemma C.2 suppose in addition that (sx(s) gk (0) s
1/(m/5)/ 1/d for all iterations steps s = 0, 1, .Then for each k,
[i - v < 8 - yll
a.mmm
for s 0.1,
To prove linear rate of convergence we analyze the s iterate error [|f(s ylla relative that of the iterate, [[f(s) - y112. Consider the network's 's coordinate- wise difference in output between iterations, f.(8 1) f((s). writing this explicitly based on gradient descent updates yields
(s + 1)
(agk(s) [
f(s f((ss(
σ (V& Tx,)
(v)(s))T (x:). x;). (C.1)
/ m
Vv 1)ll2
17

---

Under review as a conference paper at ICLR 2020
We now decompose the summand in [C.1] looking at the updates in each layer, f((s + fi(s) (s)s) + (s) with
Ckgk (s + 1)
a:(s) = mm
VA + 1)ll2 (Va(s)
(vi(s) (x));
[
CL.9k + +1
by(s)
(o(vx + 1)= x,) o(vx(s) x.))
vs + 1)ll2
Further, each layer summand is then subdivided into primary term and residual. as(s), correspond- ing to the difference in the first layer as follows:
(a. ve(x+1]12
(a)
is subdivided into of (8) and at (s)
[v
af (s) 1
(s +1
l|vx())122 (onalllovv(ss) (vvx((s]xx))
(x9)(s)
(C.2)
/
[s)x(
k=
Ca.lu (s +1)
( + o (vv((s)
af (s) = m
(C.3)
v + 1>1la 11vx())122
(s) is sub-divided based on the indices in the St that monitor the changes of the rectifiers. For now, S; = (R) with R to be set later in the proof. b:(s) is partitioned to summands in the set S; and the complement set,
CKOK (s 1)
(x)))
(o(va(s (1) - (v(x(()) (x)))
VA + 1)1l2
kgs,
1 CaOK (s + 1)
(s)
(o(vx
(vv xx))-
Vm
[ 1)ll2
kES;
With this sub-division mind, the terms corresponding to convergence are a (5), bs(s) whereas (s)(,, (x)(s) are residuals that are the result of discretization. We define the primary and residual vectors as
P(s) as(s) + bs(ss
r(s) + (s)(s)
(C.4)
1
"1
If the residual r(s) is sufficiently small and p(s) may be written p(s) --{(s((((s)) y) for some iteration dependent evolution matrix ((s) that has
Amin (A())) w/2
(C.5)
for w >> then the neural network (1.2 converges linearly when trained with WeightNorm gradient descent of step size We formalize the condition on r(s) below and later derive the conditions on the over-pant preeraaaatttiinioonnnn (m) ensuring that r(s) is sufficiently small.
Property 1. Given a network from the class (1.2) initialized as in 2.4 and trained with gradient descent of sizp-size n, define the residual r(s) as in (C.4) and take w as in (C.5). We specify the "residual condition" at iteration
|[(()]l2 S (w]lf(s) y
for a sufficiently small constant > 0 independent of the data or initialization.
Here present Theorem C.1 which is the backbone of Theorems 4.1 and 4.2
Theorem C.1. Suppose a network from the class (.2) is trained via WeightNorm gradient descent
with an evolution matrix A(s) in (C.5) satisfying Amio Amiu(A (A(s)) 2 w/2 for 0, 1,.. . K. In
addition if the data meets assumptions 2 the step-size of gradient descent satisfies 1j S [s)]l
and that the residual r(s) defined in CC.4 satisfies Property 7
for
.,..., K then we have that
(1
[[f(s)
y1
[((0) - -y1
2
for 0, ...... K.
18

---

Under review as a conference paper at ICLR 2020
Proof of Theorem C11:
This proof provides the foundation for the main theorems. In the proof we also derive key bounds to be used in Theorems 4.1 4.2 We use the decomposition described above and consider again the difference between consecutive terms f(s + 1) f(s),
(agg(s 1)
cRgh(s)
+)( fi(s)
V 1)ll2 (vx(s +1 x))x
(s) xx). (C.6)
vm
[|v(2)]l2
Following the decompostion introduced in (C.2 af (8) is re-written in terms of (
(s) m
m
Ck
aL(s)
o(va(s) x,)
(x(()]l2
1
Ōgk.
1
Ck
E(}(s)) vi) \va(s)]l2 (s)
[|vx(
m
m > (f)(s) 41)
- m Σ (c))30
Vr((s)
(va(s)
7
[[(v()))12
j=1
Σ (J)(6) - y1 G;y(+),
/=1
where the first equality holds by the gradient update rule ( + 1) 9x(s) 1/ gu. L(s). In this proof we also derive bounds on the residual terms of the decomposition which we will aid us proofs of Theorems 4.1
4.2 af (s) is the primary term of (s), now we bound the residual term
(s). Recall d((ss) is written as
af (s)
Σ Vm 1=1
CL (s (1+ (s (VVx(S) xx),
[s [|va())122
which corresponds to the difference the normalization the second layer. Since V L(s) is orthogonal to (s)s) have that
(= +1)
1
1
(vv xx)
||va($ 1)ll2 [svx())]l2
cagn(s
[va(s)l2 (s)x(()Tx
|I (s) + 1 V. L(s)
(s + 1)n Vv, L(s)
1|vx(s 1)1l2 Vv (1 (s)] + +) (vv(ss) xi)
< (s + 1)ny V [<)]] (x(8)
[+)]2ll]]2]] 1)ll2
[s)l())
where the first equality above is by completing the square, and the inequality is due to the increasing magnitudes (s)]l2)
va(a) x, [[x(
Since 0 <o
< 1, the above can be bounded as
(a(s 1 L(s)
[a)((s) (s)l <
2 v/ 1)
71 Ro (m 3
n||((s) y13(m//6)/4
amm
n + (m 1/4 - -1
(C.7)
19

---

Under review as a conference paper at ICLR 2020
The second inequality is the result of applying the bound in equation EE.1 the gradient norm VVV (s)]l2 and using Lemma B.10
Next analyze (s) and sub-divide it based the sign changes of the rectifiers. Define the set S; == (R) as Lemma C.1 with taken to such that ||v (s + 1) (x) I for all Take (s) the sub-sum of (s)s) with indices lt from the set St.
of (s) corresponds to the sub-sum with the remaining indices. By the definition of S., for k g S we have that (s + [s)(s. This enables us to factor (s) and represent b/ (s) as a Gram matrix similar (s) with correction term from the missing indices in S,.
Ca +1)
(x)
(nrVVr, I(8), (s(()
[Ive(( + 1)]l2
m
kg
7
Cu + +1)
chon(()
(1(()))-))(()))))6)(((3)3 x.).
m
vv 1)ll2
||*(2)]22
kgs:
Note that (x) (x)a(o)+ x:) = (x x xx((s)
therefore.
(x))
7
(C
(a9n(())
ΣUG - -000))))))))))0))) , x
m
kgs:
j=1
Define (s) as
(s +1) [v + 1)1la {
( [[va())]])) 1 (x) x)a(s)))
Vi((s)
m
(99(s+119e This matrix is identical to V(s) except for modified scaling term however that
We note
min ((rv)t6611))) ) ( (ca.n(s +1) (c)
< camn(() [Iv[(s)lz)
( +1)
[[ 1)1l2 (1)(s)+))l))
[+
(( (Iiva(9)le) )²
(
2
Ca0a(s +1) 2
max
[|vx 1)1l (1)/2)+))22
because Gk (8), ot are positive. Hence the matrix V(s) satisfies the hypothesis of Lemma B.4 entirelyy. We write 6/ (s) as
= =(s))=n/a* (f((s) - (11)))))(Vv) Vs)()),
1=1
where we have defined
1
(CC
(c + +1) ) (=(()))(())))))000 x
(+)
[vve())]12
[|v + 1)1l2
(C.8)
m
KES.
We then bound the magnitude of each entry (s)(:):
V.L [i)(
m Σ
acc.sa(s)
aca. (8 +1)
(ss( (x) x
[iva(s)]2z)
Vi + 1)1l2
KES.
(1 + R. (m (m/))
(C.9)
m
20

---

Under review as a conference paper at ICLR 2020
Lastly we bound the size of the residual term b!" (s),
Cxgg(s + 1) V& 1
[b)(s)]
KES.
gu (s 1)ml S v Ls)ill2
mml Vv (s + 1)llz
n| S| (m/d)² // R2)1 VvcL(s))p
avm
Where we used the Lipschitz continuity a in the first bound, and took Rg 0 that satisfies lax(s + 1) 9b (0)l S Rg in the second inequality. Applying the bound (E.1)
7|5alvm(1 /2 -yll
(s) <
(C.10)
a²m
The sum f(s + 1) - f()) (00)=a(( (s) + a (s) + bs()) + bb'(s) is separated into the primary term np(s) (s + (s) and the residual term r7((s) arr bys(s) which is result of the
discretization. With this, the evolution matrix A (s) in C.5 is re-defined as
x= G(s)) V(s) (s)
a²
and
f(s + 1) - f(s) (f))(((((3))) - yy + m)((s).
Now we compare
[[f(s + 1) yl1 with [|f(s) - y1l..
[[[( + 1) - yl =I[((s 1) f(x) + f(s) - yllă
=I[((s) - y11 2((((s++1) - f(ss,, f(s) -y)
+ +(((++1) ((s), (c+1)-f((s)
Substituting
f(s 1) - f(8)= = (00())))((((((((()==0000000000)- - y) + +s(s)
we obtain
[f(s 1 y11 =1((s) - -
-V) - ) r(s))
y)
7 - -y)
+ (I= + (r))))
Now Amia (A(s)) w and 1 || we have that
- ( - y) 5 3rpw
( - y) =
8 [[((s) -y112.
Next we analyze the rest of the terms and group them as q(s).
q () == (I)))()))((()) (f))
+
- < -111:))))11()>11>=>>>>>
By Property we have
(s)) s n(w))f(s)
y1 now) s 2csw)lf((s) -y1l..
21

---

Under review as a conference paper at ICLR 2020
so that
q(s) S c'mpolf((s) - -112.
for d' sufficiently small. Substituting, the difference f(s + 1) - y bounded as
[f(ss + 1) y1l < [[f(s) - - 7o - (1))) - -yll + c' ((mp)lf((s) -yl1
S (1 (1
(s) + ) [f(s) - -y11
< (1 mw/22)lf(s) y11..
for well chosen absolute constant c. Hence for each = 0, I,...,,,,
[[f(s + 1) v11 v (1 m2/2)]l((s) - y12
so the prediction error converges linearly.
In what comes next we prove the necessary conditions for Property I and define the appropriate w for the V and G dominated regimes, in order to show Amin (A(s) 2 w/2.
Proof of Theorem 4.1
To prove convergence we would like apply Theorem C.1 with w/2 22. To do need to show that (n log(n/5) X guarantees that Property holds and that Ami (A(s)) 2 22/2a?
For finite-step gradient training, take
ad R 192m(m/8)1m
Ao Rg 96n(m/6)1/a
(C.11)
Note the residual r(s) and the other terms by (s). byr(s) depend on the sets S, that we define here using Rg. We make the assumption that (s) Vx (0)1l2 S. Ry and [g)(()) g (0)] Rg for all k and that s = 0, 1 ... K + 1, this guarantees that (y(s) and (s) are well defined. Applying Lemmas B.1 B.4 with R,, Rg defined above, we have that Amin Main(Ve (V(s) 2 Ddd. Then the least eigenvalue of evolution matrix (s)) is bounded below
8
Amiu (A(s)) = Again G(s) + V(8) (s)
a²
Aー (s)
2 Amin
a
Amin
((8) (8))
a
5
(s)
8
a²
The first inequality holds since G(8) 0 and the last inequality is since Amin (V())) 2 52e
To show Amin (A())) Z
An 2a
we bound V++()]12 S 2r. By we have
[1)(s (1 (m/8) /2) S < (1 + Rg (1
V2R.
16 16log(1/6)
m
V T
3m
Substituting Ru, Ry and m. direct calculation shows that
Ao 8n
[+}{s <
which yields
(8-())) VV- (s)(lr - Ao
8
Hence Amin (A(s)) 2 2 for iterations
0, 1,... K.
22

---

Under review as a conference paper at ICLR 2020
We proceed by showing the residual r(s) satisfies property Recall r(s) is written
r(s) a (1((s) b²(s)
7
and Property 1 states that ||x(s)]2 I at
[[((s) - y1l2 for sufficiently small absolute constant 1. ' (s), bd (s) satisfy
This is equivalent to showing that both a
an [[f(s) -yll2- (a" -
(C.12)
a²
[
l[f(s) -ylle- a²
(C.13)
We consider each term at turn. By (C.10).
| (s)lla < v max by
max m (1 + Rg (1 yy112
amm
CmR (m((s) yl12 y
a²m {s] -yll2 a²
nCR..
In the above we used the values of R2, Rg defined in (C.11) and applied Lemma C.I in the third inequality. Taking m (nn log(n/8)/ Xx) with large enough constant yields
c)uulI((s) - yll2
[bb((s) (s)1l <
a²
Next analogously bound [s)]())) via the bound (C.7)
||a S vn max a! (s)
1/2 + Rg (m (m/5)) 1d)) [f(s) - ylB(m/6))/4 <
at vm
171 + (mmm))))/ ( /ll2(m/)) 1//2)(((())
n7oll - yllle
a²
2oa2
noo ((ol(((s) - yll2
n Cnê Cn² (og(nn/)
a²
davm
I (s)) yy122
In the above we applied Lemma B.9
once again. The last inequality holds since m
R(n ( log(n/8)/A) and 7 O
n²
hence r(s) satisfies Property Now since Theo-
[V
rem C.I holds with 2o/a² have that the maximum parameter trajectories are bounded as [[v v4 (0)| < Ri and [I 9u (0)l < R, for all k and every iteration s = 0, K +
via Lemmas
To finish the proof, we apply the same contradiction argument as in Theorems B.1 B taking the
first iteration s Ko where one of Lemmas C.2 C.3 does not hold. We note that Ko 0 and by
the definition of Ko. for = 0, 1,... Ko the Lemmas C.2
C.3 hold which implies that by the
argument above we reach linear convergence in iteration Kg- This contradicts one of Lemmas
C.3 which gives the desired contradiction, so we conclude that we have linear convergence with rate Ao/ 222 for all iterations.
Proof of Theorem 4.2 For G-dominated convergence, follow the same steps in the proof of Theorem 4.1 We redefine
23

---

Under review as a conference paper at ICLR 2020
the trajectory constants for the finite step
Virapo
RS
Rg
140
64n(m/8)1/2
48n(m/8)4
To use Theorem C.1 we need show that m (n 2n log(n/)) pá)) guarantees Property and that Amin (A(s) no/2. We again that the residual rss) and (s))), brr(s) depend the sets St that we define here using R. above
(R,)).
We start by showing the property on the least eigenvalue. We make the assumption that we have linear convergence with w/2 1o/2 2 and step-size vj for iterations 0,... K so that Lemmas C.2
C.3
hold. Via analogous analysis of the continous
reach that 22(n log(n/5)/ 1
imp ies
S /6a/n/100 yllz
< R.: (gc(8) - gb g0)( S SVm|IP(0) yllz
[s){ vx(0)]12
< Rg.
aymujo
Vmnoo
for K + by Lemmas C.2
C.3 and that (s), (s) are well defined. Using the bounds
on the parameter trajectories, Lemma B.5
and R, defined above yield Amin MainGGe (G(s)) 2 5yo The least
eigenvalue of the evolution matrix A 8) is bounded below as
Amin (s)) Amin G(s) ((8) - v+((s)
a²
Amin (G(s) - (s)
since V(s) > 0 and a 2 1. We bound the spectral norm of (s)]l2,, for each entry i, we have by C.9
that
Rm(m/0)) (
m
22
16 16log(n/0)
(1
R2 (m/88/)/
Viaa
3m
&R
V2TT
M0
8n'
where in the above inequalities we used our bounds on Rw, Rg and m. Then the spectral norm is bounded as
I (s)lla S VIV (s)lle S no/8.
Hence we have that Amii (A(s)) 2 Po/2 for s = 0, 1,... K.
Next we show the residual r(s) satisfies Property
Recall r(s) is written
(s) b²((s)
r(s)
n
Property 1 states the condition ||r())]2 S ownl ((8) yll2 for sufficiently small < with w = This is equivalent to showing that both a (s), b (s) satisfy that
μo-
aa 1 (s) eapall (fs) yl12.
(C.14)
bb T (s)]l2 S cmpoll((s) - yl12.
(C.15)
for sufficiently small absolute constant For (s) we have that (C.10) gives bbd (s)l1) x vn ma
11 + Rg (1 f(s) yl2
< max
am
24

---

Under review as a conference paper at ICLR 2020
Next applying Lemmas C.I and B.9 in turn yields
(mlenn)((((s) yll2
a²m
Rr
mpoll((s) yyl2
no²
Substituting (2n log(n/6)///33 for large enough constant and R2 we get b (s)ll2 < co/oll - yll2.
Analogously we bound ||a'((s) (s)ll2 using CC7
||a (s)ll Viiaaaa! (s)
1/ (1 + (m 00) ([(ss) yl8(m//))va
a²
())llf((s) - y|l2- n(1 (m/88/) ( (1(3) y v112(m/8)//e
Moar vm
On² Vlg((/j)
qpoll((s)) yyl2-
a² a2pōym
$ snnpollf( yyl2.
Where have used Lemma B.9 in the third inequality and substituted m 2(n log(n/5)/a² (od)/////l mh) noting that 7 0 A and that a 2 in the last inequality. Therefore we have that r(s) satisfies Property | so that Theorem Theorem[C.]hoold. By the same contradiction argument as in Theorem we have that this holds for all iterations.
D ADDITIONAL TECHNICAL LEMMAS AND PROOFS OF LEMMAS FROM APPENDIX B
Proof of Lemma 411
We prove Lemma 4 for a Go separately. y can be viewed as the covariance matrix of the functionals db; defined as
0c(v)= =x
1(v x; 2 0}
(D.1)
over the Hilbert space of (2 (²))) of functionals. Under this formulation, if Φ1, $2 On linearly independent, then y is strietly positive definite. Thus, to show that V is strictly positive definite is equivalent to showing that
c1 C202 + c,O, in V
(D.2)
implies 0 for each i. The 6,8 are piece-wise continuous functionals, and equality in V equivalent to
is
c1 0202 + Cn almost everywhere.
For the sake of contradiction, assume that there exist C,, that are not identically 0, satisfying (D.2). As o; are not identically 0, there exists an such that e * O. We show this leads contradiction by constructing non-zero measure region such that the linear combination Σ; Goss is non-zero.
Denote the orthogonal subspace to x; as Dj = (v Rd vTx; 0). By Assumption 1
D; & UDD
ifi
25

---

Under review as a conference paper at ICLR 2020
This holds since D, is (d- dimenssiol space which may not be written the finite union of sub- spaces Dj n Dj of dimension (since x, and x, are not parallel). Thus, take z E -D, DDA Dj- Since Uبور D3 is closed in RR there exists an R > 0 such that
Blz, AR)
UD; j#1
Next take ( n D; (where @ denotes the boundary) on the smaller disk of radius 3R so that it satisfies |y 20 11y'|12. Now for any r S R. the ball Byy, r) is such that
for all points (y, r) we have | ||2 2 2R and ||v**
22 S R. Then for any R, the points
v E r) C (zz, 4ft) satisfy that
|
ll 2 x
X; V
2 |x:12
R
x ll
Tvll2
2R
2
Next we decompose the chosen ball B(y,r) = (r) (r) to the areas where the ReLU function at the point x; is active and inactive
B (+())= =
2 0), B (r) = Bly, [x] < 0}.
Note that o; has a discontinuity on D, and is continuous within each region B (+)r) and B (r). Moreover, for j * i, Φ2 is continuous on the entire region Byy, r) since Bly,r) B(z, 4R) c Dj. Since we have that Φj is continuous in the region, the Lebesgue differentiation theorem implies that for r -> 0, Φi satisfies on B+ (r), B (r):
/
lim 1 (r)) B+(r)
Φi x # O, lim r-0 (( (r)) B-(r)
For j # i oj is continuous on the entire ball Byy,r) hence the Lebesgue differentiation theorem also gives
lim r-0 1 (B)(r))
ai = dy()), lim B Bi(r)
Φs dy)
-00 ((B ((B-(r))
(r)
We integrate c1 + ... On over B (r) and B+ (r) separately and subtract the integrals. By the assumption, Φ1 +... + Cn 0 almost everywhere so each integral evaluates to 0 and the difference is also
(rB+(r)) I
J (r)
ci +... cadn m (r))
ci .... Codn.
(D.3)
(i(r)
By the continuity of by for # taking r 0 we have that
lim (+)
M(B (r)) B-(r) 0 = o k,() = 0.
(BB B + (r))
For Φ; the functionals evaluate differently, For B (r) we have that
1 lim
lim di μ(B (r)) n(B
0= 0,
B (-
(r)
while the integral over the positive side, B (r) is equal to
m(B+(r)) JO (z(x)dz= ((B-(r)) (+(r)
x du x²
By construction, ||x ll R and is non-zero conclude that for D.3 to hold must have
= O. This gives the desired contradiction and implies that Φ1.... On are independent and y is positive definite with Amin (**) An-
26

---

Under review as a conference paper at ICLR 2020
Next consider G and again frame the problem in the context of the covariance matrix of functionals, Define
(,(v)
|
for v * O. Now the statement of the theorem is equivalent to showing that the covariance matrix of {0:} does not have vero-eigenvalues, that is, the functionals 0,5 are linearly independent. For the sake of contradiction assume 3 CI.... ........... Cn such that
1 + c202 +... C,O,, =0 in V (equivalent to a.e).
Via the same contradiction argument show that 0 for all i. Unlike o; defined in D.I each is continuous and non-negative so equality "a.e" is strengthened to "for all v",
c101 + cy02 + +... cn 0.
Equality everywhere requires that the derivatives of the function are equal to 0 almost everywhere. Computing derivatives with respect to v yields
x 1(v X1 2 03 c2x2 1 1( X2 2 03 + G, 1(v Xn 2 0} 0.
Which coincide with
c +.
By the first part of the proof, the linear combination (10) + ..... + Cn is non-zero around a ball of positive measure unless c; for all i. This contradicts the assumption that the derivative is almost everywhere; therefore G is strictly positive definite with \G
> 0.
We briefly derive an inequality for the sum of indicator functions for events that are bounded by the sum of indicator functions of independent events. This enables develop more refined concentration than in Du et al. 15 for monitoring the orthogonal and aligned Gram matrices during training.
Lemma D.1. Let AI...., Am be a sequence of events and suppose that Aş C By with BI.... Br mutually independent. Further assume that for each k, P(B)) S p. and define S 1 Then with probability 1 8, S satisfies
Em A m
8 8log( (lgg(1)))
S < p 2+
3mp
Proof of Lemma D.I: Bound S as
8
Σ k=1
11
n
We apply Bernstein's concentration inequality to reach the bound. Denote X₃ m
1s, and $
Em Xs. Then
Var(Xs) S EX -1/m) + +05 m
P
ES = _
Xx S.p
Applying Bernstein's 's inequality yields
-22/2
P(Š ES 2 t) exp
Ek k= EX?
3m
Fix and take the smallest such that P E. 2 1) S 8. Denote r. T.Š. either TPŠ F. > ES)= < d, or = rEŠ corresponds to r 2 1. Note that = rES rp. In the latter case, the bound written
(2/) p/m + 3m
22 5)
(pr)) = exp P
-3pmm
P(Š - ES 2 rp) < exp
< exp
< exp
27

---

Under review as a conference paper at ICLR 2020
Solving for gives
llo((1/8) 3m
rp S
Hence with probability 8,
S S $ < max pp( 1+
8 (10g(1/0)
p
8 8log(1/0)
.2p
2
3mp
3mp
Proof of Lemma [B.1}
We prove the claim by applying concentration on each entry of the difference matrix. Each entry V ig (0) is written
(1)
[=] xx
xxx10)+)
[cck (ack
gk
L (O)
m
At initialization Is (0) = [|)x20)]l2/a ch = so so (1) simplifies to
(0) 1 m m
(=)+)
x xx((0) >x=10)))1 (,)()),,x))))
Since the weights (0) are initialized independently for each entry we have E, (c) Voc We measure the deviation V(0) v via concentration. Each term in the sum
(O) (0) 1 (0)1 (0) independent and bounded.
-1 -1 (x (0)
x x
1 (0)1,xx0) 1
Applying Hoeffding's inequality each entry yields that with probability 1 8/n², for all i,j,
V (0) V $ 2 2olog(n2/0)
mm
Taking union bound over all entries, with probability 1- 8,
4 4vlog(n/0)
V2y - v S
mm
Bounding the spectral norm, with probability 1 8- 8,
[V(0) V(0)) - Vo |2 S
Vi
V
16n log(n/8)
m
Taking m -2(" n² log(n/8)) Ag
therefore guarantees
[|V(0) - v 12 Au
Proof of Lemma B.2;
This is completely analogous to B.I
Recall G(0) is defined as,
G (0) m
1
x, > (0)1,
v=(
28

---

Under review as a conference paper at ICLR 2020
with c and vx(0) ~ I2) initialized iid. Since each term is bounded like B.1 the same analysis gives
16n log(n/5)
[G,((0) - G
m
Taking 12 (nnloor /
therefore guarantees.
14
|[G(0) G 1 44
Proof of Lemma B.3 For given R. define the event of a possible sign change of neuron k at point x;
A, [3v | (x)0) - R and I (v) x; 2 0) * (v 2 0}}
A, (R) occurs exactly when (0) _ x, < R, since |x and the perturbation may be taken in the direction of -x, To bound the probability A, (R) we consider the probability of the event
((Ac,((R)) (0) x R)
P([=| R)-
Here, z ~ N(O, a²) since the product v4 (0) T x; follows a centered normal distribution. The norm of ||x;I12- = 1 which implies that computes to standard deviation a. Via estimates on the normal distribution, the probability on the event is bounded like
2R
P(A,+(R)) S
2
We the estimate for ((A,,(R)) to bound the difference between the surrogate Gram matrix and the Gram matrix at initialization V(0). Recall the surrogate (t) is defined as,
V.((1) m
va
) (1)()))((())
x
xxx())
Thus for entry j. we have
(t)(t) - Voj(0)l
v(())
(x))) 1x)=10) x3x(0) ,0),
This sum is decomposed into the difference between the inner product and the difference in the rectifier patterns terms respectively:
(xx/a00) .x)
ve(1)'
(x) vu(o)
xx) x2/=111))
(In(t))(())) I. (0)))))))
Define
11hh (xxx(()) x) xxy(()' ) x xxx10)) 1) (1
z (xx:1(0)+ x2x10+ )) 1 (1 (t)L)))))))) (0)0))))))
Then
V. = - ΣΣ x <
1=1
To bound
78 Σ
Y bound each |Y]] follows.
29

---

Under review as a conference paper at ICLR 2020
(x xxal0*) -(x: x=(00 x (Ix(0)
x x= xx((0)) -
- [0)= x
(x,x)) (x ve())
x)0(0) + +xx (o xj x (x,,
x va(t) vx(t) x][x((()
va(()
(x x xx)((01)
(t)l2
(t)(2)
[v)(2)ll2
[t)(2)
x]]v((t) v()
(x
l[v((t)l2
[vv(2)]l2
x (4(
x] (0)
vi(()
v&(0)
x3 vt)
+x
(0)]le
[l)x())l22
(t)ll
[0)]2
[[vx(t)l2
+x7
(IVA(OIIE
vx(t)
vo(0)
) x
v
(xx=
x (a(l))
(O)ll (0)ll)
vx(1)
vo(0) (+(()
vx(()
vx(0)
v2)((())
x
(1)l2
(0)l2)
(1)l2
(1v
[[x 12
[vx(t)]22
(t)
(0)
2 vi (1)
[0)]l2 2
Therefore, we have
m
2 m
va(()
(x
<
[1)l2
[
k=1
4Rw (2m/ /8)2/2
8Ry(m/on (m/5)1/4
a
where the first inequality follows from Lemma B.10 probability - 5/2 for all i,j.
Note that the inequality holds with high
For the second sum, ! Σm Z < D.1 get, with probability 8/2n²
Σ
(R) + Em (R) so apply Lemma
m
2R,
2V2TT log (2n²/0)
2
m
av2T 2π
3m R.
SR,
v 2m
since satisfies Q( (m/ log(n/8) probability 2n ado
Combining the two sums for Y and 2,j with
(V-- < 8R,
(m(55))
12R (m/6))/
a
Taking union bound, with probability - 5/2,
12nR. (m/8)1/4 1/a
(t v(0)l
Σ Viy(t) (1y(0)12 <
30

---

Under review as a conference paper at ICLR 2020
Bounding the spectral norm by the Frobenous norm,
12nR, (m/6)//4
(V(t) v
a
Taking R2
ado gives the desired bound.
36n(m/6)173
Ao [I((t) v(0) -
8
Proof of Lemma[B.
To bound [V(t)) V(0)ll2 we now consider || (tt)ll. The entries of V,y (t) are given as
22 ) (tee() ( acs 9h
(x)
vx(1)*
V [g (t) =
[[v]())]]2
k=1
The surrogate (t) is defined as
(t)(t)
x va()) xyx()) (t)
k=
The only difference the second layer terms. The difference between each entry written as -1
((
Viy(() Vo
va(t)+ =,y(0+)) ,x00000)))(0011
(Ivx(())l2
a (1)2
-1)
max 1sksm
(t)
(0) [v,,0 since (1) is increasing in t according to (2.3
Write
g²gu (1)²
a² (1)²
a (0)²
S 3Rg (m/5)) /4 3R, (m/88))) //x
(t)l
(t)
(0)
The above inequality shown by considering different cases for the sign of the difference go (t) Is (0). Now
a (t)2
a 9h (0)
(t) agx(0)
(t)
agg (0)
(t)
vv (O)E
[[xx(t)l2
[Vx(())22
(0)]l
(0) +aRg
(0)
(gg((t)
agu (0)
[vx(0)]a)
[[v(00]]1
[[v(()]2
[0)ll)
(1)
(gg)(()
< (2 + Rg(m/6)4/o)
[[v221)22
[1vx
[((x(0) Ry)
(ggi(())
a a( (0) Rg)
agg (0)
< (2 (m/ max
(0)())
|| (0) R.
||vx(0)]l
< (2 + (m 8) //d max (R,(m/0)2/4 (m/ + (m)mm))/////m
3R, (m (m/))2/d 3R. (m/
where the second inequality holds due to Lemma B.10 with probability 5 over the initialization.
Hence:
(+(()) V(0122 < (((())
v(tile=
/
-v
Vo((t) 3m/)(m (m/) /
31

---

Under review as a conference paper at ICLR 2020
Substituting Re, Ry gives
A0
(I(()) - v(OIl2 -
8
Now we use Lemma B.3 to get that with probability 1 1 8
Ao
(IV(+) - V(0)lla -
8
combining we get with probability 1- 6
A 4
[IV(t) ( -
We note that the source for all the high probability uncertainty 1 ô all arise from initialization and the application of Lemma B.
Proof of Lemma B.
To prove the claim we consider each entry j,j of G(t) G()). We have,
vx(() x
xx(t)
vo(0) X
vo)( T X (0)(2]
[G)(()) - (o)(
(0)12
k=1
ve(()xx x;
vx(1)xx Xj
vx(()xx X
Vo((O) xj (0)
[vx(0)12
va(1)x
vo) Xj [vc(0)]22
(o x;
(v=(0) X [0)]2
(1)
vo(
2n, (m/0)///
(1ll
1
In the last inequality we used the fact,
(0)
v
[i((() - (0)l2
(m/8)a//
(x)()]
(0)l2
(t)l
(0)12
where the first incquality uses that [[)]2 S (t) and is intuitive from a geometrical stand- point. Hence,
2mRo(m/8)1/4
[GG(t) G(O)]l2 < ||G(t) G(O))l==
Σ (ty(t) (0) < a a/24
Taking R.
4/2spgg 8n(m/8)172 gives the desired bound. Therefore, with probability 1- 5,
[|G(t) G()) < Ho
Now that we have established bounds on V(t). Gt) given that the parameters stay near initialization, we show that the evolution converges in that case:
Proof of Lemma B.6:
Consider the squared norm of the predictions ||[(() - y12.. Taking the derivative of the loss with respect to time,
d
y) (G()+ V()) (P(I) - y).
||())) yll = -(((()))))))
di
o²
32

---

Under review as a conference paper at ICLR 2020
Since we assume that Amin
G(t)
+
Vit) a
z.4 the derivative of the squared norm bounded as
d
[f((t) yll - -wllf(t) yll..
dt
Applying an integrating factor yields Substituting the initial conditions, we get
[[((t) - - exp(wtt S C.
[|(()) yll2 S exp(-wi)) [[()) y112.
For now, assuming the linear convergence derived in Lemma B.6 bound the distance of the parameters from initialization. Later we combine the bound on the parameters and Lemmas [B.4]
B.5 bounding the least eigenvalue of (t), to derive condition on the over parameterizzation and ensure convergence from random initialization.
Proof of Lemma B.7:
Denote fxx:) at time L fi(l). Since ||x; ||x)a(0) 1/2 S ||x: 1, we have that
dv (1)
y Si(())
Ck- (4) [
x Taa(1)
dt
mm
ys fi(t)) (1))(1)
[t)l2)
Now using 2.3 and the initialization
||v (0), we bound
(t)
(t)
< cx
(0)(0) + Rg
[0)]l)) - 1+ [Rg/Ivx(000)]
(t]l2
By Lemma B.10 we have that with probability 5 over the initialization,
a/llv=(0)ll S C(m//)2/4
Hence aRt//ll. 1. This fact bounds
ce (xlll
with probability 1 - 8 for each k.
(t) [t)
2/a.
Substituting the bound,
d dt
2
vt(()
(f(()) Vel
aym m
2
2/7
[((1) yll2
aym
2/n
exp(-ut (() - y112-
aym
Thus, integrating and applying Jensen's inequality.
(-' dvv(s)) dt
4 (VT(f((0) - yllz
[(v (x)2 <
ds <
(ww /
Note that the condition (t) (0) Rg is stronger than needed and merely assuring that (g)(() (00( 1/(m/8)1/d suffices.
33

---

Under review as a conference paper at ICLR 2020
Analogously derive bounds for the distance of gie from initialization.
Proof of Lemmal B.8;
Consider the magnitude of the derivative dyu.
dgk
(Js Ui)
Ck
a(vi
dt
|vel12
==1
Note
= ||
Ck
o (V xy)
vv 2
|v+ll
Thus applying Cauchy Schwartz (t)(t)
2/m
2/n
I
[[((t) - y112
exp( (pp(=w//2)(F(0) y112.
dt
vm
mm
and integrating from 0 to / yields
1ak (1) g& (0) < / dgk
( 2
y1l2ds < 4 f(0)]22 Vmw
(s)
ds 5
dt
j vm
Proof of Lemma B.9: Consider the ith entry of the network at initialization,
1
9k VAVE&
(a(0)
l|v
Since the network is initialized randomly and m is taken to be large we apply concentration to bound fi( for each i. Define 2/ = Cga (G))v (0)) random variables with
Note that 24 are independent uub-Gaussian
[[vx(0] 2
|| S (1, = CC
Here || denotes the 2-sub-Gaussiae norm, (see 31 for example). Applying Hoeffding's inequality bounds (0) as
12/2
P(I/mf((0)) > t) S 2exp
"m -= || 1ive
-12
2xxp
2mC
Which gives with probability - 8/n that
[f(0]] < Öo (n/8).
Now with probability 5 we have that, for each i,
(f:(0) wil: < | Öolol(n/0) < C2 Vlo(n//))
Since y = (1). Hence, with probability 1 - 8.
[|f(0) - yyl2 < C. C/llog(n/8)
Proof of Lemma B.10:
At initialization Vı NO,, I2I) the norm behaves like [|v= a² Xa. The cumulative density of a chi-squared distribution with degrees of freedom behaves like F(x) ((xd/2) for
34

---

Under review as a conference paper at ICLR 2020
small have that with probability 1 - & that ||v(00]l2 2 a(m/6) à where d is the input dimension. Applying a union bound, with probability 1 6, for all S k $ m,
(m/6)) 1/d
(v)(0)122
Now by 2.3 for t 2 0. (1v22 2 (0v2(
(m/5) 1/a
1
(v)(1)22
a
E PROOFS OF LEMMAS FROM APPENDIX
C
Proof of Lemma
Fix R. without the loss of generality we write S; for S, For each k vx(0) is initialized independently via ~ (0, a²I), and for a given k. the event (0) & 1(v x; 2 0} corresponds to Iv (0) x,1 < R. Since |xi|l2- 1, v0( X; N(0, a²). Denoting the event that an index k E S; as Askk, we have
2R P(A,)) S
av22m 2m
Next the cardinality of S is written
| = A
k=1
Applying Lemma D.I with probability 1 8/n.
|. < 2mR
16 log(n/))
2n
3
Taking union bound, with probability 1 6, for all we have that
|S v 2mR
16 log(n/5)
0v 2T
3
Proof of Lemma C.2
To show this we bound the difference gl((s) (0) as the of the iteration updates. Each update is written as
OL(s)
Σ (f((s) vi)
n
C₁ (Vx(()) x:)
8gk
[v*[s]|2
(a) 'x [iva(s]lla
As cgo
< 1.
OL(s)
1
Vn mil
Σ (f((s)
[[((s) -yll2. Vm
Ogk
vm
By the assumption in the statement of the lemma,
(L(s)
Vn - m /0 yll2
Ögk
m
35

---

Under review as a conference paper at ICLR 2020
Hence bounding the difference the of the gradient updates:
[k K 1) gb (0)
aL(s)
AnvTil(F(0) yll2
E (1
mw ya/2
Ögk
vm
2
The last term yields geometric series that is bounded
S
Hence
4 f(0) - y2 w wym m
19x + 1 -gx(0)] 5
Proof of Lemma
To show this write (s)s) the sum of gradient updates and the initial weight vx( Consider the norm of the gradient of the loss with respect to Vk.
vm Σ (1.(s) n.)
vvx(s)l2 (x)xx)))())+++++
vv [s)]l2
Since [>vx(>)]l2 2 ||v 2 (/60m))// with probability 1 - 8 over the initialization, applying
Cauchy Schwartz's s incquality gives
(1+ (mm)))) 1/d ) [(s) yy
IVv. Lss)l2 -
(E.1)
avm
By the assumption on [|f(s) - y/12 this gives
v., M8)]l2 v 2/7(11 - Th / yy
aym m
Hence bounding the parameter trajectory by the of the gradient updates:
2/nl(f(() - -yl2
4/2
lvv +1) - (v) S Σ V L(s)ll2 S
L())ll
Σ
1
avm
yields geometric series. Now the series is bounded as
mpu
which gives
8yn]|f(0)- yll2 y
Vvv(K + +1) - -v
a./mi
36

---

Under review as a conference paper at ICLR 2020
0.014
Total angle variation
next 100 iterations
0.012
0.010
lag(Training
Training loss
Average
0.006
2000 4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Gradient updates
Gradient Updates
(a) Average a during training
(b) Total variation in angle, next 100 steps
Figure 2: Training dynamics of networks from class 1.2 on digits 4,9 of MNIST
F NUMERICAL ILLUSTRATION
Below we provide preliminary numerical illustrations demonstrating the phase transition between V-dominated to G-dominated convergence. We follow the settings introduced in Section 2 In the
experiments we run WeightNorm gradient descent for K = 10000 gradient iterations and learning rate 7 3 10-3 We train the neural network from class (I.2), with m 10000, n 1000, d 784, = 10-3 3 and use the first 1000 images of the digits and 9 of the MNIST dataset. We restrict the digits of 4 and since we focus on the scalar output network with two classes.
To compute for the network during training we calculate the ratio,
a(s) = Ene V[)
2k=1 (s)
During training we note that a grows, the training loss decreases and the convergence rate slows down (emergence of the G-dominated regime). To measure the change in the direction of v& (t) during training we compute the angle variation of the parameter, this is computed for each neuron for each gradient update as,
(vu(s), va + 1)>
($)(s) arccos
[Vv(s)]la/lvv(( +1)12
To visualize the angle change of the network during training, we compute the mean angle change for each iteration, Agve Ex= (s)(). We plot moving sum of (sve window of size 100,
Aiindow (8) = >>+ (r) to measure the change of the angle throughout training.
37


Reviews:
[{"review_id": "rygJndyntr", "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": "Global convergence of NNs is an important research direction in deep learning. There have been significant progresses in this direction since last year. Most noticeable, the Neural tangent kernels (NTK) [1], which shows in the infinite width setting, NTK is deterministic and remains almost constant during gradient descent. NNs are essentially the same as kernel methods. Proofs of global convergence of NNs (without normalization) are built on this intuition. \n\nThis is the first paper (to my best knowledge) to prove such convergence result for weight normalization. The paper is very well written and the presentation is very clear and I really enjoy reading it! The proof builds on (and very similar to) [2] and other recent works concerning the global convergence of NNs in the kernel regime. The main strategy is as follows: \nstep 1. show the finite-width NTK concentrates near the infinite width NTK, whose least eigenvalue is positive (need proof) \nstep 2. show the change of finite-width NTK is tiny and essentially does not alter the least eigenvalue.   \n\nAs such, the optimization problem is essentially a strong convex problem. Although the high level picture is very similar to previous convergence papers, the technical details are different. In particular, the authors show some improvements over  previous works: e.g. the width required for the proof here is n^4 (n == dataset size) rather than n^6 without normalization ([3]). I think these bounds are very loose and it is not clear to me if normalization provably reduces the degree of over-parameterization; see [4].  There are also some other interesting results concerning weight normalization, e.g. the NTK could be decoupled into the sume of the `directional`   NTK and the `length`  NTK. \n\nOverall, this is a good paper but the contribution might not be sufficient for acceptance for the reasons below. \n1. the overall framework is very similar to previous works and the dynamics of NNs still lives in the kernel regime, which might not be the most interesting regime for deep learning. \n2. In this kernel regime, global convergence (or GD dynamics) might not be the most interesting object to study since we already have many existing works in this direction. I hope to see new insights beyond global convergence, e.g. benefits of normalization to generalization (potentially for multilayer networks), etc. See comments below. \n\n\nComments: \n1. Extending to multilayer? \n2. Show normalization provably reduces the level of over-parameterization needed for convergence. This requires a lower bound for the width that NN cannot converge if the width is below the threshold.  \n3. What can we say about generalization: normalization vs no normalization? e.g. [5]\n\n\n\n\n\n[1] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in\nneural networks. In Advances in neural information processing systems, pages 8571–8580, 2018.   \n[2] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes overparameterized neural networks.\n[3]Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization\nand generalization for overparameterized two-layer neural networks. In International Conference on Machine\nLearning, pages 322–332, 2019.\n[4]Samet Oymak, Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks\n[5] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization\nand generalization for overparameterized two-layer neural networks. In International Conference on Machine\nLearning, pages 322–332, 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Bye0AsyAKH", "reviewer": "AnonReviewer2", "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 presents a general proof of the convergence of two-layer ReLU networks with weight normalization trained with gradient descent. Weight normalization re-parameterizes the weights to decouple the directions and lengths of kernels. Depending on the lengths of kernels the training process can be divided into two regimes, corresponding to updates of lengths and directions, respectively. One of the regimes naturally corresponds to lazy training where the directions remain stable. And there are transitions from one regime to the other when the lengths gradually change during the training process.\n\nThe proofs are very solid and the results look strong to me.\n\nMy only concern is that this paper is obviously squeezed to fit into 8 pages. I am not sure whether this is acceptable. Personally I think there is no need to do so and it's okay to just use 10 pages based on the loaded contents of this paper.\n\n=====================\nI'd like to keep my original score for this paper after reading the authors' response.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bklk18_hKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary of the contributions:*\nThis paper deals with convergence, of the hidden layer of a 2-layers Relu Network trained with Weight Normalization which consists in decoupling the direction and the magnitude for the pre-activation layers. The authors show, under mild assumption, the linear convergence (with high probability) of the training loss in the over-parameterized setting.\n\nConceptually the result says that using random feature selection (the last layer is fixed, initialized with Rademacher random variables), with a large enough network, the hidden weights do not need to move much from their initialization to get arbitrarily small training loss. \nThus, the analysis of the whole dynamics is reduced to a perturbation analysis of the dynamics around the initialization. (I would like to emphasize that even though the final argument ends up to be a ‘simple’ strong convexity convergence proof, I acknowledge that the proof of such result is far from being straightforward.) \n\nThe contributions of this paper are the following: in the setting introduced in [15] (the ref numbers correspond to the ones in the paper) the authors prove the linear convergence of the training loss for a large enough output layer of a 2-layer Relu network with Weight Normalization. Regarding to [15] the difference is that the authors study Weight Normalization. They are able to get better bounds on the over parametrization, and provide an analysis that highlights two training regimes: a fast one (V-dominated) and a stable one (G-dominated) that could explain the benefit of weight normalization. \n\n\n*Decision:*\nI am leaning for a weak reject for the following reasons: \n1. The main issue to me is that this work builds up on the work by [15] without addressing the issues risen by [12]. One important takeaway from [12] that the ‘lazy training’ regime studied might not be a desired behavior and might not happen in practice. Thus, I think that extending the work form [15] to WeightNormalization would be interesting if the phenomenons described by the theory are backed-up by some practical evidence.\nFor instance : “we believe that G-dominated convergence actually is common but that it emerges at later stages in training, after the weights have adopted their directions in the V-dominated regime and improves stability.“ is something that the authors could check in practice. \n\n2. I found the discussion regarding the phase transition a bit unclear. The magnitude of the weights v_k is treated as it was alpha the coefficient used to parametrized their initialization. Then since the phase transition depends on the magnitude of \\alpha, it is argued that the model naturally transitions as \\|v_k\\| increases (which is the case because of the discrete gradient updates).\nHowever, to me to make that phase transition argument you would need to show that the scaling of the matrices at time actually depends on the norm of the current iterate v_k(t)\n\n3. Finally, regarding the proof of Theorem 4.1 and 4.2, I found it way more clear in [12]. There is a key subtle bootstrap argument that is not explicitly stated in the proof of Theorem B.1 and B.2: The condition R’ < R  (stated in Lemma 3.4 in [12]) is the key argument that leads to a sufficient bound on the overparametrization. \nI put some remark regarding the clarity of the proof in the minor comment section. I think it would improve the quality of the work but did not have a major impact on my grade. \n\n4. The presentation is slightly misleading. The fact that the last layer is not optimized is slightly mentioned once and the author make it appear just like is was done without any loss of generality  “We consider the case where the ck’s are fixed. This does not alter the capacity of the network since the gks are trainable (ck and gk are interchangeable analytically).”. Moreover, the omission that Theorem 4.1 and 4.2 are only true with high probability makes even that fact even more unclear. I think that this aspect (last layer is fixed) should be clearly emphasized in the revision. \n\n\n\n*Questions:*\n“we believe that G-dominated convergence is common”, can you provides evidence that G-dominated and V-dominated  stages occurs the way you describe it in the discussion ? \nSame for the claim “The direction of the weights changes rapidly at the earlier stages of training when α is small, and G-dominated convergence ensues as α grows, leading to improved stability.” Particularly the link between your theory, the norm of v_k and alpha. (c.f point 2. of the decision section)\nI think that it is important to emphasize that in your work c_k are randomly sampled and then fixed (it is much more clear in [15], but I do not think that the reader should know the related work to realize that). You seem to argue that it is without loss of generality when you say “We consider the case where the ck’s are fixed. This does not alter the capacity of the network since the gks are trainable (ck and gk are interchangeable analytically).”\nbut this statement seems wrong since there is a relu activation between c_k and g_k (thus you cannot interchange negative c_k with negative g_k). Can you comment this ? \nCan you clarify the bootstrap argument mentioned in section 3. of the decision section ?  More precisely, can you justify the sentence “this contradicts one of Lemmas B.7, B.8 at time T_0.” in the proof of Theorem B.1 ? \n\n\n\n*Minor comments: (do not need to be addressed in the rebuttal)*\n- In the proof of Theorems B.1 and B.2 the statement “clearly T_0>0” should justified. This statement is true but a continuity argument that should be stated. However, the dependence in t could be easily avoided using the proof technique from [12] (Lemma 3.2) where the result is actually stated for any weight close enough to the initialization.  \n- The title of [12] has changed and one author is now missing. (since you cite the NeurIPS version you should then cite the right title with all the authors) \n- I would not say that  “smaller alpha leads to faster convergence” since the optimal step size depend on \\alpha. \n\n\n=== After rebuttal ===\nI would like to thank the author for their detailed answer.  \nI still think that experimental evidence that the phenomenon described by the theory actually happens in practice should be provided. I maintain my score. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The goal of this paper is to study the dynamics of convergence of neural network training when weight normalization is used. This is an important and interesting area. The authors focus on analyzing such effect based on a recent theoretical trend which studies neural network dynamics based on the so called neural tangent kernel (NTK). The authors show an interesting phenomena of length-direction decoupling. The reviewers raise various points some of which have been addressed by the authors in their response. Two main points not yet clearly addressed is (1) what is the novelty of the theoretical framework given existing literature and (2) what are the benefits of weight normalization based on this theory (e.g. generalization etc. ). The authors suggest improved convergence rate and overparameterization dependence (i.e. that with weight normalization the required width is decreased) as a possible advantage. However, as pointed out by reviewer 3 there are existing results which already obtain better results without weight normalization (the authors' response that this is only true in randomized scenarios is actually not accurate). Based on above I do not think the paper is ready for publication. That said I think this is a nice direction and well-written paper. I recommend the authors revise and resubmit to a future venue. Some suggestions for improvements in case this is helpful (1) improve literature review and discussion of existing results (2) identify clear benefits to weight normalization. I doubt that improving overparameterization in existing form is one of them unless you provide a lower-bound (I suspect one can eventually obtain even linear overparameterization i.e. number of parameters proportional to number of training data even in the NTK regime without weight normalization. The suggestion by the reviewer at looking at generalization might be a good direction to pursue. 

    
Decision: Reject