Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the "Benign Overfitting" phenomena in the setting of linear classification of sub-gaussian mixtures. Precise risk upper bounds are provided for adv-training of linear classifiers under exponential loss.
main_review: This paper studies the "Benign Overfitting" phenomena in the setting of linear classification of sub-gaussian mixtures. Precise risk upper bounds are provided for adv-training of linear classifiers under exponential loss.

Overall, this paper is well-written and the technical results look correct to me (although I did not check the details very carefully). The setting of interest is an important first step towards understanding overparameterized models - it generalizes the prior works to the sub-Gaussian mixture setting.

However, there are a few weaknesses, summarized below.

(1) Important references missing: there are a few recent papers that studied very similar settings which the authors weren't aware of:
ICML 2020, Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification, by Chen Dan, Yuting Wei, Pradeep Ravikumar
https://arxiv.org/abs/2010.11213: Precise Statistical Analysis of Classification Accuracies for Adversarial Training, by Adel Javanmard, Mahdi Soltanolkotabi
https://arxiv.org/abs/2010.13275: Asymptotic Behavior of Adversarial Training in Binary Classification, by Hossein Taheri, Ramtin Pedarsani, Christos Thrampoulidis
All of these papers studied a Gaussian setting (which is a special case of the sub-Gaussian setting studied in this work). The latter two papers also worked on overparameterized models under d/n = \Theta(1) regime, which is slightly different from this paper (their results are stronger in certain aspects and weaker in some other aspects).

I think a detailed comparison with these works is very necessary and may help readers understand the contribution and novelty better.

