Shift Invariance Can Reduce Adversarial Robustness
Authors: Vasu Singla
Songwei Ge
Ronen Basri
David Jacobs
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial robustness
adversarial examples
adversarial machine learning
shift invariance

Abstract: Shift invariance is a critical property of CNNs that improves performance on classification.  However, we show that invariance to circular shifts can also lead to greater sensitivity to adversarial attacks.  We first characterize the margin between classes when a shift-invariant {\em linear} classifier is used. We show that the margin can only depend on the DC component of the signals.  Then, using results about infinitely wide networks, we show that in some simple cases, fully connected and shift-invariant neural networks produce linear decision boundaries.  Using this, we prove that shift invariance in neural networks produces adversarial examples for the simple case of two classes, each consisting of a single image with a black or white dot on a gray background.  This is more than a curiosity; we show empirically that with real datasets and realistic architectures, shift invariance reduces adversarial robustness.  Finally, we describe initial experiments using synthetic data to probe the source of this connection.

Shift Invariance Can Reduce Adversarial Robustness
Vasu Singla, Songwei Go Univeristy of Maryland {vsingla, songweig)@cs umd. edu
Ronen Basri
Weizmann Institute Science
ronen. basr i @wei imann, ac il
David Jacobs Univeristy of Maryland dwj@cs. umd. edu
Abstract
Shift invariance is critical property of CNNs that improves performance on classification. However, we show that invariance to circular shifts can also lead to greater sensitivity to adversarial attacks. We first characterize the margin between classes when a shift-invarian linear classifier is used. We show that the margin can only depend on the DC component of the signals. Then, using results about infinitely wide networks, we show that in some simple cases, fully connected and shift-invariant neural networks produce linear decision boundaries. Using this, we prove that shift invariance neural networks produces adversarial examples for the simple case of classes, each consisting of single image with a black white dot on gray background. This is more than a curiosity; we show empirically that with real datasets and realistic architectures, shift invariance reduces adversarial robustness. Finally, we describe initial experiments using synthetic data to probe the source this connection.
1 Introduction
In adversarial attacks (Szegdyy et al., 2013) against classifiers, an adversary with knowledge of the trained classifier makes small perturbations test image or even objects in the world (Eykholi) et al. 2018 Wu et al., (2220b) that change the output. Such attacks threaten the deployment of deep learning systems in many critical applications, from spam filtering to self-driving cars.
Despite great deal of study, it remains unclear why neural networks are so susceptible to adversarial attacks. We show that invariance to circular shifts in Convolutional Neural Networks (CNNs) can be one cause of this lack of robustness. All reference to shifts will refer to circular shifts.
To motivate this conclusion study in detail simple example. Indeed, one of our contributions is to present perhaps the simplest possible example in which adversarial attacks can occur. Figure shows two class classification problem in which each class consists of a single image, white black dot on a gray background. We train either a fully connected (FC) network or a CNN that is designed to be fully shift-invariant distinguish between them. Since each class contains only single image, we measure adversarial robustness as the la distance to an adversarial example produced by a DDN attack (Rony al.] 2019). using the training image the starting point. The figure shows that the CNN is much less robust than the FC network, and that the robustness of the CNN drops precipitously with the image size.
In Sections 3 and we explain this result theoretically. Section we study the effect of shift invariance on the margin of linear classifiers, for linearly separable data. We call a linear classifier
Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

