Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the trade-off between the test accuracy and robustness of two-layer neural networks, specifically concerning regression. More precisely, they focus on using a 2-layer network to learn a quadratic form. 
Theoretically, it is shown that there is a clear trade-off between robustness and test accuracy for some variants of the above setup where the initialization is taken into account, as well as the neural tangent regime. 
The simulations verify the findings for this specific setup.
strength_and_weaknesses: This paper studies the robustness of two-layer neural networks in different learning regimes and proves that there is a compromise between robustness and test accuracy. 

Pros:
- the paper is well structured and, (albeit dense) it is relatively clear 
- to my knowledge, understanding the tradeoff on this particular setup is novel and well motivated
- it is particularly nice that the considered setup is simple so that it can be studied thoroughly.

Cons:
- while I agree with the soundness of the robustness measure used, and I appreciate the additional details in the appendix, I am not sure to which extent the results of this paper (in the regression setting) can be generalized to the more standard classification setting.
- there are missing comparisons with existing works (see below)

## Missing comparisons with existing works
- The work of Zhang et al. (TRADES) which focuses on the classification setting is also discussing the tradeoff between robustness and accuracy
- Specifically for the regression case,  [Rothenhäusler et al., 2018.] rigorously show the trade-off between robustness and test accuracy in a linear setting; it is necessary to discuss the differences.  

[Zhang et al, 2019] *Theoretically Principled Trade-off between Robustness and Accuracy* -- https://arxiv.org/abs/1901.08573
[Rothenhäusler et al., 2018.] *Anchor regression: heterogeneous data meets causality* -- https://arxiv.org/abs/1801.06229
clarity,_quality,_novelty_and_reproducibility: 
- **Clarity**: the paper is written very clearly, and very technically precise. It is also relatively dense--see my suggestion below.
- **Quality**: the paper rigorously considers various settings and has interesting insights that I learned 
- **Novelty**: to my knowledge, considering this setup for the robustness-generalization trade-off is novel, and moreover, the connections with initializations are also novel
- **Reproducibility** : I did not see an appendix on implementation details, please clarify in your response if the code will be made public.



### Minor points / Suggestions
- Maybe this has been also done by previous works, but I personally find it confusing that the terms *teacher-student* are used here given that teacher-student is a different problem, whereas here the teacher is not a neural network.
- In the abstract, it is not clear what is referred to by *lazy training*; either add a citation or describe it with a few words therein
- While reading the paper, I was often wondering why is this relevant -- it would be very helpful to improve the flow of the reading: e.g. prepare the reader for what follows, why the answer that follows is relevant etc. I understand that there is a lack of space and it is a strict advantage of the paper that there are many contributions, but I would advise moving some less-important details in the appendix if needed (while summarizing only in an informal theorem for e.g.) in order to improve the reading flow.

summary_of_the_review: The compromise between test accuracy and robustness has been studied before in the regression and classification setting, but this work sheds light on more detailed discussions that include initialization and other regimes, specifically for regression given quadratic form. 
While broadly the question is relevant, it is not clear if these findings can be extended to the more relevant classification setting.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes generalization and robustness properties (measured by gradient norm) of two-layer neural networks in different learning regimes under the high dimensional setting with Gaussian data. The tradeoff between them is theoretically given for such two-layer neural networks trained by SGD, the random features regime, and the NTK regime. Besides, a lower bound between the test error and the robustness over general data is given, which implies that the test error cannot be decreased without increasing the robustness error.

strength_and_weaknesses: **Pros:** 

1. In two-layer neural networks with polynomial activation functions trained by SGD, random features, the neural tangent kernel for two-layer networks, the tradeoff between the generalization (excess risk) and the robustness (gradient norm) is given.
2.  a lower bound between the test error and the robustness over general data is given. 

**Cons:**

I’m familiar with this topic equipped with high dimensional statistics, and like this theoretical result on the trade-off between generalization and robustness. Nevertheless, I don’t like the writing style: mixing with Ghorbani et al. (2019) throughout this paper, e.g., problem settings, generalization results, random features regime and neural tangent kernel regime. 
For example, Section 4.2 has already been studied in Ghorbani et al. (2019) or can be easily obtained (e.g., Eq. 20).

I strongly suggest the authors rewrite this paper to emphasize their main contribution on robustness. Besides, a table is needed to summarize the problem settings and results presented in Section 3, 4, 5. 

clarity,_quality,_novelty_and_reproducibility: Appart from the above mentioned issues, I have the following questions:

