Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work builds upon Bassily et al. and extends stability analysis to adversarial training algorithms. The authors use uniform algorithmic stability to derive lower and upper bounds on the robust accuracy.  Based on the theoretical analysis, they argued that non-differentiability (or gradient-masking) reduces the stability of adversarial training, which leads to the significant gap between training and testing robust accuracy. To reduce the generalization gap, the authors suggest using noise injection into the parameters and the input of the models.
main_review: ### Originality:
- The work extends in a novel way uniform stability analysis to adversarial training algorithms.
- The authors provide bounds in case of an imperfect attack, which is the case in all applications of adversarial training.

### Quality:
- The paper gives new insights into adversarial training and in a way explains catastrophic overfitting with weak adversaries.
- The claims seem to be theoretically sound and correct.

### Clarity:
- The paper is well motivated and superbly written.

### Significance:
- The developed insights may lead to the development of new robust training algorithms.

### Questions to the authors:
1) The bounds for SGD does not depend on the batch size, which seems to be counterintuitive. Can the authors clarify that?
2) Is the input noise injection equivalent to random start for PGD adversarial training? If it is not, what are the differences?
3) What do the authors mean by vanishing initialization in Figure 1 as it is not clear from the context?
4) In appendix A remark 4, the authors state "adversarial training prefers a smaller number of steps to reduce the
corresponding UAS upper bound". It seems to be correct for training with weak adversaries but incorrect for training with strong adversaries, since robust training with a strong adversary requires many more iterations. Can the authors clarify if I am wrong?
5) In appendix C2.1, noise injection and data augmentation reduce adversarial test accuracy. Can the authors comment on this result?
limitations_and_societal_impact: ### Limitations:
- Limitations of the work are discussed.

### Societal impact:
- The authors did not discuss societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides the argument stability bound for adversarial training for linear models and 2-layer NNs with or without noise injection. The stability has a direct connection to the generalization bound. The contribution is mainly on the theoretical side. Motivated by the non-smoothness in AT which causes poor stability, the paper proposes to inject noise during training for both weight and data. Theory and simulation results justify noise injection on improving stability and shrinking generalization gap.
main_review: Pros:
- Provides the first lower bound and upper bound for uniform argument stability (UAS) for AT
- Considers numerical attack error in inner maximization which better models the real scenario
- Theoretically analyzes how noise injection improves the stability
- The paper is well written and easy to follow.

Cons:
- The theoretical results are limited to linear models (linear/logistic regression, smooth hinge loss) and two-layer NNs. Moreover, The UAS bounds without noise injection seem to be limited to convex and L-Lipschitz loss. Not sure whether it is a standard condition for UAS community.
- The connection of UAS bound to generalization error bound seems not that direct:
  - What are the proper conditions for Eqn. (3)? It seems that Eqn. (3) only relies on the argument stability but not any other properties of the model $f_\theta$ itself, which is a bit weird. Are there any assumptions here, e.g., $f_\theta$ is a linear model, $f_\theta$ is convex or $L$-Lipschitz?
  - Can Theorem 1 and Corollary 1 be extended to provide generalization bound for GD/SGD trained models? Do we need to further assume the tail distribution of $\sup \mathbb{E} ||\theta_1^{(T)} - \theta_2^{(T)}||$? Why do we have such generalization bound for noise injection (Proposition 2) regime but not for the normal regime?

Minor:
- What does $B$ stand for in Lemma 1?
- It would be better if the $x$-axis scales in Figure 1 could be the same to allow for direct comparison.
- I like the empirical evidence in C.2.1 that shows how noise injection shrinks the generalization gap in real-world data. Maybe move it to the main text?

I don't work in theory and didn't check the correctness of the proof. While it appears to me that UAS bounds provide a new perspective on analyzing the generalization and stability for AT, and the UAS bounds in this paper are technically nontrivial. I tend to support the acceptance but would adjust my evaluation based on theory reviewers.
limitations_and_societal_impact: The authors adequately addressed the limitations. As a theory paper, the potential negative societal impact of their work is little.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper investigates the stability of adversarial training when using SGD/GD, motivated by the stability analysis of Bassily et al. (2020) and Hardt et al. (2016) in the standard learning model.
In order to improve stability, the authors suggest injecting noise into the weights and data
(this was already investigated, see for example - Adversarial weight perturbation helps robust
generalization, Neurips2020).
Moreover, theoretical analysis is also provided for Linear Regression, Logistic Regression and learning with hinge loss.

main_review: The main contributions are on the theoretical side.
My main concerns are about originality/novelty. The upper and lower bound on stability are adaptations of the claims of Bassily et al. (2020).
Moreover, methods of weight perturbation were already investigated empirically  (see for example - Adversarial weight perturbation helps robust generalization, Neurips2020), and some theoretical justifications were also provided in follow-up papers.

Moreover, there are glaring omissions in the literature review, especially on the theoretical side and regrading weights perturbation methods.

