Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper is theoretical sound and well organized. This paper shows that the Bayes estimator with Gaussian prior can outperform the linear estimators (including kernel regression and k-NN), which I believe is indeed interesting and important.

Besides, I would like to raise the following comments and questions.

1. The network function is different from the commonly-used one. For example, the authors need to clip the output weights using tanh function. The authors state that the reason is to ensure the boundness condition of the network function. What if using a standard parameterization of a two-layer network but performing projected (noisy) gradient descent?

2. It seems that the goal of all estimators is to recover the teacher networks. However, the Bayes estimator actually uses the same network structure as the teacher one. It is more interesting to investigate the case where the underline teacher network is independent of the learned network (e.g., using an overparameterized network to learn a smaller network).

3. In the description of hat f, the authors may need to clearly state the definition of the function \phi_i.

4. Does the result in Theorem 2 hold for any f^{\circ}?

5. In Proposition, the convergence results look similar to the following paper, while in their paper, the right-hand side of (6) converges to O(\eta^{1/2}) when k\eta goes to infinity. Could you briefly discuss why in this paper, this quantity is in the order of O(\eta^{1/2-a})?

Xu, Pan, et al. "Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization." arXiv preprint arXiv:1707.06618 (2017).

6. Besides, I feel that the comparison with Raginsky et al., 2017 and Erdogdu et al., 2018 after Proposition may not be fair. In particular, the convergence results in these papers are derived based on different assumptions, thus their dependencies on the dimension are not directly comparable. 

7. Moreover, it may not be appropriate to state that “NGD achieves a fast convergence rate”, it seems that the spectral gap \Lambda^* still has an exponential dependency on the parameter beta (shown in Proposition 3), which will be set as beta = \Theta(n) in Theorem 2. This implies that the noisy gradient descent may require exponential time to output a good solution.

8. In Theorem 2, can we view the expected error between F_{W_k^{(M)}}  and f^{\circ} as a variant of generalization error (in expectation)? If this is the case, can we somehow apply the results in the following paper, and obtain a O(n^{-1}) generalization error bound for the Langevin dynamic gradient algorithm (if considering finite dimension case)? 

Mou, Wenlong, et al. "Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints." Conference on Learning Theory. 2018.

9. A suggestion: It is better to present Section B.1 before the first part of Section B, since the proof of Proposition 1, Theorem 2, and Corollary 1 largely rely on the assumptions and propositions in Section B.1.

10. Lastly, the authors may also want to include the following two NTK papers in the introduction section. 

Zou, Difan, et al. "Gradient descent optimizes over-parameterized deep ReLU networks." Machine Learning 109.3 (2020): 467-492.

Cao, Yuan, and Quanquan Gu. "Generalization bounds of stochastic gradient descent for wide and deep neural networks." Advances in Neural Information Processing Systems. 2019.
review_title: Interesting work but requires more refined explanations and discussions

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

The paper aims to demonstrate the superiority of deep learning methods against kernel methods by comparing their excess risk bounds. In particular, the authors first derive the minimax lower bound for linear estimators by assuming that the target function can be represented by a teacher neural network, which implies that the linear estimators suffer from curse of dimensionality. Then the authors further derive a dimension-independent upper bound of the noisy gradient descent method for overparametrized two-layer neural networks, which theoretically confirms the benefit of deep learning methods in terms of convergence rates. The paper is well written and also interesting to read. Overall, I vote for accepting.


Concerns:
1. In the teacher-student setting, what is the minimax rate for any estimator of $f^0$ instead of just linear estimators? Or is the upper bound for the noisy gradient descent method minimax optimal?
2. Traditionally we impose smoothness assumption on the target function directly (e.g. Holder space). So what is the main advantage of this teacher-student setting?
3. In Theorem 1, I feel a little bit confused why the dimension $d$ also appears in the numerator, which is different from classical lower bounds. For example, If we assume that $f^0$ belongs to a Sobolev space of order $r$, then the minimax rate of excess risk will be $n^{-\frac{2r}{2r+d}}$, which goes to 0 as $d$ goes to infinity. Do I have any misunderstanding?


