Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the excess risk of learning neural networks in the teacher-student setting, as well as the theoretical superiority of neural networks over other linear (or kernel) methods. It provides an excess risk bound of $\frac{\log n}{n}$ convergence rate (with polynomial dependency on other parameters) for the neural networks, and also a minimax lower bound of $n^{-\frac{d+2}{2d+2}-o(1)}$ for all kernel methods to learn the same target function class.
strength_and_weaknesses: Strengths:
1. This paper is clearly and rigorously written. All the notations are well explained and most of the technical difficulties are introduced naturally. It is very delightful to read as the paper managed to convey these highly technical statements with such clarity and fine elaboration.
2. The story in this paper is complete, in that this paper almost resolves most of the questions in its setting. They have the convergence guarantee with well-explained optimization algorithms and analysis, and also a generalization guarantee as excess risk upper bound. For the lower bound, they proved the LB for all linear classes (kernels) that their generalization over the teacher class is poor compared to student neural nets. 
3. The problem this paper deals with is a long-pursued one in the deep learning theory community. The results in this paper go beyond the previous works and are proven for a setting with almost minimal assumptions over the target function class (for example, it goes beyond the orthogonality condition on which many previous results are based, and it goes beyond the local convergence result of Zhou et al. 2021). This is highly non-trivial progress in this direction. The results of this paper also provide some solid technical contributions.

Weaknesses:
1. The two-stage optimization process, which uses two different optimization algorithms, seems to be the remaining problem to solve. It would be better if the analysis can be applied to settings without this technical workaround.

clarity,_quality,_novelty_and_reproducibility: This paper is written clearly and with high quality. The novelty of its results lies in that it improved the previous analysis to settings where assumptions are more natural.
summary_of_the_review: This paper presents a solid contribution to the area of deep learning theory, although it has not resolved all the problems under its setting, it still manages to improve the previous analysis and give an almost complete story of learning in the student-teacher setting beyond kernel methods.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the excess risk of two-layer ReLU neural networks in a teacher-student regression model. In particular, they showed that the student network could learn the teacher network under certain conditions in two phases: first by noisy gradient descent
and then by vanilla gradient descent. 
strength_and_weaknesses: Strength:
1. The proposed algorithm can recover the teacher network's parameters, which is a hard problem. 
2. This paper is well-written and organized.
3. This paper has proof and experiments to support their results.

Weakness:
1. This paper requires the student network has the same width as the teacher network. It is unknown whether such a result can be generalized to the case where we don't know m in advance.
2. To connect the noisy SGD and vanilla SGD, the algorithm requires reparameterizing the neural network. This kind of trick seems to be impractical in real applications, especially for DNNs.
clarity,_quality,_novelty_and_reproducibility: This paper is clear and well-written. The idea is quite interesting, although the application may be limited. 
summary_of_the_review: In general, this paper is well written. My only concern is whether the exact recovery of the parameter is necessary for NN training, if we only care about the excess risk. Instead of reparemetrizing, can we directly decrease the noise level in Noise GD to zero?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper consider the optimization and the statistical guarantee of two-layer ReLU neural networks under the teacher-student settings, demonstrating that we can obtain a fast rate on the excess risk with a computational-efficient two phase optimization algorithm, that can be shown to beat any linear estimators on the statistical efficiency.
strength_and_weaknesses: ### Strength:
* The conclusion on the superiority of the neural networks is interesting.

### Weakness:
* The presentation of the paper, especially Section 4.2 should be improved. The two-phase algorithms are not presented in a unified way, which leads to some ambiguities for me.
* The results are not a substantial improvement over [1]. The only new result for this paper is showing that when the teacher and the student have the same width, we can have a computationally efficient algorithm to perform the estimation, using the idea from [2].

[1] Suzuki, Taiji, and Shunta Akiyama. "Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods." In International Conference on Learning Representations. 2021.

[2] Zhang, Xiao, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. "Learning one-hidden-layer relu networks via gradient descent." In The 22nd international conference on artificial intelligence and statistics, pp. 1524-1534. PMLR, 2019.
clarity,_quality,_novelty_and_reproducibility: Other than Section 4.2, the paper is clearly written. However, I need to say the novelty is limited.
summary_of_the_review: The main concern for me is about the novelty. If I understand correctly, the only new content for this paper is the computational efficient algorithm. However, this part is presented poorly. I do have a specific question on this two-phase algorithm. Following the constants selected in Theorem 4.5, we still need $k^{(1)} = \exp(\mathrm{poly}(m))$, which can still be pathological when $m$ is not so small. Is this really satisfactory? Furthermore, 	I’m wondering if Proposition 4.3 is a satisfactory result, as when $\beta$ goes to infinity, the risk does not go to 0.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the excess risk of two-layer ReLU neural networks training by two-stage gradient based algorithms with spherical data iid spread on the unit sphere. Under such neural networks training, the authors demonstrate that, two layer neural networks are able to achieve the minimax $O(1/n)$ rate in a certain norm-based space, when compared to kernel methods with $O(n^{-1/2})$ rate (slightly faster  than this rate via the convex argument technique).
strength_and_weaknesses: **Pros:** 

1. propose a two-stage gradient descent algorithm combining the gradient Langevin dynamics and standard gradient descent over the first layer for neural networks training

2. Study the separation between kernel methods and neural networks in terms of excess risk


**Cons:**