In particular, I have a few questions regarding the differences with these papers: 
(1a) In Dan et al. 2020 (mentioned above), the authors proposed a notion called "adversarial signal-to-noise ratio", which measures the difficulty of adversarially robust classification in the Gaussian setting (a special case of this work). If my calculation was correct, for isotropic Gaussian mixture with l_inf perturbations, 
$$AdvSNR = \|\mu\|_2 - \epsilon \|\mu\|_1 $$
Since the minimum error is roughly exp(-O(AdvSNR^2)), which roughly translates to 
$$\exp(-C*(\|\mu\|_2^2 - 2 \epsilon \|\mu\|_1\|\mu\|_2))$$ 
in the risk bound. However, in this work (theorem 4.4 and 4.8), the risk bound has the form of
$$\exp(-C*(\|\mu\|_2^2 - 4 \epsilon \|\mu\|_1) - C'\|\mu\|_2 )$$ 
Can you explain this discrepancy? Is this a typo, or something more fundamental, like (I) the difference between Gaussian and sub-Gaussian or (II) the specific behavior of adv-trained classifiers that are different from information-theoretically optimal classifiers?

(1b) In Javanmard et al. 2020 and Taheri et al. 2020, the authors of both papers analyzed the setting of Gaussian mixtures in the d/n=O(1) setting. However, the analysis in this work (see theorem 4.4) requires d>= C*n^2 log(n), which is quite heavily overparameterized. To me, the proportional d/n=O(1) setting appears to be much more natural (although this may be my personal taste), and I think the analysis in this work isn't showing the complete story due to this requirement - it will be great if we can understand the behavior of adv training in the sub-quadratic overparameterization regime. 

(2) There doesn't appear to be much clear take-away from the theoretical results. While this paper is written clearly, it is a little too dry, and the lacking of take-aways limits the impact on the whole field of adversarial robustness. Besides, some of the behaviors that appeared in this work contradict empirical evidence for deep neural networks. 
For example, one of the main messages conveyed by this paper is that overfitting is benign in adversarial training. However, this is clearly not true for deep neural networks, as observed by Rice et al. 2020. This discrepancy takes the validity/usefulness of the setting studied into question.

summary_of_the_review: I like the theoretical results. However, some more detailed comparisons with prior works, along with take-aways for practitioners, are necessary to make this paper better.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the analysis of benign overfitting in linear regression, first described in Bartlett et al. (2020), and extends it to the case of adversarial linear classification. Previously, Chatterji & Long (2020) had studied the non-adversarial classification case, so the main new result is an extension to the adversarial case.
main_review: The main claim of the paper is that benign overfitting occurs in the adversarial case as well--that is, even though the training data are overfit perfectly, one can still attain reasonable generalization error. However, in practice it is well-documented that overfitting is indeed worse for adversarially-trained models, so I think an adequate analysis in this case would explain this phenomenon. I was not able to get such an explanation from the paper, although I may have missed it.

Aside from explaining empirical results, another potential contribution of theory papers is introducing new proof techniques. The paper does not include a discussion of what new technical contributions or proof techniques it contributes, so it was difficult to assess this aspect. While there is a proof outline in Section 5, it is not clear what is novel and what follows the previous proofs.
summary_of_the_review: I did not feel the paper made significant empirical or explanatory contributions, and was unable to assess the theoretical contributions. I thus overall would recommend against accepting the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the clean test and adversarial test error obtained using   _Gradient Descent Adversarial Training_ (GDAT). The data distribution is the gaussian mixture model and the hypothesis class is lilinear classifiers.

In Theorem 4.4, the authors show that the clean test error is worse than than the inherent noise rate. However, benign overfitting still exists though a larger $\epsilon$ for the adversarial training hurts clean error.

In Theorem 4.8, the authors upper bound the robust test error obtained by GDAT. The result shows that adversarial error is certainly worse off than clean test error. Perhaps somewhat interesting this also shows that the perturbation radius needs to decrease with increasing $d$.


main_review: Strength

The behaviour of overparameterised models in the presence of noise when trained with adversarial training is certainly a very important problem as both of these components(overparameterisation and noise) are important components in the ML context.

The analysis is clean and simple. The results are interpretable and  confirm the intuitions that one has about this problem,

Weaknesses

The proofs rely very heaviliy on Li. et. al. 2020 and Chhaterji et. al. 2020, which raises questions about the technical novelty of the paper. In particular it relies heavily on the characterisation of the GAT solution in Li. et. al. 2020 and the characterisation of test error in the presence of noise in Chatterji et. al. 2020. 

The paper also deals with a simple linear model and it is not immediately clear how it relates to overparameterised neural networks. While it is important to first understand a complex phenomenon theoretically on a linear model, in the absence of  a huge amount of novelty in the theory, I find this second drawback rather glaring.


[1] "Implicit bias of gradient descent based adversarial training on separable data", Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao, ICLR 2020.

[2] "Finite sample analysis of interpolating linear classifiers in the overparameterized regime", Niladri S Chatterji and Philip M Long.


========Update=============

I have read the author's response. It didn't change my view on the paper as the authors did not provide any new information. However, I would still recommend acceptance of the paper based on my initial evaluation of the paper.  The problem is important and the results while, might appear a bit derivative and for a simple setting, it might be necessary to first look at this simple setting to get a better progress.
summary_of_the_review: In short, I found the problem interesting and the solution clean and understandable.

However, the technical novelty in the work is relatively low and it mainly involves combining existing works in a smart way. I would urge the authors to either extend the theoretical results eg. by looking into more complex hypothesis classes or to improve the experimental work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Learning with an over-parametrized model is an important problem in machine learning, and the benign overfitting problem garnered attention. The results shown in this paper has a significant implication in this context. In this paper, the authors investigate the phenomenon of benign overfitting in adversarial training. Surprisingly, the authors report that the benign overfitting phenomenon can be observed even in the case where we use adversarial training. The authors' approach is reasonable and should serve as a reference for future research.
main_review: The problem discussed in this paper is very essential in machine learning, and the method of analysis will be useful for future reference.
The authors show that the upper bound of adversarial risk under adversarial training becomes similar to the standard risk under adversarial training. 

However, I could not how the theoretical result relates to the "benign" or optimality.  
- In this context, what does the "benign" means?
- Are there lower bounds on both of adversarial risk under adversarial training and the standard risk under adversarial training?
- Do the upper bound match the lower bounds? I would like to see a clearer explanation of the connection between the two.  

The result just implies that the upper bound under adversarial risk matches that under standard risk, but this does not imply the "benign overfitting" because there is a possibility that the upper bounds are not tight.

Minor:
Holders' -> Hölder's?
summary_of_the_review: This paper studies a very interesting setting. The approach is meaningful and can be used for future reference. However, I could not understand the extent to which the authors' claim of "benign overfitting" is supported. Therefore, I vote weak reject. If this point becomes clear to me and readers, I will raise the score to acceptance.
review_title: null

Meta-review: The paper studies the benign overfitting phenomenon for linear models with adversarial training. The main issue is that the result is quite expected for experts versed in the benign overfitting papers, and indeed the reviewers pointed out that they could not see much technical novelty. However, even more importantly, the original benign overfitting papers had the advantage of proposing of simpler model (linear!!!) with the same behavior as the complex ones in practice. This is not the case here, as the result diverge from empirical observations on deep networks. The authors argue that it is a valuable finding that the empirical observation is not "universal", but this is a somewhat moot point as linear models are a priori very very different from the setting in which these empirical observations were made. For these reasons I believe the paper does not meet the bar for ICLR (yet it could still be publishable elsewhere).
Decision: Reject