Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary:
 
This paper considers the convergence property of averaged stochastic gradient descent on a overparameterized two-layer neural networks for a regression problem. This paper is the first to achieve the optimal convergence rate under the NTK regime. They show that smooth target functions efficiently specified by the NTK are learned rapidly at faster convergence rate.


##########################################################################Pros: 
 
+ The paper is technically sound. It adapt the neural networks and the RKHSs theory into the NTK regime and the proof techniques are different from existing literatures.

+ It achieves the minimax optimal convergence rate of $O(T^{-2r\beta/2r\beta + 1})$ which is always faster than $O(T^{-1/2})$.

+ This work shows the connection between RKHS and NN in term of the $L_{\infty}(\rho_X)$ norm while the convergence result does not need the positivity of the NTK


##########################################################################
Cons: 
 
- The writing of this paper is not clear enough, for example $L_2(\rho(x))$ appeared without any explaination
- The practical choice of M in their experiment is 2e4, which is impractical in NN tasks
 

##########################################################################
Overall, I vote for accepting. This paper combine the convergence analysis of averaged stochastic gradient descent on kernel methods with the connection of kernel method with neural network to derive an optimal convergence rate of NN in NTK regime while the proof technique is novel. My major concern is about the practical influence of this paper to the theory of deep learning training, as the width of the output layer is required to be large.

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

Questions:
 
In Assumption A3, why the parameter $r$ has to be in the range [1/2, 1]
Is the averaging mechanism at the output of the algorithm beneficial to the rate in Theorem 1?
review_title: Technically good paper

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper analyzed the averaged SGD for overparameterized two-layer NNs for regression problems. Particularly, they show that the averaged SGD can achieve the minimax optimal convergence rate, with the global convergence guarantee. To achieve, they propose a new parameter which captures the ``complexities’’ of the target function and the RKHS associated with the NTK.

The paper is well-written, and the result looks very interesting. I am tending to accept the paper. This paper is a theory, so experiments are a plus. If the authors can address some of my comments, I am tending to increase the score of the paper.



Here are some comments about writing.

I believe Assumption 1 and 2 are reasonable. But each statement is just math, it is good to write a 2~4 words to summarize each A1, A2 .. Also several math statements highly replied on the definitions, and it is hard to find them in the paper.

After Assumption 1, in the next page, page 5, there is a Remark that has 4 bullets, maybe write Ai at the beginning of each bullet.

Algorithm 1 requires more words and explanation, it is hard to understand this algorithm in the following sense : the size of each matrix/vector is not mentioned and hard to find them in the paper.

In page 6, is it possible to simplify the statement of Theorem 1 a bit? e.g. write a simplified version here, and put the full version in appendix.

In Theorem 1, what is M_0? Is that over-parameterization size? Is that polynomial in parameters or exponentially in parameters? (This is not major point of the paper, I am just curious about the bound) 

In page 4, Eq. (2), is it possible to consider a simple model where gamma = 0? This is quite common in previous work.

In appendix, e.g. page 30, the last step of many equations use ->0. I don’t follow the meaning of this notation. Is that possible to avoid it?

This paper is focusing on average SGD, is there any intuition why non-average SGD won’t give the similar result?

I felt the following paper is highly close to this work, and should be cited and discussed more deeply. Usually optimization has two parts, one is the number of iterations, and the other is cost per iteration. This paper focused on improving the number of iterations. The following paper improved the cost per iteration, in the NTK overparameterized regime. 
Training (Overparametrized) Neural Networks in Near-Linear Time
Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein


Minor comments

In page 1, second paragraph, the place cited Du et al. 2019b, Allen-Zhu et al. 2019 and Du et al. 2019a.

The following two papers should also be cited

Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks.  [This paper shows the result for recurrent neural networks. Note that RNN is  a harder case, In deep neural networks the weight matrices in different layers are different. However in RNN, the weights matrix are the same over all the layers]

Zhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound.
[This paper improved the over-parameterization bound from m >= n^6 (Du et al. 2019b) to m >= n^4, where m is the width of a neural network, and n is the number of input data points.]

In page 2, the first paragraph, the place cited Du et al. 2019b, Arora et al. 2019a, Weinan et al. 2019, Arora et al. 2019b, Lee et al,. 2019.

The following papers should also be cited

Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. [Arora et al. paper shows a connection between neural networks with neural tangent kernel regression. This paper generalizes the Arora et al result, and shows the connection between regularized neural networks with neural tangent kernel ridge regression.]

Similarly, in page 5, some citations should be added.

Small typos:
The last paragraph, Page 2 “the key to show” -> “the key to showing”
The third paragraph, Page 3 “which enable” -> “which enables”
The fifth paragraph, Page 4 “ A stochastic gradient descent” -> “Stochastic gradient descent”
The third paragraph Page 5 “a neural networks” -> “a neural network”
The third paragraph Page 6 “arbitrary small” -> “arbitrarily small”
The first paragraph Page 8 “the single-layer learning” -> “single-layer learning”

review_title: A nice result

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Here is the review of the article: ``Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime''.

**SUMMARY**

The authors show that under the Neural Tangent Kernel Regime investigated lately, averaged SGD achieves optimal rates in the attainable case.  Note that this result is not a *plug and play* based on the current kernelized-SGD litterature: the difficulty the authors achieve to overcome is the fact that they could bound the difference between the dynamics of SGD on the neural networks and on the neural tangent kernel. This is stated in Proposition A and it represents the novelty of the article

