Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper formalizes different definitions of adversarial risk for binary classification and studies the equivalence between those definitions. Moreover, the authors analyze optimal adversarial risk through the lens of optimal transport, which leads to the existence of a Nash equilibrium of the adversarial robustness game. The contribution of this paper is theoretical.
main_review: 
**Originality**

This paper is original and novel as far as I can see. It seems that one of the closest work to this paper is *M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings.* The authors discuss their advances from this one. 

**Quality**

I did not notice wrong statements in the main paper. However, I only read the proofs in the main paper. 

My questions are the following.

1.	This paper defines the adversarial risk as various set functions, i.e., loss function w.r.t. the decision region $A$. However, it is more general to define the adversarial risk w.r.t. the model $f$ itself.  For example, given the input space $\mathcal{X}$, output space $\mathcal{Y}$, the data generating distribution $p\in \mathcal{P}({\mathcal{X}\times \mathcal{Y}})$, and a cost function $c: \mathcal{Y} \times \mathcal{Y} \to [0,+\infty)$, the adversarial loss function can be modeled by $$R(f)=\int \sup_{x'\in B_\epsilon(x)} c(f(x'),y)\ \ \mathrm{d}p(x,y).$$
For binary classification, any function $f:\mathcal{X}\to \mathbb{R}$ defines a decision region by $A=f^{-1}((0, +\infty))$. By defining $c(\cdot,\cdot)$ to be the $\ell_{0/1}$ loss based on the decision region, it seems that it recovers the $R_{\oplus \epsilon}$ loss. Moreover, the above $R(f)$ can be applied to other settings, e.g., multi-class classification and regression.
    
    Denoting $\ell^\epsilon(x, y)=\sup_{x'\in B_\epsilon(x)} c(f(x'),y)$, to study the well-definedness for $R(f)$, it becomes to study the measurability of $\ell^\epsilon$ and the integrability of $\ell^\epsilon$ w.r.t. the data generating measure $p$. Therefore, does studying the well-definedness of $R(f)$ give the well-definedness of the set-based risk function? Moreover, what are the benefits of studying the set-based risks over the function based risk $R(f)$?

2. For Theorem 6.1, it is mentioned that the infimum on the right hand side is attained. I'm curious that is the supremum on the left hand side attained? It seems that it leads to whether the optimal $A$ in Theorem 6.2 is attained. 
3. For non-theory people, the contribution of this paper may be limited. For example, an empirical person may think that the measurability is never a problem in real-world machine learning. Since NeurIPS is a big conference where attenders have diverse background, is there any point of this paper that may intrigue an empirical person?

**Clarity**

This paper is rigorous and well-written as far I see. 

**Significance**

It is important in the sense that this paper rigorously defines several adversarial risk functions, filling the gap of previous work and building the ground for future work.
limitations_and_societal_impact: The authors discuss some of the limitations of their results in section 8. Comparing to the condition of Lebesgue measurable, I'm more curious about the case of general loss functions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper focuses on formalizing the definition of "adversarial risk" which is risk under test-time perturbation attacks. The focus is on subtle measure theoretic issues that arise when the distributions are continuous. 
main_review: Several definitions are given for adversarial risk in the literature. Most are not formal, and some are formal. The paper’s starting point is the formal ones. Yet, it revisits those definitions in the general case where distributions are not discrete, and hence subtle points arise about measurability of events and in particular whether or not certain probabilities associated with adversarial risk are always well defined. In particular, it is argued that some definitions use a union of Minkowski balls, which in general is not a measurable set. Other subtle points arise depending on what measure is used (e.g., Lebesgue or not). The paper also gives conditions under which: (1) various definitions become equivalent, (2) certain objects of interest exist and are characterized by intuitive formulations (e.g., optimal classifier under attack and Nash equilibrium in adversary’s game against algorithm designers).

As far as I understand, these points only arise when we pay attention to subtle aspects of formalism in a measure theoretic sense for general measures. So, this makes the work quite theoretical, as “in practice” (e.g., when we deal with *algorithmic* attacks and distributions), everything is discrete and none of the issues studied here arise. So, I don’t think the paper has a “practical” effect, as basically all the definitions that paper revisits are fine in the discrete setting and all the subtle points the paper mentions only show up when we go beyond the discrete case and start to care about measurability of sets in the continuous regime. 


