Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

The proofs are very solid and the results look strong to me.

My 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.

=====================
I'd like to keep my original score for this paper after reading the authors' response.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: *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. 

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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. 

This 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: 
step 1. show the finite-width NTK concentrates near the infinite width NTK, whose least eigenvalue is positive (need proof) 
step 2. show the change of finite-width NTK is tiny and essentially does not alter the least eigenvalue.   

As 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. 

Overall, this is a good paper but the contribution might not be sufficient for acceptance for the reasons below. 
1. 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. 
2. 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. 


Comments: 
1. Extending to multilayer? 
2. 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.  
3. What can we say about generalization: normalization vs no normalization? e.g. [5]





[1] 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.   
[2] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes overparameterized neural networks.
[3]Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization
and generalization for overparameterized two-layer neural networks. In International Conference on Machine
Learning, pages 322–332, 2019.
[4]Samet Oymak, Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
[5] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization
and generalization for overparameterized two-layer neural networks. In International Conference on Machine
Learning, pages 322–332, 2019.

review_title: Official Blind Review #3

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