Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the adversarial robustness of the majority vote method by deriving PAC-Bayesian generalization bounds in the adversarial settings.
In details,  the adversarial robustness means that an algorithm can still work well when the input covariates "X" is adding some noise but not the labels "Y".

main_review: The paper, itself, introduces two novel definitions for (and relates to) the classical adversarial risk, which are "Averaged adversarial risk" and "Averaged-max adversarial risk".
PAC-Bayesian empirical bounds are derived with respect to these two risks for the "surrogates linear loss" of the weighted majority vote. 
An algorithm is also given by minimizing these empirical bounds and some applications to real data sets are given to illustrate the soundness. 

Although the used Pac-Bayesian bound technique in this paper is known, the settings considered is novel. Thus, I believe these theoretical results are an important contribution.

However, my main concern is that: 
As in Theorem 6, the authors noted that the result does not depend on "n". 
While Theorem 7 is stated for all 'n', So, could you compare these bounds?

Other comments:
1. (line 15-17) any reference for this claim? "This phenomenon known as adversarial robustness contributes to the impossibility to ensure the safety of machine learning algorithms for safety-critical applications such as aeronautics functions (e.g., vision-based navigation), autonomous driving or medical diagnosis."
2. (line 19) is badly written, I can not understand this "...of its input; We talk about adversarial examples. In other words, ......."
3. (line 74) "The learner objective is then to...." should be "The learner's objective....."
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies robust generalization using the PAC-Bayes framework. Specifically, the authors establish bounds on relaxations of the worst-case adversarial risk. In the first relaxation (Theorem 6), they are concerned with the average-risk with respect to a distribution over adversarial distributions (instead of worst-case). The second relaxation (Theorem 7), is concerned with an average-max risk, where instead of drawing a single adversarial perturbation, n adversarial perturbations are drawn and then the worst-case among them is counted. The authors also provide a bound on the gap between their relaxations and the worst-case adversarial risk (Proposition), which depends on the total-variation distance between the fixed distribution and the worst-case. 

The authors also ran empirical experiments with an adversarial learning procedure that is inspired by the theoretical bounds.
main_review: Applying Bac-Bayes analysis to obtain robust generalization bounds is new and hasn’t been considered in prior work to the best of my knowledge. However, what is concerning is the fact that the bounds established are on relaxations of the worst-case adversarial risk. 

The authors do not provide strong justification for why such relaxations are considered, e.g., is it the case that the analysis breaks down when studying the worst-case adversarial risk? 

While the relaxations may still be useful, I am not totally convinced of that yet. For example, the total-variation distance in Proposition 4 can be arbitrarily large, and will really depend on how good the choice of distribution D is. Even though the authors empirically show that the gap is small on datasets of MNIST and Fashion-MNIST, I am not sure if these are appropriate datasets to compare the gap between the relaxations and the worst-case since they are in a sense "easy" datasets that we can train robust models against.

Can the results in Theorems 6 and 7 be extended to obtain generalization guarantees against a specific attacking algorithm? For example, what if in distribution D the adversarial perturbations are generated by the PGD attack. The challenge that I see is that in this case the distribution over adversarial perturbations will depend on the specific predictor/classifier that is being attacked. But this is really what is sort of happening in the experiments in Section 4. Where a prior P_0 is chosen, then distribution D over adversarial perturbations is determined as a function of this prior (and PGD attack), then a posterior Q_0 is learned, then this is repeated again with prior P_1=Q_0, and so on. It would be nice if the theoretical guarantees in Theorems 6 and 7 can be extended to capture this dynamic.

In Section 4.2, I believe that including the simple baseline of adversarial training with a single classifier (compared to a majority-vote) would be useful. Also, how is the majority-vote predictor attacked? It would be good to include details of this.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

After Rebuttal. 

I thank the authors for their response. After consideration, I decided to keep my score the same.
I do think that this would be a stronger contribution if perhaps the authors could strengthen their results in Theorems 6 and 7 to obtain generalization guarantees against specific attacking algorithms. This would be one way to show case the usefulness of considering the PAC-Bayes framework, and the relaxations to adversarial risk considered in this work. 