1. There exists different definitions on over-parameterization, e.g., $m/d \gg 1$ in (Allen-Zhu, 2018, https://arxiv.org/abs/1811.03962) that this paper used or $m/n \gg 1$ in (Belkin et al. 2019). I suggest the authors clarify this.

2. This work shows that over-parameterization hurts robustness, which is contrary to (Bubeck and Sellke, 2021) as well as other results on robustness. More discussion is needed.


3. This work uses the gradient norm in a L2-integrable space in the sense of expectation as a robustness metric, called Dirichlet energy. In fact, this average-case robustness view also exists in [1] under different initializations as well as the over-parameterization. (authors are excused for this paper because this paper was recently posted). Besides, I’m wondering that, the tradeoff between robustness and generalization in this paper can be extended to other robustness metrics, e.g., [1] and Lipschitz constant? 

[1]  Zhu, Z., Liu, F., Chrysos, G.G. and Cevher, V. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization). NeurIPS 2022.

4. It is unclear to me why the input dimension $d$ is used in the assumption $d || \Gamma ||_{op} = O(1)$. 
Normally $ || \Gamma ||_{op} = O(1)$ makes sense in RMT.

5. It is unclear to me why the neural networks in Section 3 exhibit a form of feature learning? 

**Minor issues:**

The studied test error in this paper works in the approximation theory view, but I suggest the authors adopt the estimation/test error instead of approximation error, leading to extra confusion to readers.

summary_of_the_review: This paper give a rigious theoretical evidence on the trade-off between robustness and generalization in high dimensional settings under two-layer neural networks. I vote for acceptance of this paper but strongly suggest the authors re-organize this work for better presentation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the trade-off between robustness and test error for learning a quadratic target function. The models considered include two-layer quadratic nets, random feature models, and the neural tangent one. The sample size is assumed to be infinite and thus, the test error is essentially the approximation error. 

The authors show that there exist a trade-off between approximation error and robustness of approximant: $robust(f) + error(f) = 1$. The authors argue that these theoretical findings can contribute to the explanation of why there exists a  trade-off between clean accuracy and adversarial robustness, a phenomenon observed in practice. 
strength_and_weaknesses: I do not know how to assess the results of this paper. I feel that it is **not even wrong** since the result has nothing to do with adversarial robustness. If I understand correctly, the theoretical result basically means that when $f-f^*$ is small, $||\nabla f||$ is close to $||\nabla f^*||$.  Here $f$ and $f*$ are our model and target function, respectively. In other words, the relative robustness approaches $1$ when the approximation error is decreasing toward zero. 

First, this result is kind of irrelevant, since we only need the approximant and the target function to satisfy a **coercive condition**: that the smallness of $||f-f^*||$ can imply the smallness of $||\nabla f - \nabla f^*||$. This can be seen in Section 6, where the authors actually prove the trade-off for any functions that satisfy the Poincare inequality. 

Second, I think the result has nothing to do with the vulnerability of ML models. As the approximation error is small, we have $||\nabla f||\approx ||\nabla f^*||$, which in fact suggests that our model is as robust as the ground truth. This is almost the best we can expect. The vulnerability issue should be the case that the learned model is much more vulnerable than the ground truth but the test error is small. This is obviously not the case studied in this work.
clarity,_quality,_novelty_and_reproducibility: The presentation is clear but the interpretation of their result seems irrelevant (at least to me)
summary_of_the_review: This paper provides a precise characterization of the trade-off between robustness and approximation error for a few models. Unfortunately, I find the result is kind of irrelevant. Please correct me if I misunderstandard the result.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the trade-off between robustness and test error in a setting in which (i) the teacher is a quadratic function, (ii) infinite training data are available, and (iii) a proportional scaling between the input dimension and the neural network width is assumed. The authors provide results for 3 different regimes: (i) two-layer networks trained via SGD (Theorem 3.1), (ii) random features (Theorem 4.1), and (iii) neural tangent approximation, with and without initialization (Theorem 5.1-5.2). The test error in such models was computed in previous work by Ghorbani et al. (2019) and the contribution of this paper consists in computing a certain metric of robustness/sensitivity using rather similar tools (coming from high-dimensional statistics). By doing so, the authors are able to exhibit an interesting balance between the generalization error and the robustness to perturbation. Finally, a lower bound is provided for a general non-linear teacher/student model (Theorem 6.1). This lower bound is a relatively simple consequence of the concentration of measure phenomenon. 
strength_and_weaknesses: Strengths:

(1) The problem is well motivated and the particular measure of robustness/sensitivity is well discussed (in Appendix C).

(2) The trade-off exhibited is, to the best of my knowledge, novel.

(3) Even though the assumptions are sometimes strong (see the weakness (2)), it is always remarkable to have an exactly solvable model, leading to a closed-form expression for the robustness.


Weaknesses:

(1) From the technical standpoint, the paper is somewhat incremental, since the tools are essentially those of Ghorbani et al., (2019). If that's not the case, I would like to encourage the authors to highlight their technical innovations in the rebuttal.

(2) The assumptions on the model are rather strong, although I understand that they are taken from Ghorbani et al., (2019). In particular: 

