Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: They show that invariance to circular shifts increase adversarial vulnerability. To motivate this finding, they characterize the margin between classes for a shift-invariant linear classifier. Based on the NTK settings, they show that FC and shift-invariant networks produce linear decision boundaries, which partially explains their adversarial vulnerability. They further empirically verify that shift-invariance reduces adversarial robustness on real datasets and realistic architectures.
main_review: Strengths
- Their hypothesis about shift invariance is first verified in a simple setting. They also provide theoretical justification and further demonstrate the evidence in real-world architectures and datasets. 

Weaknesses
- I found this is a nice paper. I don't particularly see weaknesses.

Minor:
L292: Visual Transformer -> Vision Transformer

Additional comments:
- It would be interesting to consider more common image corruptions like gaussian noise, blur, etc.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work provides theoretical and empirical justifications on why shift-invariant neural networks are less adversarial robust than fully-connected neural networks. Using Neural Tangent Kernels and Convolutional Neural Tangent Kernels, the authors prove that for simple neural networks, shift-invariant neural networks produce separators with decreasing margins, making them not as robust as fully-connected neural networks. Empirically, the authors provide experiments on simple neural networks with MNIST and more complicated networks such as ResNet on bigger datasets such as CIFAR10. 
main_review: There is originality in this work; however, there are a number of works that address the relationship between invariance and robustness in the past. Related works also seem to be adequately cited. The submission is also well-organized, with good teaser figures and example in the front, followed by a number of theorems and experiments to justify the claims made. 

There are a wide-range of experiments, testing different architectures and datasets. This shows that authors are willing to testify their claims through their experiments carefully. Having theorems to justify those claims is also a plus usually.
limitations_and_societal_impact: Despite the pros above, I am not entirely convinced it is a fair problem to compare adversarial robustness of shift-invariant networks vs fully-connected networks. For both theory and experiments, the tasks designed for the two networks are different. For instance, facial recognition that requires translation invariance is a different task than facial recognition with aligned images. What might be a better comparison in this paper is if the authors only focus on shift-invariant networks, rather than comparing fully-connected networks to shift-invariant networks.

In Section 5.2, the authors compared “training a shift-invariant network is similar to training a fully-connected network using all shifted versions of the training set.” This is true generally, at the very least, experiment results should show that the network trained is actually shift-invariant. Or else, the experiment does not seem convincing that it actually applies to shift-invariant networks. 

In addition, since the network now is shift-invariant, to test adversarial robustness, it seems to deserve a more thorough study on doing experiments on generating adversarial images with not only original images but also shifted images.  

Arguably, requiring a network to be shift-invariant also imposes a harder challenge to the learning problem than training a network without shift-invariance. I would also expect that imposing more shift-invariance on a network will naturally lead to weaker performances and worse adversarial robustness. Although this work provides some good experiments to verify this, I am not sure if the work’s contribution is big enough to be accepted for this conference. 

If the authors can provide a better argument for why the comparison is fair, or point out any important parts I misunderstood, I am more than happy to change my score.

The authors have adequately address the work's societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The adversarial attack is one of the critical problems in current machine learning research that causes end-users to mistrust models deployed for high-stakes decision-making applications. The paper identifies the "shift-invariance" property of neural networks to be a possible reason behind their high sensitivity to adversarial attacks. The paper shows that the margin between the classes for a shift-invariant linear classifier only depends on the DC component of the signals. Further, the authors show that in simple cases, 
fully connected and shift-invariant neural networks learn linear decision boundaries. Finally, experimental evaluations on real datasets and architectures show that shift invariance reduces adversarial robustness.
main_review: Strengths:
1. The paper is very well-motivated and addresses an important problem in adversarial machine learning, i.e., a better understanding of adversarial attacks.
2. The work provides a better understanding of the relationship between adversarial robustness, shift-invariance, dimensionality, and the linear margin of the data in neural networks.
3. The hypothesis for shift-invariance is empirically tested on large datasets and diverse neural network architectures such as FC, CNNs, and transformers.