While the authors comment in their response that this is possible, I am not fully sure that it follows immediately, and perhaps some care is needed.
limitations_and_societal_impact: In my opinion, the authors have adequately addressed the limitations of their work. Also, while it is true that the work is mainly theoretical, the authors should address how their theoretical guarantees can impact society.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a PAC-Bayes analysis of adversarial robustness. In opposite to standard techniques that derive a worst-case analysis of the risk over all the possible perturbations, the authors use PAC-Bayes bounds to design a learning algorithm that minimizes an adversarial risk. They also provide numerical evidence to support their theoretical results.

main_review: This paper is clear and well written, and the theoretical analysis is sound, and technically quite solid. These are nice results. I enjoyed the idea of using PAC-Bayes to analyze adversarial robustness and obtain theoretical guarantees on the adversarial risk. However, I'm not convinced that in general, considering the averaged-risk can really help much for adversarial attack as it is generally a classifier- and sample-dependent risk.

I enjoyed the experimental section as well. However, a point that I do not understand (and that I think quite important as the aim of PAC-Bayes is to provide a learning algorithm through the bound) is why the authors do not optimize the TV distance in the bound. They say in the supplementary material that "this term is 0 when we sample one noise for each example", but this is not a requirement, and the TV distance is a key quantity in the bounds of the authors, specific to their analysis. Also, I would have liked seeing experiments on more complicated datasets like CIFAR-10.
limitations_and_societal_impact: No specific societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the problem of robustness to evasion attacks from a learning theory point of view. Unlike most existing works from the literature, the authors do not study the uniform bounds on the worst-case risk under attack (a.k.a. adversarial risk). Instead they introduce a new analytical framework that considers less powerful randomized adversaries and majority vote classifiers.  This new setting allows them to leverage existing results from the PAC-Bayes literature; hence providing generalization bounds on the averaged risk under attacks of a majority vote classifier (where the average is taken over the randomness of the adversary). 
main_review: Relevance: The topic of evasion attacks is still lacking some theoretical ground. Accordingly, presenting new theoretical results to this community is an interesting and relevant line of research.

Clarity: The paper is well written and understandable. Nevertheless I feel like some statements (listed below) lack justification or at least were not perfectly clear to me.
- In line 44. The authors say that their definition has the advantage of being suited to majority voting. While I agree with this statement, it is unclear to me why previous definitions were not. Indeed, I can always define my hypothesis space as being a set of classifiers that have been constructed by majority voting, which allows me to apply every classical definition from adversarial learning theory (including adversarial risk). Did I misunderstood something here? 
- In line 46. The authors claim that their bounds are independent from the kinds of attacks they consider. However, it seems to me that the attack they consider does have an impact in the bound presented in Theorem 7. Indeed the TV term depends on $\mathcal{E}_i$ which is directly sampled from $D$ (i.e., the distribution characterizing the set of randomized attacks considered).
- In lines 208-209. It was a bit unclear to me what the TV term in Theorem 7 stands for. The authors state that this term goes to $0$ when the voters are fooled by the same attack $\epsilon \in \mathcal{E}_i$, but such a setting seems counterproductive to me. If all the classifiers are fooled by the same attack, then I don’t see how building majority vote classifiers with them will bring robustness to the system. 
- In line 249, the authors present their randomized adaptation of $PGD$ and $IFGSM$ attacks, namely $PGD_U$ and $IFGSM_U$. I felt like the definition of these new attacks was a bit confusing. More precisely, it was a bit unclear to me whether the uniform noise was injected before performing the attack or after (i.e., directly adversarial example computed with $PGD$ or $IFGSM$). I think it is the latter, but to make this clearer, the author could present these attacks a bit more formally (only one line explaining where the uniform noise is injected). 

Quality: The technical part of the paper looks sound to me. The main issue I have with this part is that it does not clearly relate to the problem of adversarial examples usually considered by the ML community. In general, in the problem we are interested in (even for a fixed model and not a class of models), we study a worst-case scenario, i.e., if the attacker can find the solution to (5). Here the authors consider a much weaker model where the attacker can only select the best attack from a fixed-size set of random points. While the authors claim that their definition can be connected to the classical problem (Propositions 3 and 4), this connection seems quite loose to me and not very informative. Indeed, as there is no concrete values for $TV(\Pi,\Delta)$, the left-hand term in (8) could be arbitrarily small. I think it would have been much more convincing to present a connection that depends on the number of samples one considers, not only an inequality like in Proposition 3, but a true dynamic depending on $n$ and $D$. 