CNN
FC
FC
CNN
CNTK (1/v2)
1.0
0.8
0.6
0.4
0.0
(a) Clean Samples
(b) Adversarial Examples
(c) Distance to generate adversarial examples vs. image width vd
In binary classification problem, with each image as a distinet class (a), FC network requires an average L. distance close to 1 to construct an adversarial example while a shift-invariant CÑN only requires approximately J where d is the input dimension. (b)-left shows adversarial examples for the CNN. On the top, for example, the adversarial example looks just like the clean sample for the white dot class, but is classified as belonging to the black dot class. (b)-right shows that "adversarial" examples for the FC network just look like gray images. (c) shows accuracy under an adversarial attack, where the L2 norm of the allowed adversarial perturbation is shown in the horizontal axis. The curve labeled CNN shows results for a real trained network, while CNTK shows the theoretically derived prediction of Va for an infinitely wide network.
Figure 1:
Vaa
shift invariant when it places all possible shifts of signal in the same class. We prove that for shift invariant linear classifier the margin will depend only on differences in the DC (constant) components of the training signals. It follows that for the classes shown in Figure [ the margin of a linear, shift invariant classifier will shrink in proportion to Va" where d is the number of image pixels.
Next, in Section we prove that under certain assumptions, a CNN whose architecture makes shift invariant produces linear decision boundary for the example in Figure [ explaining its lack of adversarial robustness. We draw on recent work that characterizes infinitely wide neural networks as kernel methods, describing FC networks with the neural tangent kernel (NTK) (Jacot et 2018) and CNNs with a convolutional neural tangent kernel (CNTK) (Arora et al. 2019; Li et al. 2019). Our proof uses these kernels, and applies when the assumptions of this prior work hold. However, the results in Figure T are produced with real networks that do not satisfy these assumptions, suggesting that our results are more general.
We feel that it is valuable to produce such a simple example in which adversarial vulnerability provably occurs and can be fully understood. Still, is reasonable question whether shift invariance can affect robustness in networks trained on real data. In Section 5 we show experimentally that it can.
First, compare the robustness of FC and invtr-invariant networks on MNIST and Fashion- On these smaller datasets, FC networks attain reasonably good test accuracy on clean data. We find that indeed, FC networks are also quite a bit more robust than shift-invariant CNNs. We also show that if we reduce the degree of shift invariance of a CNN, we increase its adversarial robustness on these datasets. Next we show that the SVHN dataset, FC networks architectures suggesting that this phenomenon extends to realistic convolutional networks. Finally, consider industrial strength networks trained on CIFAR- 10 and ImageNet. We note that ResNet and VGG are shift-invariant to degree, while AlexNet, FCNs and transformer based networks are much less so. This suggests that ResNet and VGG will also be less robust than AlexNet, FCNs, and transformer networks, which we confirm experimentally.
robust than ResNet
Finally, use simple synthetic data to explore the connection between shift invariance and robustness. We show that when shift invariance effectively increases the dimensionality of the training data, it produces less robustness, and that this does not occur when shift invariance does not increase dimensionality. This is in line with recent studies that connect higher dimensionality to reduced robustness. However, also show, at least in simple example, that higher dimensionality only affects robustness when it also affects the margin of the data.
The main contribution of our paper is to show theoretically that shift invariance can under- mine adversarial robustness, and show experimentally that this is indeed the case on real- world networks. This enhances understanding of robustness, and suggests that we can improve

---

robustness by judiciously reducing invariances that are not needed for good performance. Our code can be found at http:///ttuuuoooo/////neneeeeeee shift invariinceeee-eeie adv robustness
2
Related Work
In this section we survey prior work on the origin of adversarial examples and briefly discuss work on shift-invariance in CNNs, and on the NTKs.
2.1 The Cause of Adversarial Examples
One common explanation for adversarial examples lies in the curse of dimensionality. Goodfellow ct al.] (2015) argues that even with a linear classifier lack of adversarial robustness be explained by high input dimension. They suggest that large gradients naturally occur as the input dimension increases, assuming that the magnitude of weights remains constant. Following this, Gabriel
et al.] 2019) provides theoretical and empirical evidence that gradient magnitude in neural networks grows as O( (d)) instead of (dd. where d is the input dimension. Gilmer et al. (2018) analyzes the case of two classes consisting of concentric spheres, and shows that adversarial examples arise when the spheres are of high dimension. (Shafahi et al. (2019) provides a general discussion of how high dimensional data lead adversarial examples can be inevitable by showing that small perturbation in a high dimensional space can cover the whole space. Khoury & Hadfield-Menell (2019) argues theoretically and empirically that adversarial examples arise when data lies on lower dimensional manifold in high dimensional space.
Other studies show that adversarial examples could arise due properties of the data. Wang et al. (2020) argues that adversarial examples can be explained by the dependence of the model on the high frequency components of the image data. TTipras al. (2019) shows that to achieve high accuracy one must sacrifice robustness due to biases in the features. Follow-up work (Schmidt et al., 2018) shows that the sample complexity requirements for adversarially robust classifier to achieve good generalization are much higher than for a normal classifier. Furthermore, a recent study (Chen) al. 2020) shows that in some cases more data actually undermines adversarial robustness and also provides a more complete picture of this line of research.
Apart from the data, some papers look for explanations in the model. Nakkiran (2019) conjectures that the reason adversarial robustness is hard to achieve is that current classifiers are still not complex enough. (Shah et al. (2020) shows that in many cases networks learn simple decision boundaries, with small margins, rather than more complex ones with large margins, which induces adversarial vulnerability. Daniely & Shacham (020)) shows that for most ReLU networks with random weights, most samples x admit an adversarial perturbation at distance O ||كع]]] ). where is the input dimension. Shamir et al. (2019) shows that for ReLU networks, adversarial examples arise as a consequence of the geometry R. and show they can find targeted adversarial examples with mn lo distance, when networks are designed to distinguish between classes. Galloway et al. (2019) provides empirical evidence that using batch normalization can reduce adversarial robustness. Madry et al. (2018) and Wu et al.) (2020a) have discussed the relationship between robustness and network width. Kamath ct al. (2020) examine the interplay between rotation invariance and robustness. They empirically show that by inducing more rotational invariance using data augmentation in CNNs and druuu--quivvariant CNNs the adversarial robustness of these models decreases. This work is especially relevant to results that shift invariance can reduce robustness (A quite different notion of invariance is also explored in Jacobsen et al. (2019) and subsequent work).
2.2
CNNs and Shift-Lnvrriance
Several papers have pointed out that the modern CNN architectures are not fully shift invariant for reasons such as padding mode, striding, and padding size. (Zhang) 2019) improves the local shift invariance to global invariance with the idea of "antialiasing" (Kayhan & Gemert 2020) proposes to undermine the ability of CNNs to exploit the absolute location bias by using full convolution. (Chaman & Dokmanic 2021) proposes the use of a novel sub-sampling scheme to remove the effects of down-sampling caused by strides and achieve perfect shift invariance. (Alsallakh et al. 2021)
show padding mechanism can cause spatial bias in CNNs. (Azulay Weiss 2019) relates a lack of shift invariance to a failure to respect the sampling theorem.
3

---

