Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studies the power of abstention in robust classification. A classifier that has the power of abstention can refuse to answer the query because it is unsure of the answer. For robust classification, the abstention power enables the classifier to refuse adversarial queries, if the query is detected as an adversarial example.

The paper first shows a negative result on the possibility of robust classification. After reading the statement of theorem and the proof multiple times, it is not clear what the theorem is stating. The theorem only says that the adversary can flip the label using arbitrary large perturbations, which seems to be a trivial statement. In the comments bellow I have listed several questions to get a clear understanding of this theorem.

After the negative result, the paper studies the effect of abstention by showing a positive result on the 1-nearest neighbor classifier. The idea is simple, whenever the query is far from its nearest neighbor in the training set, the classifier refuses to answer. This clearly provides some lower bound on the robustness as long as the data is well separated. This result cannot be used for actual image datasets that are used in practice because 1NN will definitely not have good accuracy even without abstention. Also, the images are not well-separated at all. However, the authors still run some experiments by considering the adversarial attacks in the feature space (the noise is added in the feature space instead of input space.). They show that using some good feature representation, they can get acceptable robust accuracy using their method. However, it is important to note that this will not have any meaningful effect on the real datasets classification tasks. 

As for evaluation, I find the idea of paper in studying the provable effect of abstention exciting. However, the theorems that are proved lack clarity and significance. I suggest the authors to re-write the theorem in a more understandable way with all parameters clearly explained. From a technical point of view, it seems that the theorems that are proved are not really relevant to adversarial perturbations. The definitions of adversarial perturbations seem arbitrary and not aligned with standard definitions. 

Comments/Questions to Authors:

Theorem 4.1: 
1- The current statement of theorem is trivial. You don't provide any bound on the size of perturbation which makes the theorem not very useful.
2-The statement of theorem says a random vector v. What does that mean? Are you considering robustness to random noise or adversarial noise? If so, how is this related to adversarial examples?
3-In the proof it says R=\frac{r_\delta \sqrt{n_2}}{\delta} is large enough to provide some property about the balls of size r_\delta. Doesn't this statement require some distributional assumptions for data distribution?
4- There are already some negative results about adversarial robustness that the paper could refer to. 

Theorem 5.1: 

1-The definition of \Epsilon^x_adv is not clear at all which makes the whole theorem not really understandable.
2-It sounds to me that the bound on the error could be well beyond 1? If not, you should explain why. what if n3=n2?
3-  What does this sentence mean? " The adversary is allowed to corrupt F(x) with arbitrarily large perturbation in a uniform-distributed subspace S of dimension n3". Again, what do you mean by uniform distributed?
4-In general, defining adversarial perturbation in a subspace with smaller dimension seems not standard. Did you choose this type of perturbation for a specific reason or just for the sake of proving the theorem?
5- The proof of this theorem does not sound to be rigorous. Are you assuming that without any perturbation, the 1NN classifier is 100% accurate?
review_title: Writing needs to be improved. Theorems statements are not clear and they seem not to be relevant to adversarial robustness research. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:

This paper studies, through a provable approach, whether abstaining (i.e., refusing to answer) can be beneficial for achieving small adversarial/robust error in settings where the input is potentially adversarially perturbed. The paper proves a separation between the power of models with and without abstain. In particular, it is shown that for a certain adversarial model (more about this below) when we force the model to answer without an abstain option, it will have high adversarial error, but when abstain is allowed, it can have small adversarial error as well as small abstention rate in certain settings. The paper then studies algorithms for robust contrastive learning in which they map the inputs into high-dimensional spaces and then aim to classify them using an abstain-enabled model based on 1-NN. The paper studies ways to adjust the parameters of the model as the data comes in an online fashion (divided into batches). They show how to achieve sublinear regret in such settings. They then compare linear classifiers with their own (1-NN style) classifiers and show advantages in robustness with such models when abstaining is allowed.

Pros: 

Not many previous works have studied the role of abstention in adversarial attacks (aka adversarial examples / evasion attacks). This work is the first to aim for a provable separation. This is a very natural and potentially impactful direction. The ideas for the algorithm design (through a data driven approach) could lead to useful methods that have practical values.

Cons:

