Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes a fine-grained definition for adversarial robustness, dividing adversarial robustness into perturbation robustness and invariance robustness. Same as the previous definition of adversarial robustness (robustness against imperceptible perturbations), perturbation robustness reflects the model's ability to maintain the prediction after a label-preserving transform. Invariance robustness, on the other hand, reflects the model's flexibility against invariance-based adversaries which changes the actual label within the norm ball around clean samples. With examples from the two-sphere experiment, MNIST dataset with large epsilons and a triplet of natural images, it reaches the conclusion that training models to be invariant to any sample within a norm ball is a bad idea when epsilon is too large. 

I like this paper in that it points out the problems with some established evaluation protocols for adversarial robustness, e.g., evaluating the robustness on MNIST with a max l_infty norm of 0.4. However, it comes at no surprise that large epsilon gives rise to non-label-preserving perturbations on images. No automated solution can be inspired from the paper. A more valuable direction would be to evaluate the minimum l_p distance between classes, but it seems intractable at the moment. 

Also, it should be emphasized that the invariance-based adversarial examples exist only when epsilon is improperly high for image classification tasks. This can also be verified by the two-sphere experiments. By taking average of the accuracy on the inner sphere and outer sphere, the accuracy against perturbation attack drops before invariance attack with the increasing epsilon, demonstrating invariance attack is only a problem when epsilon is too large for training the model. For other tasks such as language understanding, invariance-based adversarial examples may be a much severe problem for the seemingly robust models. 

As a conclusion, I tend to accept this paper to draw more attention to a better notion of robustness, or developing more sophisticated approaches to defending against perturbation and invariance attacks simultaneously at a larger epsilon. However, the current version is still short of any foreseeable solution. Still, this is perhaps the best we can hope for.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 
================ Update after reading the rebuttal and the revised paper ======================================= 

I have now read the author rebuttal and the revised paper. I had raised two main issues with the paper in my initial review (see below): 1) experiments don't provide enough support for the main claim; 2) the main claim seems to contradict an earlier result by Engstrom et al. (2019). 

With respect to the second point, the authors have responded that Engstrom et al. (2019) use relatively small perturbation sizes during adversarial training and that the trade-off between invariance vs. perturbation based adversarial robustness may be different for such small perturbation sizes. This sounds plausible, although I would have much preferred a more direct demonstration of this (for example, by adversarially training MNIST models with different perturbation sizes, then looking at their performance on invariance-based adversarial examples).

With respect to the first point, the authors have pointed to some numbers in Table 1, but my criticism still stands: for example, the perturbation-robust ABS performs better than the undefended CNN model (similarly for the l_inf PGD model, even though it is trained for a different metric). This seems to contradict the authors' claim that excessive perturbation robustness leads to worse performance on invariance-based adversarial examples.

In conclusion, I very much appreciate the authors' rebuttal and I definitely think there are some interesting ideas in this paper. However, given that one of my main concerns has not been addressed and the other one only insufficiently addressed, I'm inclined to keep my score as it is. Going forward, I would encourage the authors to develop the trade-off between invariance vs. perturbation based adversarial sensitivity for different perturbation sizes more thoroughly.

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

This paper argues that the standard notion of l_p-norm bounded adversarial examples does not adequately capture all types of adversarial examples we may care about. In particular, the authors note the existence of adversarial examples caused by the excessive invariance of classifiers to semantically meaningful perturbations. This was noted in earlier works as well, but the current paper purports to establish a link between l_p-ball robustness and invariance-based adversarial examples. It also introduces a method to generate such invariance-based adversarial examples. There are interesting ideas in this paper, however I have some questions and concerns about some of the claims made in the paper that I would like to see addressed. Here are the main issues for me:

1) If I’m not mistaken, the main claim of the paper, namely that l_p-ball robustness worsens the performance on invariance-based adversarial examples does not actually seem to be supported by any result in the paper beyond some of the simplest, toyest examples.  For example, in the MNIST examples in Table 1, I don’t see how l_p-ball robust models are performing worse than the other models on the invariance-based adversarial examples (the results seem mixed at best). Even in some of the toy examples, this claim is not supported: for example, in the adversarial spheres example, the l_p-ball robust classifier would correspond to the max-margin classifier, which is not vulnerable to invariance-based adversarial examples. Even the ad-hoc sub-optimal classifier chosen in this example doesn't show that l_p-ball robust models are more vulnerable to invariance-based adversarial examples, just that the two phenomena are distinct. There’s the single ImageNet example in Figure 6, which is cute and is consistent with the claim, however it’s just a single example. Also please note that this example does not work with the l_inf norm, so it just shows the inadequacy of the l_2 norm, not of l_p norms in general.

2) The main claim of this paper seems to contradict a result in Engstrom et al. (2019) (https://arxiv.org/abs/1906.00945). They also demonstrate the existence of invariance-based adversarial examples in non-robust models (e.g. see their Figure 2), but their results seem to suggest that these types of examples do not arise in robust models (models trained with adversarial training). Please discuss this paper and clarify the seeming discrepancy between the results there and your claims.

Other issues: 

3) It is really hard to follow the invariance-based adversarial example generation process described in section 4.2. Please describe this more clearly, motivating each step of the process (currently the steps seem ad hoc, it is not explained why each step is needed), so that a reader can understand the generation process at a high level without having to consult the appendix. 

4) The labels are misaligned in Figure 4.

5) In section 4.3, it is mentioned that “we additionally hand-crafted 50 invariance adversarial examples under the specific norms”. It is not explained at all why these additional examples are needed and it is not described how exactly these are generated (neither in the main text, nor in the appendix as far as I can see).

6) In Table 1, the different models are not described at all (neither in the main text, nor in the appendix). They are just acronyms right now. Please describe what these models are.

7) The idea that there may be trade-offs between different notions of robustness and that l_p-ball robustness is not the be all and end all of all robustness measures have been noted in some previous works: for example, Yin et al. (2019): https://arxiv.org/abs/1906.08988 Although the phenomenon discussed in Yin et al. (2019) is different from the one highlighted in the current paper, the main message seems quite similar. So, please discuss this connection in your paper. 
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Thanks for your response. It has addressed most of my concerns. I'd like to increase my score.

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

This paper examines the perturbation-based and invariance-based robustness of deep neural networks. They found that models trained to be robust under l_p threat model are more vulnerable to invariance-based adversarial examples. This paper provides several illustrative examples to tell the reasons behind this phenomenon. An attack method for generating invariance-based adversarial examples is also proposed to attack the (provably robust) models.

Overall, this paper analyzes the invariance-based robustness of deep neural networks with norm-bounded robustness, which is an interesting problem. Several illustrative examples provide reasons on why models robust to perturbation-based adversarial examples could be more sensitive to invariance-based adversarial examples.

However, my main concern is on the contributions of this paper. A clear contribution of the paper is to study the perturbation-based and invariance-based robustness together, and present several demo examples to illustrate that. Are there any other contributions in this paper? Is the proposed attack method novel compared with previous methods? And what are the differences between the proposed attack with previous methods? The authors could discuss more on the attack method and compare its performance with others.

I'd like to raise my currently rating based on the author feedback.
review_title: Official Blind Review #2

Meta-review: The paper considers the relationship betwee:

- perturbations to an input x which change predictions of a model but not the ground truth label
- perturbations to an input x which do not change a model's prediction but do chance the ground truth label. 

The authors show that achieving robustness to the former need not guarantee robustness to the latter. 

While these ideas are interesting, the reviewers would like to see a tighter connection between the two forms of robustness developed. 
Decision: Reject