In fact, typically, by just assuming the space to be Polish these issues go away (e.g., see the last paragraph of page 11 here http://cgm.cs.mcgill.ca/~breed/conc/Talagrand.pdf) but evidently, in the context of adversarial risk and optimal adversarial strategies certain issues still exist, and the paper shows how to resolve them by carefully finding sufficient conditions. 

The writing is very clear and precise and readable, and that is a big plus for a paper that has such a goal of formalizing notions.

Overall, I think the paper fills a gap in an important direction, even though this gap is purely theoretical and has no immediate impact on the “practical” side. Still it is important to have a general and precise theory for this phenomenon, and that could be important to practice also in the long run. Considering the quality and clarity of the writing and its content, I think the paper will be useful for the program and recommend acceptance.

Comments:

What is the main reason for focusing on binary classification? Any major limitations for larger label sets?

The term “decision region” is used in line 46 which is not clear. It is clarified later in line 109, but it is confusing the first time around.

The paper’s formulation of adversarial risk does not pay any attention to whether or not the perturbed point is in fact misclassified. Of course, if the perturbed point is “close” to the original point to the degree that the “truth” does not change, this would happen and this is how adversarial examples are perceived (“imperceptible” changes in a setting where humans are the judge for true labels). The issue is discussed here:
http://proceedings.mlr.press/v89/suggala19a/suggala19a.pdf
and the cited paper [9]. This aspect does not negatively affect this paper, becaue the paper's focus is mostly on "welldefinedness of events", yet it would be good to know how this can fit into this paper’s formal studies.

The letter “T” is used for both the probability weight and the transportation notation.

Line 156 : “It generalizes a similar result of [32] for closed and open sets. ” What is the key new insight? In general, it would be good to point out the new part of the generalized arguments.

Line 290: “Our minimax theorems establish such an equality.”
But in the cited paper [31] the authors say "Then we demonstrate, in Section 4, the non-existence of a Nash equilibrium in the deterministic setting of this game".
How is their result compatible with yours? Please clarify.

Line 362: “transport characterization adversarial risk” I think you need to add “of” after “characterization”

limitations_and_societal_impact: The paper is mainly theoretical and the long term impacts are positive.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper extends previous works of the study of the adversarial risk. The authors interest in the well definition of the adversarial risk. They then show a minimax theorem on the game between the classifier and the adversary.
main_review: Overall I enjoyed reading the paper. The paper brings insights on Adversarial risks extending previous results from the literature. The paper is well written and easy to follow. The current trend of theoretical papers on adversarial attacks can be only beneficial for the understanding of the topic. I tried to make a thorough reading of the proofs, but I still might have missed some points. I would like to discuss the following points with the authors:

- On the definition of the adversarial risk. I believe it is provable that $A^{\oplus\epsilon}$ is  analytic (cf 1 for more details) and hence universally measurable. Idea: write $1_{x\in A^{\oplus\epsilon}}$ as $\sup_{a\in A} 1_{x\in\bar{B}_\epsilon(a)}$. Then you can use the results from Bertsekas and Shreve (2004), Prop 7.39 and Corollary 7.42.1. Maybe the authors can use these ideas to prove a more general result. I think all further results can be extended to all Borel sets instead that only $G_\delta$ and $F_\sigma$ sets. I am happy to discuss more about this during the rebuttal phase. I might be mistaken, but I think it worth discussing. It would simplify some results in the paper I’d say.

- The authors said they prove the existence of Pure Nash equilibria. Although the classifier is deterministic, the attacker is still « randomized ». Maybe they should mention that the equilibria are hybrid. This result seems right and reasonable.

- I would also suggest the authors to give some more intuition to the different notions of risks the authors introduced. For instance, draw some figures to explain it. It would be more readable for non advertised readers

- Finally, although I enjoyed reading the paper, I also find that the paper lacks a bit of novelty with regards to existing literature (Pydi et al., Dohmatob, Bhagoji et al.). These papers have proved the majority of the results exposed in the paper ($W_\infty$, $c_\epsilon$ costs,etc.). The authors managed to treat unbalanced probabilities. This is my major concern about accepting/rejecting the paper. I am willing to discuss with the authors and the other reviewers on this.

For now, I rate this paper as borderline,  but I am willing to change my rating if the authors explain to me more clearly the novelties of their paper. Moreover, I hope authors can get rid of their hypothesis on $F_\sigma$ and $G_\delta$.
limitations_and_societal_impact: The understanding of Adversarial robustness is a very important topic. It can impact positively the safety of autonomous ML systems.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a lot of theoretical insights to connect the different definitions of adversarial risk. It also discusses some other properties such as well-definedness and minimax theorem.
main_review: Originality: this paper utilizes a lot of different mathematical tools and provides rigorous analysis. Such an analysis is complicated and is novel based on my knowledge.

Quality, clarity and significance: my biggest concern is that the paper piles up a lot of different definitions and mathematical symbols, which may prevent readers from related areas to understand it (e.g. people who work on empirical study of adversarial training).  The authors are strongly encouraged to reorganize this paper and simplify some notations so that it has a more clear structure and is easier to understand.  Two examples:

(1) Although this paper uses the definition of adversarial risk in [9], the definition in [9] is self is much easier than the one in this paper to understand. Please consider use simple definitions first (even informal), and try to provide their more formal definitions later. 

(2) The four contributions listed in Section 1 need to have a clear connection with the following five sections in this paper. I would suggest to first write down the corresponding sections when listing the contributions, and recall the readers about the this when starting each section.

The authors also need to emphasize the significance of this paper, e.g. provide some concrete easy-to-understand example where some definitions of adversarial risk may fail while others work well, and provide some experiments (or even simple simulation) to help illustration. It is hard to justify the significance of this paper from its current writing. 
 
A minor issue:
A missing related reference: Xu, Q., Bello, K., & Honorio, J. (2020). A Le Cam Type Bound for Adversarial Learning and Applications. arXiv preprint arXiv:2007.00289.

====================================================

After author feedback:

The authors provided useful materials for the readability based on my major concern. Raised my score from 5 to 6.



limitations_and_societal_impact: No social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper discusses different definitions of adversarial risk that have been used in various papers throughout the years, where, by using tools from optimal transport theory, robust statistics, functional analysis, and game theory, these definitions are viewed under a different lens, and in several ways new connections (and separations) between some of these definitions are established. 

main_review: The paper first gathers and discusses different notions of adversarial risk and then takes a unified approach on looking at these definitions in different settings. Though I have to admit that I have not carefully looked into the proofs, I think that for the largest part the paper is ok and provides the reader with new insights connecting different definitions of adversarial risk. Having said that, there are some claims in the related literature that are a little bit confusing to the reader and indeed not all the definitions are discussed. 

Section 3 is very important as the authors discuss 4 different definitions of adversarial risk. However, the way some definitions are presented is confusing for the reader. 
- For example, the authors claim that the formulation of adversarial risk studied in [9, 16] is a special case of the approach followed in [25, 34]. This is only partially true as [9] and [16] spend a significant amount explaining the differences between different definitions and in particular those that are used in [25] and [34]. So, while the papers [9] and [16] indeed discuss, among other things, a special case of the definitions used in [25] and [34], they nevertheless take a different route and explain that when misclassification is the goal for the generation of adversarial examples, then the definitions used in [25] and [34] may in turn compute completely wrong values. As an extreme case, for example, when PAC learning Boolean functions, it is often-times the case that we learn the target function completely. Then, in such situations [9] and [16] claim that indeed the learnt model is infinitely robust since it cannot be fooled by any adversarial example. However, both [25] and [34] can somehow claim that they can find adversarial examples in these situations, by making the model flip the prediction label. However, when the ground truth also changes, then there is no misclassification -- which is really the whole point behind adversarial examples. This is also true in equations (2) and (3) in this paper where we can see that the adversarial risk would be positive, even if the model was entirely correct against a ground function that does the labeling. 
- And to go one step further, equation (3) in the current paper still makes this assumption, and I do not believe it is even studied in [26] which is cited as the paper where this definition has its origin. [26] uses the same definition of "error-region adversarial risk" that is used in [9] (or what is called "exact in the ball adversarial risk" in [16]).

The above points need to be clarified so that everything is crystal clear to the reader. The current paper studies variations of adversarial risk that follow along the lines of "corrupted-inputs adversarial risk" [9] or "constant in the ball adversarial risk" [16]. Such versions of risk are indeed special cases of [25] and [34]. But in general, and that is the main point of [9] and [16], these definitions do not compute, adversarial examples -- again, assuming that misclassification is the goal of an adversarial example, and I believe we all agree that this is indeed the goal.

Hence, as far as I understand, the current paper indeed tries to formulate variations of the "corrupted-inputs / constant in the ball" adversarial risk. This has indeed its own merit, but the presentation in section 3 needs to be more careful and really explain things in a better way. The current paper does not touch upon the different definitions that are out there -- in fact, in some situations I believe that the presentation is entirely misleading. 

Getting along I must admit that I really appreciate all the effort and the work that the authors have done and indeed I find the different connections that are established, to be interesting. The authors try to be clear and make interesting comments on their results. Nevertheless, it is also a little bit unclear to me up to what point we can accept some of the consequences, in general, as this assumption of maintaining the ground-truth label in some region around a sampled point does not necessarily hold.

*Post-rebuttal:*

Thank you for the response to all the reviews. I am looking forward to seeing the improvements that have been suggested on clarifications by myself as well as from the other reviewers. Assuming these clarifications will be seen in the final manuscript, I am increasing my score from 5 to 6. Thank you for a very interesting paper!
limitations_and_societal_impact: I am happy with the discussion that the authors have done in the paper.
review_title: null

Meta-review: All the reviewers agreed that this paper provides important contributions in the area of robust learning. I recommend to the authors to incorporate all the comments made by the reviewers in the updated version of the paper. The reviews have indeed brought many important points.
Decision: Accept (Poster)