Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a fundamental question regarding the adversarial Bayes classifier, i.e., does the optimal Bayes classifier exists and does it have any robustness guarantee. The contribution of this paper is theoretical: it proposes the concept of ‘pseudo-certifiable robustness’ and proves that the optimal Bayes classifier exists and satisfies the proposed ‘pseudo-certified robustness’. The proofs are mostly about real analysis and measure theory. 
main_review: **Originality**

The concept of ‘pseudo-certified robustness’ is new to me. In addition, by formalizing the adversarial risk as a function of sets and thus transforming the original problem to a real analysis problem, the proof techniques seem to be not very common in the adversarial machine learning literatures. 

**Quality**

The paper is rigorous and mostly well-written. Reading through the main paper, I did not notice wrong statements assuming all the lemmas are correct. The contents in appendix are quite overwhelming, for which I only had a skim.

I do not have any major criticisms for this paper, but I do have some suggestions. I think some of the considerations may be too mathematical and far away from the area of machine learning. These pure mathematical considerations complicate the proofs and theorems, while has no real meaning to machine learning. 

For example, the measurability issue of $A\oplus \overline{B_\epsilon(0)}$. Even though there exists extreme cases where the direct sum of two measurable sets is not measurable, I do not think that can be a real problem for machine learning models. The authors put quite an effort to establish the ‘universal $\sigma$-algebra’, but the measurability issue can be worked around effortlessly by being a little bit more ‘machine learning’. I am not suggesting being less rigorous but being a bit more practical.

Concretely, $A\oplus \overline{B_\epsilon(0)}$ is open, thus measurable, if $A$ is open. Moreover, $A\oplus \overline{B_\epsilon(0)}$ is measurable if $A$ is closed (See Lemma 3.1 in [1]). This kind of $A$ (i.e., being either an open set or a closed set) should cover most of, if not every, realistic cases I think. For example, $A=\\{x:f(x) > 0 \\}=f^{-1}((0, +\infty))$ is open whenever the model $f$ is continuous, which covers many common models, e.g., SVM, neural networks with any continuous activation like ReLU and Sigmoid. Moreover, I think there should be weaker conditions for $A\oplus \overline{B_\epsilon(0)}$ being measurable to hold. 

The bottom-line: the results are interesting, but I believe there are simpler ways to deliver the same message without sacrificing rigorousness.

Question: Theorem 1 proves that the minimizer of adversarial risk exists and is pseudo-certifiably robust. However, it seems that pseudo-certified robustness alone cannot guarantee a low adversarial risk. What other conditions do we need to guarantee pseudo-certified robustness imply low adversarial risk? More generally, it would be interesting to see more investigations about the pseudo-certified robustness.

**Clarity**

The paper is well-written in my opinion. 
Minor things: line 193 typo (is is is). In Lemma 4 $X$ should be $\mathbb{R}^d$? Some equations are too wide (e.g. line 318, 329)

**Significance**

I think the results of this paper is novel, fundamental and important.

[1] Adversarial risk via optimal transport and optimal couplings. Muni Sreenivas Pydi and Varun Jog.

limitations_and_societal_impact: The main result (theorem 1) requires a strictly convex norm which excludes two common norms, $\ell_1$ and $\ell_\infty$. The authors discuss this limitation in appendix.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proves the existence of universally measurable classifiers minimizing the adversarial risk for strictly convex set of perturbations. This is the first result of this kind in adversarial literature.
main_review: I would like to highlight how nice it is to see theoretical papers in the field of adversarial attacks. I really believe this kind of paper can improve the research in the field and helps understanding the very nature of this phenomenon. The paper is very technical. I acknowledge I have a good background in measure theory which helped me understand better the paper. Yet, this paper needs to be somekind of simplified if the authors would like it to have an impact broader than people mastering measure theory and having interest in adversarial machine learning. I am fine with the current version, but it is rather a suggestion. 

I must admit I read the proofs but I did not check them carefully. From what I read, I am confident in the results. In the meantime of the review it is complicated to have a thorough reading of the paper and the proofs for such a technical paper. That said, I still have some comments about your work:

