Year: 2019

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.

heading: 1 INTRODUCTION
text: Dynamic normalization in neural networks is a re-parametrization 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 [20] and has led to a plethora of additional normalization methods, notably including Layer Normalization (LayerNorm) [6] and Weight Normalization (WeightNorm) [28]. WeightNorm was proposed as a 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 is 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 we provide sufficient conditions on the data, initialization, and over-parameterization 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 : Rd → R parameterized by (W, c) ∈ Rm×d × Rm as
f(x; W, c) = 1√ m m∑ k=1 ckσ(w > k x). (1.1)
Here the activation function is the ReLU, σ(s) = max{s, 0} [26], m denotes the width of the second layer, and f is normalized accordingly by a factor √ m. We investigate gradient descent training with WeightNorm for (1.1), which re-parameterizes the network in terms of (V,g, c) ∈ Rm×d×Rm×Rm as
f(x; V,g, c) = 1√ m m∑ k=1 ckσ ( gk · v>k x ‖vk‖2 ) . (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 to the
L2 loss with random parameter initialization and focus on 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 [3, 15, 33, 36] along with other similar over-parameterized architectures [1, 14, 23]. An exuberant series of recent works prove that feed-forward ReLU networks converge to zero training error when trained with gradient descent from random initialization. Nonetheless, to the best of our knowledge, there are no proofs that ReLU networks trained with dynamic normalization on general data converge to a 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 over-parameterization of the networks, which allows for guaranteed descent while the gradient is 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 overparameterization, while the works of [3, 15, 27, 33, 36] analyze the finite width setting. For finitewidth over-parameterized networks, the training evolution also exhibits a kernel that takes the form of a 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 a 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-parameterization needed for provable convergence, as compared with un-normalized settings. The decomposition of the NTK also connects to observations of [12] that discuss “lazy training” which refers to a training regime where the weights of the network stay close to their initialization (see Section 6). Further, we present a 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 of 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 a 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-parameterization required for provable convergence as compared with un-normalized training.
The paper is organized as follows. In Section 2 we provide background on WeightNorm and derive key evolution dynamics of training in Section 3. We present and discuss our main results, alongside with the idea of the proof, in Section 4. We discuss related work in Section 5, and offer a discussion of our results and their implications to dynamic normalization training and “lazy training” in Section 6. Proofs are presented in the Appendix.

heading: 2 WEIGHTNORM
text: 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 U{1,−1} and write N(µ,Σ) for a Gaussian with mean µ and covariance Σ. Training points are denoted by x1 . . .xn ∈ Rd and parameters of the first layer by vk ∈ Rd. We use σ(x) := max{x, 0}, and write ‖ · ‖2, ‖ · ‖F for
the spectral and Frobenius norms for matrices. λmin(A) is used to denote the minimum eigenvalue of a matrix A and 〈·, ·〉 denotes the Euclidean inner product. For a vector v denote the `2 vector norm as ‖v‖2 and for a positive definite matrix S define the induced vector norm ‖v‖S := √ v>Sv. The projections of x onto u and u⊥ are defined as xu := uu >x
‖u‖22 , xu
⊥ := x ( I− uu >
‖u‖22
) . Denote the
indicator function of event A as 1A and for a weight vector at time t, vk(t), and data point xi we denote 1ik(t) := 1{vk(t)>xi≥ 0}.
WeightNorm procedure For a single neuron σ(w>x), WeightNorm re-parametrizes the weight w ∈ Rd in terms of v ∈ Rd, g ∈ R as
w(v, g) = g · v ‖v‖2 , σ
( g · v >x
‖v‖2
) . (2.1)
This decouples the magnitude and direction of each weight vector (referred as the “length-direction” decomposition). In comparison, for BatchNorm each output w>x is normalized according to the average statistics in a batch. We can draw the following analogy between WeightNorm and BatchNorm if the inputs xi are centered (Ex = 0) and the covariance matrix is known (Exx> = S). In this case, batch training with BatchNorm amounts to
σ ( γ · w
>x√ Ex ( w>xx>w
) ) = σ ( γ · w
>x√ w>Sw
) = σ ( γ · w >x
‖w‖S
) . (2.2)
From this prospective, WeightNorm is a special case of (2.2) with S = I [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-parameterization (2.1) of a network function f that is initially parameterized with a weight w, the gradient ∇wf relates to the gradients∇vf, ∇gf by the identities
∇vf = g
‖v‖2 (∇wf)v
⊥ , ∇gf = (∇wf)v.
This implies that∇vf · v = 0 for each input x and parameter v. For gradient flow, this orthogonality results in ‖v(0)‖2 = ‖v(t)‖2 for all t. For gradient descent (with step size η) the discretization in conjunction with orthogonality leads to increasing parameter magnitudes during training [4, 19, 28], as illustrated in Figure 1,
‖v(s+ 1)‖22 = ‖v(s)‖22 + η2‖∇vf‖22 ≥ ‖v(s)‖22. (2.3)
Problem Setup We analyze (1.1) with WeightNorm training (1.2), so that
f(x; V, c,g) = 1√ m m∑ k=1 ckσ ( gk · v>k x ‖vk‖2 ) .
We take an initialization in the spirit of [17, 28]:
vk(0) ∼ N(0, α2I), ck ∼ U{−1, 1}, and gk(0) = ‖vk(0)‖2/α. (2.4)
Where α is the variance of vk at initialization. The initialization of gk(0) is therefore taken to be independent of α. We remark that the initialization (2.4) gives the same initial output distribution as in methods that study the un-normalized network class (1.1). The parameters of the network are optimized using the training data {(x1, y1), . . . , (xn, yn)} with respect to the square loss
L(f) = 1
2 n∑ i=1 (f(xi)− yi)2 = 1 2 ‖f − y‖22, (2.5)
where f = (f1, f2, . . . , fn)> = (f(x1), f(x2), . . . , f(xn))> and y = (y1, y2, . . . , yn)>.

heading: 3 EVOLUTION DYNAMICS
text: 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 C we tackle gradient descent training with WeightNorm where the predictions’ evolution vector dfdt 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 to that parameter. The optimization dynamics give
dvk dt = − ∂L ∂vk , dgk dt = − ∂L ∂gk . (3.1)
We consider the case where we fix the top layer parameters ck during training. In the overparameterized regime, the dynamics of ck and gk turn out to be the same. To quantify convergence, we monitor the time derivative of the i-th prediction, which is computed via the chain rule as
∂fi ∂t = m∑ k=1 ∂fi ∂vk dvk dt + ∂fi ∂gk dgk dt .
Substituting (3.1) into the i-th prediction evolution and grouping terms yields
∂fi ∂t = − m∑ k=1 ∂fi ∂vk ∂L
∂vk︸ ︷︷ ︸ T iv
− m∑ k=1 ∂fi ∂gk ∂L
∂gk︸ ︷︷ ︸ T ig
. (3.2)
The gradients of fi and L with respect to vk are written explicitly as
∂fi ∂vk (t) = 1√ m ck · gk(t) ‖vk(t)‖2 · xvk(t) ⊥ i 1ik(t), ∂L ∂vk (t) = 1√ m n∑ i=1 (fi(t)− yi) ck · gk(t) ‖vk(t)‖2 x vk(t) ⊥ i 1ik(t).
Thus T iv(t) in (3.2) can be calculated as
T iv(t) = n∑ j=1 (fj(t)− yj) 1 m m∑ k=1 1jk(t)1ik(t) ( ck · gk(t) ‖vk(t)‖2 )2〈 x vk(t) ⊥ j , x vk(t) ⊥ i 〉 .
Defining the v-orthogonal Gram matrix V(t) as
Vij(t) = 1
m m∑ k=1 ( αck · gk(t) ‖vk(t)‖2 )2〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t), (3.3)
we can write T iv as
T iv(t) = n∑ j=1 Vij(t) α2 (fj(t)− yj).
Note that V(t) is the induced neural tangent kernel [21] for the parameters v of WeightNorm training. While it resembles the Gram matrix H(t) studied in [3], here we obtain a matrix that is not piece-wise
constant in v since the data points are projected onto the orthogonal component of v. We compute T ig in (3.2) analogously. The associated derivatives with respect to gk are
∂fi ∂gk (t) = 1√ m ck ‖vk(t)‖2 σ(vk(t) >xi), ∂L ∂gk (t) = 1√ m n∑ j=1 (fj(t)− yj) ck ‖vk(t)‖2 σ(vk(t) >xj),
and we obtain
T ig(t) = m∑ k=1 1 m n∑ j=1 (fj(t)− yj) ( ck ‖vk(t)‖2 )2 σ(vk(t) >xj)σ(vk(t) >xi).
Given that c2k = 1, define G(t) as
Gij(t) = 1
m m∑ k=1 σ(vk(t) >xi)σ(vk(t) >xj) ‖vk(t)‖22 (3.4)
hence we can write
T ig(t) = n∑ j=1 Gij(t)(fj(t)− yj).
Combining Tv and Tg, the full evolution dynamics are given by
df dt = −
( V(t)
α2 + G(t)
) (f(t)− y). (3.5)
Denote Λ(t) := V(t)α2 + G(t) and write df dt = −Λ(t)(f(t)− y). We note that V(0),G(0), defined in (3.3), (3.4), are independent of α: Observation 1 (α independence). For initialization (2.4) and α > 0 the Gram matrices V(0),G(0) are independent of α.
This fact is proved in Appendix A. When training the neural network in (1.1) without WeightNorm (see [3, 15, 36]) , the corresponding neural tangent kernel H(t) is defined by ∂fi∂t = ∑m k=1 ∂fi ∂wk dwk dt =
− ∑m k=1 ∂fi ∂wk ∂L ∂wk = − ∑n j=1 Hij(t)(fj − yj) and takes the form
Hij(t) = 1
m m∑ k=1 x>i xj1ik(t)1jk(t). (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(0) as in (3.3), (3.4), and (3.6) respectively. then for all α > 0,
V(0) + G(0) = H(0).
Thus, for α = 1,
∂f ∂t = −Λ(0)(f(0)− y) = −H(0)(f(0)− y).
That is, WeightNorm decomposes the NTK in each layer into a length and a direction component. We refer to this as the “length-direction decoupling” of the NTK, in analogy to (2.1). From the proposition, normalized and un-normalized training kernels initially coincide if α = 1. The utility of normalization methods can be attributed to the modified NTK Λ(t) that occurs when the WeightNorm coefficient, α, deviates from 1. For α 1 the kernel Λ(t) is dominated by G(t), and for α 1 the kernel Λ(t) is dominated by V(t). We elaborate onthe details of this in the next section. In practice, by (2.3) as training progresses, ‖vk‖2 grow monotonically, leading to larger α and a transition from the V-dominated to the G-dominated regime. In our analysis we will study the two regimes α > 1 and α < 1 in turn.

heading: 4 MAIN CONVERGENCE THEORY
text: In this section we discuss our convergence theory and main results. From the continuous flow (3.5), we observe that the convergence behavior is described by V(t) and G(t). The matrices V(t) and G(t) are positive semi-definite since they can be shown to be covariance matrices. This implies that the least eigenvalue of the evolution matrix Λ(t) = 1α2 V(t) + G(t) is bounded below by the least eigenvalue of each kernel matrix,
λmin(Λ(t)) ≥ max{λmin(V(t))/α2, λmin(G(t))}.
For finite-step gradient descent, a discrete analog of 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 easy 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 t ≥ 0,
λmin ( Λ(t) ) ≥ ω/2, with ω > 0. (4.1)
Then the change in the regression loss is written as
d dt ‖f(t)− y‖22 = 2(f(t)− y)> df(t) dt = −2(f(t)− y)>Λ(t)(f(t)− y)
(4.1) ≤ −ω‖f(t)− y‖22.
Integrating this time derivative and using the initial conditions yields
‖f(t)− y‖22 ≤ exp(−ωt)‖f(0)− y‖22,
which gives linear convergence. The focus of our proof is therefore showing that (4.1) holds throughout training.
By Observation 1 we have that V and G are independent of the WeightNorm coefficient α (α only appears in the 1/α2 scaling of Λ). This suggests that the kernel Λ(t) = 1α2 V(t) + G(t) can be split into two regimes: When α < 1 the kernel is dominated by the first term 1α2 V, and when α > 1 the kernel is dominated by the second term G. We divide our convergence result based on these two regimes.
In each regime, (4.1) holds if the corresponding dominant kernel, V(t) or G(t), maintains a positive least eigenvalue. Having a least eigenvalue that is bounded from 0 gives a convex-like property that allows us to prove convergence. To ensure that condition (4.1) is satisfied, for each regime we show that the corresponding dominant kernel is “anchored” (remains close) to an auxiliary Gram matrix which we define in the following for V and G.
Define the auxiliary v-orthogonal and v-aligned Gram matrices V∞,G∞ as
V∞ij := Ev∼N(0,α2I) 〈xv ⊥ i ,x v⊥
j 〉1ik(0)1jk(0), (4.2) G∞ij := Ev∼N(0,α2I) 〈xvi ,xvj 〉1ik(0)1jk(0). (4.3)
For now, assume that V∞ and G∞ are positive definite with a least eigenvalue bounded below by ω (we give a proof sketch below). In the convergence proof we will utilize over-parameterization to ensure that V(t),G(t) concentrate to their auxiliary versions so that they are also positive definite with a least eigenvalue that is greater than ω/2. The precise formulations are presented in Lemmas B.4 and B.5 that are relegated to Appendix B.
To prove our convergence results we make the assumption that the xis have bounded norm and are not parallel.
Assumption 1 (Normalized non-parallel data). The data points (x1, y1), . . . , (xn, yn) satisfy ‖xi‖2 ≤ 1 and for each index pair i 6= j, xi 6= β · xj for all β ∈ R \ {0}.
In order to simplify the presentation of our results, we assume that the input dimension d is not too small, whereby d ≥ 50 suffices. This is not essential for the proof. Specific details are provided in Appendix A.
Assumption 2. For data points xi ∈ Rd assume that d ≥ 50.
Both assumptions can be easily satisfied by pre-processing, e.g., normalizing and shifting the data, and adding zero coordinates if needed.
Given Assumption 1, V∞,G∞ are shown to be positive definite. Lemma 4.1. Fix training data points {(x1, y1), . . . , (xn, yn)} satisfying Assumption 1. Then the v-orthogonal and v-aligned Gram matrices V∞ and G∞, defined as in (4.2) and (4.3), are strictly positive definite. We denote the least eigenvalues λmin(V∞) =: λ0, λmin(G∞) =: µ0.
Proof sketch Here we sketch the proof of Lemma 4.1. The main idea, is the same as [15], is to regard the auxiliary matrices V∞,G∞ as the covariance matrices of linearly independent operators. For each data point xi, define φi(v) := xv ⊥
i 1{x>i v≥0}. The Gram matrix V ∞ is the covariance
matrix of {φi}i=1:n taken over Rd with the measure N(0, α2I). Hence showing that V∞ is strictly positive definite is equivalent to showing that {φi}i=1,...n are linearly independent. Unlike [15], the functionals under consideration are not piecewise constant so a different construction is used to prove independence. Analogously, a new set of operators, θi(v) := σ(xvi ), is constructed for G∞. Interestingly, each φi corresponds to dθidv . The full proof is presented in Appendix D. As already observed from evolution (3.5), different magnitudes of α lead to two distinct regimes that are discussed below. We present the main results for each regime.
V-DOMINATED CONVERGENCE
For α < 1 convergence is dominated by V(t) and λmin(Λ(t)) ≥ 1α2λmin(V(t)). We present the convergence theorem for the V-dominated regime here. Theorem 4.1 (V-dominated convergence). Suppose a neural network of the form (1.2) is initialized as in (2.4) with α ≤ 1 and that Assumptions 1,2 hold. In addition, suppose the neural network is trained via the regression loss (2.5) with targets y satisfying ‖y‖∞ = O(1). If m = Ω ( n4 log(n/δ)/λ40 ) , then with probability 1− δ,
1. For iterations s = 0, 1, . . . ,K, the evolution matrix Λ(s) satisfies λmin(Λ(s)) ≥ λ02α2 . 2. WeightNorm training with gradient descent of step-size η = O ( α2
‖V∞‖2
) converges linearly
as
‖f(s)− y‖22 ≤ (
1− ηλ0 2α2
)s ‖f(0)− y‖22.
The proof of Theorem 4.1 is presented in Appendix C. We will provide a sketch below. We make the following observations about our V-dominated convergence result.
The required over-parameterization m is independent of α. Further, the dependence of m on the failure probability is log(1/δ). This improves previous results that require polynomial dependence of order δ3. Additionally, we reduce the dependence on the sample size from n6 (as appears in [3]) to n4 log(n).
In Theorem 4.1, smaller α leads to faster convergence, since the convergence is dictated by λ0/α2. Nonetheless, smaller α is also at the cost of smaller allowed step-sizes, since η = O(α2/‖V∞‖2). The trade-off 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 is not balanced by a limitation on the step-size. The works [4, 19, 32] define an effective step-size (adaptive step-size) η′ = η/α2 to avoid the dependence of η on α.
G-DOMINATED CONVERGENCE
For α > 1 our convergence result for the class (1.2) is based on monitoring the least eigenvalue of G(t). Unlike V-dominated convergence, α does not affect the convergence speed in this regime. Theorem 4.2 (G-dominated convergence). Suppose a network of the form (1.2) is initialized as in (2.4) with α ≥ 1 and that Assumptions 1, 2 hold. In addition, suppose the neural network is trained via the regression loss (2.5) with targets y satisfying ‖y‖∞ = O(1). If m = Ω ( max { n4 log(n/δ)/α4µ40, n 2 log(n/δ)/µ20 }) , then with probability 1− δ,
1. For iterations s = 0, 1, . . . ,K, the evolution matrix Λ(s) satisfies λmin(Λ(s)) ≥ µ02 .
2. WeightNorm training with gradient descent of step-size η = O (
1 ‖Λ(t)‖
) converges linearly
as
‖f(s)− y‖22 ≤ (
1− ηµ0 2
)s ‖f(0)− y‖22.
We make the following observations about our G-dominated convergence result, and provide a proof sketch further below.
Theorem 4.2 holds for α ≥ 1 so long as m = Ω ( max { n4 log(n/δ)/µ40α 4, n2 log(n/δ)/µ20 })
. Taking α = √ n/µ0 gives an optimal required over-parameterization of order
m = Ω ( n2 log(n/δ)/µ20 ) .
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/δ, and n6 dependence in the number of samples n. In contrast to V-dominated convergence, here the rate of convergence µ0 is independent of α but the over-parameterization m is α-dependent. We elaborate on 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 [3, 13, 15, 33, 36]. The proof has the following steps: (I) We show that at initialization V(0),G(0) can be viewed as empirical estimates of averaged data-dependent kernels V∞,G∞ that are strictly positive definite under Assumption 1. (II) For each regime, we prove that the corresponding kernel remains positive definite if vk(t) and gk(t) remain near initialization for each 1 ≤ k ≤ m. (III) Given a uniformly positive definite evolution matrix Λ(t) and sufficient overparameterization we show that each neuron, vk(t), gk(t) remains close to its initialization. The full proof is presented in Appendix B for gradient flow and Appendix C 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.

heading: 5 RELATED WORK
text: 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 WeightNorm resp. suggest that dynamic normalization methods improve training by fixing the intermediate layers’ output distributions. The works of Bjorck et al. [8] and Santurkar et al. [29] argue that 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. [18] 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. [4] 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 “length-direction decoupling” perspective. The authors along with [9] analyze the linear least squares regime, with [22] presenting a 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-field analysis. The authors show that gradient instability is inevitable even with BatchNorm as 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.
Over-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 a teacher network [30], [24] and [14] (with WeightNorm). Assumptions on the data distribution are relaxed in [15] and the works that followed [3, 33, 36]. Our work is inspired by the mechanism presented in this chain of works. Wu et al. [33] extend convergence results to adaptive
step-size methods and propose AdaLoss. Recently, the global convergence of over-parameterized neural networks was also extended to deep architectures [2, 13, 37, 38]. In the over-parameterized regimes, Arora et al. [3] develop generalization properties for the networks of the form (1.1). In addition, in the context of generalization, Allen-Zhu et al. [1] illustrates good generalization for deep neural networks trained with gradient descent. Cao and Gu [10] and [11] derive generalization error bound of gradient descent and stochastic gradient descent for learning over-parameterization deep ReLU neural networks.

heading: 6 DISCUSSION
text: In this section we interpret our main results and make a connection of the convergence theory with “lazy training”.
Chizat et al. [12] analyze recent works of over-parameterized 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, we observe a new type of “lazy training” that is different from the one presented in [12] . 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 WeightNorm leads to a gradual transition from V-dominated to the G-dominated regimes. We recall that since the weights grow (see (2.3)), the WeightNorm coefficient α 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 α > 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 η = O(1/‖G(t)‖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 at the beginning of training (V-dominated 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 “length-direction decoupling” is clarified by the neural tangent kernel Λ(t) that naturally separates in our analysis into “length”, G(t), and “direction”, V(t)/α2, components. For α = 1 the decomposition initially matches un-normalized 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 as training proceeds and the magnitude of the weights grow. Our improved analysis is able to reduce the amount of over-parameterization that was needed in previous convergence works in the un-normalized setting and in the G-dominated regime, we prove convergence with a significantly lower amount of over-parameterization as compared with un-normalized training.

heading: APPENDIX
text: We present the detailed proofs of the main results of the paper below. The appendix is organized as follows. We provide proofs to 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 B,C. The proofs for gradient flow and gradient descent share the same main idea, yet the proof for gradient descent has a considerate number of additional technicalities. In Appendices D and E we prove the lemmas used in the analysis of Appendices B and C respectively.

heading: A WEIGHTNORM DYNAMICS PROOFS
text: In this section we provide proofs for Proposition 1, which describes the relation between vanilla and WeightNorm NTKs and Observation 1 of the paper.

heading: Proof of Proposition 1:
text: We would like to show that V(0) + G(0) = H(0). For each entry, consider
(V(0) + G(0))ij = 1
m m∑ k=1 〈 x vk(0) ⊥ i , xj vk(0) ⊥〉 1ik(0)1jk(0) + 1 m m∑ k=1 〈 x vk(0) i , xj vk(0) 〉 1ik(0)1jk(0).
Note that〈 xi, xj 〉 = 〈 x vk(0) i + x vk(0) ⊥ i , x vk(0) j + x vk(0) ⊥ j 〉 = 〈 x vk(0) ⊥ i , xj vk(0) ⊥〉 + 〈 x vk(0) i , xj vk(0) 〉 .
This gives
(V(0) + G(0))ij = 1
m m∑ k=1 〈 xi, xj 〉 1ik(0)1jk(0) = Hij(0)
which proves the claim.

heading: Proof of Observation 1:
text: We show that the initialization of the network is independent of α. Take α, β > 0, and for each k, initialize vαk ,v β k as
vαk (0) ∼ N(0, α2I), v β k (0) ∼ N(0, β 2I).
Then
vαk (0)
‖vαk (0)‖2 ∼
vβk (0)
‖vβk (0)‖2 ∼ Unif(Sd−1) (in distribution).
Hence the distribution of each neuron σ ( vk(0) ‖vk(0)‖2 ) at initialization is independent of α. Next for gk(0), we note that
‖vαk (0)‖2 ∼ α
β ‖vβk (0)‖2.
Initializing gαk (0), g β k (0) as in (2.4),
gαk (0) = ‖vk(0)‖2
α , gβk (0) = ‖vk(0)‖2 β ,
gives
gαk (0), g β k (0) ∼ χd, and
gαk (0)v α k (0) ‖vαk (0)‖2 ∼ gβk (0)v β k (0) ‖vβk (0)‖2 ∼ N(0, I),
for all α, β. This shows that the network initialization is independent of α and is equivalent to the initialization of the un-normalized setting. Similarly, inspecting the terms in the summands of V(0),G(0) shows that they are also independent of α. For
Vij(0) = 1
m m∑ k=1 1ik(0)1jk(0) ( αck · gk(0) ‖vk(0)‖2 )2〈 x vk(0) ⊥ i , x vk(0) ⊥ j 〉
the terms 1ik(0), x vk(0)
⊥
i are independent of scale, and the fraction in the summand is identically 1. G(0) defined as
Gij(0) = 1
m m∑ k=1 1ik(0)1jk(0) 〈 x vk(0) i , x vk(0) j 〉 is also invariant of scale since the projection onto a vector direction vk(0) is independent of scale.

heading: B CONVERGENCE PROOF FOR GRADIENT FLOW
text: In this section we derive the convergence results for gradient flow.
The main results are analogous to Theorems 4.1, 4.2 but by considering gradient flow instead of gradient descent the proofs are simplified. In Appendix C we prove the main results from Section 4 (Theorem 4.1, 4.2) for finite step gradient descent.
We state our convergence results for gradient flow. Theorem B.1 (V-dominated convergence). Suppose a network from the class (1.2) is initialized as in (2.4) with α < 1 and that assumptions 1,2 hold. In addition, suppose the neural network is trained via the regression loss (2.5) with target y satisfying ‖y‖∞ = O(1). Then if m = Ω ( n4 log(n/δ)/λ40 ) , WeightNorm training with gradient flow converges at a linear rate, with probability 1− δ, as
‖f(t)− y‖22 ≤ exp(−λ0t/α2)‖f(0)− y‖22.
This theorem is analogous to Theorem 4.1 but since here, the settings are of gradient flow there is no mention of the step-size. It is worth noting that smaller α leads to faster convergence and appears to not affect the other hypotheses of the flow theorem. This “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 is 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 1, 2 hold. In addition, suppose the neural network is trained on the regression loss (2.5) with target y satisfying ‖y‖∞ = O(1). Then if m = Ω ( max { n4 log(n/δ)/α4µ40, n 2 log(n/δ)/µ20 })
, WeightNorm training with gradient flow converges at a linear rate, with probability 1− δ, as
‖f(t)− y‖22 ≤ exp(−µ0t)‖f(0)− y‖22.

heading: B.1 PROOF SKETCH
text: To prove the results above we follow the steps introduced in the proof sketch of Section 4. The main idea of the proofs for V and G dominated convergence are analogous and a lot of the proofs are based of Du et al. [15]. We show that in each regime, we attain linear convergence by proving that the least eigenvalue of the evolution matrix Λ(t) is strictly positive. For the V-dominated regime we lower bound the least eigenvalue of Λ(t) as λmin(Λ(t)) ≥ λmin(V(t))/α2 and in the G-dominated regime we lower bound the least eigenvalue as λmin(Λ(t)) ≥ λmin(G(t)). The main part of the proof is showing that λmin(V(t)), λmin(G(t)) stay uniformly positive. We use several lemmas to show this claim.
In each regime, we first show that at initialization the kernel under consideration, V(0) or G(0), has a positive least eigenvalue. This is shown via concentration to an an auxiliary kernel (Lemmas B.1, B.2), and showing that the auxiliary kernel is also strictly positive definite (Lemma 4.1). Lemma B.1. Let V(0) and V∞ be defined as in (3.3) and (4.2), assume the network width m satisfies m = Ω (n2 log(n/δ) λ20 ) . Then with probability 1− δ,
‖V(0)−V∞‖2 ≤ λ0 4 .
Lemma B.2. Let G(0) and G∞ be defined as in (3.4) and (4.3), assume m satisfies m = Ω (n2 log(n/δ)
µ20
) . Then with probability 1− δ,
‖G(0)−G∞‖2 ≤ µ0 4 .
After showing that V(0),G(0) have a positive least-eigenvalue we show that V(t),G(t) maintain this positive least eigenvalue during training. This part of the proof depends on the over-parameterization of the networks. The main idea is showing that if the individual parameters vk(t), gk(t) do not change too much during training, then V(t),G(t) remain close enough to V(0),G(0) so that they are still uniformly strictly positive definite. We prove the results for V(t) and G(t) separately since each regime imposes different restrictions on the trajectory of the parameters.
For now, in Lemmas B.3, B.4, B.5, we make assumptions on the parameters of the network not changing “too much”; later we show that this holds and is the result of over-parameterization. Specifically, over-parameterization ensures that the parameters stay at a small maximum distance from their initialization.
V-dominated convergence To prove the least eigenvalue condition on V(t), we introduce the surrogate Gram matrix V̂(t) defined entry-wise as
V̂ij(t) = 1
m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t). (B.1)
This definition aligns with V(t) if we replace the scaling term (αckgk(t) ‖vk(t)‖2 )2 in each term in the sum Vij(t) by 1.
To monitor V(t) − V(0) we consider V̂(t) − V(0) and V(t) − V̂(t) in Lemmas B.3 and B.4 respectively: Lemma B.3 (Rectifier sign-changes). Suppose v1(0), . . . ,vk(0) are sampled i.i.d. as (2.4). In addition assume we have m = Ω ( (m/δ)1/dn log(n/δ) αλ0 ) and ‖vk(t)− vk(0)‖2 ≤ αλ096n(m/δ)1/d =: Rv. Then with probability 1− δ,
‖V̂(t)−V(0)‖2 ≤ λ0 8 .
Lemma B.4. Define
Rg = λ0
48n(m/δ)1/d , Rv = αλ0 96n(m/δ)1/d . (B.2)
Suppose the conditions of Lemma B.3 hold, and that ‖vk(t)−vk(0)‖2 ≤ Rv , ‖gk(t)−gk(0)‖2 ≤ Rg for all 1 ≤ k ≤ m. Then with probability 1− δ,
‖V(t)−V(0)‖2 ≤ λ0 4 .
G-dominated convergence We ensure that G(t) stays uniformly positive definite if the following hold. Lemma B.5. Given v1(0), . . . ,vk(0) generated i.i.d. as in (2.4), suppose that for each k, ‖vk(t)− vk(0)‖2 ≤ √ 2παµ0
8n(m/δ)1/d =: R̃v , then with probability 1− δ,
‖G(t)−G(0)‖2 ≤ µ0 4 .
After deriving sufficient conditions to maintain a positive least eigenvalue at training, we restate the discussion of linear convergence from Section 4 formally.
Lemma B.6. Consider the linear evolution dfdt = − ( G(t) + V(t)α2 ) (f(t)− y) from (3.5). Suppose
that λmin ( G(t) + V(t)α2 ) ≥ ω2 for all times 0 ≤ t ≤ T . Then
‖f(t)− y‖22 ≤ exp(−ωt)‖f(0)− y‖22 for all times 0 ≤ t ≤ T .
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 ≤ t ≤ T , λmin ( G(t) + 1α2 V(t) ) ≥ ω2 and |gk(t)− gk(0)| ≤
Rg ≤ 1/(m/δ)1/d. Then with probability 1− δ over the initialization
‖vk(t)− vk(0)‖2 ≤ 4 √ n‖f(0)− y‖2 αω √ m =: R′v (B.3)
for each k and all times 0 ≤ t ≤ T . Lemma B.8. Suppose that for all 0 ≤ t ≤ T , λmin ( G(t) + 1α2 V(t) ) ≥ ω2 . Then with probability
1− δ over the initialization
|gk(t)− gk(0)| ≤ 4 √ n‖f(0)− y‖2√
mω =: R′g
for each k and all times 0 ≤ t ≤ T.
The distance of the parameters from initialization depends on the convergence rate (which depends on λmin(Λ(t))) and the width of the network m. We therefore are able to find sufficiently large m 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 is initialized as (2.4) and that y ∈ Rn has bounded entries |yi| ≤M . Then ‖f(0)− y‖2 ≤ C √ n log(n/δ) for some absolute constant C > 0.
Lemma B.10 (Failure over initialization). Suppose v1(0), . . . ,vk(0) are initialized i.i.d. as in (2.4) with input dimension d. Then with probability 1− δ,
max k∈[m]
1 ‖vk(0)‖2 ≤ (m/δ) α
1/d
.
In addition by (2.3), for all t ≥ 0, with probability 1− δ,
max k∈[m]
1 ‖vk(t)‖2 ≤ (m/δ) α
1/d
.
Remark (Assumption 2). Predominately, machine learning applications reside in the high dimensional regime with d ≥ 50. Typically d 50. This therefore leads to an expression (m/δ)1/d that is essentially constant. For example, if d = 50, for maxk∈[m] 1‖vk(0)‖2 ≥ 10, one would need m/δ ≥ 1080 (the tail of χ2d also has a factor of (d/2)! · 2d/2 which makes the assumption even milder). The term (m/δ)1/d therefore may be taken as a constant for practicality,
max k∈[m]
1 ‖vk(0)‖2 ≤ C α .
While we make Assumption 2 when presenting our final bounds, for transparency we do not use Assumption 2 during our analysis and apply it only when we present the final over-parameterization results to avoid the overly messy bound. Without the assumption the theory still holds yet the over-parameterization bound worsens by a power 1 + 1/(d− 1). This is since the existing bounds can be modified, replacing m with m1− 1 d .

heading: Proof of Theorem B.1:
text: Note that m = Ω ( n4 log(n/δ)/λ40 ) implies that Lemma B.1 holds. Further since the gradient flow updates are continous (since the time derivative with respect to each parameter may be bounded), there exist a small time T for which the parameters are bounded from initialization for 0 ≤ t ≤ T and for all 1 ≤ k ≤ m,
‖vk(t)− vk(0)‖2 ≤ Rv, |gk(t)− gk(0)| ≤ Rg.
The bounded trajectory above, along with the over-parameterization, ensures that with probability 1− δ over the initialization that Lemma B.4 holds and that
λmin
( G(t) + 1
α2 V(t)
) ≥ λmin(V(t))/α2 ≥
λ0 2α2
for times 0 ≤ t ≤ T . The condition on the eigenvalue of the evolution matrix along with the bounded trajectory of gk implies that Lemmas B.7, B.8 hold for at least times 0 ≤ t < T . Define T0 to be the first failure point of either Lemmas B.8, B.7, we have that T0 ≥ T > 0. For 0 ≤ t < T0, by substituting m = Ω ( n4 log(n/δ)/λ40 ) and using the bound on ‖f(0)− y‖2 of Lemma B.9, a direct calculation utilizing Lemma B.7 shows that
‖vk(t)− vk(0)‖2 B.7 ≤ α √ n‖f(0)− y‖2√
mλ0 ≤ Rv.
Similarly by Lemma B.8 m ensures that
|gk(t)− gk(0)| B.8 ≤ α 2 √ n‖f(0)− y‖2√
mλ0 ≤ Rg.
The over-parameterization of m implies that the parameter trajectories stay close enough to initialization to satisfy the hypotheses of Lemmas B.3, B.4 and that λmin(Λ(t)) ≥ λmin(V(t))/α2 ≥ λ02α2 at time T0. This implies that Lemmas B.7, B.8 both hold at time T0 which contradicts the definition of T0. Therefore we conclude that Lemmas B.7, B.8 hold for t > 0 which implies that Lemma B.4 holds for t > 0 hence Lemma B.6 guarantees linear convergence.
Here we consider the case where the convergence is dominated by G. This occurs when α > 1. Proof of Theorem B.2: Similarly to Theorem B.1, we note that m = Ω ( max { n4 log(n/δ)/α4µ40, n 2 log(n/δ)/µ20 })
implies 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 ≤ k ≤ m
‖vk(t)− vk(0)‖2 ≤ R̃v.
The bounded trajectory above, along with the over-parameterization, ensures that with probability 1− δ over the initialization that Lemma B.5 holds and that
λmin
( G(t) + 1
α2 V(t)
) ≥ λmin(G(t))/α2 ≥
µ0 2
for times 0 ≤ t ≤ T . The condition on the eigenvalue of the evolution matrix along with the bounded trajectory of gk implies that Lemmas B.7, B.8 hold for at least times 0 ≤ t < T . Define T0 to be the first failure point of either Lemmas B.8, B.7, we have that T0 ≥ T > 0. For 0 ≤ t < T0, by substituting m = Ω ( max { n4 log(n/δ)/α4µ40, n 2 log(n/δ)/µ20 })
and using the bound on ‖f(0)− y‖2 of Lemma B.9, a direct calculation utilizing Lemma B.7 shows that
‖vk(t)− vk(0)‖2 B.7 ≤ 4 √ n‖f(0)− y‖2 αµ0 √ m
B.9 ≤ Cn √ log(n/δ)
αµ0 √ m
≤ R̃v.
Similarly by Lemma B.8 m ensures that
|gk(t)− gk(0)| B.8 ≤ √ n‖f(0)− y‖2√
mµ0 ≤ Rg.
The over-parameterization of m implies that the parameter trajectories stay close enough to initialization to satisfy the hypotheses of Lemmas B.5 and that λmin(Λ(t)) ≥ λmin(G(t))/α2 ≥ µ0/2 at time T0. This implies that Lemmas B.7, B.8 both hold at time T0 which contradicts the definition of T0. Therefore we conclude that Lemmas B.7, B.8 hold for t > 0 which implies that Lemma B.5 holds for t > 0 hence Lemma B.6 guarantees linear convergence with rate µ0/2.
Note that if α is large, the required complexity on m is reduced. Taking α = Ω( √ n/µ0) gives the improved bound
m = Ω
( n2 log (n/δ)
µ20
) .

heading: C FINITE STEP-SIZE TRAINING
text: 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 (1.2). We first introduce some needed notation.
Define Si(R) as the set of indices k ∈ [m] corresponding to neurons that are close to the activity boundary of ReLU at initialization for a data point xi,
Si(R) := {k ∈ [m] : ∃ v with ‖v − vk(0)‖2 ≤ R and 1ik(0) 6= 1{v>xi ≥ 0}}.
We upper bound the cardinality of |Si(R)| with high probability. Lemma C.1. With probability 1− δ, we have that for all i
|Si(R)| ≤ √
2mR√ πα + 16 log(n/δ) 3 .
Next we review some additional lemmas needed for the proof of Theorems 4.1, 4.2. Analogous to Lemmas B.7, B.8, we bound the finite-step parameter trajectories in Lemmas C.2, C.3. Lemma C.2. Suppose the norm of ‖f(s) − y‖22 decreases linearly for some convergence rate ω during gradient descent training for all iteration steps s = 0, 1, . . . ,K with step-size η as ‖f(s)− y‖22 ≤ (1− ηω 2 ) s‖f(0)− y‖22 . Then for each k we have
|gk(s)− gk(0)| ≤ 4 √ n‖f(0)− y‖2√
mω
for iterations s = 0, 1, . . . ,K + 1.
Lemma C.3. Under the assumptions of Lemma C.2, suppose in addition that |gk(s) − gk(0)| ≤ 1/(m/δ)1/d for all iterations steps s = 0, 1, . . .K . Then for each k,
‖vk(s)− vk(0)‖2 ≤ 8 √ n‖f(0)− y‖2 α √ mω
for s = 0, 1, . . . ,K + 1.
To prove linear rate of convergence we analyze the s+ 1 iterate error ‖f(s+ 1)− y‖2 relative to that of the s iterate, ‖f(s)− y‖2. Consider the network’s coordinate-wise difference in output between iterations, fi(s+ 1)− fi(s), writing this explicitly based on gradient descent updates yields
fi(s+ 1)− fi(s) = 1√ m m∑ k=1 ckgk(s+ 1) ‖vk(s+ 1)‖2 σ(vk(s+ 1) >xi)− ckgk(s) ‖vk(s)‖2 σ(vk(s) >xi). (C.1)
We now decompose the summand in (C.1) looking at the updates in each layer, fi(s+ 1)− fi(s) = ai(s) + bi(s) with
ai(s) = 1√ m m∑ k=1 ckgk(s+ 1) ‖vk(s+ 1)‖2 σ(vk(s) >xi)− ckgk(s) ‖vk(s)‖2 σ(vk(s) >xi),
bi(s) = 1√ m m∑ k=1 ckgk(s+ 1) ‖vk(s+ 1)‖2 ( σ(vk(s+ 1) >xi)− σ(vk(s)>xi) ) .
Further, each layer summand is then subdivided into a primary term and a residual. ai(s), corresponding to the difference in the first layer (
ckgk(s+1) ‖vk(s+1)‖2 − ckgk(s) ‖vk(s)‖2 ) , is subdivided into aIi (s) and a II i (s)
as follows:
aIi (s) = 1√ m m∑ k=1 ( ckgk(s+ 1) ‖vk(s)‖2 − ckgk(s) ‖vk(s)‖2 ) σ(vk(s) >xi), (C.2)
aIIi (s) = 1√ m m∑ k=1 ( ckgk(s+ 1) ‖vk(s+ 1)‖2 − ckgk(s+ 1) ‖vk(s)‖2 ) σ(vk(s) >xi). (C.3)
bi(s) is sub-divided based on the indices in the set Si that monitor the changes of the rectifiers. For now, Si = Si(R) with R to be set later in the proof. bi(s) is partitioned to summands in the set Si and the complement set,
bIi (s) = 1√ m ∑ k 6∈Si ckgk(s+ 1) ‖vk(s+ 1)‖2 ( σ(vk(s+ 1) >xi)− σ(vk(s)>xi) ) ,
bIIi (s) = 1√ m ∑ k∈Si ckgk(s+ 1) ‖vk(s+ 1)‖2 ( σ(vk(s+ 1) >xi)− σ(vk(s)>xi) ) .
With this sub-division in mind, the terms corresponding to convergence are aI(s),bI(s) whereas aII(s),bII(s) are residuals that are the result of discretization. We define the primary and residual vectors p(s), r(s) as
p(s) = aI(s) + bI(s)
η , r(s) =
aII + bII(s)
η . (C.4)
If the residual r(s) is sufficiently small and p(s) may be written as p(s) = −Λ(s)(f(s) − y) for some iteration dependent evolution matrix Λ(s) that has
λmin(Λ(s)) = ω/2 (C.5)
for ω > 0 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-parameterization (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 step-size η, define the residual r(s) as in (C.4) and take ω as in (C.5). We specify the
“residual condition” at iteration s as
‖r(s)‖2 ≤ cω‖f(s)− y‖2 for a sufficiently small constant c > 0 independent of the data or initialization.
Here we present Theorem C.1 which is the backbone of Theorems 4.1 and 4.2. Theorem C.1. Suppose a network from the class (1.2) is trained via WeightNorm gradient descent with an evolution matrix Λ(s) as in (C.5) satisfying λmin(Λ(s)) ≥ ω/2 for s = 0, 1, . . .K. In addition if the data meets assumptions 1, 2, the step-size η of gradient descent satisfies η ≤ 13‖Λ(s)‖2 and that the residual r(s) defined in (C.4) satisfies Property 1 for s = 0, 1, . . . ,K then we have that
‖f(s)− y‖22 ≤ (
1− ηω 2
)s ‖f(0)− y‖22
for s = 0, 1, . . . ,K.

heading: Proof of Theorem C.1:
text: 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 we described above and consider again the difference between consecutive terms f(s+ 1)− f(s),
fi(s+ 1)− fi(s) = 1√ m m∑ k=1 ckgk(s+ 1) ‖vk(s+ 1)‖2 σ(vk(s+ 1) >xi)− ckgk(s) ‖vk(s)‖2 σ(vk(s) >xi). (C.6)
Following the decompostion introduced in (C.2), aIi (s) is re-written in terms of G(s),
aIi (s) = 1√ m m∑ k=1 ck ‖vk(s)‖2 ( − η ∂L(s) ∂gk ) σ(vk(s) >xi)
= − η m m∑ k=1 ck ‖vk(s)‖2 n∑ j=1 (fj(s)− yj) ck ‖vk(s)‖2 σ(v>k (s)xj)σ(v > k (s)xi)
= −η n∑ j=1 (fj(s)− yj) 1 m m∑ k=1 (ck) 2σ ( vk(s) >xi ‖vk(s)‖2 ) σ ( vk(s) >xj ‖vk(s)‖2 )
= −η n∑ j=1 (fj(s)− yj)Gij(s),
where the first equality holds by the gradient update rule gk(s + 1) = gk(s) − η∇gkL(s). In this proof we also derive bounds on the residual terms of the decomposition which we will aid us in the proofs of Theorems 4.1, 4.2. aIi (s) is the primary term of ai(s), now we bound the residual term aIIi (s). Recall a II i (s) is written as
aIIi (s) = 1√ m m∑ k=1 ( ckgk(s+ 1) ‖vk(s+ 1)‖2 − ckgk(s+ 1) ‖vk(s)‖2 ) σ(vk(s) >xi),
which corresponds to the difference in the normalization in the second layer. Since ∇vkL(s) is orthogonal to vk(s) we have that
ckgk(s+ 1)
( 1
‖vk(s+ 1)‖2 − 1 ‖vk(s)‖2
) σ(vk(s) >xi)
= ckgk(s+ 1)
( 1√
‖vk(s)‖22 + η2‖∇vkL(s)‖22 − 1 ‖vk(s)‖2
) σ(vk(s) >xi)
= −ckgk(s+ 1)η2‖∇vkL(s)‖22
‖vk(s+ 1)‖2‖vk(s)‖2(‖vk(s)‖2 + ‖vk(s+ 1)‖2) σ(vk(s)
>xi)
≤ −ckgk(s+ 1)η 2‖∇vkL(s)‖22
2‖vk(s)‖2‖vk(s+ 1)‖2 σ
( vk(s)
>xi ‖vk(s)‖2
) ,
where the first equality above is by completing the square, and the inequality is due to the increasing magnitudes of ‖vk(s)‖2. Since 0 ≤ σ ( vk(s) >xi
‖vk(s)‖2
) ≤ 1, the above can be bounded as
|aIIi (s)| ≤ 1√ m m∑ k=1 ∣∣∣∣gk(s+ 1)η2‖∇vkL(s)‖222‖vk(s)‖2‖vk(s+ 1)‖2 ∣∣∣∣
≤ 1√ m m∑ k=1
η2 ( 1 +Rg(m/δ) 1/d )3 n‖f(s)− y‖22(m/δ)1/d
α4m = η2n ( 1 +Rg(m/δ) 1/d )3‖f(s)− y‖22(m/δ)1/d
α4 √ m
. (C.7)
The second inequality is the result of applying the bound in equation (E.1) on the gradient norm ‖∇vkL(s)‖2 and using Lemma B.10. Next we analyze bi(s) and sub-divide it based on the sign changes of the rectifiers. Define the set Si := Si(R) as in Lemma C.1 with R taken to be such that ‖vk(s + 1) − vk(0)‖2 ≤ R for all k. Take bIIi (s) as the sub-sum of bi(s) with indices k from the set Si.
bIi (s) corresponds to the sub-sum with the remaining indices. By the definition of Si, for k 6∈ Si we have that 1ik(s+ 1) = 1ik(s). This enables us to factor 1ik(s) and represent bIi (s) as a Gram matrix similar to V(s) with a correction term from the missing indices in Si.
bIi (s) = − 1√ m ∑ k 6∈Si ( ckgk(s+ 1) ‖vk(s+ 1)‖2 )( η 〈 ∇vkL(s), xi 〉) 1ik(s)
= − η m ∑ k 6∈Si ( ckgk(s+ 1) ‖vk(s+ 1)‖2 )( ckgk(s) ‖vk(s)‖2 ) n∑ j=1 (fj(s)− yj)1ik(s)1jk(s) 〈 x vk(s) ⊥ j , xi 〉 .
Note that 〈 x vk(s) ⊥ j , xi 〉 = 〈 x vk(s) ⊥ j , x vk(s) ⊥ i 〉 therefore,
bIi (s) = − η
m ∑ k 6∈Si ( ckgk(s+ 1) ‖vk(s+ 1)‖2 )( ckgk(s) ‖vk(s)‖2 ) n∑ j=1 (fj(s)− yj)1ik(s)1jk(s) 〈 x vk(s) ⊥ j , x vk(s) ⊥ i 〉 .
Define Ṽ(s) as
Ṽij(s) = 1
m m∑ k=1 ( αckgk(s+ 1) ‖vk(s+ 1)‖2 )( αckgk(s) ‖vk(s)‖2 ) 1jk(s)1ik(s) 〈 x vk(s) ⊥ i , x vk(s) ⊥ j 〉 .
This matrix is identical to V(s) except for a modified scaling term ( c2kgk(s+1)gk(s) ‖vk(s)‖2‖vk(s+1)‖2 ) . We note however that
min
(( ckgk(s)
‖vk(s)‖2
)2 , ( ckgk(s+ 1)
‖vk(s+ 1)‖2
)2) ≤ ( ckgk(s)
‖vk(s)‖2
)( ckgk(s+ 1)
‖vk(s+ 1)‖2
)
≤ max
(( ckgk(s)
‖vk(s)‖2
)2 , ( ckgk(s+ 1)
‖vk(s+ 1)‖2
)2)
because gk(s), c2k are positive. Hence the matrix Ṽ(s) satisfies the hypothesis of Lemma B.4 entirely. We write bIi (s) as
bIi (s) = −η/α2 n∑ j=1 (fj(s)− yj)(Ṽij(s)− Ṽ⊥ij(s)),
where we have defined
Ṽ⊥ij(s) = 1
m ∑ k∈Si ( αckgk(s) ‖vk(s)‖2 )( αckgk(s+ 1) ‖vk(s+ 1)‖2 ) 1ik(s)1jk(s) 〈 x vk(s) ⊥ i , x vk(s) ⊥ j 〉 . (C.8)
We then bound the magnitude of each entry Ṽ⊥ij(s):
Ṽ⊥ij(s) = 1
m ∑ k∈Si ( αckgk(s) ‖vk(s)‖2 )( αckgk(s+ 1) ‖vk(s+ 1)‖2 ) 1ik(s)1jk(s) 〈 x vk(s) ⊥ i , x vk(s) ⊥ j 〉 ≤ (1 +Rg(m/δ)
1/d)2|Si| m . (C.9)
Lastly we bound the size of the residual term bIIi (s), |bIIi (s)| = ∣∣∣∣− 1√m ∑
k∈Si
ckgk(s+ 1)
‖vk(s+ 1)‖2
( σ(vk(s+ 1) >xi)− σ(vk(s)>xi) )∣∣∣∣
≤ gk(s+ 1)η|Si| · ‖∇vkL(s)‖2√ m‖vk(s+ 1)‖2
≤ η|Si|(1 + (m/δ) 1/dRg)‖∇vkL(s)‖2 α √ m .
Where we used the Lipschitz continuity of σ in the first bound, and took Rg > 0 that satisfies |gk(s+ 1)− gk(0)| ≤ Rg in the second inequality. Applying the bound (E.1),
|bIIi (s)| ≤ η|Si|
√ n(1 +Rg(m/δ)
1/d)2‖f(s)− y‖2 α2m . (C.10)
The sum f(s + 1) − f(s) = aI(s) + aII(s) + bI(s) + bII(s) is separated into the primary term ηp(s) = aI(s) + bI(s) and the residual term ηr(s) = aII(s) + bII(s) which is a result of the discretization. With this, the evolution matrix Λ(s) in (C.5) is re-defined as
Λ(s) := G(s) + Ṽ(s)− Ṽ⊥(s)
α2
and
f(s+ 1)− f(s) = −ηΛ(s)(f(s)− y) + ηr(s).
Now we compare ‖f(s+ 1)− y‖22 with ‖f(s)− y‖22,
‖f(s+ 1)− y‖22 =‖f(s+ 1)− f(s) + f(s)− y‖22 =‖f(s)− y‖22 + 2 〈 f(s+ 1)− f(s), f(s)− y 〉 + 〈 f(s+ 1)− f(s), f(s+ 1)− f(s) 〉 .
Substituting
f(s+ 1)− f(s) = aI(s) + bI(s) + aII(s) + bII(s) = −ηΛ(s)(f(s)− y) + ηr(s)
we obtain
‖f(s+ 1)− y‖22 =‖f(s)− y‖22 + 2(−ηΛ(s)(f(s)− y) + ηr(s))>(f(s)− y) + η2(Λ(s)(f(s)− y)− r(s))>(Λ(s)(f(s)− y)− r(s)) ≤‖f(s)− y‖22 + (f(s)− y)>(−ηΛ(s) + η2Λ2(s))(f(s)− y)
+ ηr(s)>(I− ηΛ(s))(f(s)− y) + η2‖r(s)‖22.
Now as λmin(Λ(s)) ≥ ω/2 and η = 13‖Λ(s)‖2 , we have that
(f(s)− y)>(−ηΛ(s) + η2Λ2(s))(f(s)− y) = −η(f(s)− y)>(I− ηΛ(s))Λ(s)(f(s)− y) ≤ −3ηω 8 ‖f(s)− y‖22.
Next we analyze the rest of the terms and group them as q(s),
q(s) := ηr(s)>(I− ηΛ(s))(f(s)− y) + η2‖r(s)‖22 ≤ η‖r(s)‖2‖f(s)− y‖2 + η2‖r(s)‖22.
By Property 1 we have
q(s) ≤ ηcω‖f(s)− y‖22(1 + ηcω) ≤ 2cηω‖f(s)− y‖22,
so that
q(s) ≤ c′ηω‖f(s)− y‖22,
for c′ sufficiently small. Substituting, the difference f(s+ 1)− y is bounded as
‖f(s+ 1)− y‖22 ≤ ‖f(s)− y‖22 − ηω(1− η‖Λ(s)‖2)‖f(s)− y‖22 + c′ηω‖f(s)− y‖22 ≤ (1− ηω(1− η‖Λ(s)‖2) + c′ηω)‖f(s)− y‖22 ≤ (1− ηω/2)‖f(s)− y‖22,
for well chosen absolute constant c. Hence for each s = 0, 1, . . . ,K,
‖f(s+ 1)− y‖22 ≤ (1− ηω/2)‖f(s)− y‖22 so the prediction error converges linearly.
In what comes next we prove the necessary conditions for Property 1, and define the appropriate ω for the V and G dominated regimes, in order to show λmin(Λ(s)) ≥ ω/2.

heading: Proof of Theorem 4.1:
text: To prove convergence we would like to apply Theorem C.1 with ω/2 = λ02α2 . To do so we need to show thatm = Ω ( n4 log(n/δ)/λ40 ) guarantees that Property 1 holds and that λmin(Λ(s)) ≥ λ0/2α2. For finite-step gradient training, take
Rv = αλ0
192n(m/δ)1/d , Rg = λ0 96n(m/δ)1/d . (C.11)
Note the residual r(s) and the other terms bI(s),bII(s) depend on the sets Si that we define here using Rv . We make the assumption that ‖vk(s)−vk(0)‖2 ≤ Rv and |gk(s)− gk(0)| ≤ Rg for all k and that s = 0, 1, . . .K+ 1, this guarantees that bI(s) and Λ(s) are well defined. Applying Lemmas B.1, B.4 with Rv, Rg defined above, we have that λmin(Ṽ(s)) ≥ 5λ08 . Then the least eigenvalue of the evolution matrix Λ(s) is bounded below
λmin(Λ(s)) = λmin
( G(s) +
Ṽ(s)− Ṽ⊥(s) α2 ) ≥ λmin ( Ṽ(s)− Ṽ⊥(s)
α2 ) = λmin(Ṽ(s)− Ṽ⊥(s))
α2
≥ 5λ0 8α2 − ‖Ṽ ⊥(s)‖2 α2 .
The first inequality holds since G(s) 0 and the last inequality is since λmin(Ṽ(s)) ≥ 5λ08 .
To show λmin(Λ(s)) ≥ λ02α2 we bound ‖Ṽ ⊥(s)‖2 ≤ λ08 . By (C.9), we have
|Ṽ⊥ij(s)| ≤ (1 +Rg(m/δ) 1/d)|Si| m
≤ (1 +Rg(m/δ)1/d) (√
2R̃v√ πα + 16 log(n/δ) 3m
) .
Substituting Rv, Rg and m, a direct calculation shows that
|Ṽ⊥ij(s)| ≤ λ0 8n ,
which yields
‖Ṽ⊥(s)‖2 ≤ ‖Ṽ⊥(s)‖F ≤ λ0 8 .
Hence λmin(Λ(s)) ≥ λ02α2 for iterations s = 0, 1, . . .K.
We proceed by showing the residual r(s) satisfies property 1. Recall r(s) is written as
r(s) = aII(s)
η +
bII(s)
η .
and Property 1 states that ‖r(s)‖2 ≤ cηλ0α2 ‖f(s)− y‖2 for sufficiently small absolute constant c < 1. This is equivalent to showing that both aII(s), bII(s) satisfy
‖aII(s)‖2 ≤ cηλ0 α2 ‖f(s)− y‖2, (C.12)
‖bII(s)‖2 ≤ cηλ0 α2 ‖f(s)− y‖2. (C.13)
We consider each term at turn. By (C.10),
‖bII(s)‖2 ≤ √ nmax
i bIIi (s)
≤ max i ηn(1 +Rg(m/δ) 1/d)2|Si|‖f(s)− y‖2 α2m ≤ CmRvηn‖f(s)− y‖2 α2m ≤ λ0η‖f(s)− y‖2 α2 · nCRv.
In the above we used the values of Rv, Rg defined in (C.11) and applied Lemma C.1 in the third inequality. Taking m = Ω ( n4 log(n/δ)/λ40 ) with large enough constant yields
‖bII(s)‖2 ≤ cλ0η‖f(s)− y‖2
α2 .
Next we analogously bound ‖aII(s)‖ via the bound (C.7),
‖aII(s)‖2 ≤ √ nmax
i aIIi (s)
≤ η2n3/2
( 1 +Rg(m/δ) 1/d )3‖f(s)− y‖22(m/δ)1/d
α4 √ m
≤ ηλ0‖f(s)− y‖2 α2
· η ( 1 +Rg(m/δ) 1/d )3 n3/2‖f(s)− y‖2(m/δ)1/d
λ0α2 √ m
≤ ηλ0‖f(s)− y‖2 α2 · η α2 · Cn2
√ log(n/δ) λ0 √ m
≤ cηω‖f(s)− y‖2.
In the above we applied Lemma B.9 once again. The last inequality holds since m = Ω(n4 log(n/δ)/λ40) and η = O ( α2
‖V(s)‖2
) , hence r(s) satisfies Property 1. Now since Theo-
rem C.1 holds with ω = λ0/α2 we have that the maximum parameter trajectories are bounded as ‖vk(s)−vk(0)‖2 ≤ Rv and ‖gk(s)− gk(0)‖ ≤ Rg for all k and every iteration s = 0, 1, . . . ,K+ 1 via Lemmas C.2, C.3.
To finish the proof, we apply the same contradiction argument as in Theorems B.1, B.2, taking the first iteration s = K0 where one of Lemmas C.2, C.3 does not hold. We note that K0 > 0 and by the definition of K0, for s = 0, 1, . . . ,K0 − 1 the Lemmas C.2, C.3 hold which implies that by the argument above we reach linear convergence in iteration s = K0. This contradicts one of Lemmas C.2, C.3 which gives the desired contradiction, so we conclude that we have linear convergence with rate λ0/2α2 for all iterations.

heading: Proof of Theorem 4.2:
text: For G-dominated convergence, we follow the same steps as in the proof of Theorem 4.1. We redefine
the trajectory constants for the finite step case
R̃v :=
√ 2παµ0
64n(m/δ)1/d , Rg := µ0 48n(m/δ)1/d .
To use Theorem C.1 we need to show that m = Ω ( n4 log(n/δ)/α4µ40 ) guarantees Property 1, and that λmin(Λ(s)) ≥ µ0/2. We again note that the residual r(s) and bI(s),bII(s) depend on the sets Si that we define here using R̃v above as Si := Si(R̃v).
We start by showing the property on the least eigenvalue. We make the assumption that we have linear convergence with ω/2 = µ0/2 and step-size η for iterations s = 0, . . .K so that Lemmas C.2, C.3 hold. Via an analogous analysis of the continous case we reach that m = Ω ( n4 log(n/δ)/µ40α 4 ) implies
‖vk(s)− vk(0)‖2 ≤ 16α √ n‖f(0)− y‖2 α √ mµ0 ≤ R̃v, |gk(s)− gk(0)| ≤ 8 √ n‖f(0)− y‖2√ mµ0 ≤ Rg.
for s = 0, . . .K + 1 by Lemmas C.2, C.3 and that Λ(s),bI(s) are well defined. Using the bounds on the parameter trajectories, Lemma B.5 and R̃v defined above yield λmin(G(s)) ≥ 5µ08 . The least eigenvalue of the evolution matrix Λ(s) is bounded below as
λmin(Λ(s)) = λmin
( G(s) +
Ṽ(s)− Ṽ⊥(s) α2 ) ≥ λmin(G(s))− ‖Ṽ⊥(s)‖2
since Ṽ(s) 0 and α ≥ 1. We bound the spectral norm of ‖Ṽ⊥(s)‖2, for each entry i, j we have by (C.9) that
|Ṽ⊥ij(s)| ≤ (1 +Rg(m/δ) 1/d)|Si| m
≤ (1 +Rg(m/δ)1/d) (√
2R̃v√ πα + 16 log(n/δ) 3m ) ≤ 8R̃v√
2πα
≤ µ0 8n .
where in the above inequalities we used our bounds on R̃v, Rg and m. Then the spectral norm is bounded as
‖Ṽ⊥(s)‖2 ≤ ‖Ṽ⊥(s)‖F ≤ µ0/8.
Hence we have that λmin(Λ(s)) ≥ µ0/2 for s = 0, 1, . . .K. Next we show the residual r(s) satisfies Property 1. Recall r(s) is written as
r(s) = aII(s)
η +
bII(s)
η .
Property 1 states the condition ‖r(s)‖2 ≤ cωη‖f(s)− y‖2 for sufficiently small c < 1 with ω = µ0. This is equivalent to showing that both aII(s), bII(s) satisfy that
‖aII(s)‖2 ≤ cηµ0‖f(s)− y‖2, (C.14) ‖bII(s)‖2 ≤ cηµ0‖f(s)− y‖2, (C.15)
for sufficiently small absolute constant c. For bII(s) we have that (C.10) gives
‖bII(s)‖2 ≤ √ nmax
i bIIi (s)
≤ max i η(1 +Rg(m/δ) 1/d)2|Si|n‖f(s)− y‖2 α2m .
Next applying Lemmas C.1 and B.9 in turn yields
≤ CmR̃vηn‖f(s)− y‖2 α2m
≤ ηµ0‖f(s)− y‖2 R̃v nα2
Substituting m = Ω ( n4 log(n/δ)/µ40α 4 ) for a large enough constant and Rv we get
‖bII(s)‖2 ≤ cηµ0‖f(s)− y‖2.
Analogously we bound ‖aII(s)‖2 using (C.7),
‖aII(s)‖2 ≤ √ nmax
i aIIi (s)
≤ η2n3/2
( 1 +Rg(m/δ) 1/d )3‖f(s)− y‖22(m/δ)1/d
α4 √ m
≤ ηµ0‖f(s)− y‖2 · η ( 1 +Rg(m/δ) 1/d )3 n3/2‖f(s)− y‖2(m/δ)1/d
µ0α4 √ m
≤ ηµ0‖f(s)− y‖2 · η α2 · Cn2
√ log(n/δ)
α2µ20 √ m
≤ cηµ0‖f(s)− y‖2.
Where we have used Lemma B.9 in the third inequality and substituted m = Ω(n4 log(n/δ)/α4µ40) noting that η = O
( 1
‖Λ(s)‖2
) and that α ≥ 1 in the last inequality. Therefore we have that r(s)
satisfies Property 1 so that Theorem C.1 holds. By the same contradiction argument as in Theorem 4.1 we have that this holds for all iterations.

heading: D ADDITIONAL TECHNICAL LEMMAS AND PROOFS OF LEMMAS FROM
text: APPENDIX B

heading: Proof of Lemma 4.1:
text: We prove Lemma 4.1 for V∞, G∞ separately. V∞ can be viewed as the covariance matrix of the functionals φi defined as
φi(v) = xi
( I− vv >
‖v‖22
) 1{v>xi ≥ 0} (D.1)
over the Hilbert space V of L2(N(0, α2I)) of functionals. Under this formulation, if φ1, φ2, . . . , φn are linearly independent, then V∞ is strictly positive definite. Thus, to show that V∞ is strictly positive definite is equivalent to showing that
c1φ1 + c2φ2 + · · ·+ cnφn = 0 in V (D.2)
implies ci = 0 for each i. The φis are piece-wise continuous functionals, and equality in V is equivalent to
c1φ1 + c2φ2 + · · ·+ cnφn = 0 almost everywhere.
For the sake of contradiction, assume that there exist c1, . . . , cn that are not identically 0, satisfying (D.2). As ci are not identically 0, there exists an i such that ci 6= 0. We show this leads to a contradiction by constructing a non-zero measure region such that the linear combination ∑ i ciφi is non-zero.
Denote the orthogonal subspace to xi as Di := {v ∈ Rd : v>xi = 0}. By Assumption 1, Di 6⊆ ⋃ j 6=i Dj
This holds sinceDi is a (d−1)-dimensional space which may not be written as the finite union of subspaces Di ∩Dj of dimension d− 2 (since xi and xj are not parallel). Thus, take z ∈ Di\ ⋃ j 6=iDj .
Since ⋃ j 6=iDj is closed in Rd, there exists an R > 0 such that
B(z, 4R) ∩ ⋃ j 6=i Dj = ∅.
Next take y ∈ ∂B(z, 3R) ∩Di (where ∂ denotes the boundary) on the smaller disk of radius 3R so that it satisfies ‖y‖2 = maxy′∈∂B(z,3R)∩Di ‖y′‖2. Now for any r ≤ R, the ball B(y, r) is such that for all points v ∈ B(y, r) we have ‖vx⊥i ‖2 ≥ 2R and ‖vxi‖2 ≤ R. Then for any r ≤ R, the points v ∈ B(y, r) ⊂ B(z, 4R) satisfy that
‖xv ⊥ i ‖2 ≥ ‖xi‖2 − xi · v ‖v‖2
≥ ‖xi‖2 (
1− R 2R
) ≥ ‖xi‖2
2 .
Next we decompose the chosen ball B(y, r) = B+(r)∨B−(r) to the areas where the ReLU function at the point xi is active and inactive
B+(r) = B(y, r) ∩ {x>i v ≥ 0}, B−(r) = B(y, r) ∩ {x>i v < 0}.
Note that φi has a discontinuity on Di and is continuous within each region B+(r) and B−(r). Moreover, for j 6= i, φj is continuous on the entire region of B(y, r) since B(y, r) ⊂ B(z, 4R) ⊂ Dcj . 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 r→0
1
µ(B+(r)) ∫ B+(r) φi = x y⊥ i 6= 0, limr→0 1 µ(B−(r)) ∫ B−(r) φi = 0.
For j 6= i φj is continuous on the entire ball B(y, r) hence the Lebesgue differentiation theorem also gives
lim r→0
1
µ(B+(r)) ∫ B+(r) φi = φj(y), lim r→0
1
µ(B−(r)) ∫ B−(r) φi = φj(y).
We integrate c1φ1 + . . . cnφn over B−(r) and B+(r) separately and subtract the integrals. By the assumption, c1φ1 + · · · + cnφn = 0 almost everywhere so each integral evaluates to 0 and the difference is also 0,
0 = 1
µ(B+(r)) ∫ B+(r) c1φ1 + · · ·+ cnφn − 1 µ(B−(r)) ∫ B−(r) c1φ1 + · · ·+ cnφn. (D.3)
By the continuity of φj for j 6= i taking r → 0 we have that
1
µ(B+(r)) lim r→0 ∫ B+(r) φj − 1 µ(B−(r)) ∫ B−(r) φj = φj(y)− φj(y) = 0.
For φi the functionals evaluate differently. For B−(r) we have that
1
µ(B−(r)) lim r→0 ∫ B−(r) φi = 1 µ(B−(r)) lim r→0 ∫ B−(r) 0 = 0,
while the integral over the positive side, B+(r) is equal to
1
µ(B+(r)) ∫ B+(r) φi(z)dz = 1 µ(B+(r)) ∫ B+(r) xz ⊥ i dz = x y⊥ i .
By construction, ‖xy ⊥
i ‖2 > R and is non-zero so we conclude that for (D.3) to hold we must have ci = 0. This gives the desired contradiction and implies that φ1, . . . φn are independent and V∞ is positive definite with λmin(V∞) = λ0.
Next we consider G∞ and again frame the problem in the context of the covariance matrix of functionals. Define
θi(v) := σ ( v>xi ‖v‖2 ) for v 6= 0. Now the statement of the theorem is equivalent to showing that the covariance matrix of {θi} does not have zero-eigenvalues, that is, the functionals θis are linearly independent. For the sake of contradiction assume ∃ c1, . . . , cn such that
c1θ1 + c2θ2 + · · ·+ cnθn = 0 in V (equivalent to a.e). Via the same contradiction argument we show that ci = 0 for all i. Unlike φi defined in (D.1), each θi is continuous and non-negative so equality “a.e” is strengthened to “for all v”,
c1θ1 + c2θ2 + · · ·+ cnθn = 0. Equality everywhere requires that the derivatives of the function are equal to 0 almost everywhere. Computing derivatives with respect to v yields
c1x v⊥ 1 1{v>x1 ≥ 0}+ c2xv ⊥ 2 1{v>x2 ≥ 0}+ · · ·+ cnxv ⊥ n 1{v>xn ≥ 0} = 0. Which coincide with
c1φ1 + · · ·+ cnφn By the first part of the proof, the linear combination c1φ1 + · · · + cnφn is non-zero around a ball of positive measure unless ci = 0 for all i. This contradicts the assumption that the derivative is 0 almost everywhere; therefore G∞ is strictly positive definite with λmin(G∞) =: µ0 > 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 us to develop more refined concentration than in Du et al. [15] for monitoring the orthogonal and aligned Gram matrices during training. Lemma D.1. Let A1, . . . , Am be a sequence of events and suppose that Ak ⊆ Bk with B1, . . . , Bm mutually independent. Further assume that for each k, P(Bk) ≤ p, and define S = 1m ∑m k=1 1Ak . Then with probability 1− δ, S satisfies
S ≤ p ( 2 + 8 log(1/δ)
3mp
) .

heading: Proof of Lemma D.1:
text: Bound S as
S = 1
m m∑ k=1 1Ak ≤ 1 m m∑ k=1 1Bk .
We apply Bernstein’s concentration inequality to reach the bound. Denote Xk = 1Bk m and S̃ =∑m
k=1Xk. Then
Var(Xk) ≤ EX2k = (1/m)2P(Xk) + 0 ≤ p
m2 , ES̃ = E m∑ k=1 Xk ≤ p.
Applying Bernstein’s inequality yields P(S̃ − ES̃ ≥ t) ≤ exp (
−t2/2∑m k=1 EX2k + t 3m
) .
Fix δ and take the smallest t such that P(S̃ − ES̃ ≥ t) ≤ δ. Denote t = r · ES̃, either P(S̃ − ES̃ ≥ ES̃) ≤ δ, or t = rES̃ corresponds to r ≥ 1. Note that t = rES̃ ≤ rp. In the latter case, the bound is written as
P(S̃ − ES̃ ≥ rp) ≤ exp ( −(pr)2/2 p/m+ pr3m ) ≤ exp ( −(pr)2/2 p m (1 + r 3 ) ) ≤ exp ( −(pr)2/2 p m ( 4r 3 ) ) = exp ( −3prm 8 ) .
Solving for δ gives
rp ≤ 8 log(1/δ) 3m .
Hence with probability 1− δ,
S ≤ S̃ ≤ max { p ( 1 + 8 log(1/δ)
3mp
) , 2p } ≤ p ( 2 + 8 log(1/δ)
3mp
) .

heading: Proof of Lemma B.1:
text: We prove the claim by applying concentration on each entry of the difference matrix. Each entry Vij(0) is written as
Vij(0) = 1
m m∑ k=1 〈 x vk(0) ⊥ i , x vk(0) ⊥ j 〉(αck · gk ‖vk‖2 )2 1ik(0)1jk(0).
At initialization gk(0) = ‖vk(0)‖2/α, c2k = 1 so Vij(0) simplifies to
Vij(0) = 1
m m∑ k=1 〈 x vk(0) ⊥ i , x vk(0) ⊥ j 〉 1ik(0)1jk(0).
Since the weights vk(0) are initialized independently for each entry we have EvVij(0) = V∞ij . We measure the deviation V(0) − V∞ via concentration. Each term in the sum 1 m ∑m j=1 〈 x vk(0) ⊥ i , x vk(0) ⊥ j 〉 1ik(0)1jk(0) is independent and bounded,
−1 ≤ 〈 x vk(0) ⊥
i , x vk(0)
⊥
j
〉 1ik(0)1jk(0) ≤ 1.
Applying Hoeffding’s inequality to each entry yields that with probability 1− δ/n2, for all i, j, |Vij(0)−V∞ij | ≤ 2 √
log(n2/δ)√ m .
Taking a union bound over all entries, with probability 1− δ, |Vij(0)−V∞ij | ≤ 4 √
log(n/δ)√ m .
Bounding the spectral norm, with probability 1− δ, ‖V(0)−V∞‖22 ≤ ‖V(0)−V∞‖2F ≤ ∑ i,j |Vij(0)−V∞ij |2
≤ 16n 2 log(n/δ)
m .
Taking m = Ω (n2 log(n/δ)
λ20
) therefore guarantees
‖V(0)−V∞‖2 ≤ λ0 4 .

heading: Proof of Lemma B.2:
text: This is completely analogous to B.1. Recall G(0) is defined as,
Gij(0) = 1
m m∑ k=1 〈 x vk(0) i , x vk(0) j 〉 c2k1ik(0)1jk(0)
with c2k = 1 and vk(0) ∼ N(0, α2I) are initialized i.i.d. Since each term is bounded like B.1 the same analysis gives
‖Gij(0)−G∞ij ‖22 ≤ 16n2 log(n/δ)
m .
Taking m = Ω ( n2 log(n/δ)
µ20
) therefore guarantees,
‖G(0)−G∞‖2 ≤ µ0 4 .

heading: Proof of Lemma B.3:
text: For a given R, define the event of a possible sign change of neuron k at point xi as
Ai,k(R) = {∃v : ‖v − vk(0)‖2 ≤ R, and 1{vk(0)>xi ≥ 0} 6= 1{v>xi ≥ 0}}
Ai,k(R) occurs exactly when |vk(0)>xi| ≤ R, since ‖xi‖2 = 1 and the perturbation may be taken in the direction of −xi. To bound the probability Ai,k(R) we consider the probability of the event
P(Ai,k(R)) = P(|vk(0)>xi| < R) = P(|z| < R).
Here, z ∼ N(0, α2) since the product vk(0)>xi follows a centered normal distribution. The norm of ‖xi‖2 = 1 which implies that z computes to a standard deviation α. Via estimates on the normal distribution, the probability on the event is bounded like
P(Ai,k(R)) ≤ 2R
α √ 2π .
We use the estimate for P(Ai,k(R)) to bound the difference between the surrogate Gram matrix and the Gram matrix at initialization V(0). Recall the surrogate V̂(t) is defined as,
V̂ij(t) = 1
m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ k 〉 1ik(t)1jk(t).
Thus for entry i, j we have |V̂ij(t)−Vij(0)| = ∣∣∣∣ 1m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t)− 〈xvk(0) ⊥ i , x vk(0) ⊥ j 〉1ik(0)1jk(0) ∣∣∣∣
This sum is decomposed into the difference between the inner product and the difference in the rectifier patterns terms respectively:(〈
x vk(t)
⊥
i ,x vk(t)
⊥
j
〉 − 〈 x vk(0) ⊥
i ,x vk(0)
⊥
j
〉) ,
( 1ik(t)1jk(t)− 1ik(0)1jk(0) ) .
Define
Y kij =
(〈 x vk(t) ⊥
i , x vk(t)
⊥
j
〉 − 〈 x vk(0) ⊥
i , x vk(0)
⊥
j
〉)( 1ik(t)1jk(t) ) ,
Zkij =
(〈 x vk(0) ⊥
i , x vk(0)
⊥
j
〉)( 1ik(t)1jk(t)− 1ik(0)1jk(0) ) .
Then
|V̂ij(t)−Vij(0)| = ∣∣∣∣ 1m m∑ k=1 Y kij + Z k ij ∣∣∣∣ ≤ ∣∣∣∣ 1m m∑ k=1 Y kij ∣∣∣∣+ ∣∣∣∣ 1m m∑ k=1 Zkij ∣∣∣∣. To bound | 1m ∑m k=1 Y k ij | we bound each |Y kij | as follows.
|Y kij | = ∣∣∣∣∣ (〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 − 〈 x vk(0) ⊥ i , x vk(0) ⊥ j 〉)( 1ik(t)1jk(t) )∣∣∣∣∣ ≤ ∣∣∣∣〈xvk(t)⊥i , xvk(t)⊥j 〉− 〈xvk(0)⊥i , xvk(0)⊥j 〉∣∣∣∣
= ∣∣∣∣〈xi,xj〉 − 〈xvk(t)i , xvk(t)j 〉+ 〈xvk(0)i , xvk(0)j 〉− 〈xi,xj〉∣∣∣∣ = ∣∣∣∣∣ 〈 x>i vk(t) ‖vk(t)‖2 · vk(t) ‖vk(t)‖2 , x>j vk(t) ‖vk(t)‖2 · vk(t) ‖vk(t)‖2 〉 − 〈 x vk(0) i , x vk(0) j
〉∣∣∣∣∣ = ∣∣∣∣∣ x>i vk(t)‖vk(t)‖2 · x > j vk(t) ‖vk(t)‖2 − 〈 x vk(0) i , x vk(0) j
〉∣∣∣∣∣ = ∣∣∣∣∣ x>i vk(0)‖vk(0)‖2 · x > j vk(0) ‖vk(0)‖2 + x>i ( vk(t) ‖vk(t)‖2 − vk(0) ‖vk(0)‖2 ) · x>j vk(t) ‖vk(t)‖2
+ x>j
( vk(t)
‖vk(t)‖2 − vk(0) ‖vk(0)‖2
) · x > i vk(0) ‖vk(0)‖2 − 〈 x vk(0) i , x vk(0) j 〉∣∣∣∣∣ ≤ ∣∣∣∣∣x>i ( vk(t) ‖vk(t)‖2 − vk(0) ‖vk(0)‖2 ) · x>j vk(t) ‖vk(t)‖2 ∣∣∣∣∣+ ∣∣∣∣∣x>i ( vk(t) ‖vk(t)‖2 − vk(0) ‖vk(0)‖2 ) · x>j vk(t) ‖vk(t)‖2
∣∣∣∣∣ ≤ 2 ∥∥∥∥ vk(t)‖vk(t)‖2 − vk(0)‖vk(0)‖2 ∥∥∥∥ 2 .
Therefore, we have ∣∣∣∣ 1m m∑ k=1 Y kij ∣∣∣∣ ≤ 2m m∑ k=1 ∥∥∥∥ vk(t)‖vk(t)‖2 − vk(0)‖vk(0)‖2 ∥∥∥∥ 2
≤ 4Rv(2m/δ) 1/d
α
≤ 8Rv(m/δ) 1/d
α ,
where the first inequality follows from Lemma B.10. Note that the inequality holds with high probability 1− δ/2 for all i, j. For the second sum, | 1m ∑m k=1 Z k ij | ≤ 1m ∑m k=1 1Aik(R) + 1 m ∑m k=1 1Ajk(R) so we apply Lemma D.1 to get, with probability 1− δ/2n2∣∣∣∣ 1m m∑ k=1 Zkij ∣∣∣∣ ≤ 2Rvα√2π ( 2 + 2 √ 2πα log (2n2/δ) 3mRv
) ≤ 8Rv α √ 2π
since m satisfies m = Ω ( (m/δ)1/dn2 log(n/δ)
αλ0
) . Combining the two sums for Y kij and Z k ij , with
probability 1− δ2n2 ,
|V̂ij(t)−Vij(0)| ≤ 8Rv
α √ 2π +
8Rv(m/δ) 1/d
α ≤ 12Rv(m/δ)
1/d
α .
Taking a union bound, with probability 1− δ/2, ‖V̂(t)−V(0)‖F = √∑
i,j
|V̂ij(t)−Vij(0)|2 ≤ 12nRv(m/δ)
1/d
α .
Bounding the spectral norm by the Frobenous norm,
‖V̂(t)−V(0)‖2 ≤ 12nRv(m/δ)
1/d
α .
Taking Rv = αλ096n(m/δ)1/d gives the desired bound.
‖V̂(t)−V(0)‖2 ≤ λ0 8 .

heading: Proof of Lemma B.4:
text: To bound ‖V(t)−V(0)‖2 we now consider ‖V(t)− V̂(t)‖2. The entries of Vij(t) are given as
Vij(t) = 1
m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t) ( αck · gk ‖vk(0)‖2 )2 .
The surrogate V̂(t) is defined as
V̂ij(t) = 1
m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t).
The only difference is in the second layer terms. The difference between each entry is written as |Vij(t)− V̂ij(t)| = ∣∣∣∣ 1m m∑ k=1 〈 x vk(t) ⊥ i , x vk(t) ⊥ j 〉 1ik(t)1jk(t) (( αck · gk ‖vk(t)‖2 )2 − 1 )∣∣∣∣∣ ≤ max
1≤k≤m
( α2gk(t) 2 ‖vk(t)‖22 − 1 ) .
Write 1 = α 2g2k(0)
‖vk(0)‖22 , since ‖vk(t)‖2 is increasing in t according to (2.3)
α2gk(t) 2
‖vk(t)‖22 − 1 = α
2gk(t) 2
‖vk(t)‖22 − α
2gk(0) 2
‖vk(0)‖22 ≤ 3Rg(m/δ)1/d + 3Rv(m/δ)1/d/α.
The above inequality is shown by considering different cases for the sign of the difference gk(t)− gk(0). Now∣∣∣∣∣α2gk(t)2‖vk(t)‖22 − α 2gk(0) 2 ‖vk(0)‖22 ∣∣∣∣∣ = ∣∣∣∣∣ ( αgk(t) ‖vk(t)‖2 + αgk(0) ‖vk(0)‖2 )( αgk(t) ‖vk(t)‖2 − αgk(0) ‖vk(0)‖2 )∣∣∣∣∣ ≤ ∣∣∣∣∣ ( αgk(0) + αRg ‖vk(0)‖2 + αgk(0) ‖vk(0)‖2 )( αgk(t) ‖vk(t)‖2 − αgk(0) ‖vk(0)‖2
)∣∣∣∣∣ ≤ (2 +Rg(m/δ)1/d) ∣∣∣∣∣ ( αgk(t) ‖vk(t)‖2 − αgk(0) ‖vk(0)‖2
)∣∣∣∣∣ ≤ (2 +Rg(m/δ)1/d) max (∣∣∣∣α(gk(0) +Rg)‖vk(0)‖2 − αgk(0)‖vk(0)‖2 ∣∣∣∣, ∣∣∣∣ α(gk(0)−Rg)‖vk(0)‖2 +Rv − αgk(0)‖vk(0)‖2 ∣∣∣∣ )
≤ (2 +Rg(m/δ)1/d) max ( Rg(m/δ) 1/d, Rg(m/δ) 1/d +Rv(m/δ) 1/d/α )
≤ 3Rg(m/δ)1/d + 3Rv(m/δ)1/d/α,
where the second inequality holds due to Lemma B.10 with probability 1− δ over the initialization. Hence:
‖V̂(t)−V(t)‖2 ≤ ‖V̂(t)−V(t)‖F = √∑
i,j
|V̂ij(t)−Vij(t)|2 ≤ 3nRg(m/δ)1/d + 3nRv(m/δ)1/d/α.
Substituting Rv, Rg gives
‖V̂(t)−V(t)‖2 ≤ λ0 8 .
Now we use Lemma B.3 to get that with probability 1− δ
‖V̂(t)−V(0)‖2 ≤ λ0 8
combining we get with probability 1− δ
‖V(t)−V(0)‖2 ≤ λ0 4 .
We note that the source for all the high probability uncertainty 1− δ all arise from initialization and the application of Lemma B.10.

heading: Proof of Lemma B.5:
text: To prove the claim we consider each entry i, j of G(t)−G(0). We have,
|Gij(t)−Gij(0)| = ∣∣∣∣∣ 1m m∑ k=1 σ ( vk(t) >xi ‖vk(t)‖2 ) σ ( vk(t) >xj ‖vk(t)‖2 ) − σ ( vk(0) >xi ‖vk(0)‖2 ) σ ( vk(0) >xj ‖vk(0)‖2 )∣∣∣∣∣ ≤ 1 m ∣∣∣∣∣ m∑ k=1 σ ( vk(t) >xi ‖vk(t)‖2 ) σ ( vk(t) >xj ‖vk(t)‖2 ) − σ ( vk(t) >xi ‖vk(t)‖2 ) σ ( vk(0) >xj ‖vk(0)‖2
)∣∣∣∣∣ + 1
m ∣∣∣∣∣ m∑ k=1 σ ( vk(t) >xi ‖vk(t)‖2 ) σ ( vk(0) >xj ‖vk(0)‖2 ) − σ ( vk(0) >xi ‖vk(0)‖2 ) σ ( vk(0) >xj ‖vk(0)‖2 )∣∣∣∣∣ ≤ 2 ∥∥∥∥ vk(t)‖vk(t)‖2 − vk(0)‖vk(0)‖2 ∥∥∥∥ 2 ≤ 2R̃v(m/δ) 1/d α .
In the last inequality we used the fact,∥∥∥∥ vk(0)‖vk(0)‖2 − vk(t)‖vk(t)‖2 ∥∥∥∥ 2 ≤ ‖vk(t)− vk(0)‖2 ‖vk(0)‖2 ≤ (m/δ) 1/d α ‖vk(t)− vk(0)‖2,
where the first inequality uses that ‖vk(0)‖2 ≤ ‖vk(t)‖2 and is intuitive from a geometrical standpoint. Hence,
‖G(t)−G(0)‖2 ≤ ‖G(t)−G(0)‖F = √∑
i,j
|Gij(t)−Gij(0)|2 ≤ 2nR̃v(m/δ)
1/d
α √ 2π .
Taking R̃v = √ 2παµ0
8n(m/δ)1/d gives the desired bound. Therefore, with probability 1− δ,
‖G(t)−G(0)‖2 ≤ µ0 4 .
Now that we have established bounds on V(t),G(t) given that the parameters stay near initialization, we show that the evolution converges in that case:

heading: Proof of Lemma B.6:
text: Consider the squared norm of the predictions ‖f(t) − y‖22. Taking the derivative of the loss with respect to time,
d dt ‖f(t)− y‖22 = −2(f(t)− y)>
( G(t) + V(t)
α2
) (f(t)− y).
Since we assume that λmin ( G(t) + V(t)α2 ) ≥ ω2 , the derivative of the squared norm is bounded as
d dt ‖f(t)− y‖22 ≤ −ω‖f(t)− y‖22.
Applying an integrating factor yields
‖f(t)− y‖22 exp(ωt) ≤ C.
Substituting the initial conditions, we get
‖f(t)− y‖22 ≤ exp(−ωt)‖f(0)− y‖22.
For now, assuming the linear convergence derived in Lemma B.6, we 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 a condition on the over-parameterization m and ensure convergence from random initialization.

heading: Proof of Lemma B.7:
text: Denote f(xi) at time t as fi(t). Since ‖xvk(t) ⊥
i ‖2 ≤ ‖xi‖2 = 1, we have that∥∥∥∥dvk(t)dt ∥∥∥∥ 2 = ∥∥∥∥ n∑ i=1 (yi − fi(t)) 1√ m ckgk(t) 1 ‖vk(t)‖2 xv ⊥ i 1ik(t) ∥∥∥∥ 2
≤ 1√ m n∑ i=1 |yi − fi(t)| ckgk(t) ‖vk(t)‖2 .
Now using (2.3) and the initialization ‖vk(0)‖ = αgk(0), we bound ∣∣∣∣ ckgk(t)‖vk(t)‖2 ∣∣∣∣,∣∣∣∣ ckgk(t)‖vk(t)‖2 ∣∣∣∣ ≤ ∣∣∣∣ck(gk(0) +Rg‖vk(0)‖2 )∣∣∣∣ ≤ 1α ( 1 + αRg/‖vk(0)‖2 ) .
By Lemma B.10, we have that with probability 1− δ over the initialization,
α/‖vk(0)‖2 ≤ C(m/δ)1/d. Hence αRg/‖vk(0)‖2 ≤ 1. This fact bounds ∣∣∣∣ ckgk(t)‖vk(t)‖2 ∣∣∣∣ with probability 1− δ for each k,∣∣∣∣ ckgk(t)‖vk(t)‖2 ∣∣∣∣ ≤ 2/α.
Substituting the bound, ∥∥∥∥ ddtvk(t) ∥∥∥∥ 2 ≤ 2 α √ m n∑ i=1 |fi(t)− yi|
≤ 2 √ n
α √ m ‖f(t)− y‖2
≤ 2 √ n
α √ m exp(−ωt/2)‖f(0)− y‖2.
Thus, integrating and applying Jensen’s inequality, ‖vk(t)− vk(0)‖2 ≤ ∫ s 0 ∥∥∥∥dvk(s)dt ∥∥∥∥ 2 ds ≤ 4 √ n‖f(0)− y‖2 αω √ m .
Note that the condition |gk(t) − gk(0)| ≤ Rg is stronger than needed and merely assuring that |gk(t)− gk(0)| ≤ 1/(m/δ)1/d suffices.
Analogously we derive bounds for the distance of gk from initialization.

heading: Proof of Lemma B.8:
text: Consider the magnitude of the derivative dgkdt ,∣∣∣∣dgkdt ∣∣∣∣ = ∣∣∣∣ 1√m n∑ j=1 (fj − yj) ck ‖vk‖2 σ(v>k xj)
∣∣∣∣. Note ∣∣∣∣ ck‖vk‖2σ(v>k xj) ∣∣∣∣ = ∣∣∣∣σ( v>k xj‖vk‖2 )∣∣∣∣ ≤ 1
Thus applying Cauchy Schwartz∣∣∣∣dgk(t)dt ∣∣∣∣ ≤ 2√n√m ‖f(t)− y‖2 ≤ 2 √ n√ m exp(−ωt/2)‖f(0)− y‖2,
and integrating from 0 to t yields |gk(t)− gk(0)| ≤ ∫ t 0 ∣∣∣∣dgkdt (s) ∣∣∣∣ds ≤ ∫ t 0 2 √ n√ m exp(−ωs/2)‖f(0)− y‖2ds ≤ 4 √ n‖y − f(0)‖2√ mω .

heading: Proof of Lemma B.9:
text: Consider the ith entry of the network at initialization,
fi(0) = 1√ m m∑ k=1 ckσ ( gkv > k xi ‖vk‖2 ) .
Since the network is initialized randomly and m is taken to be large we apply concentration to bound fi(0) for each i. Define zk = ckσ ( gk(0)vk(0) >xi ‖vk(0)‖2 ) . Note that zk are independent sub-Gaussian
random variables with
‖zk‖ψ ≤ ‖N(0, 1)‖ψ = C.
Here ‖·‖ψ denotes the 2-sub-Gaussian norm, (see [31] for example). Applying Hoeffding’s inequality bounds fi(0) as
P(| √ mfi(0)| > t) ≤ 2 exp ( − t
2/2∑m k=1 ‖zk‖ψ2 ) = 2 exp ( −t2
2mC
) .
Which gives with probability 1− δ/n that |fi(0)| ≤ C̃ √ log (n/δ).
Now with probability 1− δ we have that, for each i, |fi(0)− yi| ≤ |yi|+ C̃ √ log(n/δ) ≤ C2 √ log(n/δ).
Since yi = O(1). Hence, with probability 1− δ, ‖f(0)− y‖2 ≤ C √ n log(n/δ).

heading: Proof of Lemma B.10:
text: At initialization vk ∼ N(0, α2I) so the norm behaves like ‖vk(0)‖22 ∼ α2χd. The cumulative density of a chi-squared distribution with d degrees of freedom behaves like F (x) = Θ(xd/2) for
small x so we have that with probability 1 − δm , that ‖vk(0)‖2 ≥ α(m/δ) 1 d where d is the input dimension. Applying a union bound, with probability 1− δ, for all 1 ≤ k ≤ m,
1 ‖vk(0)‖2 ≤ ( m/δ ) α 1/d .
Now by (2.3) for t ≥ 0, ‖vk(t)‖2 ≥ ‖vk(0)‖2 so
1 ‖vk(t)‖2 ≤ 1 ‖vk(0)‖2
≤ ( m/δ ) α 1/d .

heading: E PROOFS OF LEMMAS FROM APPENDIX C

heading: Proof of Lemma C.1:
text: Fix R, without the loss of generality we write Si for Si(R). For each k, vk(0) is initialized independently via ∼ N(0, α2I), and for a given k, the event 1ik(0) 6= 1{v>xi ≥ 0} corresponds to |vk(0)>xi| ≤ R. Since ‖xi‖2 = 1, vk(0)>xi ∼ N(0, α2). Denoting the event that an index k ∈ Si as Ai,k, we have
P(Ai,k) ≤ 2R
α √ 2π .
Next the cardinality of Si is written as
|Si| = m∑ k=1 1Ai,k .
Applying Lemma D.1, with probability 1− δ/n,
|Si| ≤ 2mR
α √ 2π +
16 log(n/δ)
3 .
Taking a union bound, with probability 1− δ, for all i we have that
|Si| ≤ 2mR
α √ 2π +
16 log(n/δ)
3 .

heading: Proof of Lemma C.2:
text: To show this we bound the difference gk(s)− gk(0) as the sum of the iteration updates. Each update is written as ∣∣∣∣∂L(s)∂gk ∣∣∣∣ = ∣∣∣∣ 1√m n∑ i=1 (fi(s)− yi) ck ‖vk(s)‖2 σ(vk(s) >xi)
∣∣∣∣. As ∣∣∣∣ckσ(vk(s)>xi‖vk(s)‖2 )
∣∣∣∣ ≤ 1,∣∣∣∣∂L(s)∂gk ∣∣∣∣ ≤ 1√m n∑ i |fi(s)− yi| ≤ √ n√ m ‖f(s)− y‖2.
By the assumption in the statement of the lemma,∣∣∣∣∂L(s)∂gk ∣∣∣∣ ≤ √n(1− ηω2 )s/2‖f(0)− y‖2√m .
Hence bounding the difference by the sum of the gradient updates:
|gk(K + 1)− gk(0)| ≤ η K∑ s=0 ∣∣∣∣∂L(s)∂gk ∣∣∣∣ ≤ 4η√n‖f(0)− y‖2√m K∑ s=0 (1− ηω 2 )s/2.
The last term yields a geometric series that is bounded as
1 1− √ 1− ηω2 ≤ 4 ηω ,
Hence
|gk(K + 1)− gk(0)| ≤ 4 √ n‖f(0)− y‖2 ω √ m .

heading: Proof of Lemma C.3:
text: To show this we write vk(s) as the sum of gradient updates and the initial weight vk(0). Consider the norm of the gradient of the loss with respect to vk,
‖∇vkL(s)‖2 = ∥∥∥∥ 1√m n∑ i=1 (fi(s)− yi) ckgk(s) ‖vk(s)‖2 1ik(s)x vk(s) ⊥ i ∥∥∥∥ 2 .
Since ‖vk(s)‖2 ≥ ‖vk(0)‖2 ≥ α(δ/m)1/d with probability 1− δ over the initialization, applying Cauchy Schwartz’s inequality gives
‖∇vkL(s)‖2 ≤ (1 +Rg(m/δ)
1/d) √ n‖f(s)− y‖2 α √ m . (E.1)
By the assumption on ‖f(s)− y‖2 this gives
‖∇vkL(s)‖2 ≤ 2 √ n(1− ηω2 )
s/2‖f(0)− y‖2 α √ m .
Hence bounding the parameter trajectory by the sum of the gradient updates:
‖vk(K + 1)− vk(0)‖2 ≤ η K∑ s=0 ‖∇vkL(s)‖2 ≤ 2 √ n‖f(0)− y‖2 α √ m K∑ s=1 ( 1− ηω 2 )s/2 yields a geometric series. Now the series is bounded as
1 1− √ 1− ηω2 ≤ 4 ηω ,
which gives
‖vk(K + 1)− vk(0)‖2 ≤ 8 √ n‖f(0)− y‖2 α √ mω .

heading: F NUMERICAL ILLUSTRATION
text: 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 η = 3× 10−3. We train the neural network from class (1.2), with m = 10000, n = 1000, d = 784, α = 10−3 and use the first 1000 images of the digits 4 and 9 of the MNIST dataset. We restrict to the digits of 4 and 9 since we focus on the scalar output network with two classes.
To compute α for the network during training we calculate the ratio,
α(s) = ∑m k=1 ‖vk(s)‖2∑m k=1 gk(s) .
During training we note that α grows, as the training loss decreases and the convergence rate slows down (emergence of the G-dominated regime). To measure the change in the direction of vk(t) during training we compute the angle variation of the parameter, this is computed for each neuron for each gradient update as,
∆θk(s) = arccos ( ∣∣〈vk(s),vk(s+ 1)〉∣∣ ‖vk(s)‖2‖vk(s+ 1)‖2 ) .
To visualize the angle change of the network during training, we compute the mean angle change for each iteration, ∆ave(s) = 1m ∑m k=1 ∆θk(s). We plot a moving sum of ∆ave(s) window of size 100,
∆θwindow(s) = ∑s+100 r=s ∆ave(r) to measure the change of the angle throughout training.

Review summaries:
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.

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.