Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the author focus on the theoretical framework of minimizing training risk when the loss satisfy PL conditions. They prove the linear convergence in subquadratically over-parameterized shallow networks with smooth activation functions. They conduct experiments on different initialization to support the theory. The theory also provides insights toward avoiding lazy training.
main_review: The paper is well written and smooth to follow. The work looks original to me but I have a few concerns.
1. On experiment perspective, to what extent the theory can even deeper network and relu activation?
2. The experiments are not support the theorem well, no experiments provide to show how width (or overparameterization) relates to convergence and training dynamic. 
limitations_and_societal_impact: Yes, applying to ReLU is a pretty realistic direction.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The focus of this paper is to improve the state-of-the-art overparameterization condition for training shallow neural networks. Besides, this paper also claims that the proposed analytical framework can be applied to the setting that uses standard initialization strategies, which possibly avoids lazy training.
main_review: Basically, the main weakness of this paper is regarding the contribution. First, the utilization of smoothness, near-isometry, and PL conditions is not new in the analysis of training overparameterized neural networks. The convergence analysis in [1, 12, 27, 41] has also explicitly or implicitly made use of these properties. Besides, the $O(n^{1/2})$ improvements are not significant and remarkable as this cannot provide us a better understanding of the true learning behavior of GD/SGD for neural network models.

Regarding Table 1, the authors should also clearly state the data assumption made in [34] and this paper in the table. I think the $O(n^2)$ result in [34] is built under the assumption that the training data is Gaussian-like. Besides, [12, 40] are actually considering ReLU activation function while this paper considers smooth activation, which should also be clarified clearly in the table.

The results in Theorem 3 seem to be similar to [34], the authors may need to comment on the difference right after the theorem.

In Section 6, the authors briefly discuss the relationship between initialization to lazy training. However, there might be an issue since the lazy training happens as long as $w_1\cdot w_2$ is large, e.g., $w_1\cdot w_2 = O(1/\sqrt{d_0 d_1})$, instead of the scaling of solely $w_1$ or $w_2$. Different ratio $w_2/w_1$ only determines the learning speed of the first and second layers but does not affect the fact that GD is still practicing lazy training, since $||\Theta_t - \Theta_0||\rightarrow 0$. Therefore, unless considering the regime that $w_1\cdot w_2$ is smaller (e.g, $w_1\cdot w_2<1/d_1$), the convergence of GD will still be in the lazy training regime.

===================

Thank you for providing such a thorough response to my questions. I agree that O(n^{1/2}) improvement is nontrivial and the study of the initialization scaling is also interesting. 

I mentioned [1,  27, 41] since I feel that the gradient lower bound results in their paper are similar to the PL condition. So it would be better to comment on this after the definition of PL condition or introduction in your paper.

It would be great if the authors can clarify the difference to [34] since this is the most related work. The results in [34] also have some dependency on the input dimension, it could be better to also comment on the over-parameterization condition proved in [34] when the input dimension is $\Omega(\sqrt{n})$.

The results on the norm between $h(\Theta_i)$ and $\tilde h(\tilde \Theta_i)$ is also interesting. It would also be better to include that lemma in the main part of this paper.

Overall I would like to increase my evaluation to marginally acceptance.
limitations_and_societal_impact: This paper has no negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper shows that overparameterized neural networks with $O(n^{3/2})$ neurons, where $n$ is the number of datapoints, are globally convergent at a linear rate with high probability provided that the weights are initialized from Gaussian distributions with the right variances and the activation function is twice-differentiable. The work is the first one to give a result in the regime where the number of neurons is subquadratic in $n$, and unlike previous papers, it considers the case in which both layers are trained.

main_review: The argument proposed seems novel and the results obtained are a significative improvement over what was known. The explanation is mostly clear: in particular, Section 3 is useful to get an idea of the proof in the simplified case of gradient flows.

Clarification to be made: In Assumption 2, Line 231, an assumption is made on $sigma_{\max}(V_k)$. Aren’t the matrices $V_k$ the parameters of the optimization problem, i.e. not fixed? How come an assumption is made on them?

Suggestions: When applying Theorem 2 to the case of shallow neural networks, it is mentioned that random matrix theory techniques are applied. Apparently, these techniques are applied in  the proof of Theorem 3, but there is little explanation in the main text about them. It would be good to provide an intuition on them, if space permits. Moreover, the reference to the Khatri-Rao product is hard to parse, given that the concept is not introduced in advance.
limitations_and_societal_impact: The authors have addressed the limitations. There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work presents an analysis of the amount of hidden units needed for convergence of a 1 hidden layer neural network to a global minimum under gradient descent (and gradient flow).  In particular, this work establishes a bound of $\tilde{\Omega}(n^{\frac{3}{2}})$ parameters for linear convergence.  Importantly, this work analyzes convergence in a 1 hidden layer network in the case where both weight matrices are trained.  The results also hold for a range of initialization schemes including the Kaiming Normal Initialization.  

main_review: 

Positives: 
(1) I found the work to be a novel usage of existing techniques for proving convergence in the non-convex setting via the PL inequality.  I found the analysis and the proof idea clear and easy to follow. 

(2) The results are novel to the best of my knowledge and the authors provide a nice comparison of how the derived scaling differs with several related works.  

(3) Overall, I thought the results were clearly presented.  I especially liked that the authors included upfront a description of the proof technique that would be used throughout the work.  The theoretical results all appear to be correct to the best of my knowledge (I was able to check through Appendix C + G but unfortunately, could only skim through Appendices D-F due to time constraints).  

###############################################################

Limitations: 
(1) The proof technique is very reminiscent of local convergence results under the PL inequality and smoothness and it might be useful to cite the following related work: https://arxiv.org/abs/2003.00307 , https://arxiv.org/abs/2010.01092.  

(2) I think the presentation can be improved slightly by introducing the motivation for analyzing gradient flow first.  Correct me if I’m mistaken, but the proof for the gradient flow case seems to mainly exist to provide intuition for the argument controlling the length of the optimization path in the gradient descent case.  It may be helpful to add text to mention something like this to motivate the gradient flow case a bit more.  

(3) This comment is not as related to the main results of the paper, but more to the discussion on the lazy training regime.  I think the authors emphasize quite a bit that the lazy training regime leads to poor generalization, but this is not generally true.  In fact, the infinite width NTK can generalize well in many cases (see https://arxiv.org/abs/1910.01663, https://arxiv.org/abs/2007.15801).  I think the authors may be trying to say that the finite width linearization of a neural network seems to underperform training the same finite width network when all parameters are updated.  I feel this can be clarified a bit throughout the paper (in the introduction & Section 6).  

###############################################################

Minor Comments:

(1) I think the function $\psi$ should be real valued for the PL inequality correct? Right now it appears to map to $\mathbb{R}^{d_2}$.  I also think over-parameterization is an implicit assumption for this statement of the PL inequality - this is stated later, but may be useful to say this right before the PL inequality definition.

limitations_and_societal_impact: The authors discuss some limitations and societal impact appropriately in the conclusion.
review_title: null

Meta-review: This paper proves $O(n^{3/2})$ overparameterization condition for training two-layer neural networks when the activation function is smooth and the loss function is square loss. The majority of the reviewers are in support of accepting this paper. Thus, I recommend acceptance. In the camera-ready, the authors should make it clear that the comparison in Table 1 is under different assumptions on the activation functions (e.g., smooth activation functions vs. ReLU). 
Decision: Accept (Poster)