I think the theoretical separation is not that meaningful due to two issues:
1. The robustness is defined for an un-natural perturbation model: it is a mixture of random and adversarial (i.e., the perturbations are allowed to be in a *randomly selected* subspace) but that is not the main issue. The main issue is that the amount of perturbation in the subspace is *unbounded*. This means the adversary can basically perturb the point to an arbitrarily far point where the *ground truth* also changes. Therefore, it is not cleat at all if the perturbed point would indeed be mis-classified or not, which seems to be the minimum requirement to call something adversarial example. Here I want to contrast the noise model with, say, ell_p-based noise model that is extensively studied in the literature to clarify the issue. The idea there is that, e.g. in the case of images, bounded ell_p perturbation preserves the ground truth (in that case human’s judgement). So, an attack that finds images with small ell_p distance with a different classified label would be misclassified. Here, nothing like that could be said as perturbations are arbitrarily long. 
2. To see (a different but related) issue with the definition used for robust error assume a function f(.) completely learns the concept correctly and have zero error. Then on the one hand, such model should not be able to have an adversarial example, because any perturbation would be *correctly* answered (i.e., imagine a change in a cat image to modify it into a dog picture and when the model says it is a dog, we count this as error). However, the definition used in this paper would still allow to prove *unconditional* adversarial error for the model. Note that previous works (e.g., the cited work of Madry et al.'18) are (sometimes implicitly) defined for a setting that the perturbation cannot change the ground truth (e.g., bounded perturbation of images do not change human judgement, so if the label changes it would be misclassified) but here the noise allows arbitrarily far perturbations.

-  It seems the experiments compare the new method (with possible abstention) with a linear classifier that is not designed to be robust.
I think a fairer way to show the advantage of abstain is to show that your method (with abstain) can beat another previous method that was designed to be robust (e.g., using traditional adversarial training). That would show a real jump in what we can do with abstention.

Due to the above reasons, I think the theoretical and the experimental contributions can be interpreted in a limited way, and hence I am more inclined to recommend rejection.

Main comments:

In Algorithm 1: line 2: do you do this in some order? e.g., if two points are at distance less than sigma, you remove one of them or both of them?

Discussions after Theorem 5.1 somehow interpret it as showing some form of (inherent) trade-off between success probability and abstention rate on *normal* (not adversarial) inputs. But that does not seem to be necessarily the case. For example, going back to the case of images. Note that the input distribution (e.g., images in CIFAR-10) keep their concept label even after perturbation (e.g., human judgement). Now, one can either ask a robust model to output a label *even when images are perturbed* or be allowed to abstain when a perturbed image is given. In the latter case, a model can actually have 100% accuracy on the normal inputs, while it might have a lot of abstain on adversarially perturbed points. The disparity between my example and the message of Theorem 5.1 seems to be either stemming from the fact that you allow arbitrarily long perturbations (that will eventually change the label) or that 1-NN based approaches are not sufficiently powerful here. 

Assumption 1 page 5: 
"We assume that at least 1 − delta fraction of mass of the marginal distribution D_{F(X)|y} over..."
Is this for every y?
Also, can you discuss whether Assumption 1 typically correct on real data?

In your experiments (reported in Table 1 (page 8)) how much the numbers change if you aim to get an adversarially perturbed point misclassified (by further restricting what constitutes as a legitimate adversarial example). My objection above to the theoretical formulation and proofs does not prevent you from (potentially) showing a separation in these experiments by really forcing the adversarial examples to be misclassified.

Is your approximate adversary provably approximating the robust error?

###############################

Further comments (and typos):

The label y appears (twice) in the proof of page 4 as non-math (missing $..$).

D_nat does not seem to be the best choice to represent the abstention rate on normal data (at least it is hard to guess it based on the notation).


***** post rebuttal comment *****

Thanks for sharing the response. Unfortunately, the very basic issue with the definition used in this paper, and its implications to practice, remains unsolved.

To clarify the definition, you just need to focus on the following simple example: what if the model has zero risk/error?  If you perturb a point, it would still be correctly classified. Yet, they still show that adversarial examples are inevitable even in this setting. This already shows something is fundamentally wrong with the definition used.

Your response is that the attacker/adversary will not get to change the label, but only the features. But please note: the adversary *is not allowed* to choose the label. The adversary picks the features, and it is up to the model to correctly classify it or not. If an attacker changes the picture of a cat to to a picture of a dog, the neural net (or any other model) should call this dog (and if does still calls it cat it would be a a mistake not the other way around). The ground truth (i.e., the concept function) determines what is correct and what is not. 

The above issue is not imaginary, it has real affect on the experiments, and as I said, it is important to report in the experiments whether or not they attacks lead to *actual misclassification*.

I hope these comments will help improving the paper, since as I said, the topic of this paper is a very important one, and so exactly because of this, it is important to have the basics right.
review_title: Important problem, but the theoretical formulation seems flawed and (consequently) experiments are not quite meaningful either .

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
This paper proves some fundamental facts about classifiers that can't abstain (provide a non-classification) and their robustness to adversarial perturbations. In Sec. 4, they provide a result that such classifiers are always vulnerable to adversarial perturbations in a technical sense. In particular, there will always be a class in which most training examples can be randomly perturbed in a way that an incorrect label will result nearly half the time. In Sec 5, they propose a modified nearest-neighbor classification algorithm, with two parameters that control abstention and "noise removal". They provide upper bounds on error in a random subspace attack scheme, and refine/loosen these results in several more specific/general scenarios. In Secs. 6 & 7, they discuss methods to tune the two parameters and provide experimental evidence of their theoretical results.

#### Strengths & Weaknesses

First, the strengths: I found the paper to be well-organized, and mostly well-written. It aims to tackle a pretty fundamental problem, and provides some clear and simple results in relation to a simple algorithm. For the statements I checked, the paper was technically sound.

As for the weaknesses, I found some of the mathematical exposition to be hard to follow. The proofs and sketches could really benefit from some diagrams and perhaps some simple example scenarios. Additionally, I found myself unsure of the practical gains from their algorithm. They make a single comparison to a linear classifier, and it's almost certain that the comparison would not be as favorable against any method that allows for classification in a non-binary fashion (with some level of confidence, and thus some natural level of abstention).

#### Recommendation

Based on the above, I gave a rating of 7. I did not give a higher score, as I am not sure of the practical relevance of the suggested algorithm. On the other hand, the theoretical results seem solid and are of a pretty fundamental nature. I do provide this score with a grain of salt, as I was not able to check all the theoretical statements, which are the backbone of this paper, in my opinion.

UPDATE: I am downgrading my score to a 6. Based on the opinions of my fellow reviewers, it seems that perhaps the theoretical results are based on scenarios that are too simplistic for the community at hand. Moreover, there are clearly some readability issues, based upon the reactions of the other reviewers.

#### Clarification Questions & Suggestions

1. As suggested, perhaps it would be helpful to discuss or consider existing methods that provide classification with some level of confidence. It seems that these automatically provide some notion of abstention when confidence is not high enough. I found it surprising that none of these were mentioned.
2. I noticed that the supplementary material contains a few references on examples of the subspace threat model. I feel like a sentence in the main text would be helpful to provide some context for the relevance of this threat model.
3. In the proof of Thm. 4.1, the existence of a label \\(y^*\\) with volume fraction less than 0.5 exists by virtue of having at least two labels. Even with an abstention option, existence would hold, I believe.
review_title: A theoretical paper with fundamental results; uncertain practical import

final_score: rating: 3: Clear rejection
review_content: Summary: The authors propose a connection between abstention and robustness to adversarial examples. Specifically, the authors contend that without the ability to abstain, any classifier can be fooled by an adversarial perturbation in the feature space. They additionally provide results and experiments concerning the proper selection of a hyperparameter that tunes the abstention.

Pros: The authors include many theoretical analyses. A good effort is made to address the problem from several relevant angles. 

Cons: 

The paper is very difficult to read. 
 - The introduction does not provide a clean line of thought motivating the paper. I am not aware that the attack model considered, that of an adversary allowed to make arbitrarily large moves in a subset of feature space, with no constraints on the input space, exists elsewhere in the literature. The work cited (Brown et al. 2018) requires that unrestricted adversarial examples remain unambiguous to human judges.

 - The abstract cites results for "any classifier" when in fact the result seems to be for a nearest-neighbor style classifier, which is unusual given that the setting is deep networks.

- The variables used throughout are difficult to keep track of.

Major issues:

- Theorem 4.1: This is obviously not true for all classifiers. The proof is very difficult to follow, and there are no useful details given in Figure 1. The result seems like it may be true by virtue of the fact that KNN with K=1 defines a hyperplane between any two points. Then a randomly chosen vector with probability 1/2 + epsilon inevitably crosses such a hyperplane eventually, but there's no reason to believe such a value in feature space could be reverse engineered or even lies within the range of F.

- The testing in Section 7.1 does not seem to include the use of non-adversarial test samples. In evaluating whether or not a threshold is too strict to be of use, it would be necessary to evaluate on in-domain test samples as well as the training set. These results seem likely to be overfit to the training data. 

- The testing setup is unclear. Perhaps there are further details in the referenced papers, but it is not even clear to me how many classes are in the set. Is it only two, given the baseline of a linear classifier?

- The clarity of the paper is severely lacking. It is difficult to follow the contribution of many of the theorems, especially concerning their generality or lack thereof

Given that I find these issues too concerning to recommend publication, I have not carefully checked all of the proofs.
review_title: clarity issues, unclear whether the setting fits within the literature

Meta-review: The paper considers the problem of abstention in robust classification. A number of issues were identified in the formal framework and the writing was also not up to scratch. The authors should take into regard the very many constructive suggestions made by the reviewers in preparing a revision.
Decision: Reject