Similarly, I think the experimental part of the paper was not convincingly illustrating the connection between the adversarial risk and the averaged risks the paper introduces. The authors are only studying an empirical version of the adversarial risk, that has been calculated using a specific attack (that might as well be suboptimal). Accordingly, I don’t think that the author should claim to provide non-vacuous bound on the adversarial risk. On the randomized attack part, if my understanding of the adversarial attack $PGD_U$ and $IFGSM_U$ is right, I think these attacks are suboptimal. In fact, there is no clear reason to me why injecting uniform noise on an existing attack could provide stronger examples. To consider randomized attacks in a stronger scenario, I suggest that the author uses random restart instead (i.e., inject the uniform noise before computing the attack) which is a well-known technique to improve the efficiency of PGD and IFGSM. More generally, the authors could strengthen the experimental protocol by following some good practices to guarantee that the attacks have been correctly computed (see e.g. [1]).

Originality: To the best of my knowledge, this work is the first one to consider adversarial robustness through the lens of the PAC-Bayes Learning. Nevertheless, I feel like the authors failed to compare with (or at least to discuss) some important lines of research that are connected to the present work. 
- The classifiers considered in the paper are built by a majority voting rule as $\text{sign}(E_{h\sim\mathcal{Q} }[h(x)])$. This formulation is very similar to certifiable defenses based on randomized smoothing (see e.g. [3,4]). Let us for example consider a real-valued hypothesis $h$, and $h_\delta$ the function defined as $h_\delta(x) := h(x+\delta)$. Let us also set $\mathcal{Q}$ to be the distribution that samples $\delta$ from a Gaussian distribution $\mathcal{N}(0,\sigma^2)$ and outputs $h_\delta$. Then $\text{sign}(E_{h\sim\mathcal{Q}}[h(x)])$ reduces to applying randomized smoothing with Gaussian noise $\mathcal{N}(0,\sigma^2)$. Accordingly, it would be interesting if the author could explain how these techniques differ from theirs, if their bounds are applicable to randomly smoothed classifiers and how their bounds can be compared to the certificates presented in previous works. 
- One of the originality of this paper is to consider randomized attackers. In this context, it could be interesting to compare to some recent theoretical works (see e.g. [4,5] ) investigating adversarial robustness from a distributional point of view (i.e., where the attacker can be random).

[1] Florian Tramèr, Nicholas Carlini, Wieland Brendel, Aleksander Madry. On Adaptive Attacks to Adversarial Example Defenses. NeurIPS 2020. 

[2] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. ICML 2019.

[3] Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, Sebastien Bubeck. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. NeurIPS 2020.

[4] Muni Sreenivas Pydi, Varun Jog. Adversarial Risk via Optimal Transport and Optimal Couplings. ICML 2020.

[5] Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, Yann Chevaleyre. Mixed Nash Equilibria in the Adversarial Examples Game. ICML 2021.

limitations_and_societal_impact: I don’t see any possibly negative social impact of this work.
review_title: null

Meta-review: The author(s) provide the 1st PAC-Bayes bounds proving robust generalization in the context of adversarial robustness. The risk they consider is not the usual "worst-case adversarial risk", but randomized versions (or relaxations), that imply a less powerful adversary. Two versions are considered: Theorem 6 is a bound on an average risk with respect to the distribution on the adversary, while Theorem 7 considers the worst case of n random attacks.

The paper relies on standard PAC-Bayes techniques, but they are applied to a new setting: adversarial robustness. Given the lack of theoretical results in this setting, all Reviewers agree that such results are potentially very interesting.

On the other hand, the relaxations studied in Theorem 6 and Theorem 7 are not standard in the literature on adversarial robustness. Three Reviewers: y2sg, Jhjk and N9WH, questioned these definitions and expressed doubt that they would be of interest to researchers in the field of adversarial robustness. The discussion allowed some clarifications, but overall, it remains clear that, while these results are new, the authors failed to convince that they will be useful for the community of adversarial robustness.

For this reason, I recommend to reject the paper. I encourage the author(s) to work on a new version of the paper, but you should either work on the worst-case risk, or explain to what extend the average risks they introduce is related to the worst-case risk. You should also take into account the typos found by Reviewer KAbu and the many comments of Reviewer Jhjk. I wish you good luck with the revision of the paper.
Decision: Accept (Poster)