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.
*Summary of the contributions:*
This 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.
Conceptually 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. 
Thus, 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.) 
The 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. 
*Decision:*
I am leaning for a weak reject for the following reasons: 
1. 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.
For 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. 
2. 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).
However, 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)
3. 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. 
I 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. 
4. 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. 
*Questions:*
“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 ? 
Same 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)
I 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).”
but 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 ? 
Can 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 ? 
*Minor comments: (do not need to be addressed in the rebuttal)*
- 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.  
- 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) 
- I would not say that  “smaller alpha leads to faster convergence” since the optimal step size depend on \alpha. 
=== After rebuttal ===
I would like to thank the author for their detailed answer.  
I still think that experimental evidence that the phenomenon described by the theory actually happens in practice should be provided. I maintain my score.