Drawing Robust Scratch Tickets: Subnetworks with Inborn Robustness Are Found within Randomly Initialized Networks
Authors: Yonggan Fu
Qixuan Yu
Yang Zhang
Shang Wu
Xu Ouyang
David Daniel Cox
Yingyan Lin
Venue: NeurIPS 2021 Poster (2021)
Keywords: model robustness
adversarial training
lottery ticket hypothesis

Abstract: Deep Neural Networks (DNNs) are known to be vulnerable to adversarial attacks, i.e., an imperceptible perturbation to the input can mislead DNNs trained on clean images into making erroneous predictions. To tackle this, adversarial training is currently the most effective defense method, by augmenting the training set with adversarial samples generated on the fly. \textbf{Interestingly, we discover for the first time that there exist subnetworks with inborn robustness, matching or surpassing the robust accuracy of the adversarially trained networks with comparable model sizes, within randomly initialized networks without any model training}, indicating that adversarial training on model weights is not indispensable towards adversarial robustness. We name such subnetworks Robust Scratch Tickets (RSTs), which are also by nature efficient. Distinct from the popular lottery ticket hypothesis, neither the original dense networks nor the identified RSTs need to be trained. To validate and understand this fascinating finding, we further conduct extensive experiments to study the existence and properties of RSTs under different models, datasets, sparsity patterns, and attacks, drawing insights regarding the relationship between DNNs’ robustness and their initialization/overparameterization. Furthermore, we identify the poor adversarial transferability between RSTs of different sparsity ratios drawn from the same randomly initialized dense network, and propose a Random RST Switch (R2S) technique, which randomly switches between different RSTs, as a novel defense method built on top of RSTs. We believe our findings about RSTs have opened up a new perspective to study model robustness and extend the lottery ticket hypothesis.

Drawing Robust Scratch Tickets: Subnetworks with Inborn Robustness Are Found within Randomly Initialized Networks
Yonggan Fu', Qixuan Yu!, Yang Zhang?, Shang Wu', Xu Ouyang!
David Cox², Yingyan Lin'
Rice University, MITT-BB Watson Lab
9y222, xo2)) edu, Lyang zhang2, David D. 2.. Cox)@ibm.com
Abstract
Deep Neural Networks (DNNs) are known to be vulnerable to adversarial attacks, i.e., an imperceptible perturbation the input can mislead DNNs trained on clean images into making erroneous predictions. To tackle this, adversarial training is currently the most effective defense method, by augmenting the training set with adversarial samples generated on the fly. Interestingly, we discover for the first time that there exist subnetworks with inborn robustness, matching or sur- passing the robust accuracy of the adversarially trained networks with com- parable model sizes, within randomly initialized networks without any model training, indicating that adversarial training on model weights is not indispensable towards adversarial robustness. We name such subnetworks Robust Scratch Tickets (RSTs), which are also by nature efficient. Distinct from the popular lottery ticket hypothesis, neither the original dense networks nor the identified RSTs need to be trained. To validate and understand this fascinating finding, we further conduct extensive experiments to study the existence and properties of RSTs under different models, datasets, sparsity patterns, and attacks, drawing insights regarding the rela- tionship between DNNs' robustness and their inttaalzatiion/verrraameett hwwpr//aaaaaaaattiittiiioo Furthermore, identify the poor adversarial transferability between RSTSs of different sparsity ratios drawn from the same randomly initialized dense network, and propose Random RST Switch (R2S) technique, which randomly switches between different RSTs, as a novel defense method built on top of RSTs. We believe our findings about RSTs have opened up new perspective study model robustness and extend the lottery ticket hypothesis. Our codes are available at: http://gitbbbooom/oc/HHCCCoooott
Introduction
There has been an enormous interest in deploying deep neural networks (DNNs) into numerous real-world applications requiring strict security. Meanwhile, DNNs vulnerable to adversarial attacks, i.e., an imperceptible perturbation to the input can mislead DNNs trained on clean images into making erroneous predictions. To enhance DNNs' robustness, adversarial training augmenting the training set with adversarial samples is commonly regarded as the most effective defense method. Nevertheless, adversarial training is time-consuning iteration requires multiple gradient computations to produce ad adversarial images. In fact, its actual slowdown factor over standard DNN training depends on the number of gradient steps used for adversarial example generation, which can result in a 3-30 times longer training time M.
each stochastic gradient descent (SGD)
In this work, ask intriguing question: "Can find robust subnetworks within randomly initial- ized networks without any training"? This question not only has meaningful practical implication
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