- The supplementary material is very difficult to read. I suggest the authors to write a linear appendix. Going up and down to check proofs is not very comfortable.
- Measurability of the adversarial risk was treated in this paper [1] using the same concepts of universal measurability.
- I am not sur  the risk $R^\epsilon(f)$ defined L138 actually corresponds to the risk $R^\epsilon(A)$. I think the "right" loss should be $1_{ysign(f(x))\leq 0}$. but I might be mistaken
- The paper is motivated by calibration/consistency and provable robustness. I am not sure to see the direct link. Can the authors elaborate a bit on that?

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

limitations_and_societal_impact: Understanding theoretically adversarial examples can help building more robust networks.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper establishes the existence of a binary classifier which minimizes the expected adversarial loss under a data and label distribution, which they call the adversarial Bayes classifier. The authors do so by constructing a sequence of classifiers which converges to the infimum risk, and then demonstrate that the risk is sequentially lower semi-continuous, which establishes the existence of a minimum. They also extend this result to some non-additive perturbations.
main_review: I am somewhat unfamiliar with the prior work in this area of adversarial learning theory, so I cannot comment much on the originality of the work. Since this seemed to be a point of concern in previous submissions, I will defer to the other reviewers' opinion in this area. However, one point in the introduction about previous work is a bit misleading: in lines 82-84, the authors write that

> a process called randomized smoothing makes the classifier certifiably robust in the `$\ell_2$ norm with high probability. Notably, randomized smoothing is applied after training. A better understanding of the adversarial Bayes classifier could help find other such procedures.

This seems to indicate that prior work has not incorporated certified robustness *during* training, but many papers have explored this idea [1-4, among others]. It would be good to clarify this.

The exposition is good throughout the paper. All the math appears to be sound, although I did not carefully check every proof.

The results seem useful for adversarial learning theory, although again I am not sure exactly how novel they are. I think the authors could do a bit more to flesh out the implications of the work. While the introduction and conclusion refer to giving insight into the consistency of adversarial losses, they are mostly vague. Are there implications of the Bayes optimal classifier being pseudo-certifiably robust? In Appendix B, the authors argue that removing the non-pseudo-certifiably robust region of a classifier generally reduces the loss and that "one could try and device algorithms to take advantage of this property." Moving and adding statements like this to the conclusion or introduction could give some more intuition about why and how the results are significant.

Overall, the paper is well-written and sound; I would vote to accept it if the above concerns are addressed and barring serious concerns from the other reviewers. 

*A typo*: in Definition 1, I believe the last line should read "A is pseudo-certifiably robust *if it is* pseudo-certifiably robust", not "is is is".

[1] Weng et al. Towards fast computation of certified robustness for ReLU networks. ICML 2018.

[2] Wong and Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. ICML 2018.

[3] Zhang et al. Efficient neural network robustness certification with general activation functions. NeurIPS 2018.

[4] Raghunathan et al. Semidefinite relaxations for certifying robustness to adversarial examples. NeurIPS 2018.
limitations_and_societal_impact: The authors state that "our work is theoretical in nature and we do not anticipate any immediate negative societal impact"; I agree with this assessment.
review_title: null

Meta-review: This paper studies a variety of theoretical questions regarding the Bayes optimal classifier and associated robustness guarantees. This is an important topic, adding to the growing discussion around theoretical tools for robustness-related questions. The reviewers found the theoretical results to be substantial, using novel arguments in linear algebra and measure theory. The reviewers also believe that the results are interesting, well-motivated, and technically sound. Therefore, I recommend accepting this paper.

In the reviews, there were two main concerns that the authors should address for the final version of the paper: (1) certain relevant references were missing and should be discussed, and (2) there was a strong suggestion to improve the readability of the supplemental results and proofs in the paper. I agree that both of these should be addressed, and that writing a good theory paper can be challenging but is ultimately a good service to the community. Specifically, for (1), I think the authors can also be clearer in the paper about the relationship with prior work, focusing more on the theoretical comparison between the prior results in some of the references and the present results (e.g., a proper technical overview may be a good way to address both points and set up the exposition for the appendix and proofs). 
Decision: Accept (Spotlight)