Moreover, they give an explicit representation of the capacity condition (decrease rate of the eigenvalues of the covariance matrix) in the cases where they have a smooth approximation of the ReLu.

**Clarity**

The paper is outstandly clear. Indeed, despite the fact that optimality in RKHS can be technical to introduce, I found the paper very clearly presented and well motivated. It was very pleasant and smooth to read. The references are also both precise and sufficient to understand well the problem.

The only default of the paper is that, in my opinion, the authors do not stress enough their contribution and their novelty. Indeed, despite Proposition A and the sketch of the proof, the article consists in a *plug and play* result on averaged SGD. The authors should then stress the outline of the proof (going to a M-approximation of the Neural Tangent RKHS) and comparing the dynamics on these.

**Quality and Originality**

The paper is not super original, and as accustomed to this literature, there is no surprise seeing this result. However, the quality of the paper is undeniable and fills the gap between optimality of kernel methods and the NTK literature. I thank the authors to have done it very clearly.



**Comments**

-My main comment is about the fact that except from Proposition A, this article is a *plug and play* one. This proposition, and the full sketch of the proof should be emphasized as they consist on the true novelty of the work.

-Three remarks concerning the plots :

1-*Minor comment.* They should be bigger.
2-*Minor comment.* Figure 1 should illustrate the fact that $\beta = 1 + \frac{1}{d-1}$. I suggest a log-log plot.
3-*Intermediate comment.* I do not really see how exactly the discussion of the experimental part illustrates really the result. The discussion is fairly interesting, but I really would like to see a theoretical proposition showing that taking the two layers is better for learning.


*** Conclusion***

Yet the fact remains that, I would really like this article to be published when the commentaries of the reviewers will be taken into accounts. 
review_title: Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper considers the optimization of a wide two layers neural network (for a regression task) using averaged SGD. The authors consider the Neural Tangent Kernel (NTK) regime. The NTK is a kernel defined using the activation function and the initial distribution of the parameters of the input layer. The RKHS H associated to this NTK is assumed to contain the Bayes predictor. Based on this, the authors derive a convergence rate for the predictor constructed from the T-th iterate of averaged SGD and the Bayes predictor in terms of the L2 distance wrt the distribution of the features. By specifying this bound in terms of the decay of the eigenvalues of the integral operator in H, they obtain an explicit generalization error bound, which is optimal for the class of problems considered in the paper.

It seems that the paper solves an important problem related to the training of neural nets. The paper is rather well written even if some paragraph are hard to understand for a non expert. 
For example, several paragraphs of the paper are dedicated to compare the obtained results with those of concurrent work. The level of technicality of these discussions makes the reading experience difficult (e.g. last paragraph of Page 6), often because the discussion happens at a step where the reader is not familiar with the results (e.g. Section 1.2). These paragraphs seem like a discussion with the authors of these concurrent works. I would suggest to gather these discussions at the end of the paper, once the reader understands the results. Moreover, a better approach in my opinion would be to explicitly state the results (mathematically) of these concurrent work. This way, the comparison will be easier.

As a non expert, I believe that the results are new but I cannot be sure because I cannot compare with existing works (see my comment above). I recommend acceptation.


Overall, the paper shows an important result: optimal rate for generalization bounds for 2 layers NN in the NTK regime. The result is well explained but some precision could make the paper even more insightful. For instance, why considering the NTK regime? What is the intuition behind that? How would you define mathematically "the NTK regime" ? I would also like to understand better the relaxation of the positivity of the NTK. Does it have to do with the assumption that the norm of the integral operator is greater than lambda?


Moreover, Proposition A, which is fundamental in the approach, should be stated in the main paper for a better understanding. I think that the authors can move the numerical experiments to the appendix to win some space.




MINOR:

Check the def of excess risk, last equation of Page 3
"negative dependence on" should be "inverse dependence on"
", That is, "
Why is Figure 1 in Section 1? Is it a mistake? It should not be placed here. Moreover it is not commented in the text.
review_title: Seems very good

final_score: rating: 7: Good paper, accept
review_content: Summary:

The paper focuses on the understanding of neural tangent kernel (NTK), which has been a central topic in deep learning theory recently and plays an important role in characterizing the generalization ability of artificial neural networks. In Particular, the authors derive minimax-optimal learning rates of the averaged stochastic gradient descent method for over-parametrized two-layer neural networks with smooth activation functions. The results are novel and offer insights into the connections between deep learning methods and kernel methods. One difference of this paper from other studies is that the positivity of NTK is not required in the error analysis. Numerical experiments are also illustrated to confirm the theoretical results. The paper is well written and interesting to read. Overall, I vote for accepting.


Concerns:
1. Although the paper considers smooth approximations of the ReLU and also shows the explicit optimal rate, its analysis does not apply to ReLU networks which may be of greater interest to researchers. 

2. It looks a little bit strange to me that the regularization is conducted around the initial values. Will this lead to a big difference in the numerical experiments?

3. Is there an explicit form for the lower bound of network width in Theorem 1, i.e., $M_0$?
review_title: Official Blind Review #4

Meta-review: The paper presents some exciting results on the convergence of averaged SGD for overparameterized two-layer neural networks. The AC and reviewers all agree that the contributions are significant and well presented, and appreciate the author feedback to the reviews. The corresponding revisions on assumptions and references, and the added simplified proposition in the introduction have nicely improved the manuscript. 
Decision: Accept (Oral)