but also potential theoretical ones. If the answer is yes, it will shed light on new methods towards robust DNNs, e.g., adversarial training might not be indispensable towards adversarial robustness; furthermore, the existence of such robust subnetworks will extend the recently discovered lottery ticket hypothesis (L.HH) 2 which articulates that neural networks contain sparse subnetworks that can be effectively trained from scratch when their weights being reset to the original initialization, and thus our understanding towards robust DNNs. In particular, we make the following contributions:
We discover for the first time that there exist subnetworks with inborn robustness, matching or surpassing the robust accuracy of adversarially trained networks with comparable model sizes, within randomly initialized networks without any model training. We name such subnetworks Robust Scratch Tickets (RSTs), which are also by nature efficient. Distinct from the popular LTH, neither the original dense networks nor the identified RSTs need to be trained. For example, RSTs identified from a randomly initialized ResNet101 achieve a 3.56% % and 1. 222% higher robust/natural accuracy than the adversarially trained dense ResNet18 with a comparable model size, under a perturbation strength of e 2 and = 4, respectively.
We propose a general method to search for RSTs within randomly initialized networks, and conduct extensive experiments to identify and study the consistent existence and proper- ties of RSTs under different DNN models, datasets, sparsity patterns, and attack methods, drawing insights regarding the relationship between DNNs' robustness and their initializa- tion/oveparrancteiizaioon Our findings on RSTs' existence and properties have opened up new perspective for studying DNN robustness and can be viewed complement to LTH.
We identify the poor adversarial transferability between RSTs of different sparsity ratios drawn from the same randomly initialized dense network, and propose Random RST Switch (R2S) technique, which randomly switches between different RSTs, as a novel defense method built on top of RSTs. While adversarially trained network shared among datasets suffers from degraded performance, our R2S enables the use of one random dense network for effective defense across different datasets.
2 Related Works
Adversarial attack and defense. DNNs are vulnerable to adversarial attacks, i.e., an imperceptible perturbation on the inputs can confuse the network into making a wrong prediction [3. There has between adversaries and defenders. On the adversary side, stronger 7
been a continuous war 4 5
attacks continue to be proposed, including both white-box 66
g g
10 and black-box ones []] 12]
13 14 [5]. to notably degrade the accuracy of the target DNNs. In response, on the defender side, various defense methods have been proposed to improve DNNs' robustness against adversarial attacks. For example, randomized smoothing [16 17 on the inputs can certifiably robustify DNNs against adversarial attacks; [8
22 purify the adversarial examples back to the distribution of 25 adopt detection models to distinguish adversarial examples from clean ones. In particular, adversarial training (26 6 27 28 is currently the most effective defense method. In this work, we discover the existence of RST, i.c., there exist subnetworks with inborn robustness that are hidden in randomly initialized networks without any training.
19
20
21
clean ones; and (23 24
Model robustness and efficiency. Both robustness and efficiency (2 matter for many DNN- powered intelligent applications. There have been pioneering works 30
that explore the potential of pruning on top of robust DNNs. In general, it is observed that moderate sparsity necessary for maintaining DNNs' adversarial robustness, over-sparsified DNNs are more vulner- able [30), and wwer-parameterization is important for achieving decent robustness ( Pioneering examples include: [31) finds that naively pruning an adversarially trained model will result in notably degraded robust accuracy: (35) for the first time finds that quantization, if properly exploited, can even enhance quantized DNNs' robustness by a notable margin over their full-precision counterparts; and [32 adopts pruning techniques that are aware of the robust training objective via learning a binary mask on an adversarially pretrained network; and [34] prunes vulnerable features via a learnable mask and proposes a vulnerability suppression loss to minimize the feature-level vulnerability. In contrast, our work studies the existence, properties, and potential applications of RSTs, drawn from randomly initialized networks.
32
33 34
Lottery ticket hypothesis. The LTH 2 shows that there exist small subnetworks (i.e., lottery tickets (LTs)) within dense, randomly initialized networks, that can be trained alone to achieve comparable

---

accuracies to the latter. The following works aim to: (1) study LTs' properties [3 37 38 39
(2)
43 and (3) extend LTH to various networks/tasks/trainii The L.T's drawn by existing works need to be (1) drawn from a pretrained network (except 43), and (2) trained in isolation after being drawn from the dense network. In contrast, RSTs are drawn from randomly initialized networks and, more importantly, no training is involved. We are inspired by [51], which finds that randomly weighted networks contain subnetworks with impressive accuracy and (2 53 which provide theoretical support for [5]] and extend [51] to identify binary neural networks in randomly weighted networks, respectively. While DNNs' adversarial robustness is important, it is not clear whether robust subnetworks exist within randomly initialized networks. We provide a positive answer and conduct a comprehensive study about the existence, properties, and potential applications for RSTs.
improve LTs' performance
40,
42
pipelines 44 45
46
47
48
49
50
3 Robust Scratch Tickets: How to Find Them
In this section, we describe the method that we adopt to search for RSTs within randomly initialized networks. As modern DNNs contain staggering number of possible subnetworks, it can be non- trivial to find subnetworks with inborn robustness in randomly weighted networks.
3.1 Inspirations from previous works
Our search method draws inspiration from prior works. In particular, 31 finds that naively pruning an adversarially trained model will notably degrade the robust accuracy, on an adversarially pretrained network to make pruning techniques aware of model robustness, and [50] shows that randomly weighted networks contain subnetworks with impressive nature accuracy, inspiring us to adopt learnable masks on top of randomly initialized weights to identify the RSTs.
32
learns a binary mask
3.2 The proposed search strategy
Overview. Our search method adopts sparse and learnable mask m associated with the weights of randomly initialized networks, where the search process for RSTs is equivalent to only update m without changing the weights as inspired by [32 [1]. To search for practically useful RST's the update of m has to (I) be aware of the robust training objective, and (2) ensure that the sparsity of m is sufficiently high, e.g., higher than specified value (1 k/N) where k is the number of remaining weights and N is the total number of weights. In particular, we adopt an adversarial search process to satisfy (1) and binarize m activate only fraction of the weights in the forward pass to satisfy (2).
Objective formulation. We formulate the learning process of m as minimax problem:
arg min Σ max E(f(mn O 0, + y1) s.t. l & k Se
where E is the loss function, f is a randomly initialized network with random weights @ E RN and Yr are the i-th input and label pair, O denotes element-wiss product operation, ö is a small perturbation applied to the inputs and e is scalar that limits the perturbation magnitude in terms of the Linf norm. Following [51. i {0, 1)d approximates the top & largest elements of m e RN using 1 and O otherwise during the forward pass to satisfy the target sparsity constraint, while all the elements in m will be updated during the backward pass via ttraight-through estimation [54]. Such an adversarial search process guarantees the awareness robustness, which differs from vanilla adversarial training methods 126 6 27 (8 in that here the model weights are never updated. After the adversarial search, a found RST is claimed according to the finally derived binary mask m. As discussed in Sec. 4.5) m can have different sparsity patterns, e.g., clement-wiss row-wise, kernel-wisg where RSTs are consistently observed.
Inner optimization. We solve the inner optimization in Eq. I with Projected Gradient Descent (PGD) (6) which iteratively adopts the sign of one-step gradient as an approximation to update with small step size a, where the 1-th iteration can be formulated as:
8,41 = clip (8, + sign( s o 0, +,),))0)))
where clipe denotes the clipping function that enforces its input to the interval [-e, é]. As shown in Sec. 4.6 other adversarial training methods can also be adopted to draw RSTs.
3

---

Rablut Aquuaay
ResNet18 WideResNet22
ResNeti8 Wit2
Reclitt8
ResNet18 WideResNNtt22
WideReaaNet22
Radie
[a] Robust Acc @ CIFAR-10
(b) Natural Acc @ CIFAR-10
(c) Robust Acc @ CIFAR-100
(d) Natural Acc @ CIFAR-100
Rab Aocuray (h)
tatrinngee nereal Kaireing Unforn
Aitning horeal
Rear wise
Berrnt
PIGH PIGOLLRS
PGD
kaiving Frilurn
Kammi wisa
ResNet18 CIFAR-10
ResNet18 CIFAR-100
(g) ResNett8 @ CIFAR-10
(b) ResNet18 CIFAR-10
Figure I: Illustrating RSTs' consistent existence, where (a)~ The robust and natural accuracy of RSTs with different remaining ratios in ResNet18 and WideRestNet32 on CIFAR-I0/ respec- tively; (e)~(f): The robust accuracy of RSTs with different remaining ratios identified in R under different initialization methods on CIFAR- 1000R000000,,,- respectively; (g) The robust accuracy of RSTs with different sparsity patterns identified in ResNet18 on CIFAR-I0; and (h) The robust accuracy of RSTs identified using different ad adversarial search methods in ResNet18 on CIFAR- 10. The accuracies of the adversarially trained original dense networks are annotated using dashed lines.
4 The Existence of Robust Scratch Tickets
In this section, we validate the consistent existence of RSTs across different networks and datasets with various sparsity patterns and initialization methods based on the search strategy in Sec. 3
4.1
Experiment Setup
Networks and datasets. Throughout this paper, we consider a total of four networks and three datasets, including PreActResNet188 (noted as ResNet18 for simplictt/WiidResNeee22 on CIFAR-IOCCIFAR (55) and ResNec50/ResNet100 on ImageNet [56).
Adversarial search seftings. For simplicity, we adopt layer-wise uniform sparsity when searching for RSTs, i.e., the weight remaining ratios k/N for all the layers are the same. On CIFAR-IO/CITAR 100, we adopt PGD-7 (7-step PGD) training for the adversarial search based on Eq. following 6 On ImageNet, we use FGSM with random starts (FGSM-RS) (27). which can be viewed as a 1-step PGD, to update the mask m. The detailed search settings can be found in the Appendix.
Adversarial attack settings. We adopt PGD-20 6 attacks with e = 8, which is one of the most effective attacks, if not specifically stated. We further examine the robustness of RSTss under more attack methods and larger perturbation strengths Sec. 5.3 and Sec. 5.5 respectively.
Model initialization. As RSTs inherit the weights from randomly initialized networks, initialization can be crucial for their robustness. We consider four initialization methods: the Signed Kaiming Constant [5]] Kaiming Normal (57]. Xavier Normal (58), and Kaiming Uniform [57]. If not specifically stated, we adopt the Signed Kaiming Constant initialization thanks to its most competitive results (see See. 4.4). We report the average results based three runs with different random seeds.
4.2 RSTs exist on CIFAR-10/100
Fig. (a)~(d) visualize both the robust and natural accuracies of the identified RSTs with different weight remaining ratios (i.e., k/N) in two networks featuring different degrees of overparameteriza- tion on CIFAR- 10/100. We also visualize the accuracy of the original dense networks after adversarial training, while RSTs are drawn from the same dense networks with only random initialization.
Observations and analysis. RSTs do exist as the drawn RSTs with a wide range of weight remaining ratios achieve both decent robust and natural accuracy, even without any model training. Specifically, we can see that (1) RSTs can achieve a comparable robust and natural accuracy with the adversarially trained original dense networks under a wide range of remaining ratios (i.e., 5%.40%), e.g., the RST drawn from ResNet18 with remaining ratio of 20% (i.e., 80% sparsity) without any training suffers from only 2.08% and 2.43% drop in the robust and natural accuracy, respectively, compared with the adversarially trained dense ResNet18; (2) RSTs hidden within randomly initialized networks

---

with more overparameterrizatoon achieve a better robustness than the adversarially trained dense networks with a similar model size, e.g., the RST with remaining ratio of 10% identified in the randomly initialized WideResset322 achieves 1.14% higher robust/natural accuracy with 60% reduction in the total number of parameters without any training, over the adversarially trained dense ResNet18; and (3) RSTs under very large or small remaining ratios have relatively inferior robust and natural accuracies, which is expected since RSTs under large remaining ratios (e.g.. 60%) are close to the original randomly initialized networks that mostly make random predictions, while RSTs under small weight remaining ratios (e.g., 5%) are severely underparamettrrizd.
4.3 RSTs exist on ImageNet
We further validate the existence of RSTs on ImageNet. As shown in
Table 1: Comparing RSTs identified in ResNet50/101 with the adversarially trained ResNet18 on ImageNet.
Tab. D we can see that (1) RSTs do exist on ImageNet, e.g.. RSTs identified within ResNet101 achieve a 3.56% and 1.22% higher robust/nnttral accuracy than the adversarially trained ResNet18 with a comparable model size, under = 2 and 4, respectively; and (2) RSTs identified from more overparameteriized networks achieve
Remaining Ratio
# Parameter
Natural Ace
Robust Acc
Network
(M)
(%)
RosNet18 (Dease)
11.17
56.25
37.09
RST ResNet50
0.4
9.41
53.84
35.24
ResNet101
60.56
Res (Deuse)
11.17
50.41
25,46
RST ResNet50
0.4
9.41
46.36
21.99
RST @ ResNett01
0.25
10.62
54.84
26.68
better robust/natural accuracy than those from lighter networks, as RSTs from ResNet101 are notably more robust than those from ResNet50 under comparable model sizes.
4.4 RSTs exist under different initialization methods
We mainly consider Signed Kaiming Constant initialization [5] for the randomly initialized networks, as mentioned in Sec. [4.]] and here we study the influence of different initialization methods on RSTs, Fig. (e) and (f) compare the robust accuracy of the RSTs drawn from ResNet18 with different initializations on CIFAR-10/100, respectively. Here we only show the robust accuracy for better visual clarity, as the corresponding natural accuracy ranking is the same and provided in the Appendix.
Observations and analysis. We can see that (1) RSTs consistently exist, when using all the initializa- tion methods; and (2) RSTs drawn under the Signed Kaiming Constant [5T] initialization consistently achieve a better robustness than that of the other initialization methods under the same weight re- maining ratios, indicating that RSTs can potentially achieve stronger robustness with more dedicated initialization. We adopt Signed Kaiming Constant initialization in all the following experiments.
4.5
RSTs exist under different sparsity patterns
We mainly search for RSTs considering the commonly used element-wise sparsity, as mentioned in Sec. 4.1 A natural question is whether RSTs exist when considering other sparsity patterns, and thus here we provide an ablation study. Specifically, for each convolutional filter, we consider another three sparsity patterns: row-wise sparsity, kernel-wise sparsity, and channel-wise sparsity.
Observations and analysis. Fig. (g) shows that RST's with more structured row-wise and kernel- wise sparsity still exist, although suffering from a larger robustness accuracy drop over the adver- sarially trained original dense networks, and we fail to find RSTs with a decent robustness when considering channel-wise sparsity. Indeed, RSTs with more structured sparsity show a more inferior accuracy, since it is less likely that a consecutive structure within a randomly initialized network will be lucky enough to extract meaningful and robust features. Potentially, customized initialization can benefit RSTs with more structured sparsity patterns and we leave this as a future work.
RSTs exist under different ad adversarial search methods 4.6
To study RSTs' dependency on the adopted adversarial search methods, here we adopt another two adversarial search schemes, FGSM 3 and FGSM-RS (27. for the inner optimization in Eq. D
Observations and analysis. Fig. I (h) shows that (1) using an FGSM or FGSM-RS search scheme can also successfully identify RSTs from randomly initialized networks; and (2) RSTs identified uing PGD-7 training consistently show a better robustness under the same weight remaining ratios compared with the other two variants. This indicates that better adversarial search schemes can lead to higher quality RSTs and there potentially exist more robust RSTs within randomly initialized networks than the reported ones, when adopting more advanced adversarial search schemes.
5

---

RST
FT FT_RST Inherit
TT_RSS_Inherit
PT_RST_Reinit
Robust Accuracy (%)
Robust Accuracy (%)
45
40
E
35
30
6.05
0.16
115
Remaining
Remaining Ratio
(a) ResNet18 @ CIFAR-10
(b) ResNet18 @ CIFAR-100
30.0
Robust Accuracy 1%
30
27.5
23.0
22.5
20.0
17.5
15.0
Remaining
Remaining
(c) WideResNet32 @ CIFAR-10
(d) WideResNet32 @ CIFAR-100
Figure 2: Comparing the robust aceuracy of RSTs, fine-tuned RSTs with inherited weights, and fine-tuned RSTs with reinitialization, with zoom-ins for the low remaining ratios (1 (1%-~00))
4.7 Comparison with other adversarial lottery tickets
We further benchmark RSTs with other adversarial lottery tickets identified by (59]. On top of WideResNet32 on CIFAR-10, [59] achieves 50.48% robust accuracy with a sparsity 80% under PGD-20 attacks with 8, while 90%, which indicates that RSTs are high quality subnetworks with decent robustness even without model training. As will be shown in Sec. 5.I the robustness of RSTs can be further improved after being adversarially fine-tuned.
RST achieves 51.39% robust accuracy with sparsity of
4.8 Insights behind RSTs
The robustness of RSTs is attributed to RSTs' searching process which ensures the searched subnet- works effectively identify critical weight locations for model robustness. This has been motivated by (60] that the location of weights holds most of the information encoded by the training, indicating that searching for the locations of subset of weights within randomly initialized network might be potentially as effective as adversarially training the weight values, in terms of generating robust mod- els. In another word, training the model architectures may be an orthogonal and effective complement for training the model weights.
5
The Properties of Robust Scratch Tickets
In this section, we systematically study the properties of the identified RSTs for better understanding.
5.1 Robustness of vanilla RSTs vs. fine-tuned RSTs
An interesting question is "how do the vanilla RSTs perform compared to RSTs with adversarially fine-tuned model weights"? Inspired by (2). we consider two settings: (1) fine-tuned RSTs starting with model weights inherited from the vanilla RSTs, and (2) fine-tuned RSTs with reinitialized weights. Fig. 2g.22ee compares their accuracy on three networks and two datasets with zoom-ins under low remaining ratios -2%). Here only show the robust accuracy for better visual clarity, where the natural accuracy with a consistent trend is provided in the Appendix.
Observations and analysis. We can see that (1) the vanilla RSTs achieve a comparable robust
accuracy with that of the fine-tuned RSTs under wide range of weight remaining ratios according to Fig. (a), excepting under extremely large and small remaining ratios for the same reason as analyzed in Sec. 2 (2) under low remaining ratios (I (1%%),), fine-tuned RSTs with inherited weights can
mostly achieve the best robustness among the three RST variants, but the robust accuracy gap with

---

RST
Natural_ RTT
RTT_RTT
Robust Accuracy (Ng
Robust Accuracy (K)
45
43
20-
30
38-
4.2
1.5
2111
1.20
0.0
0.3
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.0
0.3
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Remaining Ratio
Remaining Ratio
(a) ResNet18 @ CIFAR-10
(b) ResNet18 @ CIFAR-100
12
Robust Accuracy (%)
50
Robust Accuracy (56
48-
26
<6
22
26
3.7
0.0
0.2
0.55
0.4
0.5
0.6
07.
0.8
0.0
0.2
0.2
0.5
0.4
0.5
0.6
0.7
0.8
Remaining Ratio
Remaining Ratio
(c) WideResNet32 @ CIFAR-10
(d) WideRessNe32@ CIFAR-100
Figure 3: The robust accuracy achieved by RSTs, natural RTTs, and adversarial RTTs drawn from ResNet1 W/ideeeseee22222222 on CIFAR-10/100, with zoom-ins under low remaining ratios (1 (1%)...)
the vanilla untrained RSTs is within -0.22%%33552%; and (3) under commonly used weight remaining only achieve comparable or even inferior robust accuracy compared with the vanilla RSTs without any model training. We also find that under extremely low remaining ratios like 1% (i.e., 99% sparsity), fine-tuned RSTs with re-initialization achieve a better robustness than the vanilla RSTs on extremely overparameterized networks (e.g, WideResNe(32) since they still retain enough capacity for effective feature learning.
ratios (5%~20%) 61]. fine-tuned RSTs with re-initialization
Key insights. The above observations indicate that the existence RSTs under low weight remaining ratios reveals another lottery ticket phenomenon in that (1) RST without any model training can achieve better comparable robust and natural accuracy with adversarially trained subnetwork of the same structure, and (2) the fine-tuned RSTs with inherited weights can achieve notably better robust accuracy than the re-initialized ones, indicating that RSTs win better initialization.
5.2 Vanilla RSTs vs. RTTs drawn from trained networks
As the adversarial search Eq. can also be applied to trained networks, here we study whether subnetworks searched from trained models, called robust trained tickets (RTTs), can achieve comparable accuracy over the vanilla RSTs. Fig. 3 compares RST with two kinds RTTs, i.e., natural RTTs and adversarial RTTs which are searched from naturally trained and adversarially trained networks, respectively. For better visual clarity, we only show the robust accuracy in Fig. and the corresponding natural accuracy with consistent trend is provided in the Appendix.
Observations and analysis. We can observe that (1) ad- versarial RTTs consistently achieve the best robustness, indicating that under the same weight remaining ratio, sub- networks drawn from adversarially trained networks are more robust than RSTs drawn from randomly initialized ones or RTTs from naturally trained ones; (2) there ex- ist natural RTTs with decent robustness even the robust accuracy of the corresponding trained dense networks is al- most zero; and (3) interestingly. RST' consistently achieve a better robust/natural accuracy over natural RTTs, indicat- ing the subnetworks from naturally trained networks are less robust than the ones drawn from randomly initialized neural networks.
Dormaltzed aond Distance
1012
Signed Adv Trained Naturally Trained
Figure 4: Normalized distances between the feature maps generated by clean and noisy images ResNet18 CIFAR-10.

---

REMMIT ACCUINO (70 1
Bobb Rebbutt Aucur (50
Mablet houreey
F1,07
5.0 66)
63F 020
6:0
355
6:13
2:0
6.3
Remmiiing Radio
(a)
12
(b)
(c)
12
(d) 16
Figure 6: Validating RSTs' properties under stronger perturbations on ResNet18 10.. (a)-(b): Comparing vanilla RSTs with fine-tuned RSTs under =12 and 16, respectively; and (c)~(d): Comparing vanilla RSTs with RTTs under =12 and 16, respectively.
To understand the above observations, we visualize the normalized distance between the feature maps of the last convolution layer generated by (1) clean images and (2) noisy images (i.e., clean images plus a random noise with magnitude of e on top of ResNet18 with random initialization (Signed Kaiming Constant [51), weights trained on clean images, and weights trained on adversarial images on CIFÁR-10) -0), inspired by [62]. Fig. shows that the naturally trained ResNet18 suffers from large distance gaps between the feature maps with clean and noisy inputs, indicating that it is more sensitive to the perturbations applied its inputs and thus the natural RTTs identified within are potentially less robust, while the adversarially trained ResNer18 is the opposite.
Is overparameterizatio necessary in adversarial training? We further compare the vanilla RSTs, fine- tuned RSTs with inherited weights, and adversarial RTTs, drawn from ResNet18 8 on CIFAR-10 10 in Fig. 5 We can see that adversarial RTTs consistently achieve the best robust- ness under the same weight remaining ratio. The compar- ison between adversarial RTTs and fine-tuned RSTs with inherited weights indicates that robust subnetworks within an adversarially trained and overparameterized network can achieve better robustness than those drawn from randomly initialized network or adversarially trained from scratch, i.e., the everparameterization during adversarial training is necessary towards decent model robustness.
Robust Accuracy (80
50.0
45.0
62.5
40.0
RST inherit
37.5
0.0
0.2
0.4
0.6
0.8
Remaining Ratio
Figure 5: Robust accuracy vs. remain- ing ratio for RSTs, fine-tuned RSTs with inherited weights, and adversarial RTTs.
5.3 RSTs' scalability to stronger perturbations
To explore whether the findings in Sec. 5. and Sec. 5.2 can be scaled to more aggressive attacks with stronger perturbations, visualize the comparison between RST' and fine-tuned RSTs/RTTs in Fig. when considering the perturbation strength = 12, 16 in ResNet18 on CIFAR-10.
Observations and analysis. We can observe that (1) RSTs still can be successfully identified under stronger perturbations; and (2) the insights in both See. Sec.5.1 and Sec. 5.2 still hold and the accuracy gaps between the vanilla RSTs and natural RTTs are even larger under stronger perturbations.
5.4 RSTs' robustness against L2-PGD attacks
We further evaluate RSTs with differ- remaining ratios and their correspond- ing dense networks trained by Linf- PGD against Lz-PGD attacks top of ResNetl R/side on CIFAR-10. As shown in Tab. 2 we can see that with increased perturbation strength e, the dense networks suffer from larger robust accuracy drops and RSTs can gradually outperform the dense networks by notable margin, indicating that RSTs will suffer less from overfitting to specific norm-ban based attack than the dense networks.
Table 2: Evaluating RST's and the corresponding dense networks trained by Ling against L2-PGD attacks with different perturbation strengths on CIFAR-10.
ResNet18
WideResNet32
Network
c=0.50
c=1.71
c=2.00
c=0.50
c=1.71
c=2.00
Dense
63.61
40.85
39.04
63,94
36.55
34.66
85%
43.81
42.25
47.75
45.96
63.04
43.94
42.41
65.05
43.63
42.08
RST@ 10%
63.61
44.49
42.81
66.93
45.56
43.87
RST@ 15%
62.03
44.16
42.58
67.18
45.23
43.44
RST@ 20%
64.43
44.35
42.51
67.54
45.21
43.51.
5.5 RSTs robustness against more adversarial attacks
We also evaluate the robustness of RSTs against more adversarial attacks, including the CW-1.2/CW-
Inf attacks [8). an adaptive attack called Auto-Attack [7]. and the gradient-free Bandits [2] as

---

detailed in the Appendix. We find that RSTs are generally robust against different attacks, e.g., under auto-Attack/CW-Int attacks on CIFAR-10, the RST with a weight remaining ratio of 5% identified in a randomly initialized WideResNet322 achieves 2.51 2.51% %%22.00% higher robust accuracy, respectively, together with an 80% parameter reduction as compared to the adversarially trained ResNet18.
Applications of the Robust Scratch Tickets
In this section, we show that RSTs can be utilized to build defense method, serving as the first heuristic to leverage the existence of RSTs for practical applications. Specifically, we first identify the poor adversarial transferability between RST's of different weight remaining ratios drawn from the same randomly initialized networks in Sec. 6.1, and then propose a technique called R2S in Sec. 6.2 Finally, we evaluate R2S's robustness over adversarially trained networks in Sec. 6.3
6.1 Poor adversarial transferability between RSTs with different weight remaining ratios
To study the adversarial transferability between RSTs of different remaining ratios drawn from the same randomly initialized networks, we transfer the adversarial attacks generated under one remaining ratio to attack RSTs with other remaining ratios and visualize the resulting robust
0.83
43.8
67.5
72.1
72.6
09.4
74.2 74.3 71.3
0.06
00.7-00.7
45.5
69.3 70.2
96.0
72.5
72.2 59.1
Attack RST
0.87
0.87-50.0
62.5
470
68.0 64.1
70.1
70.0 67.0
6.3
60.0
62.6
67.2
47.0 63.4
65.7
69.7 06.6
accuracy on ResNet18 with CIFAR-10 in Fig. 7 We can see that the robust accuracies in the diagonal (i.e..
0.15
63.9
68.9 68.8
71.
70.7
68.4
0.2 63.3
53.5
65.1 85.0
the same RST for generating attacks and inference) are notably lower than those of the non-diagonal ones, i.e.,
6.4-00.1 65.7
69.2
65.0
6.6
70.5
the transferred ones. Similar observations, provided in the Appendix, can consistently be found on different net- works/datasets, indicating that the adversarial transferabil- ity between RSTs is poor and thus providing potential opportunities for developing new defense methods.
0.03 0.05 0.07 0.1 0.15 0.2 0. 8.6
Inference RST
Figure 7: Adversarial transferability be- tween RSTs from the same randomly ini- tialized ResNetl8 on CIFAR-10 10, where the robust accuracy is annotated.
6.2
The proposed R2S technique
RSTs have two attractive properties: (1) RSTs with different remaining ratios from the same networks inherently have a weight-sharing na-
Table 3: Evaluating R2S under PGD-20 on CIFAR- 10 (columns 2-3) and CIFAR- 100 (columns 4-5).
ture; and (2) the adversarial transferability be- tween RSTs of different remaining ratios is poor (see Fig. 77 To this end, we propose a sim- ple yet effective technique called R2S to boost model robustness. Specifically, R2S randomly switches between different RSTss from candidate RST set during inference, leading to a mismatch between the RSTs adopted by the adversaries to generate attacks and the RSTs used for inference. In this way, robustness is guaranteed by the poor adversarial transferability between RSTs while maintaining parameter-efficieng thanks to the veight-sharing nature of RSTs with different weight remaining ratios drawn from the same networks. The only overhead is the required binary masks for different RSTs, which is negligible (e.g., 3%) as compared with the total model parameters. In addition, as evaluated in Sec. 6.3 the same randomly initialized network can be shared among different lasks with task-specific RSTs, i.e., only extra binary masks are required for more tasks, further improving parameter efficiency.
Network
Natural (%)
PGD-20
Acc (%)
Natural (%c)
Acc (%)
PGD-20
ResNett8 (Dense)
81.73
50.19
56,88
26.94
R25 @ ResNer18
77.49
63.93
52.12
41.01
WideResNec32 (Dense)
85.93
52.27
61.14
29.81
RIS WideResNer52
81.87
67.55
54.72
43.27
6.3 Evaluating the R2S technique
Evaluation setup. Since both the adversaries and defenders could adjust the probability for their RST choices, we assume that both adopt uniform sampling from the same candidate RST set for simplicity. We adopt an RST candi- date set with remaining ratios [5%, 7%, 10%. 15%, 20%, 30%] and results under different RST choices can be found in the Appendix.
Table 4: Evaluating R2S under Auto-Attack ?
and CW-Inf attack [ on CIFAR-10.
Auto-Attack
CW-Inf
Network
<=8
< 12
==8
< 12
ResNet18 (Dense)
46,39
41.13
48.99
45.91
R2S ResNet18
51.92
49.77
54.02
$2.63
WideResNer32 (Dense)
49.66
44.97
54.16
49.22
R2S @ WedeResNet322
56.06
53.91
58.55
$7.48

---

R2S against SOTA attacks. As shown in Tabs. 3 and robust accuracy under all the networks/datasstssataaac e.g., a 13.74% 15.28% and 5.53% 8.94% higher robust accuracy under PGD-20 and Auto-Attack, respectively, on CIFAR-10.
we can see that R2S consistently boosts the
R2S against adaptive attacks. We further de- sign two adaptive attacks on top of PGD-20 attacks for evaluating our R2S: (1) Expecta- tion over Transformation (EOT) following [63]. which generates adversarial examples via the expectations of the gradients from all candidate RSTs; and (2) Ensemble, which generates at- tacks based on the ensemble of all the candidate RSTs, whose prediction the averaged results of all candidate RSTs. Both attacks consider the information of all candidate RSTs. As shown in Tab. we can observe that the robust accuracy of R2S against the two adaptive attacks will drop compared with our R2S against vanilla PGD-20 attacks in Tab, 3 yet it's still 7.40% 9.83% higher than the adversarially trained dense networks, indicating that the two adaptive attacks are effective adaptive attacks and our R2S can still be a strong technique to boost adversarial robustness.
Table 5: Robust accuracy of R2S against two adaptive attacks on CIFAR-10 (columns 2-3) and
CIFAR-I00 (columns 4-5).
ResNet
WideRes Net-32
Res.et -18
WideRes Net-32
Method
-18
Dense R
50.19
52.27
26.94
57.59
64.98
36.68
40.17
R2S Envemble
59.05
62.1
35.98
38.25
Applying random switch on adversarial RTTs. Indeed, the R2S technique can also be extended to adversarial RTTs as the poor adversarial transferability still holds between adversarial RTTs with different remaining ratios (see the Appendix). For example, when adopting the same candidate RST sets as in Tab. 3] R2S on adversarial RTTs achieves a 0.84% higher robust/natural accuracy over R2S using RSTs on CIFAR- 10 under PGD-20 attacks, indicating that R2S is general technique to utilize robust tickets. More results of R2S using adversarial RTTs are in the Appendix.
A Advantages of RSTs over adversarial RTTs, unique property RSTs that the same randomly initialized network can be shared among different tasks and task-specific RSTs can be drawn from this same network and stored compactly via instantiated binary masks, leading advantageous parameter efficiency. In contrast, the task specific adversarial RTTs drawn from adversarially trained networks on a different task will lead a reduced robustness.
To evaluate this, we search for the CIFAR- CIFAR-100-speccff. 100-specific adversarial RTTs from ResNet18 adversarially trained on CIFAR-10 (with the last fully-connected layer reinitial- ized), denoted as transferred adversarial RTT', and com- pare it with (1) CIFAR- 10-A---i---eecficc.cc RSTs and (2) CIFAR- 100-specific adversarial RTTs (identified from ResNet18
Robust Accuracy (%6
24
22
trained on CIFAR-100 100). As shown in Fig. 8 we can see that the transferred adversarial RTTs consistently achieve
18-
RST
16
Adv RTT Transferred Adv RTT
the worst robust accuracy, e.g., 1.68% robust accuracy drop over the corresponding RST under a remaining ratio of 5%. Therefore, it is unique advantage of RSTs to improve parameter efficiency, especially when more tasks are considered under resource constrained applications, while simultaneously maintaining decent robustness.
14
0.05
0110
0.15
0.20
Remaining Ratio
Figure 8: Comparing transferred adver-
sarial RTTs with RSTs and adversarial RTTs in ResNet18 on CIFAR-100.
7 Conclusion
In this work, we show for the first time that there exist subnetworks with inborn robustness, matching or surpassing the robust accuracy of the adversarially trained networks with comparable model sizes, within randomly initialized networks without any model training. Distinct from the popular LTH, neither the original dense networks nor the identified RSTs need be trained. To validate and understand our RST finding, we further conduct extensive experiments to study the existence and properties of RSTs under different models, datasets, sparsity patterns, and attacks. Finally, we make heuristic step towards the practical uses of RSTs. In particular, we identify the poor adversarial transferability between RSTs of different sparsity ratios drawn from the same randomly initialized dense network, and propose a novel defense method called R2S, which randomly switches between different RSTs. While an adversarially trained network shared among datasets suffers from degraded performance, R2S enables one random dense network for effective defense across different datasets.
10

---

Acknowledgements
The work is supported by the National Science Foundation (NSF) through the MLWiNS program (Award number: 2003137).
References
[1] Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! CoRR,
1e//1904.18433. 2019.
[2] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:/803.03665,, 2018.
[3] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572, 2014.
[4] Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks deep learning in computer vision: A survey, leee Access, 6:14400-14430, 2018.
[5] Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. Adversarial attacks and defences: survey. arXiv preprint 1810.00069, 2018.
[6] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.6608: 2017.
[7] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International Conference on Machine Learning, pages 2206-2216. PMLR, 2020.
[8] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pages 39-57. IEEE, 2017.
[9] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European symposium on security and privacy (EuroS&P), pages 372-387, IEEE, 2016.
[10] Seyed-Mohsen Moosavi-Dezfooll: Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3574-2582, 2016.
[11] Pin-Yo Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26, 2017.
[12] Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversar- ial attacks with bandits and priors. arXiv preprint arXiv:1807.00
1807. 0797707978 2018.
[13] Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: a query-efficient black-box adversarial attack via random search, In European Conference on Computer Vision, pages 484-501. Springer, 2020.
[14] Chuan Guo, Jacob Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Weinberger. Simple black-box adversarial attacks. In International Conference on Machine Learning, pages 2484 2493. PMLR, 2019.
[15] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning, pages 2137-2146. PMLR, 2018.

---

[16] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing, In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[17] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. arXiv preprint arXiv:1809.00 (18800093111 13,11, 2018.
[18] Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations. arXiv preprint arXiv:/711.001 17, 2017.
[19] Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint arXiv:1711.01990 2017.
[20] Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. arXiv preprint arXiv: 1704.010055555 155, 2017.
[21] Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. arXiv preprint arXiv: 2017.
[22] Changhao Shi, Chester Holtz, and Gal Mishne. Online adversarial purification based on self-supervision. arXiv preprint 1rXiv:2101.09388) 2021.
[23] Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. arXiv preprint 172. 2017.
[24] Reuben Feinman, Ryan Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts. arXiv preprint arX1v:1703.0044 2017.
[25] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. arXiv preprint arXiv: 1807.03888, 2018.
[26] Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint 190iv:1904. 12843, 2019.
[27] Eric Wong, Leslie Rice, and J Zico Kolter. Fast better than free: Revisiting adversarial training. In International Conference on Learning Representutions, 2019.
[28] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint 1705.0040, 2017.
[29] Junru Wu, Yue Wang, Zhenyu Wu, Zhangyang Wang, Ashok Veeraraghavan, and Yingyan Lin. Deep k-means: Re-training and parameter sharing with harder cluster assignments for compressing deep convolutions. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1363-5372. PMLR, 10-15 Jul 2018.
[30] Yiwen Guo, Chao Zhang, Changshui Zhang, and Yurong Chen. Sparse dnns with improved adversarial robustness. arXiv preprint arXiv:1810.0960 2018.
[31] Shaokai Ye, Kaidi Xu, Sijia Liu, Hao Cheng, Jan-Henrik Lambrechts, Huan Zhang, Aojun Zhou, Kaisheng Ma, Yanzhi Wang, and Xue Lin, Adversarial robustness vs. model compression, or both? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 111-120, 2019.
[32] Vikash Sehwag, Shiqi Wang, Prateck Mittal, and Suman Jana. Hydra: Pruning adversarially robust neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[33] Adnan Siraj Rakin, Zhezhi He, Li Yang. Yanzhi Wang, Liqiang Wang, and Deliang Fan. Robust sparse regularization: Simultaneously optimizing neural network robustness and compactness. arXiv preprint 1905 2019.
12

---

[34] Divyam Madaan, Jinwoo Shin, and Sung Ju Hwang. Adversarial neural pruning with latent vulnerability suppression. In International Conference on Machine Learning, pages 6575-6585. PMLR, 2020.
[35] Yonggan Fu, Qixuan Yu, Meng Li, Vikas Chandra, and Yingyan Lin. Double-win quant: Ag- gressively winning robustness of quantized deep neural networks via random precision training and inference. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3492-3504. PMLR, 18-24 Jul 2021.
[36] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint arXiv: 1810.05500 2018.
[37] Jonathan Frankle, David Schwab, and Ari S Morcos. The early phase of neural network training. arXiv preprint arXiv:2002.10365. 2020.
[38] Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint 1rXiv:1906.10733 2019.
[39] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Towards more efficient training of deep networks. arXiv preprint /9Xiv:/909. 1957, 2019.
[40] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint arXiv:2003. 02389, 2020.
[41] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference Machine Learning, pages 3259-3269. PMLR, 2020.
[42] Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsifi- cation. arXiv preprint 1XXiv:9912.044277 2019.
[43] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07337, 2020.
[44] Sai Prasanna, Anna Rogers, and Anna Rumshisky. When bert plays the lottery, all tickets are winning, arXiv preprint arXiv:2005.00561, 2020.
[45] Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nip. arXiv preprint 1906.01900.22 2019.
[46] Xiaohan Chen, Yu Cheng, Shuohang Wang. Zhe Gan, Zhangyang Wang, and Jingjing Liu. Earlybert: Efficient bert training via early-bird lottery tickets. arXiv preprint 101 100063,, 2020.
[47] Haoran You, Zhihan Lu, Zijian Zhou, and Yingyan Lin. GEBT: drawing carly-bird tickets in graph convolutional network training. CoRR, 100.0103,, 2021.
[48] Sharath Girish, Shishira R Maiya, Kamal Gupta. Hao Chen, Larry Davis, and Abhinav Shrivas- tava. The lottery ticket hypothesis for object recognition. arXiv preprint arXiv:2012.044m 2020.
[49] Tianlong Chen, Yu Cheng, Zhe Gan, Jinging I Liu, and Zhangyang Wang. Ulrra-data-efficient. gan training: Drawing lottery ticket first, then training toughly. arXiv preprint arX1v:2103.00397. 2021.
[50] Neha Mukund Kalibhat, Yogesh Balaji, and Soheil Feizi Winning lottery tickets in deep generative models. arXiv preprint arXiv:2010.023500 2020.
[51] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 11893-11902, 2020.
13

---

[52] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning. pages 6682-6691. PMLR, 2020.
[53] James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning a randomly weighted network. arXiv preprint arX1v:2103.0937,, 2021.
[54] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprini arXiv:1308.55 1308.3432, 2013.
[55] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[56] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
[57] Kaiming He. Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[58] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[59] Bai Li, Shiqi Wang, Yunhan Jia, Yantao Lu, Zhenyu Zhong, Lawrence Carin, and Suman Jana. Towards practical lottery ticket hypothesis for adversarial training. arXiv preprint arXiv:2003.05733 2020.
[60] Yushi Qiu and Reiji Suda. Traeneby-reoonnect:: Decoupling locations of weights from their values. arXiv preprint wrXiv:2003.02570, 2020.
[61] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint 11.00415/0.00/49 2015.
[62] Ji Lin, Chuang Gan, and Song Han. Defensive quantization: When efficiency meets robustness. arXiv preprint arXiv: 15t4:1904.0060 08444, 2019.
[63] Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks
to adversarial example defenses. arXiv preprint 20Xiv:2002.08347, 2020.
14


Reviews:
[{"review_id": "aDywbJLjd4X", "reviewer": "Reviewer_pV21", "summary": "This paper discovers the existence of robust subnetworks coined as Robust Search Tickets (RSTs) within randomly initialized networks that attain comparable or better performance than the adversarial trained networks. The paper conducts extensive experiments to study the existence of RSTs under different models, datasets and sparsity patterns. Additionally, the paper identifies the poor transferability between RSTs of varying sparsity ratios. To tackle this problem, it proposes a novel method called Random RST Switch (R2S) that randomly switches between different RSTs.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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\n* As network pruning is getting adopted in resource-constrained applications, the lottery ticket hypothesis is one approach that has been found effective in over-parameterized deep neural networks. Thus, the paper is well-motivated and showcases an interesting phenomenon of robust search tickets within randomly initialized networks.\n* The results are intriguing, especially the comparison between RST and Robust Trained Tickets (RTTs) and the investigation of adversarial transferability between RSTs are interesting.\n* The paper is clearly written, easy to follow and provides interesting insights into robust tickets.\n\n***\n\n## Weaknesses\n* **Significance and novelty:** One of my primary concerns is the novelty of the work. Ye et al. [1] discuss the lottery ticket hypothesis in the adversarial setting (see Section 4.2). Cosentino and Zaiter et al. [2] analyzed Lottery Ticket Hypothesis with adversarial training. Li and Wang et al. [3] also demonstrate the winning tickets and boosting tickets exist for adversarial training. The paper should compare and highlight the differences with these works.\n* **Comparison with existing works:** \n     * The paper highlights existing works that utilize pruning for adversarial robustness but do not provide an empirical comparison with those methods, which makes it challenging to evaluate the efficacy of the proposed method for robustness. I would suggest having the experimental comparison with Ye et al. [1], Madaan et al. [4] and Sehwag et al.[5] to confirm the fact that the proposed method works better than the existing techniques for robustness using pruning. \n    * Additionally, while the proposed method shows slight improvement, Madry et al. is the strongest considered baseline. I would recommend including more robust baselines following RobustBench [6] to highlight the effectiveness of the proposed method over the dense baselines.\n* **Limited comparison:** The comparison with dense networks is unfair for Imagenet, in my opinion. For instance, in Table 1, the paper compares ResNet-50/ResNet-110 for RST while using ResNet-18 for the Dense Network. Instead, for a fair comparison, the paper should use the same base network. Furthermore, the paper should have used AutoAttack for all the evaluation results instead of using PGD-20, which is a significantly weaker attack in comparison.\n\n***\n\n## Other Questions and Comments\n* RST on Auto Attack does not show improvement over the dense network in Table 1 in the Appendix. Comment.\n* It is well known that adversarially trained models overfit to single $\\ell_p$ norm. Since RST does not use adversarial training, can it generalize to multiple $\\ell_p$ norms and attacks? I believe including these results can further strengthen the paper.\n* In Figure 7, please include the transferability from a dense standard, dense adversarial trained model to RST and dense to dense for comparison.\n* The proposed acronym RST also conflicts with Robust Self-Training [7] in the robustness literature. The acronym should be altered to avoid confusion in future work.\n* The code and the pre-trained models are not provided with the paper or supplementary material. I would encourage the authors to release the code to promote reproducibility and successful comparison for future works.\n* I would also suggest the authors report the variance for the Tabular results; it is also good practice for the community.\n\n***\n## References\n\n[1] Zhang et al. Prune DNN using Alternating Direction Method of Multipliers (ADMM). ECCV 2020\n\n[2] Cosentino and Zaiter et al. The Search for Sparse, Robust Neural Networks.\n\n[3] Li and Wang et al. Towards Practical Lottery Ticket Hypothesis for Adversarial Training.\n\n[4] Madaan et al. Adversarial Neural Pruning with Latent Vulnerability Suppression. ICML 2020\n\n[5] Sehwag et al. HYDRA: Pruning Adversarially Robust Neural Networks. NeurIPS 2020\n\n[6] Croce, Andriushchenko, Sehwag and Debenedetti et al. RobustBench: a standardized adversarial robustness benchmark.\n\n[7] Carmon et al. Unlabeled Data Improves Adversarial Robustness. NeurIPS 2019", "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": "10"}, "extra_text": {}}, {"review_id": "SgpNkZyjs-t", "reviewer": "Reviewer_SpL6", "summary": "The paper describes the existence of highly robust subnetworks within neural networks with random weights. Further, the paper proposes a simple way to search for these subnetworks, characterizes their properties w.r.t. initialization, model size, attacks, models, search method, and the sparsity structure, and, finally, proposes a technique for ensembling these subnetworks into a more robust model. The experimental framework appears to be sound, and the results are impressive, showing the consistent existence (and high performance) of these subnetworks across several factors.", "questions": "", "limitations": "", "rating": 7, "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:\n- The paper’s main subject of study is interesting for a large portion of the DL community (and specially for the robustness community), and its main observation can spur further works that exploit the phenomenon of RSTs.\n\n- The paper’s observation is strongly related to “What's Hidden in a Randomly Weighted Neural Network?”, Ramanujan et al., CVPR 2020 (reference [53] in the paper), and, in my opinion, is a clear contribution upon [53]’s observation: the phenomenon described in [53] also applies for robust networks by incorporating a robustness notion in the searching objective.\n\n- The experimental framework appears to be sound, spanning a sensible amount of factors around the phenomenon being observed, which suggests the results are reliable. The results themselves are significant: the robustness of RSTs is comparable with that of adversarially trained networks. \n\n- Overall, the paper is well written, clear, and concise. The ideas and sections are well organized, and the results are presented in a convenient manner for the reader.\n\n—> Weaknesses that affect my rating:\n- My main concern is regarding the evaluation setup presented in L335 (it is still unclear to me). I understand the motivation behind “ensembling” several models from the same network, but I think this may lead to gradient obfuscation, which should then be studied on its own. To study whether the gains in robustness come from a phenomenon beyond gradient obfuscation, then probably the attacker would have to have access to the “expected” gradient, right? So that gradients are more informative and the adversary can be properly constructed. The first thing that comes to mind is literally the mathematical definition of the gradient under expectation, but perhaps the authors could think of a more reasonable approach that would fit the definition of “adaptive” attack.\n\n- The paper proposes a search strategy for the weights to be pruned (Sec. 3.2). The proposed strategy is sensible (based upon previous works) and the results back the choice for this strategy. However, I think it would also be interesting to study how alternative strategies compare against this one. Have the authors considered alternatives?\n\n- While it is interesting that RSTs exist under all the initializations that were considered (Sec. 4.4), I think a similarly interesting question is what initializations would not allow RSTs to exist. That is, if we initialized with, let’s say, purely normal distribution, would that impede RSTs from existing? I do not mention this experiment as a drawback in the paper, but as a phenomenon that would be worthy of study based on the paper’s findings.\n\n- Section 6.1 reports that the diagonal of the matrix in Fig. 7 corresponds to the lowest values observed. My understanding is that given a single randomly initialized NN one can find *various* RSTs with a given weight remaining ratio. While the figure reports that attacks transfer poorly across NNs of *different* remaining ratios, I wonder how is the transferability across NNs of the same remaining ratio (not the same network topology perhaps, but the same ratio). \n\n\n\n—> Weaknesses that do not affect my rating but should be corrected/answered within reason:\n- L68: random (or randomized?)\n- L70: example\n- L116: it is a bit weird to make reference to an equation that has not been introduced yet (or is not introduced immediately after).\n- In Eq. (1), should not the “m” below the argmin have a hat?\n- In L120 and L121, “permutation” or “perturbation”?\n- In Eqn. (2), in practice, is there also a clipping for usual image pixel values, i.e. [0,1]?\n- L137: sparse or sparsity?\n- L145: ImageNet\n- L161: decent\n- Table 1 suggests a possible relation between depth (rather than parameter count) and the robustness of RSTs. Have the authors observed some phenomenon in this direction? I think there may be an interesting observation regarding depth to be made here.\n- L182: “achieves” makes reference to RSTs? If so, it should be singular\n- Sec. 4.6: another interesting “adversarial search method” would be simple Gaussian noise or uniform noise. It would be interesting to find whether any of these noises could be used as a reliable way of searching for RSTs.\n- In Fig. 2(b) there is a regime of the “Remaining Ratio” dimension for which the fine tuning from inherited weights generates a drop in robust accuracy with respect to the original RST, i.e. the green curve is below the red curve. Is there an explanation for this phenomenon? Is this an implementation error?\n- In Sec. 5.1 I assume fine tuning means “adversarial” fine tuning, and so perhaps this clarification could be useful for the reader.\n- L237: achieves\n- In L261, does this setup mean that the images are all added noise coming from a uniform distribution from [-eps,+eps]? Or {-eps,+eps}?\n- Section 5.2, L271, studies the role of overparameterization. The conclusion, as reported in L280, is that overparameterization during adversarial training is necessary towards decent robustness of RSTs. I think I understand what the paper means, but is it not semantically incorrect to say that “training is necessary towards the robustness of Robust *Scratch* Tickets”? They are either trained or from scratch, but cannot be both, right? Or is there something I am missing?\n- L275: I think there is a missing noun there, probably “accuracy”? Or “robustness” instead of “robust”?\n- I think Sec 5.4 could be written in a more convenient manner: the whole section is currently a single sentence.\n- L293: in the Appendix.\n- L296: an.\n- Fig. 7 legend: “accurracies”.\n- L346: unwanted space.\n- The experimental setup described in L358 is a bit unclear to me. My current understanding is: the networks is adversarial trained on CIFAR10, the last fully connected layer is randomly re-initialized, and then a search for robust networks is performed on this network. Is this correct? If so, I think the wording could improve as to better convey this setup.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "5y64exsjrs", "reviewer": "Reviewer_5CcE", "summary": "This paper studies the inherent adversarial robustness of subnetowrks inside a full network. It names such subnetworks as Robust Scratch Tickets (RSTs). RSTs have good properties, as they possess robustness even without adversarial training. The paper further studies the existence and properties of RSTs under various aspects. The overall findings are interesting and motivating regarding the architectural robustness.", "questions": "", "limitations": "", "rating": 7, "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:\n+ The analysis of robust subnetworks without training is intriguing and underexplored\n+ The proposed method for finding RSTs is well-motivated\n+ The experiments are thorough and cover many aspects that are related to robustness\n+ The writing is clear and easy to follow\n\nWeaknesses:\n- Although the experiments thoroughly evaluated the properties of RSTs, it still remains unclear what makes RSTs robust. For example, what architecture patterns do RSTs exhibit? Is there a pattern that correlates well with network robustness? The answers could further shed light on how to design robust networks from scratch.\n- Following the topic on robustness of model architecture, the authors might want to discuss the relationship to recent works on searching robust models with neural architecture search [1, 2]. Especially as indicated in [2], the designed model has much less number of parameters compared to ResNet / MobileNet-V2, but exhibits higher robustness. It would be interesting to also extend experiments to analyze the connections/pattern similarities of RSTs and adversarially searched robust architectures.\n\nReference:\n[1] Intriguing Properties of Adversarial Examples. 2017.\n[2] When NAS Meets Robustness: In Search of Robust Architectures against Adversarial Attacks. CVPR 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates whether subnetworks with high adversarial robustness can be found by learning a mask over the weights in a randomly initialized large network. Using this approach, the authors demonstrate that robust scratch tickets (RSTs) can be found for a number of datasets and show that multiple RSTs can be ensembled to further increase robustness. All reviewers found the work to be interesting, original, and of high quality, especially after a robust discussion with the authors, and I think this paper will be useful for the broader community. I would strongly encourage the authors to include all the experiments performed for the rebuttal in the final paper. I recommend acceptance. 
Decision: Accept (Poster)