On the other hand, I think that the main research question is interesting and important. 
limitations_and_societal_impact: -
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the theory of adversarial examples from the angle of algorithmic stability. More precisely, the authors characterize the algorithmic stability of the now famous adversarial training scheme. Their main findings can be summarized as follows. 
1) Even if the loss function utilized during adversarial training is smooth, the adversarial perturbation applied to the input image causes some non-differentiability issues which impede guaranteeing a good algorithmic stability in the worst-case scenario.
2) The numerical approximation error of adversarial attacks used during training can have an impact on the algorithmic stability of the scheme. 
3) Injecting noise to the learning procedure helps to make the loss function smooth again; hence restoring the algorithmic stability with high probability.
main_review: Relevance: 
The problem of designing models that are robust against adversarial attacks is a burning issue both in academia and in the industry right now. As adversarial training is one of the most efficient strategies against this problem, it is important to better understand this technique from a theoretical standpoint. Hence, the main focus of this paper is completely relevant to the machine learning community. 

Clarity:
I had some troubles following some parts of the paper. I feel like the overall point could be much more convincing if the author were to reorganize and focus their contributions, at least in the main paper. For example, Lemma 1 seems overcomplicated in its current form because the authors wanted to encapsulate several Lemmas at once (as explained in the appendix). To clarify the contributions and to make the paper more readable, I would suggest that the authors focus on presenting results for the linear regression and leave similar findings with other models to the appendix. Note that results are actually demonstrated in the appendix only for the regression case anyway, and extensions are left to the reader. Similarly,  Algorithm 1 (while it is quite straightforward) seemed a bit vague at first sight. To my point of view,  very generic statements such as «Add noise with size $\eta$» do not convey a clear point. I think the paper would benefit from focusing on the Gaussian noise injection, as it is the distribution that is used to demonstrate all the results.

Quality:
I had some trouble evaluating the soundness of the technical results because of the clarity issues mentioned above. Also, I am a bit uncomfortable with the way the authors demonstrate their statements. Some results (Lemma 1, Propositions 1 and 2, Corollary 1) are not provided with any formal proof. Some others (Theorems 2 and 3) are demonstrated only in the case of the linear regression. Even though the results presented in Appendix and existing works in the domain might be sufficient to provide simple proofs for these results, I feel like this should not be the reviewer’s (nor the reader’s for that matter) job to check for the soundness of the statements by combinations of different (rather technical) results . I think the authors should provide clear proofs for the result they state, even if those are very simple. As in the clarity section, I suggest providing clear statements with proofs at least for the regression case in the main paper and provide some leads for generalizing the results in the appendix. 

On the experimental part, I felt that the point was rather not very convincing and was not sufficiently correlated with the results. This impression comes mostly from the fact that 1) the mean of the Lipschitz constants with and without noise injection do not seem to differ in a significant way and 2) low-dimensional intuitions are usually misleading when dealing with adversarial examples. This problem on the experimental part is not my main concern because this is a theory paper, but I think it would be better to either present more convincing results or simply no experiments at all.

Originality and Significance:
I am might not be fully aware of the literature but I think that studying adversarial training through the scope of algorithmic stability is a new idea. The proposed solution of injecting noise is not very surprising (looking at the literature on algorithmic stability and specifically on the link between differential privacy and algorithmic stability) but the authors have the merit of using this solution in a new problem. I think the overall idea has some merit and this paper could become an interesting first step toward a better analysis of adversarial training once the technical content is polished. 

Some bibliographical notes: Here are some missing works that I think are worth mentioning.

On generalization of adversarial machine learning

[1] J. Khim, et al. ‘‘Adversarial risk bounds for binary classification via function transformation’’ 2018

[2] P. Awasthi, et al. “Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks” 2020

[3] R. Pinot, et al. ‘‘On the robustness of randomized classifiers to adversarial examples’’ 2021

On using noise injection to stabilize the model against adversarial attacks

[4] B. Wang, et al. ‘‘ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies’’ 2019

[5] J. Cohen, et al. ‘‘Certified Adversarial Robustness via Randomized Smoothing’’ 2019

[6] N. Ford, et al. ‘‘Adversarial Examples Are a Natural Consequence of Test Error in Noise’’ 2019

[7] T. Weng, et al. ‘‘Evaluating the robustness of neural networks: an extreme value theory approach’’ 2018

limitations_and_societal_impact: As this is mostly a theory paper, I do not see any potential negative social impact.
review_title: null

Meta-review: The large generalization gap of adversarial training is a central problem of adversarial robustness. This paper makes the first attempt to study this problem from an algorithmic stability point of view. The authors establish upper and lower bounds for robust accuracy of adversarial training and investigate the causes of large generalization gap. In addition, the paper proposes a noise-injection method to improve the algorithmic stability and threfore reduces the generalization gap of adversarial training. Overall, this is a nice contribution to NeurIPS. It provides insightful understanding to a key problem of adversarial training. On the other side, the paper mainly contains theoretial analysis. More experimental study would benefit more readers. I recommend accept.
Decision: Accept (Poster)