2.3 Neural Tangent Kernel
Neural networks are usually highly non-convex. But recent studies have shown that when the networks are over- parameterized, their parameters stay close to the initialization during the training, which makes the analysis of the convergence and generalization of neural networks tractable Jallen-Zhul et al. 22019a b. Du et al., 2018 2019a). When optimizing the quadratic loss using gradient descent, the dynamics of an infinitely wide neural network can be well described by a kernel regression, using the Neural Tangent Kernel (NTK) (Jacot et al., 2018). This kernel only depends on the network architecture and initialization. Subsequent studies extend NTK beyond the fully connected network to various well-known architectures (Yang 2020) including using the CNTK kernel for Convolutional Neural Networks (Arora et al., 2019; Li et al. 2019), the GNTK for Graph Neural Networks (Du al..][2200) 2019b), and the RNTK for Recurrent Neural Networks (Alemohammad et al., (00T). Earlier works with these kernels have shown superior performance over traditional kernels (Arora et al., 2020) while later theoretical and empirical studies show that NTKs are closely related to traditional
kernels (Geifman et al. 2020 Chen & Xu 202T).
The salient advantage of NTK is its ability as tool to deliver tractable analysis of deep neural networks. Many interesting studies have been done to demystify the puzzling behaviors of deep neural networks using this tool. (Basri et al. 2019: Rahaman et al., [2019 BBasi et al. (2020) study the inductive bias of the neural network in terms of the frequencies of the learned function. (Tncii et al., 2020) further apply these discoveries and random fourier features to empower neural networks to learn high-frequency signals more easily. (Huang et al., 2020) uses NTK to understand the importance of the residual connection proposed in ResNet (He et al. 2 In this paper, we use NTK and CNTK to help us understand the behavior of FC and Convolutional Neural Networks in toy examples and draw connection between CNN and adversarial examples.
3 Shift invariance and the linear margin
In this section we consider what happens when a linear classifier required to be shift invariant. That is, we suppose that any circularly shifted version of a training example should be labeled the same as the original sample. For convenience of notation we consider classes of ID signals of length d, in which x = (I1, 22 ... Our results are easily extended to signals of any dimension. We denote the set of training samples with label +1 by X1, and the set of samples with label by X2. Let x" denote the signal x shifted by s, with 0
d - 1. That is: x" = (I++1, .. ...... For a signal x, let SH((x) denote the set containing every shifted version of x. That is x" E SH(x), Vs, 0 < signals in the set X; Further, let (x) denote the DC component of a signal. That is,
d - 1. Let S, 5xexxSH(( denote the set of all shifted versions of all
fax(x)
We denote w = +/aa la. where 1a is a d-dimensional vector of all ones, so fác(x) = wFx. x. We prove the following theorem:
Theorem 1. Let S1 and S2 denote the sets of all shifts of X1 and X2, as described above. They are linearly separable if and only if maxxles, fxc(x1) < miinggesy fdc(X2) or maxxgeSa [de(X2) < minxres, (x)( Furthermore, if the two classes are linearly separable then, if the first inequality holds, the margin is minx,es, {x2) maxx,es, fae ) and similarly if the second inequality holds. Furthermore, the max margin separating hyperplane has a normal of w.
This theorem shows that a shift invariant linear classifier can only use the DC components of signals to separate them. The proof of this theorem is in the supplemental material. Here we will give an intuitive explanation for this result. For simplicity, we do not consider the bias term here.
When the two classes are linearly separable, this means WLOG that there exists a unit vector w such that w x < w. X² Vx1 E X1,X2 E X2 and any shifts $1 and 82. Consider the margin that arises when we consider just the sets SM((x)) and SH(x2). First, consider what happens when we compute w x1 for all shifts, s. When w = w, this inner product is constant and equal to fx1( Because w is a constant vector, shifting x1 has no effect on the inner product with w. Similarly, w x² = fd((x)) for all shifts. So the margin between SH(x,) (x1) and SH((2) will be fxx( (x1).

---

For any other choice of w, w X1" will not generally be constant as X1 shifts. We can show that the average value of w X, over all shifts, s, will be (x) fa. In this case, the margin between SH((1) and S'H(x2) must be no larger than the difference between the average values of w wxx," and w X2", which and equals 1 for w = w. Therefore, w maximizes the margin for two reasons. First, the margin is scaled by fao(w), which is maximized for w = w. Second the values of w X1 are constant for all choices of when margin.
fde
fac(xi (x1 (x))feeee [dc( Note that since w a unit vector, (dt(w) S 1,
w, but can vary for other choices of w. This variation can only reduce the
We now consider the example shown in Figure ! Let x1 denote an image consisting of single 1 in background of Os, and let X2 denote an image containing single -1 with Os. Since fx1( va
and fdc(x2) Va if we let X1 {x1} } and X₂ {x2} it is straightforward show:
Corollary 1. X1 and X2 defined above are linearty separable with max margin of SH(X)1 and (H2) are linearly separable with max margin of 2 and a separating hyperplane with the va
normal vector w.
4 Shift invariance and adversarial attacks: NTK vs. CNTK
To understand the robustness of shift invariant neural networks we examine the behavior of the neural langent kernel (NTK) for two networks with simple inputs. It has been shown that neural networks with infinite width (or convolutional networks with infinite number of channels) behave like kernel regression with the family of kernels called NTKs (Jacot et al. 2018). Here we consider the NTK for a two-layer, bias-free fully connected network, denoted FC-NTK. and for a two-layer bias-free convolutional network with global average pooling, denoted CNTK-GAP (Li et al. 2019).
In our theorem below we use both FC-NTK and CNTK-GAP construct two-class classifiers with a training set composed of two antipodal training points, x, -x E TR: In both cases the kernels produce linear separators, but while FC-NTK produces separator with constant margin, independent of input dimension, due shift invariance CNTK-GAP results in margin that decreases with 2/ Vd, consistent with our results in Figure I Due to space considerations, the definition of NTK, CNTK and their corresponding network architectures, the minimum norm interpolant gu (z) of the kernel regression with kernel k; along with the proof of the theorem below are deferred to Section in the Appendix.
Theorem 2. Let -x IRd be two training vectors with class labels 1, -1 respectively.
Let k(z, x) denote NTK for the bias-free, two-layer fully connected network. Then Vz E Rdd the minimum norm interpolant gz(z) 2 0 iff z x 2 O.
2. Let ((2,x) denote CNTK-GAP for the bias-free, two-layer convolutional network, and assume H& is invertible. Then Vz E Rd, either gk(z) (z) 2 0 iff 1 2 or
0rrg0x2 (x(2) 2 0 iff
z < (I.e., z" 1 0 forms a separating hyperplane.)
The theorem tells us that NTK and CNTK produce linear classifiers. (1) tells us that NTK produces separating hyperplane with a normal vector x, while (2) says that for CNTK the normal direction is
1.. The following corollary follows directly from Thm which explains the results in Figure [ Corollary 2. With a training set composed of an antipodal pair the margin obtained with CNTK is the difference between their DC components.
This theorem is proven in the supplemental material. Here we provide some intuition to explain the results. For the first part of the theorem, recall that NTK is a kernel method. When we use only two training examples, x and -x, with labels I and -1, will learn function that sums two instances of the kernel centered at x and -x. By symmetry, we expect the weight of one to be the negative of the weight of the other. Note that this holds only if k(x, x) k(-x, -x). which is not true for all kernels, but is true for NTK. The kernel prediction then depends on the difference function, k(x, z) - k( 00(xx,2 2). We show that for NTK this difference function is linear in z, which implies that the decision boundary is linear. By symmetry, this linear decision boundary has a normal vector in the direction of x. So any z will belong the same class as when xf 0.
For the second part of the theorem, the two-layer CNTK takes the average of k(Z,, x;) over all patches. Here k denotes the NTK and Z,, Xy indicate patches of a fixed size from the input. Therefore
5

---

Conv-10-512
Com--10-0448
Con--12-512
Com-100512
10m-10-2045
Com--12512
12-244
---- PC-1-256
- PC-1-512
RC-1-1044
--.- FC-1-248
PC-2-256
--.- PC-3-256
PC2-112
--.- PC-3-512
Lg robustness
L. robusiness
robustness
La robustness
100
50
Accuracy
Accuaccy
60
80-
20
0-
8
(a) MNIST
(b) Fashion-MNIST
Figure 2: Robustness of Shift Invariant CNNs FC networks
FC-1-256
FC-1-512
FC-1-1024
FC-1-2048
FC-2-256
FC-3-256
FC-2-512
FC-3-512
16.00
20.69
20.69
19.20
19.46
18.19
20.68
18.38
Table I: Shift Consistency of FCNs.
the difference K(2,x) x) k(z,- -x) is linear (an average of linear functions in 2), and due to shift- invariance, it must be orthogonal to the constant vector W.
5 Experiments
We have shown theoretically that shift invariance can reduce adversarial robustness. In this section we describe experiments that indicate that this does occur with real datasets and network architectures. We also provide experiments on simple, synthetic datasets to begin to address the question of why this might occur.
5.1 Real architectures and data
We first compare fully shift invariant and FC networks on the small datasets, MNIST and Fashion- MNIST. We then compare more realistic ResNet architectures with FC networks on the SVHN dataset. Finally we examine additional real architectures on CIFAR-10 and ImageNet.
5.1.1 Shift-invariant CNNs vs. FC Networks
In this section we compare the adversarial robustness of fully shift-inarriat convolutional neural network (CNN) with a fully connected network (FC).
Datasets We consider two datasets which FC networks are able to attain reasonable performance compared to CNNs, MNIST (LeCun al. 2010) and Eashion-MNISS (Xiao et al. 2017).
Experimental Settings All models were trained for 20 epochs using the ADAM optimizer, with a batch size of 200 and learning rate of 0.01. The learning rate is decreased by factor of 10 at the 10th and 1 15th epoch. To evaluate the robustness of these models, we use PGD la and lac. attacks (Madry et al. 2018) with different values, single random restart, 10 iterations and step-size of e/5.
We various FC and shift invariant CNN networks for experiments. The notation FC-X-Y denotes an FC network with X hidden layers and Y units in each hidden layer. Conv-X-Y denotes a network with a single convolutional layer with X kernel size and Y filters with stride and circular padding. All networks use ReLU activation. CNNs have a penultimate layer that performs Global Average Pooling. Finally, a fully connected layer is applied outputs the final logits. These CNN networks are born fully shift invariant. On the contrary, the FC networks are inherently not shift invariant. We show this by calculating the consistency scores (Zhang) 2019) in Table the consistency calculates the percentage of the time that the model preserves its predicted labels when random shift applied the image. We note that these scores are much smaller than 100 for CNNs. We report results for clear and
the end of all the CNNs, which
and robust test accuracy for l2 and Lo attacks at different e values in Figure 2a and 2b for MNIST and Fashion-MNISTT respectively.
Clean Accuracy of models is shown by 0.

---

We observe that although the clean accuracy for the models is similar on the datasets, FC networks are more robust than Shift Invariant CNNs, especially for large e values.
5.1.2 CNNs with different levels of shift invariance
ESEASSURS -020
padding size consistency
0
4
8
12
Accouges
90
18.06
18.08
15.13
21.67
padding size
16
20
24
28
20
consistency
29.83
38.40
71.45
97.80
18:00 22035 MiO0 S2925-39220
05629
5239
2220
4039
5029
Table 2: Consistency to the shift of CNNs with different padding sizes.
Figure 3: Robustness of CNNs with different levels of shift invariance.
In this section we compare the adversarial robustness of convolutional neural networks (CNNs) that have different levels of shift invariance. Specifically, convolutional layer with 1000 filters of kernel size 28 on the MNIST dataset and control the shift invariance through the size of circular paddings. Note that when the padding size equals the kernel size-1, i.e. in the "same" mode (Kayhan & Gemert (020), the output of convolution preserves the width and height of the input and the CNN is fully shift-invariant, which we will discuss more in the next section. When no padding is added, the model is just a FC network with 1000 hidden units. The higher the padding, the more shift invariant the model is. We demonstrate this by measuring the consistency of network output to shifts as suggested by (Zhang 2019). As shown in Table the large padding size does indicate larger consistency shifts. Next, we evaluate the robustness of these models using Method PGD l2 and loc attacks (Madry et al. 2018)) with different values, The results are shown in Figure 3 which illustrates that the more shift invariant CNNs (yellowish lines) are less robust than the less shift invariant CNNs (reddish lines).
train identical CNNs that all have single
5.1.3 Realistic architectures and shift invariance
Before describing experiments with real- world architectures, we discuss their shift invariance. With certain assumptions on the padding, (Cohen & Welling] 2016) proves that the convolution operation is equivariant to shifts. The convolution operation together with global pooling leads to shift invariance. Also, it is easy to derive from (Cohen & Welling 2016) results for models that use stride and local pooling, which we summarize in the note below.
Note 1. A Convolutional Neural Network that meets the following assumptions has some shift invariance:
1. It consists of N fully convolutional or local pooling layers and 1 global pooling layer followed by any fully connected layers.
2. Circular padding is used in a "same" mode in the convolutional and pooling layers.
Such a CNN with the strides Pt, P1.P2..... .PN in the convolutional or pooling layers are invariant to a shift of P pixels, where P is any integer multiple of IIa Pi.
(Kayhan & Gemert 2020) discusses padding modes. Architectures applied to real problems
generally not born shift invariant (Zhang) 2019| Kayhan & Gemert (0200) due to the violations of these assumptions. The most common case the use of zero padding. Zhang (2119) has shown that realistic architectures with zero padding still preserve approximate invariance to shifts after training. Another common cause of more severe lack of shift invariance is the use of a fully connected layer as a substitute for the global pooling layer. This is widely seen in the earlier network architectures such as LeNet (LeCun et al., 1989) and AlexNet (Krizhevsky) (014) while more recent ones have universally adopted a global pooling layer (e.g. ResNet (He et al. 2016)), DenseNet (Huang et al.) 2017)) to reduce the number of parameters. Specifically, (Zhang 2019) shows that in practice AlexNet much less shift invariant than the other architectures. For this reason, we pay extra attention to the comparison of robustness between AlexNet and other architectures in the following sections when FC networks do not achieve decent state of the art accuracy.
7

---

BIT ResNet50x1
VIT-B/16
RoNaii
RoNos-00
BiT ReNettOxxi
VIT-B/32
PCS (00)
1C-55000 -.n 10-4-0000
L2 rubustness
L. robustaess
La rubustiesss
C. robustness
[00]
Accuncy
Accureyy
75
40-
50
20-
25-
0.0
0.5
10
0/5 1/255 2/256 4/255
0.0
0.5
1.0
0/256
2/256
4/256 6/256 8/256
(a) VIT and BiT on ImageNet-IK
(b) ResNets and FC networks on SVHN.
Figure 4: Robustness of Transformers, Resnets and FC networks.
5.1.4 ResNets vs. FC Nets
We compare ResNets with previously introduced FC networks SVHN (Netzer et al. 2011) ResNets are real-world architectures that are not completely shift invariant. We use the SVHN dataset, since it is more difficult to attain reasonable performance with shallow networks this dataset. The models were trained for 100 epochs using SGD with 0.9 momentum and batch-size of 128. A learning rate of 0.I, with decay of factor 10 the 50th and 75th epochs was used. We use the same PGD attacker as described above. The results for clean and robust accuracy with different e values for la and loo are given in Figure 4b] The ResNets have much higher clean accuracy, but lower accuracy on adversarial examples, especially when e is large. We conclude that ResNet's approximate shift invariance is associated with less robust performance.
5.1.5 More realistic networks
In this section we look at the robustness of trained networks large scale datasets. We do not have firm theoretical basis for comparing the shift-invariance of these networks, since none are truly (non-) shift invariant. But we do expect that AlexNet is less shift-invariant, due to violation of most of the assumptions in Note and so we expect it to be more robust. Zhang (2019) introduces an empirical consistency measure of relative shift invariance, i.e. the percentage of the time that the model classifies two different shifts of the same image to be the same class, which we use to distinguish among models. Although it is not clear that this fully captures our notion of shift invariance, it does support the view that AlexNet is by far the least shift-invariant large-scale CNN. Specifically, the consistency of all the models except for AlexNet are over 85, while the consistency of AlexNet is only 78.11 11 (Zhang 2019). We apply 12 and 1x PGD attacks to the pretrained models provided in the Pytorch model zoo on ImageNet. The accuracy of few representative models under different attack strengths are shown in Figure 5b It clearly illustrates that AlexNet is indeed an outlier in terms of both shift invariance and robustness. We see similar results with other models. (Galloway et al., 2019) suggests that batch normalization is a cause of adversarial examples. However, note that even compared to the VGG models without batch normalization, AlexNet is much less invariant and much more robust, together suggesting that shift invariance contributes to lack of robustness.
In addition to these results on realistic CNNs, we also test Visual Transformers (ViTs), which do not have built in shift invariance. We compare 4 models that are pretrained on ImageNet21K K and fine-tuned on ImageNetIK, K, and show the accuracy under attack in Figure 4a The two ViT models are transformers, while the BiT models are ResNets with Group Normalization and standardized convolutions (Dosovitskiy et al., 202T). We can see that ViTs are much more adversarially robust than their CNN counterparts. This is contemporaneously found by Shao et al. (202T). also. We conjecture that this can be connected to the fact that ViTs do not have built in shift invariance. To test this, we calculate the consistency of these 4 models. The consistency of the VIT-B/16 and ViT-B/32 models are 8 and 78.06 respectively, while the consistency of BiT-ResNet50xl and BiT-ResNet1Olxl are 87.23 and 88.31 respectively. This indicates that visual transformers learn some measure of shift invariance, but are less shift invariant than BiT-ResNets. These less shift invariant ViT transformers therefore achieve better robustness than other architectures.
To further evaluate real-world architectures, we perform additional experments on CIFAR-10. We report test accuracy and robustness of these architectures under different attacks in Figure 5a Unlike Imagenet where fully-connected networks don't perform well, it has been shown that FCNs can achieve fairly high accuracy the CIFAR-10 dataset (Neyshabur, 2020). To compare the robustness
8

---

RasHett18 50
ResNet-152
MobilaNat V2
Alexhet
-VV--11
VGG-19
Denseeeet-122 121
Restlet-St - ResNett1101 101 - Nexlet
Sparse-MIP
ResNet-50
VGG
VGG BN
MobileNeet
robustness
robustness
robustness
L. robustness
Accuracy
60
80
40-
20
20
0.2
0.5/255
4/255
0.125
0.25
0.5/2551/25 2/255 4/255
(a) CIFAR-10
(b) ImageNet
Figure 5: Robustness of models on CIFAR-10 and ImageNet datasets. "BN" indicates that the model uses batch normalization.
of FCNs we also train a 3-layer MLP network, named Sparse-MILP using the B-lasso method following the same experimental setup proposed by Neyshabur 2020)_.. For AlexNet and five variants of ResNet, we train the models for 200 epochs using SGD with a cosine annealing schedule (Loshchilov & Hutter 2016). We use momentum equal to 0.9 for SGD and weight decay of 5e 4. We then evaluate the consistency of the models to shifts and find that all the ResNet models have consistency larger than 75 while the consistency of AlexNet and Sparse-MLP MLP is much smaller 34.79 and 29. 29.18 respectively. The clean accuracies of AlexNet and Sparse-MLP are lower than the ResNets. However, their robust aceuracy decreases a much slower rate as the attack strength increases, showing that the less shift invariant classifiers, AlexNet and Sparse-MLP achieve better robustness.
5.2 Dimension and margin
Training a network with shift invariant architecture is similar to training FC network using data augmentation with all shifted versions of the training set. This raises the question: why would data augmentation with shifted training examples affect adversarial robustness? Note that it has been argued that a different context, more training data should lead to greater robustness (Schmidt et al. 2018). We examine this question with some inital experiments.
In prior work it has been suggested that larger input dimension of the data (Goodfellow et al. 2015 Gilmer et al.) 2018) or larger intrinsic dimension of the data (Khoury & Hadfield-Mened 2019) can reduce robustness. One way that shift invariance might reduce robustness is by increasing the intrinsic dimension of the training data.
To examine this question we create two synthetic datasets, one in which shift invariance increases the implicit dimension of the data, and one in which it does not. In both datasets, each class contains orthogonal vectors, with varying n and dimension d 2000. In the first set, the vectors are randomly chosen from uniform distribution, subject to the constraint that they be orthogonal. The set of vectors single class have dimension n, but when we consider all shifted versions of even single vector, this has has dimension d. In the second dataset, training examples are sampled by frequencies sin ka and cos 2 ka. where & E [1,n]. The first class consists of frequencies which is odd, and the second class consists of frequencies with even k. Because all shifts of sin kw and cos kar are linear combinations of these two vectors, the vectors a class have dimension n, and all shifts of the vectors have dimension
If increasing the intrinsic dimension of the data reduces robustness, we would expect that for the FC network, increasing n would reduce robustness for both datasets. However, we would expect that for the shift invariant network, we would see much lower robustness for dataset than for dataset especially for small n. We do observe this, as shown in Table
In our theoretical results, and the example in Figure we see that considering all shifts of the data may not only increase its dimension but also reduce the linear margin. To tease these effects apart, we create third data set in which as its size increases, its dimension increases but its margin does not.
In this third data set, all samples in one class have common component a random direction, and second component in random direction that is orthogonal to all other vectors. That is, let C1, C2, r/ r2. < i < n be a set of randomly chosen, orthogonal unit vectors. Then the i'th vector in class j is given by x pc, + r/, where is a constant that we vary. The margin between the classes will be least 22p. Since are not controlling the margin for all shifts of this data,

---

Orth. Vectors
Orth. Frequencies
FC
CNN
FC
CNN
50
0.113
0.033
0.129
0.272
T1
0.02
0.05
0.1
0.2
0.3
100
0.083
0.029
0.126
0.251
50
0.106
0.108
0.096
0.114
0.152
0.181
200
0.060
0.024
0.103
0.326
100
0.080
0.081
0.080
0.094
0.121
0.181
0.060
0.061 0.061 0.079 0.112 0.170
Table 3: Average l2 distance for adversarial ex- amples over all samples for dataset 1 and For orthogonal vectors, FC networks are more robust than CNNs. For orthogonal frequencies, CNNs are more robust than FC networks.
Table 4: Average la distance for all samples on FC network for dataset 3. The average l2 dis- tance increases with and increase in inp.
classify this data only using FC network. As shown in Table we observe that p increases, robustness increases. Also for large p, robustness similar across different n values suggesting that the linear margin predicts robustness better than the dimension of the data.
The experiments in this subsection are meant to highlight some interesting questions about the connection between shift invariance and robustness. Does shift-invariance reduce robustness by increasing the implicit dimension of the data? And so, this because leads data that implicitly has smaller margin? Our tentative answer to these questions is yes, based on experiments with simple datasets. But these are questions that surely deserve greater attention.
Potential Negative Societal Impacts
Adversarial attacks deep learning pose significant societal threats. They threaten to disrupt deployed machine learning systems, some of which may play a critical role health and safety, including in health care systems self-driving cars. Our work aims provide better fundamental understanding of these attacks. This might potentially lead to either better defenses against attacks or to more effective attacks. However, we feel that on balance, better understanding of security threats helpful building more secure systems.
Conclusion
We have shown theoretically and experimentally that shift invariance can reduce adversarial robustness in neural networks. We prove that for linear classifiers, shift invariance reduces the margin between classes just the difference in their DC components. Using this, we construct simple, intuitive example in which shift invariance dramatically reduces robustness. Our experiments provide evidence that this reduction in robustness shows up real networks as well. Finally, our experiments on synthetic data provide step towards understanding the relationship between robustness, shift invariance, dimensionality and the linear margin of the data, in neural networks.
Acknowledgments and Disclosure of Funding
The authors thank the U.S.- Israel Binational Science Foundation, grant number 2018680 the National Science Foundation, grant no. IS-191013,, the Quamtifying Ensemble Diversity for Robust Machine Learning (QED for RML) program from DARPA and the Guaranteeing Al Robustness Against Deception (GARD) program from DARPA for their support of this project.
10

---

References
Alemohammad, S., Wang, Z., Balestriero, R., and Baraniuk, R. The recurrent neural tangent kernel. In International Conference on Learning Representations, 2021. URL http:://ppeerrreiei nett/forum2id-3T99FFCC.
Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6158-6169, 2019a.
Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization In International Conference on Machine Learning, pp. 242 252. PMLR, 2019b.
Alsallakh, B., Kokhlikyan, N., Miglani, V., Yuan, J., and Beblitz-Richardson O. Mind the pad {cnn) is can develop blind spots. In International Conference on Learning Representations, 2021. URL http::://oporrrviieee htt.://nnnnt.oooomrmmmmmmmmmoa/0
net
Arora, S., Du, S. S., Hu, W., Li, Z.,, Salakhutdinov, R. R., and Wang. R. exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8141-8150, 2019.
Arora, S., Du, S. S., Li. Z., Salakhutdinov, R., Wang, R., and Yu, D. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2020. URL Stllsttts:... httpp::://ppeeevviee www.:eeefforrue heet//forumm2dddx11BBBBBB.. 1d
Azulay, A. and Weiss, Why deep convolutional networks generalize so poorly to small image transformations? Journal of Machine Learning Research, 10(184) 2019. URL
http://jmlr www.oo/..a....... httg//apprs/v20///
519. html
Basri, R., Jacobs, D., Kasten, Y., and Kritchman, S. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems, pp. 4761-4771, 2019.
Basri, R., Galun, M., Geifman, A., Jacobs, D., Kasten, Y., and Kritchman, S. Frequency bias neural networks for imput of non-uniform density. In International Conference Machine Learning, pp. 685-694. PMLR, 2020.
Chaman, A. and Dokmanic, I. Truly shift-invariant convolutional neural networks. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3773-3783, June 2021.
Chen, L. and Xu, S. Deep neural tangent kernel and laplace kernel have the same (rkhs). In International Conference on Learning Representations, 2021. URL https::/opeereviiee net/ forum?id==v9W70000
Chen, L., Min, Y., Zhang, M., and Karbasi, A. More data can expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning, pp. 1670-1680. PMLR, 2020.
Cohen, T. and Welling, M. Group equivariant convolutional networks. In International conference on machine learning. pp. 2990-2994 PMLR, 2016.
Daniely, A. and Shacham, H. Most relu networks suffer from lell2 adversarial perturba- tions. In Larochelle, H., Ranzato, M., Hadsell, R. Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6629-6636. Curran Associates, Inc., 2020. URL lattps://proceeding hewpooooeiinnn..uuiiiiss... /ptp/p/e//20///lll// pdf
Dosovitskiy, A., Beyer, L.. Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x 16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021. 2021. URL htatpsss//peeeeeeeeeeeeeerrrrrrr

---

Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning. pp. 1675-1685. PMLR, 2019a.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 7723-5733, 2019b.
Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pultern Recognition, pp. 1625-1634, 2018.
Galloway, A., Golubeva, A., Tanay, T., Moussa, M., and Taylor, G. W. Batch normalization is a cause of adversarial vulnerability. arXiv preprint 190. 2019.
Geifman, A., Yadav, A., Kasten, Y., Galun, M., Jacobs, D., and Ronen, B. On the similarity between the laplace and neural tangent kernels. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F. and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1451-1461. Curran Associates, Inc., 2020, htt/https:///rrceeeee 0006ff22266552566667444444444440
Adversarial spheres. arXiv preprint Paper- pdf
Gilmer, J., Metz, L.,, Faghni, F., Schoenholz, S. S., Raghu, M., Wattenberg, M., and Goodfellow, I. 2018.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. International Conference Learning Representations (ICLR), 2015.
He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Huang, G., Liu, Z., Van Der Maaten, L.., and Weinberger, K. Q. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700 4708-4708, 2017.
Huang, K., Wang, Y., Tao, M., and Zhao, T. Why do deep residual networks generalize better than deep feedforward networks? neural tangent kernel perspective. Advances in Neural Information Processing Systems, 33, 2020.
Jacobsen, J.-H., Behrmann, J., Zemel, R., and Bethge, M. Excessive invariance causes adversarial vulnerability. In International Conference on Learning Representations, 2019. URL https //openreview. met/fooumm? id BddBkkbssAcFF
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 857 1-510, 2018.
Kamath, S., Deshpande, A., and Subrahmanyam, K. V. Invariance robustness of neural networks, 2020. URL http::t/p////pereeiiii wtt.://www.eeeermmmmm/dddppppppa
Kayhan, O. S. and Gemert, J. C. v. On translation invariance in cnns: Convolutional layers can exploit absolute spatial location. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14274 14285, 2020.
Khoury, M. and Hadfield-Menell D. On the geometry of adversarial examples. International Conference on Learning Representations, 2019.
Krizhevsky, A. One weird trick for parallelizing convolutional neural networks. arXiv preprint arXiv: 14045999, 2014.
LeCun, Y., Boser, B., Denker, S., Henderson, D., Howard, R. E., Hubbard, W., and Jackel, I., D. Backpropagation applied handwritten zip code recognition. Neural computation, 1(4):541-551, 1989.
12

---

LeCun, Y., Cortes, C., and Burges, C. Mnist handwritten digit database. ATT Labs Avniiae].Available: http:/yann.. http://yam.ecun.com/eee lecun.com/exdb/mmiss, 2, 2010.
Available:
Li, Z., Wang, R., Yu, D., Du, S. S., Hu, w., Salakhutdinov, R., and Arora, Enhanced convolutional neural tangent kernels. arXiv preprint arXiv:1911.00800 2019.
Loshchilov, and Hutter, F. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint 1608. 03983, 2016.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Nakkiran, P. Adversarial robustness may be at odds with simplicity. arXiv preprint arXiv:1901.0055 2019.
Netzer, Y., Wang, T., Coates, A.. Bissacco, A.. Wu, B., and Ng, A. Y. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Fea- ture Learning 2011, 2011. URL http::tttt//titi stanford.trrodrroooooo housenumbers. p
www.aaforr.ddd/uuuuuueeeeeeeeeee www wwtp://ouseenmmbrr//nis///000//0
Neyshabur, B. Towards learning convolutions from scratch. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 9078-8088. Curran Associates, Inc., 2020. URL Paper pdf
neurips
ftle//lll//////// cc/paper http:///hioosaaaaaaaeeeeeee0fff0
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville, A. On the spectral bias of neural networks. In International Conference on Machine Learning, pp. 5301-5310. PMLR, 2019.
Rony, J., Hafemann, L. G., Oliveira, L. S., Ayed, I. B., Sabourin, R., and Granger, E. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (C (CVPR), June 2019.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems, pp. 5026-5026, 2018.
Shafahi, A., Huang, W. R., Studer, C., Feizi, S., and Goldstein, T. Are adversarial examples inevitable? International Conference on Learning Representations, 2019.
Shah, H., Tamuly, K., Raghunathan, A., Jain, P., and Netrapalli, P. The pitfalls of simplicity bias in neural networks. In NeurlPS, 2020. URL http::ttt/soooceediiiiaii
nwwripe. aeurrips.cc/ppprr2222 ccpppppr//200// Abstrat.
Shamir, A., Safran, I., Ronen, E., and Dunkelman, O. A simple explanation for the existence of adversarial examples with small hamming distance, 2019.
Shao, R., Shi, Z., Yi, J., Chen, P.-Y,, and Hsich, C.-J. On the adversarial robustness of visual transformers. arXiv preprini arXiv:2 103. /5670, 2021.
Simon-Gabriel, C.-J., Ollivier, Y., Bottou, L., Schölkopf, B., and Lopez-Paz, D. First-order adversarial vulnerability of neural networks and input dimension. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. -8009 PMLR, 09-15 Jun 2019. URL http:///rrcceedings. mlr. hal...pressvv97 ssmoonimoooo//oooissoosssooossss http://onnnaabbrel..............
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing 2013.
properties of neural networks. arXiv preprint
Tancik, M.. Srinivasan, P. P., Mildenhall, B., Fridovich-Keil, S., Raghavan, N., Singhal, U.. Ra- mamoorthi, R., Barron, J. T., and Ng, R. Fourier features let networks learn high frequency functions in low dimensional domains. NeurIPS, 2020.
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019. URL. httpss //openreview.ro wttp:/teee/oommdd///ttttttee
13

---

Wang, H., Wu, X., Huang. Z., and Xing, E. P. High-frequency component helps explain the generalization of convolutional neural networks. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 8684-8694, 2020.
Wu, B., Chen, J., Cai, D., He, X., and Gu, Q. Does network width really help advensarial robustness? arXiv preprint arXiv:2010.01279, 2020a.
Wu, Z., Lim, S.-N., Davis, L. S., and Goldstein, T. Making an invisibility cloak: Real world adversarial attacks object detectors. In European Conference Computer Vision, pp. 1-17. Springer, 2020b.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.007477 2017. URL http://arxiv http://aaxxii.oraaaa////iae org/abs//708.077//
Yang. G. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006. 14548, 2020.
Zhang, R. Making convolutional networks chift-invariant again. In International conference machine learning, pp. 7324-7334. PMLR, 2019.
14


Reviews:
[{"review_id": "nct6R_sgN0M", "reviewer": "Reviewer_7xCn", "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.\n- The experimental results are worth a deeper analysis of why less shift-invariant networks appear more robust.\n- Code is provided in the supplementary.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The observation that shift Invariance can reduce adversarial robustness is an interesting and important topic.\n- The experimental results are worth a deeper analysis of why less shift-invariant networks appear more robust.\n- Code is provided in the supplementary.\n\nCons:\n\n(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.\n\n(2) The gap between theory and practice is too large.\n - 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.\n - 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.\n\n(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?\n\n(4) The empirical evidence shown here is not enough to convince me that ``in general'', more shift-invariant network will be less robust:\n - 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.\n - 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.\n - 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?\n - Does the findings still hold when network trained with adversarial training? If adversarial training is used, does the level of shift-invariance decrease?\n - 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?\n\n(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.\n\nminor:\n- The figures can be organized in a way that they are on the same page with the text that is mentioning the figure.\n- C&W attack should be used for L2 attacks https://arxiv.org/abs/1608.04644.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are several limitations of this work not mentioned by the authors:\n- There gap between theory and practice is too large and the theorem cannot represent most of the particle cases.\n- Many confounding factors mentioned in my review are not discussed in the paper.\n\nI am not aware of any potential negative social impact of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "XUbETZdQXvP", "reviewer": "Reviewer_yPtR", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- 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. \n\nWeaknesses\n- I found this is a nice paper. I don't particularly see weaknesses.\n\nMinor:\nL292: Visual Transformer -> Vision Transformer\n\nAdditional comments:\n- It would be interesting to consider more common image corruptions like gaussian noise, blur, etc.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "OwaRMvkZZJV", "reviewer": "Reviewer_SjMk", "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, \nfully 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is very well-motivated and addresses an important problem in adversarial machine learning, i.e., a better understanding of adversarial attacks.\n2. 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.\n3. The hypothesis for shift-invariance is empirically tested on large datasets and diverse neural network architectures such as FC, CNNs, and transformers.\n\n\nOpen concerns:\n1. 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).\n2. 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.\n3. 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?\n4. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "AUmhRxOaSu4", "reviewer": "Reviewer_UPzX", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThere 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nIn 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. \n\nIn 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.  \n\nArguably, 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. \n\nIf 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.\n\nThe authors have adequately address the work's societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns with this work. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

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)