1. The authors claimed that their results do not require high over-parameterization conditions. However, according to Theorem 4.5, the convergence rate is $O(m^5/n)$, as well as the minimum singular value $\sigma_{min}$ heavily depending on $m$. 
That means, their results are only valid to $m \ll n$ rather than over-parameterization.
Furthermore, I don’t agree with the authors’ current claimed $O(1/n)$ rate for neural networks, because this is a width-dependent result though the authors set $m < d$ in this work. 
Instead, kernel methods obtain a width-independent $O(n^{-1/2})$ convergence rate, e.g., (Bach, JMLR 2017, Gal et al. NeurIPS 2022). Hence, in this case, it is not enough to show the separation between kernel methods and neural networks.

[1] Vardi, Gal, Ohad Shamir, and Nathan Srebro. "The Sample Complexity of One-Hidden-Layer Neural Networks." NeurIPS 2022.

2. If we put the above key issue aside, a small $m$ (as well as the experiments) makes sense for the teacher network with few activations.  But for the student network, a few $m$ significantly restrict the model expressivity. I'm wondering the size of function space (in my next question). Besides, this also effects the convergence of phase II in Proposition 4.4 with $O(1/m^3)$. The convergence results require to work in a large $m$ setting, falling into a self-contradiction suitation.

3. The considered function space in Eq. (1) is a norm-based function space, and can be regarded as a subspace of variational space for two-layer neural networks via signed measure (or similar to the path-norm based space), see (Bach, JMLR2017). The separation between kernel methods and two-layer neural networks has been studied in this larger space [2] as kernel methods suffer from the curse of dimensionality $\Omega(n^{-1/d})$. 

[2] Parhi, Rahul, and Robert D. Nowak. "Near-minimax optimal estimation with shallow ReLU neural networks." IEEE Transactions on Information Theory (2022).

While this work focuses on a smaller function space and kernel methods are close to the $O(n^{-1/2})$ rate in high dimensional settings. I understand the authors aim to show the separation between kernel methods and neural networks on the convergence rate: $O(n^{-1/2})$ vs. $O(1/n)$. However, strictly speaking, this is not the claimed “curse of dimensionality” in the approximation theory view.

4. Proposition 4.3 appears vacuous due to the exponential order of $m$ and $\beta$. Regarding $\beta$, the authors suggest using “a sufficiently large $\beta$” in phase I to ensure a near-optimal result. However, it makes the first term exponentially large in the first term of Proposition 4.4, resulting in a vacuous result.


clarity,_quality,_novelty_and_reproducibility: This paper is well written, and has good quality, but the obtained results and claims appear a little specious. Apart from the above drawback, what’s the difference between the current problem setting and the mean field regime in terms of the function space and the obtained gradient based algorithm?

summary_of_the_review: This work presents the separation between kernel methods and neural networks in terms of excess risk, but the problem setting with a few $m$, sufficiently large $\beta$ in Proposition 4.3, and the function space require more discussion and refinement for publication. I suggest 1) the authors center around a few $m$ for the teacher network, but the student network allows for more neurons;
2) fix the over-parameterization issue in the excess risk;
3) avoid an exponential order of a sufficiently large $\beta$ in Proposition 4.3.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider learning from a two-layer network, using a) a student with matching architecture trained with a two-phase Langevin+GD procedure b) linear methods. They provide upper (resp. lower) bounds on excess test error with the number of samples, and show that the student net always display faster rates than linear method. Their discussion also provides some insight about the role of convexity (or lack thereof) to rationalize these findings.
strength_and_weaknesses: Strengths:

The paper is overall well-written, clear and easy to follow. The related works are very satisfyingly discussed.  The question asked (when, and why do neural net outperform linear methods) is definitely an important one, and the setting the authors study is very natural. I have not read the proofs.

Weaknesses:

A plot with the learning curves of the student network, along with those of some kernel methods (RF. NTK, or usual kernels such as RBF), with the relevant upper/lower rates of decay, would be extremely helpful in visualizing (and bolstering) the theoretical results.

Questions:

To my understanding, the bound for the student network seems to hold after a threshold of the order of exp(m**2) (theorem 4.5), which can be extremely large already for widths 50, thereby raising the question of whether the regime described can be observed at all unless the network is very narrow. More discussion in this sense would be helpful (or, in the case I am misunderstanding, a clarification from the authors). Note that this is more a clarification question and in any case the results remain of interest.

For small m (e.g. m=2), does the student net perform clearly better than the linear methods right after the threshold in n predicted in Theorem 4.5? For large dimensions d, I would naively expect from the results of Aubin et al. (The committee machine....., 2019) that there exists a large range of n where this is not the case.
clarity,_quality,_novelty_and_reproducibility: The paper is very clear. All parameters necessary for Fig.1 seem to be specified. Although I'm not extremely familiar with the literature in the field, the results seem of solid interest.
summary_of_the_review: Although I have not reviewed the proof, the paper comes across as clear, well-written, and seems to my understanding to bring solid results, I am therefore giving a good score, but with average-low confidence.

The paper does not display to me a clear weakness, my only comment being that a plot which illustrates the main point of the paper would to my mind improve on the clarity and impact.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Reviewers overall agree this paper should be accepted. I think the reviews summarize very well the strengths and weaknesses of the paper as well as points that the authors should include in the revised version. This is a nice addition to the conference. 
justification_for_why_not_higher_score: While this is a very nice paper I did not see any particular reason for a highlight. It is a nice theory paper but the obtained rates are somewhat disappointing for practical dimensional and width. So a poster is the best here I think. 


justification_for_why_not_lower_score: Valuable paper that should not be rejected.
Decision: Accept: poster