Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the existence of adversarial examples (found via a single gradient step) for two-layer ReLU networks in settings where the trained weights remain close to their initialized values. The authors prove that adversarial examples exist in this specific case, and support their theoretical findings via experiments on MNIST.  

strengths_and_weaknesses: Strengths
- The paper is mostly well written.
- This paper presents a novel theoretical analysis of adversarial robustness in the context of what is referred to as the "lazy regime" in this work, where the trained weights do not stray far from their initialization.  
- The authors present empirical results on MNIST that back up their theoretical findings. 

Weaknesses
- It's not immediately clear what the importance/significance of this work is, and how this extends beyond two-layer ReLU networks, and this very specific setting. 
- The proof sketch reads a bit rushed -- the readability could be improved here. 
questions: - How does this perturbation budget relate to what is typically considered an indistinguishable attack in adversarial training studies on MNIST?

Minor suggestions
- Typo line 26: lead -> led, incomplete sentence line 47, extra “a” in line 73, missing \citep throughout
- All the plots in Figures 1-3 are difficult to read -- they should be enlarged. 

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the robustness of two-layer NNs against adversarial examples in the “lazy-training” regime, extending a line of work which studied this for randomly initialized two-layer NNs. The paper shows that if after training, the weights of the NN are close to the randomly initialized weights, single-step adversarial perturbations of size O(1/\sqrt(d)) flips the prediction of this NN. The authors empirically validate their theory via experiments on MNIST.

strengths_and_weaknesses: 
#### Strengths:
- The findings in the paper are original to the best of my knowledge. The paper extends a line of work that theoretically shows that NNs are susceptible to single-step adversarial attacks.
- The claims of the paper are sounds and are well-supported by the experiments.
- I think the work is decently significant as it is the first paper to attempt to bring the theory of robustness of neural networks beyond the random-initialization regime.
- The paper is very well written and flows smoothly. I didn’t check the proof sketch in detail, but everything else was easy to grasp and follow.
- The paper lists a number of potential research directions for building on top of their work which I think is helpful and puts the contributions of the paper into context.

#### Weaknesses:
- Overall the paper is pretty good, but it can benefit from more experiments to support the theory (more datasets, multiple tasks beyond image classification)
- A discussion of extension to multi-class classification problems is missing.


#### Minor changes:
- Line 73: repeated “a”.
- Equation after line 93: extra parentheses next to the zero
- Line 134-158-164: references should be inside parentheses
- Line 146: C1 doesn’t show up in theorem 3.1 nor in the main paper.
- Line 141 and 176: a ∼ unif{1, +1} -> a ∼ unif({-1, +1})

questions: - Would similar results hold for multi-class classification problems?
- It would be more convincing to see empirical evidence supporting the theory on datasets beyond MNIST (e.g., CIFAR-10 or ImageNet), and in general on tasks beyond image classification. Is there a reason why the authors didn’t try these?

limitations: The  authors adequately addressed the limitations of their work. They didn’t include potential negative societal impact though. While I don’t think there is a direct negative societal impact of this paper, I believe the authors might be able to talk about how readers might get a wrong perspective of non-robustness of NNs in general. The readers should be aware that the claims of this paper hold only for two layer NNs and in the lazy training regime only, i.e., that there is no proof yet that it is guaranteed to find adversarial examples for general NNs.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies model robustness in the context of lazy training, i.e, the model parameters are in the neighborhood of its initialization.
Specifically, the authors find that the lazy trained models are quite vulnerable against adversarial attacks, although it has good generalization on clean inputs.
It is proved that a single step attack with a small step size can flip the prediction of the two-layer networks under lazy training. This claim is validated in the numerical stimulation.
strengths_and_weaknesses: Strengths:

1. It is interesting to study the model's robustness in the context of lazy training, which makes the model efficiently learnable.
2. The theoretical proof is sound.

Weakness:

I have several concerns listed below, addressing them can improve the manuscript.

1. In Theorem 3.1, the width needs to be both upper bounded and lower bounded (Line 145). However, the lower bounds increases with the decrease of $\gamma$, and the upper bound decreases with the decreases of $\gamma$. That is to say, in some cases, the $\gamma$ can not be arbitrarily small, i.e. $\gamma \to 0$ may make $m$ infeasible under the constraints of this theorem. This is a critical concern especially in the case of small input dimension $d$. The author should comprehensively discuss this case.