Open concerns:
1. It would be helpful if the authors can comment on why for easier datasets like Cifar-10, we observe that AlexNet is an outlier both in terms of shift-invariance and robustness, but for harder datasets like ImageNet, the gap reduces significantly (Fig. 4).
2. The connection between shift-invariance and robustness is interesting but unclear. The experimental results show some correlation between the two, but the hypothesis that shift invariance reduces robustness by increasing the implicit dimension of the data is not well explained.
3. From Fig. 2, the authors conclude that "fully-connected networks (FCNs) are more robust than Shift Invariant CNNs". It would be beneficial if the authors can provide the shift-invariance score of the respective networks to support their conclusion. In addition, unlike FCNs, convolutional neural networks (CNNs) have a spatial bias -- a type of inductive bias that assumes a certain spatial structure present in the input data. Can this contribute to their poor adversarial robustness performance?
4. In Fig. 1, we observe that the margin of a linear, shift-invariant classifier will shrink in proportion to the inverse of the total number of image pixels. It is interesting because most pixels in the images from Fig. 1 belong to the same color (gray). It would be great if the authors can comment on this answer.
limitations_and_societal_impact: There are a few open questions still remaining which have been addressed by the authors themselves. The authors present a very interesting idea which is very important to develop and deploy trustworthy machine learning models but it needs further explanation.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper begins with the finding that shows that shift-invariant linear classifiers can have a significantly smaller margin than non-shift-invariant linear classifiers. They then perform a similar analysis on neural tangent kernels (NTK) and find that the linear classifier trained on the convolutional NTK also has a smaller margin. Empirically, they found that some networks, like AlexNet, are less shift-invariant and they seem to be more robust.- The observation that shift Invariance can reduce adversarial robustness is an interesting and important topic.
- The experimental results are worth a deeper analysis of why less shift-invariant networks appear more robust.
- Code is provided in the supplementary.

main_review: Pros:
- The observation that shift Invariance can reduce adversarial robustness is an interesting and important topic.
- The experimental results are worth a deeper analysis of why less shift-invariant networks appear more robust.
- Code is provided in the supplementary.

Cons:

(1) The theoretical analysis is straightforward. In both the analysis in sections 3 and 4, a constraint on being shift-invariance is added to the classifier. When a constraint is added, the margin can only be smaller or equal to the original one.

(2) The gap between theory and practice is too large.
 - The theoretical analysis can only show that the margin decreases when the shift-invariant constraint is added. However, in practice, when we say adversarial example we only talk about ``small'' perturbation. As long as there is a healthy amount margin, it should be fine. So the real question is, does enforcing shift-invariance make the margin too small so that adversarial examples are inevitable.
 - If there is an example of an image being shifted into the adversarial example of an image from another class, this paper would be much more interesting.

(3) The authors mentioned that this work is quite relevant to (Kamath et al. (2020)). So how is this work differently from the work by Kamath et al.? Are there any new findings?

(4) The empirical evidence shown here is not enough to convince me that ``in general'', more shift-invariant network will be less robust:
 - If two networks are trained with the same architecture and optimizer, one network is trained with shifting data augmentation and the other one is trained without data augmentation is the result still consistent with your findings. Suggestion: more experiments like section 5.1.2 should be done.
 - It is mentioned that some pre-trained models are retrieved from Pytorch model zoo on ImageNet. In the comparison, are the models all trained with the same data augmentation method? I think this should be discussed as this can be a confounding factor that may change the interpretation of the result.
 - The networks in each figure are not consistent. In Figure 4, why Sparse-MLP appeared in Cifar10 but not in ImageNet? why DenseNet, MobileNet does not appear in Cifar10?
 - Does the findings still hold when network trained with adversarial training? If adversarial training is used, does the level of shift-invariance decrease?
 - It appears models with lower natural accuracy also more robust? Could it be because that AlexNet is less overfitting to the data so that it is more robust?

(5) "We have shown theoretically that shift invariance can reduce adversarial robustness." I don't agree with this statement in line 197 as sections 3 and 4 only show that shift invariance can reduce the margin. It does not say the margin becomes too small. If you have a super large perturbation and the perturbed image looks completely different from the original one. Even if this perturbed image is predicted as a different class, it wouldn't necessarily be called an adversarial example.

minor:
- The figures can be organized in a way that they are on the same page with the text that is mentioning the figure.
- C&W attack should be used for L2 attacks https://arxiv.org/abs/1608.04644.
limitations_and_societal_impact: There are several limitations of this work not mentioned by the authors:
- There gap between theory and practice is too large and the theorem cannot represent most of the particle cases.
- Many confounding factors mentioned in my review are not discussed in the paper.

I am not aware of any potential negative social impact of this paper.
review_title: null

Meta-review: This paper provides theoretical and empirical evidences that the robustness of a (linear) classifier reduces when one tries to ensure shift invariance for the input. The results are not as surprising since classifying all shifted instances is indeed conceptually more difficult, when the feature dimension is fixed. The analysis is done for two-layer networks. One of the reviewers raised a legitimate concern whether the notion of robustness studied here is directly associated with the adversarial robustness. Majority of the reviewers nevertheless think the paper is above the standard for acceptance. 
Decision: Accept (Poster)