Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The present paper proposes to consider features derived from PCA for the purposes of adversarial attack and defense. They argue that, based on these features, they can verify larger neighborhoods and provide stronger attacks. The neighborhoods are based on the ERAN verifier and the attacks are in comparison to a recent attack called AutoZoom. Defense performance is measured in number of images in the neighborhood, and attack performance in terms of L2 distance.

I was, in general, confused by many of the choices in the paper. The paper proposes to use PCA features, but then measure attack in L2 distance; if the argument is that PCA is a better basis, then why use the pixel-space L2 metric? It seems this could only help to the extent that methods such as projected gradient descent (PGD) are failing to find the optimal L2 attack. Measuring defense capability in terms of number of images also seems like an odd choice, as usually we choose some perceptually meaningful norm and measure according to that. I had also not been familiar with the ERAN verifier prior to this paper, despite being an expert on neural network verification, and it isn't obvious to me whether we should consider it to be competitive with other SDP and LP-based verification methods. Moreover, the PCA features are only used to determine the side lengths of a hyperrectangle that is provided to the verifier, so that this is a fairly indirect test of whether PCA features are useful for defense (indeed, I would like to see a more crisp formulation of what "useful for defense" is meant to mean, since they aren't used to change the model itself).

In the experimental comparison of attacks, standard baselines such as PGD and C&W are missing, such that it is difficult to interpret the results. I checked the AutoZoom paper (the main method compared to) and it also does not compare to PGD, so I feel that the present paper does not provide evidence that the method performs better than baselines.

I think the authors could improve the paper by more crisply articulating its goals, and either using more standard experimental setups and metrics or defending its deviation from these.

== Update after author response ==

Thanks for your response. I believe it is widely agreed upon that black box evaluation is not meaningful in security settings, and that we should use white box attacks. Therefore, I don't find the justification for omitting PGD and CW convincing. I also still do not feel that counting images in pixel space is a meaningful metric. Therefore, I have kept my original score.
review_title: Confusing setup and experiments

final_score: rating: 3: Clear rejection
review_content: The authors study the problem of adversarial robustness, aiming to find regions of the input space for which a classifier is robust. Instead of the standard approach of defining a neighborhood around each data point based on some $\ell_p$-norm, they use PCA to identify directions along which the model is robust or brittle. They then use these methods to identify large regions of input space for which models are robust and, in a complementary direction, to craft imperceptible adversarial examples with few model queries.

In general, understanding the set of perturbations that our models are robust to is an important research question. Unfortunately, the current paper does not go into significant depth. 

**Robustness neighborhoods.** Τhe input robustness regions computed using this approach are rather unintuitive. What insight is gained by reading Table 1? Do these robustness regions correspond to something concrete and meaningful (e.g., diagonal stripes, brightness) that we can convey to human users of the model? What fundamentally new understanding do we obtain via this analysis?

**New adversarial attacks.**  The space of existing adversarial attacks is huge. By now, there exist so many different approaches for computing examples that fool models. From that perspective, it is not clear what the new attack proposed offers. Similarly to the point above, since these directions do not necessarily capture something human-understandable it is unclear how they reveal a fundamentally new model vulnerability.

Overall, while the research direction is interesting, further exploration is needed to reach novel insights about these models.

Other comments (not affecting score):
- The large numbers representing "number of images" are somewhat misleading. How can we quantify whether these images are actually distinct. I do not think that these number convey significant information and I would thus recommend removing them.
- https://arxiv.org/abs/1807.04200 and https://distill.pub/2019/advex-bugs-discussion/response-3/ also study model robustness to PCA-based perturbations and might thus be worth discussing.

====== POST-RESPONSE UPDATE ======

I appreciate the author's response and the additional illustrations provided. At the same time, my concerns remain:
- I still disagree with the claim that PCA directions are "semantic and meaningful." Yes, some of them might correspond to image changes that are intuitive, e.g., Figure 4, but it is still impossible to draw any such conclusions without manually inspecting individual directions. In other words, what do I learn about my model by reading Table 1?
- I understand the process of counting the number of images. However, I still think that it is a fundamentally flawed metric. Based on this definition of "distinct", if I change the value of a single pixel by 1/255 I get a distinct image. This is clearly not an intuitive behavior. As a model designer, what do I understand about my model by look at these astronomical numbers.

Overall, while I still find the broad direction interesting, I believe that the paper has fundamental issues and is hence unsuitable for publication.
review_title: An interesting direction, requires further investigation

final_score: rating: 3: Clear rejection
review_content: This work proposes a method to find weak and robust features via sampling, and utilises the method to (a) define feature-guided neighborhoods and (b) to improve score-based black-box adversarial attacks.

I examine the two main contributions (a) and (b) separately. The feature-guided neighourhoods are basically defined as 1D linear subspaces around a given sample x. The subspaces are usually defined along PCA-projections of the data set, although the definitions would also allow non-linear subspaces. The work claims that along some of these directions a classifier D is robust, and that using verification techniques one can show that these robust subspaces can be much larger than simple epsilon-ball neighbourhoods. While this claim might be true, the significance of this insight is unclear to me. Of course, if carefully chosen, one can find large neighbourhoods in which a classifier does not change its decision - but I fail to see what insights can be taken away.

In a second step, this work computes weak features, i.e. directions in the pixel space along which the classifier D is generally susceptible, and uses this to perform a score-based adversarial attack. The work claims higher robustness with fewer iterations than AutoZOOM and GenAttack. This is indeed an interesting direction, but the work misses a lot of relevant prior work on this area that should be discussed and compared against (in particular many other score-based but also decision-based attacks, one would need to take into account the number of queries needed to find the weak PCA directions to compare against other attacks, etc.).

It might be beneficial to remove the discussion of the neighbourhoods and to concentrate on the improvement of black-box attacks (which would have be shown much more convincingly).
review_title: The work proposes a potentially interesting improved black-box attack, but comparison to existing attacks would have to be much more convincing.

final_score: rating: 7: Good paper, accept
review_content: The overall quality of the paper is good. This paper proposed a feature perturbation procedure, as a comparison to the commonly used perturbation to the original input data. Given access to a feature mapping and a black-box classifier, the proposed procedure is able to select the most robust/weak features. This then can be used for two important tasks: to determine a robust neighborhood for a data point using the robust features and to design adversarial examples using the weak features. For the first task, the feature-based robust neighborhood proposed by this paper is shown by experiments to contain far more points than the traditional input-based neighborhood. For the second task, the feature-based adversarial examples require less query to the black-box classifier and have less distortion from the original data points compared with other competitive methods, and thus are more human-imperceptible. These characteristics make the procedure appealing.
Therefore, the main contribution of the paper (i.e., the perturbation procedure) is important to the ML community and worth further explorations. 
The clarity of the paper is good. There is no difficulty in understanding the content and experimental details are provided. 

Cons:
1. The overall running time of Alg 1 is a concern. 
2. When generating the adversarial examples, a greedy recovery is performed which may be time-consuming when the data dimension is high. 
3. The effectiveness of the proposed procedure seems to strongly depend on the feature mappings. The performance under mapping other than PCA is unknown. 

Other comments:
1. The experiment showed good results with PCA feature mapping. Are there any other feature mappings that might work well with this proposed procedure (Alg 1)?
review_title: This paper proposed a feature perturbation procedure with given feature mappings, which can be used to select robust/weak features and generate adversarial attacks. 

Meta-review: I agree with the majority of reviews that this paper is not sufficiently convincing. 
Decision: Reject