(a) Having a teacher model which is a quadratic function is rather restrictive.

(b) I am actually wondering how crucial Condition 4.3(A) actually is. If I understand correctly, it basically ensures that the activation function is centered. In Appendix F.3, the effect of centering is discussed. Given this discussion, I wonder about what happens when Condition 4.3(A) is violated. Is the model less robust (as in the case of the neural tangent approximation with an initialization)?

(3) The authors show that having an initialization term in the neural tangent approximation (and potentially not being able to fulfil Condition 4.3(A), see remark above) leads to less robustness. It is not clear to me whether this actually means a worse resistance to adversarial examples or whether this is just an effect of the particular setting taken into account (and, more specifically, of the particular metric for robustness being chosen). Can the authors comment on this point? 

(4) One of the key messages of the paper seems to be that the trade-off between generalization and robustness is of the form $\tilde\varepsilon_{\rm test}+\tilde\varepsilon_{\rm rob}=1$. I have three comments about this. 

(a) This same trade-off is proved for the three settings taken into account. Does this mean that training with SGD, doing random features or the neural tangent approximation makes no difference as far as robustness is concerned? This would be a bit strange.

(b) As a matter of fact, if I understand correctly the paper, $\tilde\varepsilon_{\rm test}+\tilde\varepsilon_{\rm rob}=1$ holds for random features and neural tangent only in some corner cases ($\rho\to\infty$ for random features and $\beta=1$ for neural tangent). Can the authors comment on why, in these corner cases, one would expect that the trade-off is the same in different models?

(c) Finally, can the authors comment on the trade-off when it does not have the form $\tilde\varepsilon_{\rm test}+\tilde\varepsilon_{\rm rob}=1$? Theorem 4.1 and 5.1 hold more in general and should allow to discuss a more general trade-off.

(5) How does Theorem 6.1 relate to the body of literature that uses concentration of measure to show the inevitability of adversarial examples, see e.g. Mahloujifar et al., (2018)?
clarity,_quality,_novelty_and_reproducibility: The paper is overall clear. The trade-off between test-error and robustness is original. The technical tools are close to those of Ghorbani et al., (2019).

There are some typos, e.g., "the network with $m$" (end of the first paragraph of 'Related works') and "For simplicity, simplicity of this experiment," (caption of Figure 2).
summary_of_the_review: Overall, the paper demonstrates an interesting and novel trade-off between test error and robustness. At the technical level, the analysis is a bit incremental, as it appears to resemble closely that of Ghorbani et al., (2019). My borderline (leaning positive) score is due to the several weaknesses I pointed out above, which can potentially be resolved (at least partially) after the rebuttal.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the robustness of a teacher-student architecture with two layers. While prior work relied on the Lipschitz constant (i.e. worst-case measure) to measure the robustness of neural networks, this paper instead studies an average measure of the gradient. This is a novel angle that the reviewers appreciated. 

Initially, two reviewers were mildly positive, one was positive, and one was negative (reviewer d515). After the discussion period, reviewer d515 maintained his low score. We therefore had a Zoom meeting between the reviewers followed by a discussion with the meta-AC.

Overall, the paper does have an interesting aspect to it as it studies a novel measure of robustness (which is justified in the appendix) and provides an analytical formula for this robustness measure. From a technical point of view, the paper heavily builds on the prior results by Ghorbani et al. (2019) (for instance using their linearization results for the random matrix that appears in the robustness formula for the random feature model). This opinion is shared among all reviewers, including Reviewer qTks who is the most positive about the paper. I think the strong connection to Ghorbani et al. (2019) should be more clearly highlighted in the paper (the current writing simply says the paper is "inspired" by their paper, while many lemmas actually directly come from their paper). I do believe this is an interesting contribution that should be published at some point, but I largely agree with reviewer d515 that the paper shouldn't be published in its current form. I elaborate below.

As highlighted by Reviewer d515, the quadratic student-teacher setting is rather artificial and does not necessarily reflect what happens to practical neural networks. The major issue raised during the Zoom meeting is that the paper presents itself as an analysis of neural networks and does not sufficiently acknowledge the somewhat "artificial" setting studied in the paper (this can clearly be seen in the choice of the title, the introduction and the discussion section). This main point was, in my view, not adequately addressed by the authors during the discussion period, leaving it uncertain that the authors would address this point if the paper were to be accepted.
For instance, looking at the changes made to the paper during the rebuttal period, I do not see a serious attempt made by the authors to address this problem.

I will therefore reject this paper for now and I strongly recommend the authors rewrite the paper to address this concern. I hope this decision will not discourage the authors, I'm convinced a revised version of this paper would be worth publishing in a good venue.


justification_for_why_not_higher_score: I provided a detailed discussion above.
Decision: Reject