2. The main theorem (Theorem 3.1) of this paper is applicable to any model parameters in the neighborhood of the initialization. However, in the empirical experiments only study the cases of training or adversarial training, could it be the vulnerability as shown in the experiments arise from the training methods, i.e, the parameters prior encoded by your training objective and optimizer?

3. In general, I think the real interesting part of this work is to show there is no robust models in the neighborhood of a random Gaussian initialization, **even with adversarial training**. I suggest the author highlight the adversarial training part, because in vanilla training, even without constraining the model parameters in the initial neighborhood, the model is not robust at all.

4. For the presentation of Theorem 3, the ``constant'' $C_2$, $C_3$, $C_4$, and $C_5$ depends on $C_0$. I agree that for notation simplicity, there is no need to provide the exact analytical form of these values. However, I do suggest the authors discuss how these values increases or decreases with $C_0$. In addition $C_1$ is not defined in this Theorem.

In general, I like the topic and the problem settings of this paper, but there are several concerns pointed in this section and the next one. It can be a good paper if the concerns above are adequately addressed. I am happy to discuss with the authors in the rebuttal and re-evaluate this paper after that.

questions: I have pointed out the major questions in the weakness part in the previous section. In addition, I have one additional question:

1. In the right part of Figure 2, why the step size $\eta$ is significantly bigger in the small $C_0$ and small $d$ cases? This is not consistent with what the authors say.

In addition, the presentation of this paper needs improvements, such as:

1. Definition of $L_R$ (between line 95 and 96), $L_R$ is not a function of $(x, y)$ because they are averaged for expectation calculation.

2. Theorem 3.1, $C_1$ is not defined.

3. Corollary 3.2, line 176. it should be $a \sim unif\\{-1, +1\\}$

4. Lemma 4.4,  line 251, $c$ is not defined.
limitations: The authors briefly discussed the limitation of this work in the end of the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper takes a solid step towards explaining adversarial sensitivity of neural networks based on random networks. The paper shows that networks can be attacked by a single gradient descent step in the lazy regime where parameters are close to initialization. 
strengths_and_weaknesses: Strengths

1. The paper takes a solid step towards explaining adversarial sensitivity of neural networks based on random networks [1]. In the lazy regime like NTK, while networks can show good clean perfomrance, they can easily attacked by a single gradient step.

2. The paper is easy to follow with clear presentation.

3. I appreciate the adversarial training in the empirical experiments, which shows that the theorem holds for arbitrary $w$ near initialization not constraint by the training algorithms.

Weaknesses

1. My major concern is that the Theorem only optimizes the first layer $W$ while $a$ is not included. In the experiment, $a$ is also a tunable parameter. This is inconsistent. Besides, allowing tunable $a$ may bring contradictory result. In [2], the authors show that adversarial training is possible to converge in the overparameterized models. It seems to indicate that adversarial robustness is not impossible in the lazy regime.

2. I recommend the authors to report clean performance in the experiment parts to show the network actually achieves good clean generlization near initialization.

3. One conclusion is misaligned with empirical findings. The adversarial trained networks need larger size of adversarial example to attack the network (Figure 4(b) in [3]). And the common $L_2$ adversarial budget set for ImageNet (dimension is $224\times224\times 3$) is also higher than CIFAR10 (dimension is $32\times32\times 3$). This is contradictory to the conclusion that the label will be flipped with $O(\frac{1}{\sqrt{d})$ adversarial noise.

[1] S´ebastien Bubeck et.al. A single gradient step ﬁnds adversarial examples on random two-layers neural networks, NeurIPS 2021

[2] Ruiqi Gao et.al. Convergence of Adversarial Training in Overparametrized Neural Networks, NeurIPS 2019

[3] Ali Shafahi et.al. Are adversarial examples inevitable?, ICLR 2019
questions: See the weakness part.
limitations: The authors adequately addressed the potential negative societal impact of their work? I think fixing $a$ is a big limitation for the technical results.
review_title: null

Meta-review: metareview: While the overall scores are somewhat borderline, there seem to be no major flaws and all reviewers recommend accepting the paper. Hence I will follow this recommendation.
confidence: Certain
Decision: Accept