review_title: Official Blind Review #3

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: #### General comments
This paper aims at proving superiority of neural network models to any linear estimators, including kernel methods.  To attain this purpose,  this paper focuses on  two layer neural network class with an infinite width. For the non-parametric regression models within this neural network class, this paper establishes a sharp excess risk error of the least square methods with  noisy gradient descent update, although such optimization may be heavily non-convex. Moreover, a lower bound of  all linear estimators under the $L_2$-norm   are accordingly given when the true function is within the two layer neural network class, thereby showing superiority to kernel  methods.  Overall，the contribution of this paper is obvious and the literature review is full to some extent.
This paper is organized well and stated clearly. 

#### Specific Comments
（1）After Theorem 1, the sentence "for relative high dimensional settings, this lower bound becomes close to a slow rate $\Omega(1/\sqrt{n})$, which corresponds to the curse of dimensionality. "  I argue  that this sentence may be uncorrected, 
since the mentioned rate is independent of the input dimension, which is not a real curse of dimensionality. 
(2)  A constraint on  $f_{W}$ should be added, otherwise, it is impossible to identify $a_m$ and $\bar{w}_{2,m}$ simultaneously. 
(3) What is the role of noisy term in NSGD algorithm, is it a similar conclusion when the standard SGD is applied? 
(4）What  is the additional difficulty encountered when analyzing a thin but deep neural network?
review_title: Comments to "Benefit of deep learning with non-convex noisy gradient descent: ..."

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: =========================

Summary:

The paper shows that a two-layer neural network (although an extension to deeper models seem unproblematic) may outperform a class of linear functions in terms of the excess risk learning rate, and in a minimax optimality analysis, and when approximating a target function from the neural network class. The paper essentially shows that linear functions have a problem with the non-convexity of the neural network class, and approximate the slow rate of 1/(n)^(1/2) for increasing dimension. A neural network trained with noisy stochastic gradient descent on the other hand has a faster rate, depending on several parameters.

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

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

Pros:

- Well written and polished paper.

- Technically sounds as far as I can tell. (Randomly checked some parts in more detail.)

- Setting and results may be interesting for a large audience.

- Main results and message of the paper are to the point.

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

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

Cons:

Very technical and on some parts I would have liked some more intuition and discussion. See detailed feedback and also questions for rebuttal.

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

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

Scoring:

Overall I think this is a worthwhile contribution in understanding the difference in deep and shallow learning, and as the paper is very sound I will vote for accept. I will acknowledge, however, that there is a flurry of related work, as it is a very popular topic, and I can not vouch for the novelty of this contribution. The authors, however, covered much ground in that regard.

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

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

Questions for rebuttal:

It appears to me that the neural networks are not part of the linear functions class, and thus having a neural network target makes the linear functions being misspecified. Is that true? If so, does that play a role in the learning rate gap? In case it is not true, what is the essential difference then between the linear functions and the neural networks? Regarding that, what is phi_i in the definition of linear models?

Instead of noisy gradient descent you actually use semi-implicit euler scheme for optimization, do you have any thoughts on how that might effect actual performance?

As far as I can see your current analysis does not hold for relu-activations, how easy might an extension to that be?

Are you aware of any lower bounds for the neural network case, are your rates optimal?

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

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

Additional feedback:

The result that the minimiax rate of linear functions over a space F is the same as over its convex hull was not known to me. For me it would have been very useful if you could provide some intuition on why that is the case.

You show that the rate of the neural network is independent of the dimension. Do you have any intuition on why that is the case?

Under Equation (5), instead of "more faster,...,more faster" write "the faster,..., the faster"

review_title: Interesting and to the point results, technically very demanding, so difficult to verify correctness.

Meta-review: This paper analyzes deep networks optimized using non-convex noisy gradient descent. The main result shows that in a teacher-student setting, the excess risk converges in a fast-rate and is stronger than any linear estimators (which include kernel methods). The paper also gives a convergence rate result that depends on some spectral gaps (which can be very small) but not on dimension. Overall the paper is interesting. It should probably emphasize that the dependency on spectral gaps (and the fact that they could be exponentially small) on the convergence as the current abstract suggests efficient convergence.
Decision: Accept (Spotlight)