Can Pruning Improve Certified Robustness of Neural Networks?
Authors: Zhangheng LI
Tianlong Chen
Linyi Li
Bo Li
Zhangyang Wang
Venue: Accepted by TMLR ()

Abstract: With the rapid development of deep learning, the sizes of deep neural networks are getting larger beyond the affordability of hardware platforms. Given the fact that neural networks are often over-parameterized, one effective way to reduce such computational overhead is neural network pruning, by removing redundant parameters from trained neural networks. It has been recently observed that pruning can not only reduce computational overhead but also can improve empirical robustness of deep neural networks (NNs), potentially owing to removing spurious correlations while preserving the predictive accuracies. This paper for the first time demonstrates that pruning can generally improve $L_\infty$ certified robustness for ReLU-based NNs under the \textit{complete verification} setting. Using the popular Branch-and-Bound (BaB) framework, we find that pruning can enhance the estimated bound tightness of certified robustness verification, by alleviating linear relaxation and sub-domain split problems. We empirically verify our findings with off-the-shelf pruning methods and further present a new stability-based pruning method tailored for reducing neuron instability, that outperforms existing pruning methods in enhancing certified robustness. Our experiments show that by appropriately pruning an NN, its certified accuracy can be boosted up to \textbf{8.2\%} under standard training, and up to \textbf{24.5\%} under adversarial training on the CIFAR10 dataset. We additionally observe the possible existence of {\it certified lottery tickets} in our experiments that can match both standard and certified robust accuracies of the original dense models across different datasets. Our findings offer a new angle to study the intriguing interaction between sparsity and robustness, i.e. interpreting the interaction of sparsity and certified robustness via neuron stability. Codes will be fully released.

Published in Transactions on Machine Learning Research (03/2023)
Can Pruning Improve Certified Robustness of Neural Networks?
Zhangheng Li, Tianlong Chen Deportment of Electrical and Computer Engineering University of Tezas at Austin
zoharli, tienlong.chen@uueren
Linyi Li, Bo Li Department of Computer Science University of Blinois Urbana- Champaign
linyi2, lbotiilinois. edu
Zhangyang Wang
Sallswoon@@uezaus edu
Department of Electricol and Computer Engineering University of Teras at Austin
Reviewed on OpenReview: /ttps://openreveeee net/ forum? 6IF42sodul
Abstract
With the rapid development of deep learning, the sizes of deep neural networks are getting larger beyond the affordability of hardware platforms. Given the fact that neural networks are often weer-paameteeriee.. one effective way to reduce such computational overhead neural network pruning, by removing redundant parameters from trained neural networks. has been recently observed that pruning can not only reduce computational overhead but also can improve empirical robustness of deep neural networks (NNs), potentially owing to removing spurious correlations while preserving the predictive accuracies. This paper for the first time demonstrates that pruning can generally improve L.- certified robustness for ReLU-based NNs under the complete verification setting. Using the popular Branch-and-Boumd (BaB) framework, we find that pruning can enhance the estimated bound tightness certified robustness verification, by alleviating linear relaxation and sub-domain split problems. We empirically verify our findings with off-the-shelf pruning methods and further present a new stability-based pruning method tailored for reducing neuron instability, that outperforms existing pruning methods in enhancing certified robustness. Our experiments show that by appropriately pruning an NN, its certified accuracy can be boosted up to 8.2% under standard training, and up to 24.5% under adversarial training on the CIFAR10 dataset. We additionally observe the possible existence certified lottery tickets in our experiments that can match both standard and certified robust accuracies of the original dense models across different datasets. Our findings offer new angle study the intriguing interaction between sparsity and robustness, Lee. interpreting the interaction of sparsity and certified nesustness via neuron stability. Codes will be fully released.
1 Introduction
Neural Network based framework is strong general solution to many problems, yet many of these solutions remain impractical for real-world applications of low fault tolerance. A slight perturbation in the raw input sensory data could completely change the predicting behaviors of the networks. Furthermore, researchers have shown that various kinds of targeted adversarial attacks can easily fool the neural networks Szogedy et al.] (2013); Goodfellow al.) (2014), which poses threat to many deep lcarning applications. Fortunately, researchers introduced formal methods to verify neural network behaviors, which made it possible to mathematically derive the prediction bound of neural network w.r.t. certain input, and thus evaluate

---

Published in Transactions on Machine Learning Research (03/2023)
the certified robustness of the neural network. For example, in the image classification task, given an imput image with some perturbation, if the lower bound of the output probability of the correct label is higher than the upper bound of probabilities of other incorrect labels, we say the model is certifiably robust w.r.t. this image sample. The goal of the ncural network verification is to estimate the bounds as accurate as possible.
In this paper, we are concerned about the certified robustness w.r.t. Lse input perturbations under the complete verification setting, where the verifier should output the exact bounds given the input domain C, rather than some relaxation of C, given sufficient time. Despite its theoretical appeal, the complete verification of neural networks is known to be challenging NP-hard problem Katz et al. (2017) | Weng et al (2018), mainly due to the non-lincar activation functions in neural networks, such as Sigmoid and ReLU. The popular Branch-and- and-BBund (BaB) framework Bunel et al. (2017) utilized the feature of ReLU activations and adopted the classical the bound computation into multiple sub-domains recursively on ReLU nodes and computes the bounds on each sub-domain respectively. The time complexity of this framework is exponential, and typically has pre-set time limit for each sample verification.
method to solve the complete verification problem. It branches
Several verifiers Xu et al. (020b); Wang et al. 2021 based on the BaB framework were later proposed for efficient complete verification. The core problem addressed in these methods is how to estimate the pre-activation bound (i.e. propagated input bounds of the non-linear activation layers) as tight as possible given limited time. To approach this, they use relax non-linear bound propagation with linear ones and use GPU-accelerated BaB methods to further tighten the estimated bounds as much as possible. However, the estimated bound is still loose, mainly because (1) an efficient linear relaxation of multiple non-linear activation layers is loose both empirically [Salman et al. (2019) and theoretically Katz et al. (2017), Weng et al. (2018) , where tightening the relaxation requires exponential number of linear constraints which is inefficient Tjaadraatmadjaa et al. (2020); and (2) the BaB framework requires solving an exceedingly large number of sub-domains (which is exponential in the worst case Katz ct al. (017])) to provide a tight bound, so in practice we often solve only a part of the sub-domains
based Perturbation Analysis (LiRPA) to
which yields a loose bound.
Recent efforts Fu et al. (2021); ; Gui et al. (0119); Hu et al. (2020); Ye et al. [2019; ; Jordao & Pedrini (021)
Xiao et al. (2018) reveal that proper network pruning can empirically enhance neural network robustness to adversarial attacks. We take one step further to argue that pruming can also be utilized to improve the estimated bound tightness of certified robustness verification, by alleviating linear relaxation and sub-domain split problems. Improving empirical robustness (as a surrogate of "ground-truth' robustness) and verification tightness can together lead to overall measurable certified robustness, and we find that existing pruning schemes can already co-achieve both. Moreover, inspired by the fact that sparsity can eliminate unstable neurons and improve non-linear neuron stability for verification Xiao et al. (2018), we present a new stability- based pruning method, that even outperforms existing pruning methods on improving certified robustness. Our main contributions are outlined below:
For the first time, we demonstrate that pruming can generally improve certified robustness w.r.t. Loo input perturbations, We analyze pruning effects from the perspectives of both improving ground- truth robustness of the model and the verification bound tightness, and empirically validate it with extensive pruning mothods and training schemes.
As pruning can be utilized to improve non-linear neuron stability, we propose novel regularizer for pruming called NRSLoss (see Figure that effectively regularizes the neuron stability and outperforms existing pruning methods in enhancing certified robustness.
Our experiments validate the above proposals by presenting verification results under various settings. For example on the CIFAR10 dataset, under certified training, existing pruning mothods as well as our proposed NRSLoss-based pruning boost the certified accuracy for 1.6-7.1% and 8.2% respectively; under adversarial training, they boost the certified accuracy for 12.5-24.5%
2

---

Published in Transactions on Machine Learning Research (03/2023)
2 Related Work
2.1 Incomplete and complete NN verification
Neural Network verification is critical issue for developing trustworthy and safe AI. Existing verifiers be divided into either incomplete or complete verifiers. Complete verifiers can typically produce tighter bound than incomplete verifiers, but consume much larger computational resources than incomplete verifiers. Typical incomplete verifiers are based on duality [Dvijohham et al. (2018); Raghunathan et al. (2018) and linear approximations Weng et al. (2018); Wong & Kolter (2018); Zhang et al. (2018a), whereas existing complete verifiers are based on iiriisfiailiityy modulo theories (SMT) Katz et al. (2017): Ehlers (2017), mixod integer
programming (MTP) Tjeng el. al. (2017), convex hull approximation Müller et al. [2021] Branch-and-
(BaB) Bunel et al. 2017]: Xu et al. (202bb); Wang et al. (2021).
Traditional complete verifiers such as SMT and MIP are computationally expensive and hard to parallelize, To this end, a series of verifiers based on the BaB framework were recently proposed for efficient and parallelizable complete verification. Auto-LiPRA Xu et al. (2020a) was an early incomplete verifier and certified trainer, that relaxes ReLU non-linearity with a tight linear relaxation. Following that, Fast-and-Completee algorithm Xu et al. (2020b) proposed combine auto-LiRPA with BaB for tighter bound estimation and use LP solver for completeness check, which is GPU-parallelizable complete verification method. Beta-CROWN [Wang] et al. (2021) further extended Fast-and-Compler algorithm by replacing the LP completeness check with optimizable constraints based on the Lagrange function, and improved the verification elficiency.
2.2 Neural network pruning
Pruning removes the redundant structures in NNs and reduces the size of parameter numbers from the compulation graph of NNs. It not only constitutes important class of NN model compression methods but also can act as regularizer for NN training which can improve the performance w.r.t. original unpruned networks. The pruming process can be conducted at different levels or gramularitios, such as paramoter-lews
Frankle Carbin (2018; Zhang el al. (2018b); Ma el al. (2020), filter-level Luo al. (2018) : Li el al. 2016];;
Roy al.] (2020) and layer-wise Wang et ( 2018); Wu et al. (2018); Zhang al. (2019). Especially, Lottery Ticket Hypothesis (LTH) Frankle & Carbin (2018) claims the existence of independently trainable sparse
subnetworks that can match even surpass the performance of dense networks. Such sparse subnetworks
called "winning tickets", can be obtained by simple iterative parameter-level pruning.
2.3 Pruning and robustness
Recently, several works Ye et al. 2019 Gui et al. (2019); Jordao & Pedrini 2021 have revealed that proper network pruning can empirically improve the robustness of a trained NN, polentially due to removing spurious correlations while preserving the predictive accuracies. Fu et al. (0021) found that randomly initialized robust subnetworks with better adversarial accuracy than dense model counterparts can be found by IMP. Xiao et al. (2018) was the first work to inject sparsity during NN training, with the primary goal to speed up certified verification. It considered only weight magnitude pruning, and did not generally demonstrate sparsity improve the achievable Loo certified robustness. HYDRA Sehwag al. (2020) incorporated the robustness loss as pruning objective, and showed such robustness- aware pruning scheme can lead to high NN sparsity without much robust accuracy loss. Besides studying incomplete certified verification, HYDRA did not specifically analyze what benefits pruning brings for verification, whilc our NRSLoss-basee pruning is explicitly motivated by reducing unstable neurons and lightening the est istimeeed bound in the complete verification. Han et al. (2021) proposed that superficial neurons that contribute significantly to the feature map values in shallow layers were highly localized and are more prone to adversarial patches. Hence they used pruning to remove superficial neurons and improved certified defense against adversarial patches an hogongln goal to our work.
3

---

Published in Transactions on Machine Learning Research (03/2023)
3 Methodology
In this paper, following prior works on certified robustness, focus on non-linear feed-forward neural networks with ReLU activations. In this section, we first analyze what benefits would network pruning brings to certified robustness and verification, and then introduce the specific pruning methods we test in our experiments.
3.1 Preliminary
3.1.1
Unstructured and Neuron Pruning
Network pruning is one of the most effective model compression paradigms for deep neural network, by removing redundant parameters or neurons from wer-parametterzed neural networks, and many of them focus on pruning learnable weight parameters. Existing weight pruning methods can be divided to unstructured pruning and neuron pruning, depending unstructured pruning, individual weights that connect two channels (neurons) of adjacent layers are removed; for neuron pruning, all input and output weights associated with certain channels are removed.
whether weights are pruned individually or by group. For
Each of these two pruning paradigms has its advantages and disadvantages over the other. Unstructured pruning can belter preserve the performance of the original dense networks due to pruning flexibility on individual weights, but is hard realize real hardware acceleration during inference. In contrast, the hardware compression during inference for neuron pruning can be easily implemented due to the removal of entire channels, but has less pruming flexibility compared to unstructured pruning, which would generally lead to worse performance that unstructured pruning. In this paper, we investigate the influence of both unstructured and neuron pruming on certified robustness and are interested in both the performance gain and the reduction of computational overhead brought by pruning.
3.1.2 Lottery Ticket (LPH)))
The lottery ticket hypothesis Frankle & Carbin (2018) states that a randomly initialized dense neural network contains at least one subnetwork (i.e. by pruning the parameters of the dense network) that has the same initialization of the unpruned parameters and can match the test performance of the dense work after training for at most the same iterations as the dense network, and such subnetworks are called the winning tickets of the dense network. To find these winning tickets, they propose Iterative Magnitude (IMP) algorithm: Firstly, start from a dense initialization Wo, and then train the network until convergence to weight W,. Then we determine the P percent smallest magnitude weights [W]] and create a binary mask mo that prunes these. Then retrain the pruned network from the same initialization weight Wo O my to convergence. Iterating this procedure will produce subnetworks with different sparsity, among which certain subnetworks can match the test performance of the original dense network, i.e. the winning tickets.
3.1.3 ReLU Neuron Stability
The illustration of ReLU neuron stability demonstrated in Figure 1 The ReLU activation function zero when input value less than 0, and an identity function when input value is no less than 0. As shown in the Figure
( h means the pre-activation value of jth ReLU neuron at ith layer of the network. g) means the corresponding value after passing the ReLU neuron. 1. and uf) refers to the lower bound and upper bound of the pre-activation ug w.r.t. certain input perturbation. Figure aa) and Figure d) are unstable neurons
where (0) and u, has different signs, while Figure (b) and Figure c) are stable nenrons where 10 and uf
has the same sign. The yellow areas in Figure M and Figure aa refer to the bounded area of "triangle'
relaxation and linear relaxation, respectively. As shown in Figure (a,, the lower and upper bounds of (1)
will be the intersection of the orange line and the bound of the yellow triangle, and the horizontal location
of the orange line will vary from 16)) to u the input varies within the given perturbation scale. The
(6)
drawback of the triangle relaxation during bound propagation is that the lower bound of g is not linear.
4

---

Published in Transactions on Machine Learning Research (03/2023)
(8)
9
9j
9j
9j
h
h
(
h 0
19
(1)
(
0
10
(a)
(b)
(c)
dd)
Figure 1: (Figure source from Xu et al. (202bb)) mulustration of the stability of ReLU neuron and linear
relaxation, For certain network imput with batturaations, (b) and (c) demonstrate stable neurons since their lower and upper pre-activation bounds are on the same side the Y axis, while (a) and (d) demonstrate unstable neurons since the two bounds are on the different sides of the axis. (a) and (d) also show different
relaxation methods: (a) is "triangle" relaxation and (d) is the LiRPA-based linear relaxation Xu et al. 2020aa).
LiRPA-based linear relaxation (d)) addresses this issue by replacing the non-linear lower bound with an dynamic linear lower bound which line passing through the origin with an optimizable slope between [0,1]. For more details about neuron stability and bound relaxation, please refer to Xu et al. (2020b).
3.2
What factors influence Los certified robustness?
Up to now, with state-of-the-art robust training method and certified verifier, the measurable bound of trained non-linear neural network is influenced by two major factors:
3.2.1 The ground-truth bound of the network
This is mainly decided by the training method. For example, certified training usually provides much higher certified robustness than adversarial training, which demonstrated our experiments. this paper, we ideally hope pruning has positive or no influences on the normal training process, e.g. the influences of pruning-related regularizer normal gradient back-propagation. Besides, the model size, i.c. the parameter number also matters, which is important in this paper since we can use pruning to reduce parameter number. Intuitively, with more parameter numbers, the bound of the network output tends to be looser. With network pruning, we can heuristically tighten the bound of the network since the network has fewer parameters.
3.2.2 Estimated bound tightness of the verifier
This refers to the closeness of the estimated bound of the verification to the ground truth bound of the network, and it reflects the performance of the verifier. Since existing certified verifiers usually have very large computational overhead to verify even a single sample, in practice, we are concerned about the bound tightness a verifier can reach given a limited verification time.
Although efficient certifiod verification for non-linear neural networks has made rapid progress in recent years, the bound tightness, running speed and affordable network capacity limited hardware resources still have huge space awaiting to be improved. Specifically, we identify two major problems that influence the bound tightness:
Neuron Stability and Verification Speed. As mentioned in the introduction, BaB is the main- stream framework existing certified verification methods. The bound tightness is largely influenced by how many unstable ncurons have been branched given a limited time. (Please refer to Scction 3.1.3 for the explanation of neuron stability). The verifier would need to visit more sub-domains by branching on unstable neurons within limited time, and thus the verification speed matters.
Linear Relaxation. To facilitate bound computation, many recent verifiers Wang et al. 2002 Xu ct al. (2020b): Wong Kolter (2018): Zhang al. (2018a); Singh et al. (2019). utilize the linear relaxation method for unstable ReLU neurons, we illustrated in Section 3.1.3. Normally, if an
5

---

Published in Transactions on Machine Learning Research (03/2023)
unstable neuron has not been branched by BaB, then this neuron gets linearly relaxed during bound propagation, which will also loosen the bound tightness of the verifier.
3.3 What benefits for certified robustness Network pruming can bring many benefits to problems mentioned in Section 3.2 outlined as follows:
expect from pruning?
Reducing parameter number. It tighten bound propagation directly. Both and unstructured pruning reduce parameter number and the bound propagation becomes tighter after pruning. Take the widely used bound propagation method for linear layers(e.g. convolution and full-connected example, its computation can be formulated as follows:
Interval Bound Propagation (IBP) for computing Loe bounds as an
ži-1 + 21-1
P4-1
ž 2i-1
7/-1 =
44 = W +
(1)
W|ri-1
2, = 14 - Ti
&, = μ4 + T2
Eq. computes the linear bound propagation for ith linear layer of the network, where 2,11 and - are the imput lower and upper bounds of ith lincar layer, and 2 and 2, the corresponding output lower and upper bounds, respectively. W and b denote the weight and bias of the linear layer. The difference between output upper and lower bound equals 2 W/rr-- By network pruning, the weight matrix W becomes sparser, and thus the difference between output upper and lower bound tends to become smaller, and thus the overall output bound the network would be tightened.
Reducing unstable neurons. By reducing the number of unstable neurons, we can reduce the number of linear relaxations and sub- domain splits needed by the verification process, which can also directly tighten the bound and accelerate the verification process as well. However, for most existing pruning methods, reducing unstable neurons not an explicitly designated goal, but rather a possible side effect.
Real hardware acceleration with structural sparsity. If adopting neuron pruning, we can eliminate channels which will concretely reduce the network width on the hardware implementation level. This can accelerate verification and even make resource-intensive verification possible on larger models.
Those possible benefits are further entangled with each other. For empirical evaluation of these benefits, we simply follow the classical criteria: evaluate the certified accuracy, time and memory consumption, and network width/depth that can be verified after pruning.
3.4 Pruning methods
In this section, we test range of off-the-shelf pruning methods for improving certified robustness. For each pruning method, unless otherwise mentioned, we combine with iterative pruning with weight rewinding Frankle & Carbin 2018), find iterative pruning with weight rewinding generally enhances performance compared to finetunebassed pruning one-shot pruning in our experiments.
3.4.1 Existing pruning methods
In unstructured pruning, for simplicity, we only prune the weights of convolutional layers and ignore linear layers. We pick several representative methods including: 1) Random Pruning: pruning weights randomly,

---

Published in Transactions on Machine Learning Research (03/2023)
175
69
69
11
425
uppir bound
stabity
staboty
loweer bound
(a) RSLoss
(b) NRSLoss
(c) NRSLoss(?> = 0.5)
335
635
32
425
upenr bound
Upper bound
lower bound
lowor Bound
upper
lonee bound
(d) NRSLoss(7 = 1) (i.e. RSLoss)
(e) NRSLoss 2)
(f) NRSLoss(? = 1)
Figure 2: (b) The landscape of RSLoss and NRSLoss with varied stability and BN channel weight 7- Stability means the stability ReLU neuron, i.e. the pre-activation lower bound times upper bound. 7 is the corresponding channel weight of Batch-Normalization layer, whose magnitude denotes the importance of each channel. The NRSLoss is high when the neuron is unstable and the corresponding channel has low importance. (c)-(f) The sample landscape of NRSLoss with varied lower and upper pre-activation bounds given different fixed With the growth of y that implies channel importance, the NRSLoss gets increasingly suppressed.
which is used for sanity checks in our experiments. 2) Lottery ticket hypothesis (LTH), or denoted as IMP
Frankle Carbin (2018): pruning weights with the smallest magnitudes, the most standard pruning scheme.
3) SNIP Lee al. (2018): pruming weights with least loss sensitivity w.r.t. percentile magnitude change.
4) TaylorPruning (TP) Evci (2018): saliency-based pruning via first-order Taylor approximation. 5)
(2020): learnable mask-based pruning that minimizes the robustness loss empirically. The original HYDRA pruning uses adversarial loss to select the pruming mask, in certified training setting, we will adapt the adversarial loss to certified loss.
HYDRA Sehwag et al.
For neuron pruning, we choose two methods: 1) StructLTH Anonymous (022): a structured variant of LTH recently proposed, by using IMP first then ranking channels by their total magnitudes in remaining weights from high-to-low. Then we prune lowest-ranked channels and refill the IMP-pruned weights in the remaining channels. 2) Network Slimming Liu et al. (017:: for batch normalization (BN) Ioffe & Szegedy (2055) layers, we have:
F F(x)
* +
(2)
[ar +e
Network slimming enforces the L1-norm regularizer on and prune channels with the smallest y magnitudes.
3.4.2 Stability-baser Pruning
In the context of certified robustness, we wish to eliminate unstable neurons as much as possible, such that the estimated bound tightness of the verification can be improved. Pruning is a natural choice accomplish this goal. Next, we first introduce criterion that measures the degree of neuron stability of a given network, and
7

---

Published in Transactions on Machine Learning Research (03/2023)
then introduce effective stability-based regularizer and corresponding unstructured and neuron pruning methods.
Formally, we denote ( " as bound interval of the pre-activation value of j-th ReLU neuron at i-th layer. We want to measure not only the number of unstable ReLU neurons with bound intervals crossing the zero point but also to what extent the instability is. To address this problem, we propose to use -1,- y to measure the degree of instability of this neuron. It is easy to know that if we keep the bound interval width u 9 - 1 unchanged, then -1,0) u reaches maximum when 1 -u ( which means maximal instability given the same bound interval width. And thus, we simply use the average of this criterion to denote the total degree of instability of the network:
(x)
inslability = -E S
(3)
Similar to this criterion, Xiao al. 2018)) proposed regularizer named RS Loss to regularize ReLU stability and improved certified robustness. The RS Loss is defined as:
= tanh(1 (ly)
(4)
This loss can be naturally used to optimize the instability criterion, as the lank wrapper provides smooth gradients. However, we empirically find that for deep networks, batch-normalization (BN) Toffe & Szegedy (2015) layers, which are placed before ReLU layers, are necessary for the training convergence of pruned subnetworks. In this way, the performance of the RS Loss regularizer is insignificant, because it passes gradients to (i.e. the BN weight of channel j) and affects the training process, and the optimization space is relatively small due to the BN constraint. However, we find the pre-BN bounds (i.e. the input bounds of BN layers) to be very flexible. Thus, instead of regularizing the pre-activation bounds using RS Loss, propose alternative of Normalized RS Loss (NRSLoss) to directly regularize the pre-BN bounds, normalized from pre-activation bounds:
1==== = = --tanh(1 + 1 us
(.u)) 73
(5)
Since the magnitudes of I and uy are scaled from pre-BN bounds by the factor of f; NRSLoss essentially computes RS Loss on the pre-BN bounds 1//hg and u,/73- During training, the NRSLoss is combined with the original loss with an empirical coefficient. Note that we stop the gradients back-propagated from NRSLoss to 7/j, to ensure stable training, especially for pruned subnetworks. Since NRSLoss uses IBP to compute the ncuron bounds, has the same computational complexity as a forward pass of the neuron network. Therefore, it does not bring extra complexity to the training and pruning process. also has no influence for verification since NRSLoss regularizer will only be used during iterative training and pruning stage.
The loss landscape of NRSLoss is shown in Figure Note that the stability term is essentially - instability. From the loss landscape, we can interpret NRSLoss from another perspective: it penalizes neurons with high instability and low channel importance; when the instability increases, it takes larger channel importance to suppress NRSLoss.
We empirically find that combining NRSLoss as a training regularizer with pruning weights based on the least weight magnitude criterion is the most effective in most cases. We call this pruning scheme IMP+NRS: we first apply NRSLoss during training to regularize the network stability; then we apply magnitude- pruning to remove weights that are not important for both robustness loss and stability loss.
We stress the two-fold novelty of NRSLoss as follows:
takes into account both neuron importance and stability (sce Figure 2 In NRSLoss, the magnitude of BN channel weight Ty denotes the importance of each channel. The NRSLoss high when the neuron unstable and the corresponding channel has low importance. In contrast, the RSLoss is
8

---

Published in Transactions on Machine Learning Research (03/2023)
irrelevant to channel importance, which might lead to imposing too much regularization important neurons.
It also discntangles the influence of stability regularization with the BN layers, via climinating the magnitude scaling effect to the pre-activation bounds brought by the channel weight 7- In this way, BN layers can still be learned normally to control the gradients and thus it causes significantly less negative influences to the training performance.
In experiments, show in Figure that both RSLoss and NRSLoss can reduce network instability, however, since RSLoss only optimizes towards network stability while NRSLoss takes into account of both neuron importance and stability to avoid imposing too much regularization on important neurons, and causes less negative influences to the gradient flow of BN layers. Therefore, NRSLoss-based pruning can always achieve better performance than RSLoss- based pruning as we show in experiments.
4 Experiments
In this section, we evaluate all introduced pruning methods with different, training schemes and perturbation scales, and try to address three major questions: (1) Can cxisting pruning methods improve Loo certified robustness generally? (2) How cmn NRSLoss-bused pruning improve certified robustness? (3) Con we find the eristence of certified lottery tickets, i.e., sparse subnetworks after pruning that can restore not only the original performance but also certified robustness?
Based on our experiment findings, we also provide more ablation studies to further rationalize our claims. In light of whether pruning keeps effective for certified robustness at scale, we conduct experiments on the downscaled 64x64 Chagene(Crrabaszez Chrabaszez et al. (2017) with incomplete verifications, please refer to Appendix D for more details. Finally, we briefly summarize our experimental findings with several interesting takeaways.
4.1 Experiment Setup
Table 1:
The feedforward model architecture in our experiments. (on refers to the composition of (convolution layer, BN layer, ReLU layer) where the convolution layer has in input channels, out output channels, k & kernel size and strides. Note that for the FashionMNIST task which takes greyscale images instead of RGM images as input, we modify the input channel number of the first convolutional layer from 3 to 1, and modify the input units of the first FC layer from 2048 to 1152 accordingly. The parameter count of this model is 6. 6.
INPUT
CoNv
CoNvBLoCK(32,644,
CONvBLLOCK 161,6113.11
CONvBLOCK 128,4,2)
CONV 128,4,2)
F0(2048,100)
RELU FC(100,10)
OUTPUT
4.1.1 Dataset and Network architecture
Across our experiments, we choose classification datasots, FashionMNIST Xiao et al. (011 SVHN Netzer et al. (2011), and CIFAR10 Krizhevsky al. (2009) as the benchmark datasets. We introduce them follows:
9

---

Published in Transactions on Machine Learning Research (03/2023)
FashionMMNIST. FashionMNNSS is an MNIST-like greyscale image classification dataset by replacing hand-written digits with fashion items, which are more difficult to classify. Tt. has training set of 60,000 examples and a test set of 10,000 examples. Each example is a 28x28 grayscale image, associated with a label from 10 classes. We use the first 200 samples from the testing dataset for verification.
SVHN: SVHN is dataset consisting of Street View House Number images, with each image consisting of a single cropped digit labeled from 0 to 9. Each example is 32x32 RGB image. We use the first 200 samples from the testing dataset for verification.
CIFAR10: CIFARIO is a datasct consisting of object classos in the wild, and cach class has 6000 samples. This dataset is commonly used in prior works in complete verification, following Waang] (et al. 2021), we choose the ERAN test set [Singh et al. (2019) which consists of 1000 images from the CIFAR10 test set. Note that we only use the first 200 samples in the ERAN test set for verification efficiency.
Note that we don't use larger datasets such as CelebA Liu et al. (2015) and Imagenet, mainly because training on larger datasets typically require larger network size to achieve good performance. For our choosed datasets, we use 7-layer CNN as the benchmark model, whose architecture is shown in Table [ It follows the standard fora-forward CNN structure as in prior works on complete verification Xu et al. (2020b); Wang let al. [2021) : Shi et al. 2. This model has 6.7M parameters and is the largest. network that can be fitted in a GPU with 24GB memory for complete verification and can also achieve good baseline performance on our choson benchmarks. We empirically find that varying the network depth and width docsn't significantly change the relative performance of different pruning methods, therefore we only use this largest network across our experiments for considerations of both model scale and hardware resource constraint.
The design follows the cifar10-mooel-deg, setting in Wang et al. 2021 but is wider, deeper, and has BN layers.
4.1.2 Pruning methods
We try different setups of hyperparameters for unstructured and neuron pruning. For unstructured pruning methods, follow the default setting in Frankle & Carbin (2018) and set the iterative weight pruming rate to 0.2, and prune 16 times with re- re-training; for neuron pruning methods, we keep similar pruning speed.
We set the NRSLoss weight to 0.01 and set the L1-norm regularizer weight to 0.0001 following Liu et al. (2017). For RS Loss and NRS Loss-based unstructured pruning, we train with these losses and pruning with IMP, as Section introduced, denoted as IMP+RS and IMP+NRS. We also test training with NRSLoss and pruning with HYDRA, denoted as HYDRA+NRSLos,, to demonstrate the effectiveness of NRSLoss as a regularizer.
4.1.3 Training methods
To demonstrate the general effectiveness of network pruning, we choose SOTA adversarial and certified training methods:
Adversarial training: we choose the advancod FGSM+ FGSM+Grad GradAlign Andriushchenko Flammarion (2020) as the adversarial training method (we denote it as FGSM for conciseness hereinafter). The learning rate is set. to 0.01, and use Stochastic Gradient Descent with 0.9 momentum and 0.0005 weight decay as optimizer. All reeellig hyperparameters follow Andriushchenko & Flammarion (2020).
Certified training: we choose auto-LiRPA Xu et al. (2020a) under CROWN-IBP + Loss Fusion setting. The learning rate is set to 0,001, and we use Adam with a weight decay of for RSLoss and NRSLoss-based pruning and 0.00001 for other pruning methods. For the bound computation of NRSLoss and RSLoss, we use the bound produced by auto-LiRPA during certified training and use IBP during adversarial training.
Note that for HYDRA pruning, the semi-supervised training scheme which exploits extra unlaheled data in Sehwag al. 2020: is NOT used in our experiments, for a fair comparison.
10

---

Published in Transactions on Machine Learning Research (03/2023)
auto-LiRPA essentially uses IBP to compute bounds when input perturbation reaches maximum during training and uses IBP constantly during testing. As we find the results to be unstable for certified training, we use five different random seeds, 100, 200, 300, 400 and 500 to initialize the training process, and then average the results the same iterations. This is different from adversarial training where we only run one experiment.
We replace the standard IMP with weight rewinding Frankle & Carbin (0118) with each training method and each pruning method, and output the pruned subnetworks with different sparsity during iterative pruning and re-training, For each training method and each pruning method, we one of the SOTA certified verifier Beta-CROWN Wang et al. 20221) to obtain the final accuracy of the subnetworks. For more experimental details, please refer to Appendix
4.1.4 Verifier and Evaluation Criterion
For each training method and each pruming method, we use one of the SOTA complete verifier Beta Beta-CROWN Wang et al. (2021) to oblain the final accuracy of the subnetworks. Beta-CROWN is highly GPU-parallelized verification framework and has SOTA performance in terms of bound tightness and verification speed. We choose ERAN benchmark Bak et al. (2021) which contains 1000 test images, and test on the first 200 images to reduce the time budget, since note that there are difference average by comparing testing 1000 images and the first 200 images. We set the timeout of each test image to 300 seconds. We test the standard, adversarial, and verified accuracies, as well as time and GPU memory consumption of each model. We run the verifications using one NVIDIA RTX A6000 GPU card.
50
VERINED NCC. (5)
45
VERITCO ADC, (6)
40
VERFFEE ACC
40
40
15
20
15
PRUNE TIMES@O2
TRUNE_TIMESSEE
PRUNE TIMESBB.11
RYDRA
MY/RR V85L
RSLOS
STucLTH
Skm
IMP-REL
IM--NSSLOO
(b) auto-LiRPA neuron-wise
(a) auto-LiRPA unstructured
(c) FGSM unstructured
Figure 3: Verified Accuracy v.s. iterative pruming times (which can be converted to compression rate) on CIFAR1O dataset. (a) unstructured pruning under auto-LiRPA training, (b) is neuron pruning under auto-LiRPA training (Note that PRUNF_ TIMES@0.1 11 means iterative pruning epochs with 0.11 channel pruning rate), (c) is unstructured pruning under FGSM. We move neuron pruning under FGSM to Figure 10 in Appendix due to page limit. Note that for FGSM setting, we use CROWN verifier instead of Beta- Reta-CROWN due to long verification time on Beta-CROWN, We observe signifcant improvement of verified accuracy for FGSM training mainly because pruming under adversarial training siguificantly trades verified accuracy with benign accuracy compared to pruning under iertified training.
4.2 Experiment Results and Analysis
For the 3 benchmark datasets, the comprehensive experiment results under 2/255 shown in Table 2 and the sample curves of Verified Accuracy iterative pruning times with seed 100 shown in Figure 3 For cach model, we verify all subnetworks produced by iterative pruning and report the best-verified accuracy and other corresponding evaluation metries. We then choose several representative pruning methods that either have good performance or distinctive motivations or are important baselines, and evaluate them under different perturbation scales on the CIFAR10 datasct, as shown Table 3 We also conduct a experiment validate that reight-rewinding Frankle & Carbin (2018) is better than finetuning Sehwag et al. (2020) for improving certified robustness, as shown in Section B.2 The results of Random Pruning are omitted from
11

---

Published in Transactions on Machine Learning Research (03/2023)
Table 2: Comparisons subnetwork robustness and verification time for different training and pruning methods on FashionMNIST,, SVHN, and CIFAR10 datasets. std, adu, ver, refer to standard accuracy (%),, adversarial accuracy(%)), verified accuracy($) and time consumption (s/sample), respectively. Note that the remain ratio refers to remaining weights for unstructured pruning: and remaining channels for neuron pruming, respectively. Note that for HYDRA pruning, replace the adversarial loss in HYDRA with certified loss for Auto-LiRPA setting.
TRAINING METHOD
FGSM
AUTO-LIRPA
PRUNING
REMAIN
REMAIN RATIO
DATASET
METHOD
RATIO
std
adv
Ver
std
t
DENSE
85.2
81.2
1.5
298.3
77.2
68.8
7.23
IMP
0.03
80.2
75.3
39.0
85.9
0.07
78.1
73.5
7.17
SNIP
81.2
77.3
36.5
96.3
0.80
77.5
71.3
4.82
TP
0.03
80.3
76.
35.3
92.3
0.32
79.4
73.5
6.60
FASHION -NNIST
HYDRA
0.03
81.5
77.2
33.5
103.9
0.51
79.1
73.3
6.60
HYDRA+NRS
0.03
80.3
76.7
36.5
105.3
0.03
81.5
74.2
8.90
0.1
IMP+RS
0.03
79.3
72.2
37.0
94.1
0.41
80.5
72.5
6.21
4MS
74.9
41.5
0.05
6.06
STRUCTLTH
0.35
80.5
78.3
22.5
143.0
0.80
80.0
72.4
6.14
SLMM
0.35
80.7
78.3
31.0
105.0
0.32
78.5
71.8
2.96
DENSE
94.8
89.2
2.0
294.2
76.3
62.0
6.68
IMP
0.03
92.3
84.4
31.0
188.3
0.16
82.0
67.3
6.65
SNIP
92.4
84.3
29.1
204.4
0.32
82.5
66.5
5.93
TP
0.03
92.4
84.2
28.5
197.3
0.21
83.0
67.3
5.12
SVHN
HYDRA
0.03
91.2
82.7
41.5
146.3
0.64
79.5
66.3
8.75
2/255
HYDRA+NRS
0.03
89.8
81.1
40.5
144.2
0.35
82.0
66.0
4.02
IMP+RS
0.03
85.6
75.9
25.2
179.2
0.03
83.5
65.7
6.52
IMP+NRS
33.5
153.2
0.08
68.3
6.06
STRUCTLTH
0.27
87.7
78.0
33.0
159.1
0.55
82.2
65.9
3.71
SLIM
0.35
89.7
78.7
35.5
151.8
0.63
84.0
65.3
7.77
DENSE
82.4
68.6
1.5
278.9
54.1
43.0
6.68
IMP
0.03
62.2
55.4
23.5
135.3
0.13
61.0
50.1
6.65
SNIP
55.1
22.5
128.4
0.04
59.8
48.4
6.67
TP
0.03
59.7
55.4
24.0
132.4
0.05
59.9
47.6
6.02
CIFARIO 2/255
HYDRA
0.03
60.4
55.4
23.5
132.2
0.11
60.5
48.3
8.75
HYDRA
0.03
54.9
48.4
25.0
132.2
0.05
58.0
49.0
8.75
IMP+RS
0.03
60.2
54.2
23.5
134.4
0.13
58.6
46.3
6.52
IMP+NRS
0.03
25.0
131.2
0.21
62.2
51.2
6.06
STRUCTLTH
0.35
55.6
48.3
14.0
143.7
0.35
57.5
44.6
3.71
SLIM
0.35
56.9
49.6
26.0
72.9
0.79
59.2
47.5
5.65
Table 2 and 3 since its standard accuracies are very poor and non-competitive (some can be found in Figure for illustration purpose). We also provide additional results of 2 different architectures using the hyperparameter setting CIFARI0 as shown in Appendix B.3 which shows that the relative performance of different pruning methods is stable across these 2 tested architectures. We next present the result analysis.
4.2.1 Can existing pruning methods improve certified robustness?
From Table and Table 3 we observe general improvements in certified robustness brought by pruning, both under FGSM and auto-LiRPA settings. Specifically, Table shows that under the auto-LiRPA setting, existing
pruming methods can improve verified accuracies for 2.5 5.2% on FashionMNIST, 3.3 6.3% SVHN, 1.6 7.1% CIFAR1O, respectively and improve standard accuracies for 0.3 3.3% FashionMNIST,, 3.2 - 9.7% on SVHN, 3.4 - 8.1% on CIFAR10 respectively, among which IMP consistently outperforms other existing pruning methods, with highest improvements of both slandard and verified accuracies. This demonstrates that pruning can generally improve Los certified robustness. Moreover, under certified training, this improvement comes with no extra trado-off such as standard accuracy. We also observe that on more realistic datasets (SVHN, CIFAR10), the improvements under certified training are significantly bigger than that of the synthetic dataset (FashionMMISST).
12

---

Published in Transactions on Machine Learning Research (03/2023)
Table Verified accuracies of different pruning and robust training methods and perturbation scales under auto-LiRPA setting. Note that for HYDRA pruning, we replace the adversarial loss HYDRA with certified loss. We also provide the performance curves with varying compression rate when e=8/255 in Figure g Appendix. std, ver, t mcan standard accuracy, verified accuracy and verification time, respectively.
2/255
8/255
PRUNING TYPE
PRUNING METHON
REMAIN RATIO
REMAIN RATIO
std
DEr
std
DENSE
1
54.1
43.0
6.68
1
36.1
29.3
5.83
IMP
0.13
61.0
50.1
6.65
0.13
35.0
29.8
5.11
SNIP
0.04
59.8
48.4
6.67
0.21
34.0
29.5
6.73
TP
0.05
59.9
47.6
6.02
0.32
33.5
28.8
6.84
UNSTRU-
HYDRA
0.11
60.4
48.3
8.75
0.11
34.5
29.5
6.36
CTURED
HYDRA NRS
0.05
58.0
49.0
8.75
0.21
34.0
30.3
5.98
IMP+RS
0.13
58.6
46.3
6.52
0.64
35.0
28.0
4.39
IMP+
0.21
62.2
51.2
6.06
0.51
39.0
31.5
4.32
STRUCTLTH
0.55
57.5
44.6
3.71
0.63
34.6
29.4
3.51
STRUCTURED
SLIM
0.79
59.2
47.5
5.65
0.70
35.9
29.8
3.86
Under the FGSM setting, there are great improvements in verified accuracies with different pruning methods ranging from 21.0 - 40.0% on FashionMNIST,, 23.2 39.5% on SVHN, and 12.5 24.5% on CIFAR10, respectively, among which IMP+NRS, HYDRA and Network Slimming (Slim) obtain highest verified accuracy on FashionMNIST, SVHN, and CIFAR10, respectively. We also observe an obvious trade-off of accuracy v.s. verified accuracy, i.e. with the big increase of verified accuracy after pruming, the standard and adversarial accuracies drop significantly. To explain this trade-off, we visualize the ratio of unstable neurons of different pruning methods, as shown in Figure O in Appendix. We find that the ratio of unstable neurons generally decreases as the sparsity gets higher, this is compliant with that neuron stability is important for certified robustness. However, if all neurons become stable, the whole network will become a linear function, which turn withholds the standard accuracy. Hence the standard/ /verified accuracy trade-off is essentially the stability stablltyyexppressieeee /expressiveness trade-off of the network. Nevertheless, this trade-off is not obvious under the Mnto-LiRPA setting since the training objective of auto-LiRPA incorporates standard accuracy.
Across different datasets, we observe general improvement brought by pruning for certified robustness, which consolidates our conclusion that pruning can generally improve Lo certified robustness. In particular, URSLoss-based pruning can outperform other pruning methods consistently under certified training and achieves competitive performance under adversarial training, which demonstrates the effectiveness NRSLoss regularizer and the pruning scheme of IMP+NRS, as we explained in the methodology.
Resource Consumption: It can be observed from Table 2 and that unstructured pruning tends to produce better performance than neuron pruning. However, neuron pruning has the advantage over unstructured pruning that it brings real hardware acceleration for certified verification, especially given that the computational overhead is significant bottleneck for verifying large neural networks even with highly GPU-parallelized verifiers such as Beta-CROWN. We show an overview of the time and peak GPU memory consumption of neuron pruning under different pruming stages as in Figure We can see that for every prunings, which increases about 30% channel sparsity, the time consumption for models trained with auto-LiRPA can reduce by about 50%, whereas for models trained with FGSM can reduce by about 60 - 80%. We also observe that GPU memory consumption can be greatly reduced at high channel sparsity, The reduction in GPU memory consumption is even more important given the GPU memory bottleneck for complete verification of large neural networks. Furthermore, for these pruning methods, we observe similar high performing sparsity under different random seeds as shown Figure 0 in Appendix, which means we do not need to verify every sparsity one by one to pick out the best sparsity, and it crucial for accelerating the verification process practice. We further discuss some bottleneck factors as we move towards verifying large networks with our introduced methods in Appendix
13

---

Published in Transactions on Machine Learning Research (03/2023)
10
20
10
20
GPU MEMORY (GB)
GPU MEMORY (GB)
TIME (MIN)
15
TIME (MIN)
15
10
10
0
5
10
10
PRUNE TIME@0.11
PRUNE_TIME@0.11
Time
Memory
+Tmiee
Memory
(a) StructLTH w/ FGSM
(b) StructLTH w/ auto-LiRPA
10
20
GPU MEMORY (GB)
GPU GPU MEMORY (GB)
TIME TIME(MIN) (MIN)
8
15
TIME (MIN)
15
6
10
10
2
0
5
10
PRUNE_ TIME00.11
SIMNNETIMM@@011
Time
Memory
Time
Memory
(c) SLIM w/ FGSM
(d) SLIM w/ auto-LiRPA
Figure 4: The mean verification time and average GPU memory consumption for neuron pruning methods CIFAR10 dalaset under CROWN mode. X-axis means the number of pruning iterations with 0.11 channel pruming rate. Note that we don't do such test complete verification of Beta-CROWN mode which is time consuming but has highly similar trend to the results under CROWN mode.
4.2.2 How does NRSLoss-based pruning outperform other pruning methods?
From Table 2 and we observe that IMP+NRS oulperform other pruning methods under auto-LiRPA setting. Take the CIFAR10 dataset as an example, with 2/255 perturbation, IMP+NRS improves certified accuracy for 8.2% and standard accuracy for 8.1%; with 8/255 perturbation, IMP+NRS improves certified accuracy for 2.9% and standard accuracy for 2.3%. Notably, IMP+NRS achieves both the highest standard and verified accuracies, since the training objective of auto-LiRPA incorporates standard accuracy. By comparing HYDRA setting and pruning in FashionMNIST and CIFAR10 dataset, and has better standard/verin /verified accuracy tradc-off under certified training for SVHN dataset. We thus conclude that NRSLoss regularizer is effective for HYDRA pruning in most cases and is effective for IMP pruning for all cases we have tested. To demonstrate that the performance improvements of NRSLoss indeed come from stability-based regularization as discussed g we visualize the pre-activation network instability (as proposed in Section 3) in Figure 5 We
setting, we observe NRSLoss can improve the verified accuracy for HYDRA
in Section observe that the RS Loss and NRS Loss-basod pruning have significantly lower instability compared to IMP, and the instability decreases as the sparsity gets higher, which proves that pruning with NRSLoss and RSLoss regularizer decrease network instability, hence improving the certified robustness. It can also be observed that the RSLoss has lower instability than NRSLoss, however, since NRSLoss eliminates the gradients from BN layer, the RSLoss actually gets lower instability by influencing BN layers, which in turn would hurt normal training, and thus hurt overall performance. The advantage of NRSLoss can also be interpreted using the NRSLoss landscape as shown in Figure? 2 Compared to RSLoss, NRSLoss takes account the channel importance, so that using NRSLoss can avoid regularizing neurons that are in the important channels. From these results, we can again conclude that neuron stability is important for certified robustness, particular, IMP+NRS motivated by improving neuron stability effective for improving certified robustness.
14

---

Published in Transactions on Machine Learning Research (03/2023)
0
10
15
INSTABILITY
-1
-2
-3
-4
PRUNE_TIMESAR
IMP - IMP+RSLosS - IMP*NSSS
Figure 5: Network instability v.s. iterative pruning times of pre-activation and pre-BN forward pass values. The bounds are computed under 2/255 input perturbation using auto-LiRPA and the whole test set of CIFAR1O. Note that we omit the curves of SNIP, TP and HYDRA for simplicity as they are almost coincident with the IMP curve.
We note that the literature results as in Wong et al. (2018) are better than the results reported in Table and 3 In fact, is achieved by using incomplete verifications on much larger neural networks (scaling the network size can improve the results), whereas we focus the exploring the pruming effect for complete verifications because complete verifications give better (higher and exact) certified robustness results than incomplete verifications. However, existing complete verifiers are unable to verify these large networks as in Wong el al. (2018), due to OOM problem. For complete verification, our designed Lest network is the largest. one that can be verified with complete verifiers on a GPU with 24GB memory.
4.2.3 Possible existence of certified lottery tickets.
As a possible finding, we demonstrate the possible existence certified lottery tickets in our experiments, that generalizes the lottery ticket hypothesis Frankle Carbin (2018) certified robustness. Specifically, from Table 2 we observe that all pruning methods under certified training across all datascts can find certified lottery tickets that can match both standard and verified accuracies to the original dense models, and most of the pruning methods
produce certified lottery tickets that significantly outperform original dense networks. From Table 3 we see that certified lottery tickets can be found on most pruning methods with a bigger perturbation scale except for random pruning and IMP+RS. From Figure B(a), we observe that except for unstructured pruning (except for random pruning), certified lottery tickets occur almost in every sparsity. The above findings may reveal the possible existence of certified lottery tickets.
4.2.4 How should we choose pruning methods for certified robustness?
Generally, we would recommend IMP and IMP+NRS for performance concerns because they have the best verified accuracy under certified training across different datasets, and we recommend Network Slimming for efficiency concerns because its neuron pruning nature can essentially reduce the computational overhead of the complete verification. We empirically find that the relative performance of our tested pruning methods under certified training is similar to that under standard training. We conjecture that this is because important goal of most pruning methods is causing minimal negative influence on the training objective function, and this objective function is benign accuracy under standard training and verified accuracy under certified training, respectively. These pruning methods also implicitly regularize the network stability and bound tightness as stated in Scction 3.3 which leads general improvement compared dense basclines. However, our proposed NRSLoss-baut pruning explicitly regularizes network stability which makes outperform other pruning methods.
15

---

Published in Transactions on Machine Learning Research (03/2023)
4.3 Summary of Findings
In our experiments, we find that pruning can generally improve Loe certified robustness for neural networks trained with different robust training methods and observe the possible existence of certified lottery tickets. Under adversarial training, we observe a significant tradc-off between standard and verified accuracies with different pruning methods, but under certified training, pruning can improve both standard and verified accuracies. From our experiments, we know that RSLoss and NRST are both effective regularizing network stability but NRSLoss better for imposing less regularization on more important neurons and removing the negative influence of stability regularization for BN layers. From Figure E observe that neuron pruning can considerably reduce the computational overhead of complete verification for neural networks.
5 Conclusion
In this paper, we demonstrate that pruning can generally improve Lo certified robustness, both for adversarial and certified training. We analyze some important factors that influence certified robustness, and offer a new angle to study the intriguing interaction between sparsity and robustness, i.e. interpreting the interaction of sparsity and certified robustness via neuron stability. In particular, we find neuron stability to be crucial for improving certified robustness, on which motivation we propose the novel NRSLoss- pruning that outperforms existing pruning methods. We also observe the existence of certified lottery tickets. We believe our work has revealed the relationships between pruning and certified robustness, which can shed light on future research to design better sparse networks with certified robustness.
References
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. arXiv preprinl arXiv:2007.020 2020.
Anonymous. Lottery tickets can have structural sparsity. In Submilled to The Tenth International Conference on Learning Regresentations, 2022. URL http:///ppareeeeeeeeeeeeettttaas
under
review.
Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (vmn-comp 2021): Summary and results. arXiv preprint arXix:2100.00 100:0000000448, 2021.
Rudy Bunel, Tlker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. A unified view of piecewise lincar neural network verification. arXiv preprint arXiv:1711.00445, 2017.
Patryk Chrabaszez, Tlya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative the cifar datasets. arXiv preprint NT4::1777008811 2017.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. dual approach scalable verification of deep networks. In UAI, volume 1, pp. 3, 2018.
Ruediger Ehlers. Formal verification of picco-wise lincar feed-forward noural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 269 286-286. Springer, 2017.
Utku Evci. Detecting dead weights and units in neural networks. arXiv preprint xrx::1186600000 2018
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint ar Rtt::880303633 2018
Yonggan Fu, Qixuan Yu, Yang Zhang, Shang Wu, Xu Ouyang, David Daniel Cox, and Yingyan Lin. Drawing robust scratch tickets: Subnetworks with inborn robustness are found within randomly initialized networks. In Thirty-Fifth Conference Newral Information Processing Systems, 2021.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. Xix preprint ar Xiv:: 14::141: 141.11116666 6577,, 2014.
16

---

Published in Transactions on Machine Learning Research (03/2023)
Shupeng Gui, Haotao N Wang, Haichuan Yang. Chen Yu, Zhangyang Wang, and Ji Liu. Model compression with adversarial robustness: A unified optimization framework. Advances in Neural Information. Processing Systems, 32:1285 1296, 2019.
Husheng Han, Kaidi Xu, Xing Hu, Xiaobing Chen, Ling Liang, Zidong Du, Qi Guo, Yanzhi Wang, and Yunji Chen. Scalecert: Scalable certilied defense against adversarial patches with sparse superficial layers. Advances in Neural Information Processing Systems, 34, 2021.
Ting-Kuei Hu, Tianlong Chen, Haotao Wang, and Zhangyang Wang. Triple wins: Boosting accuracy, robustness and efficiency together by enabling input-adaptive inference. In International Conference Learning Represenlations, 2020.
Sergey lolle and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International conference on machine learning, pp. 448-456. PMLR, 2015.
Artur Jordao and Helio Pedrini. On the effect of pruning on adversarial robustness. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1-11, 2021.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Namhoon Lec, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Singlo-shot network pruning based on connection sensitivily. Xr preprint 1rXiv:1810.0255 2018.
Hao Li, Asim Kadav, Igor Durdanovie, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiu preprint arXio:1608.0877 2016.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE international conference on compuler vision, pp. 2736 2744, 2017.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730 3738, 2015.
Jian-Hao Luo, Hao Zhang, Hong-Yo Yu Zhou, Chen-War Xie, Jianxin Wu, and Weiyao Lin. Thinet: pruning can filters for thinner net. IEEE branscctions on pallern analysis and machine intelligence, 41(10))2525 2538, 2018.
Xiaolong Ma, Fu-Ming Guo, Wei Niu, Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang. Peonv: The missing but desirable sparsity in dnn weight pruning for real-time execution on mobile devices. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5117-5124, 2020.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Prima: Precise and general neural network certification via multi-neuron convex relaxations. arXiv preprint N1i::2203.03638 2021.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Adití Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint arXiv:1800 1801. 001.09944, 2018.
Sourjya Roy, Priyadarshini Panda, Gopalakrishnan Srinivasan, and Anand Raghunathan. Pruning filters while training for efficiently optimizing deep learning networks. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1-7. TEFF, 2020.
17

---

Published in Transactions on Machine Learning Research (03/2023)
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Vikash Schwag, Shiqi Wang, Prateck Mittal, and Suman Jana. Hydra: Pruning adversarially robust neural networks. Xiv preprint urXie:2002.1000 10509, 2020.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training with short warmup. Advances in Neural Information Processing Systems, 34, 2021.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying ncural networks. Proceedings of the ACM on Programming Languages, (PPOPL)) 2019.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 61999 2013.
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, KRUNAL KISHOR PATEL, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. Advances in Neural Informalion Processing Systems, 33:21675 21686, 2020.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. aixiv preprint orXiv: 71 711.07356, 2017.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient bound propagation with per-ncuron split constraints for complete and incomplete ncural network verification. Xiv preprint arXiv:2106 03.06624, 2021.
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing in convolutional networks. In Proceedings of the Furoopan Conference on Computer Vision (ECCV), pp- 409 424, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 2276-5285. PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295. PMLR, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses.
Advances in Neural Information Processing Systems, 31, 2018.
Zuxuan WU, Tushar Nagarajan, Abhishek Kumar, Steven Rennie, Larry S Davis, Kristen Grauman, and Rogerio Feris. Blockdrop: Dynamic inference paths in residual networks. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pp. 8817-8826, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint orXiv.1708.07747, 2017.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint Xxxi:1809.03000 2018.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai- Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020a.
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsich. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. Xiv preprint ar 2rxiv:201 13824, 2020b.
18

---

Published in Transactions on Machine Learning Research (03/2023)
Shaokai Ye, Kaidi Xu, Sijia Liu, Hao Cheng, Jan Men-ierikk Lambrechts, Huan Zhang, Aojun Zhou, Kaisheng Ma, Yanzhi Wang, and Xue Lin. Adversarial robustness vs. model compression, both? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 111 111-120, 2019.
Chiyuan Zhang, Samy Bengio, and Yoram Singer. Are all layers created equal? ar preprint wrXiv:1902.01990 2019.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsich, and Luca Danicl. Efficient neural network robustness certification with general activation functions. arXiv preprinl ar Xrc::18811.008 2018a.
Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. A systematic dnn weight pruning framework using alternating direction method of multipliers. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 184 199, 2018b.
Appendix
0.6
0.5
UNSTABLE RATIO
0.4
0.3
0.2
0.1
0
5
10
15
PRUNE TIMES@0.2
IMP IMP+NRSLOSS
-NNIP
Figure 6: The ratio of unstable neurons v.s. pruning times of different pruming methods under FGSM setting. We empirically find that all pruning methods have similar curves in this figure, so we sample 3 curves to demonstrate for simplicity. Note that PRUNE TIMES@0.2 means the iterative pruning epochs with 0.2 pruning rate, and we reuse this notation hereafter.
19

---

Published in Transactions on Machine Learning Research (03/2023)
A Experiment details
FGSM and auto-LiRPA share some common hyperparameters. The batch size is set to 128, and clip the norm of gradients to maximum of 8. We train 200 epochs in one pruning iteration for each experiment, with learning rate decay factor of 0.1 at 140 and 170 epochs. We set the input perturbation as Linf-norm ball to 0.1 for the PashionMNIST dataset and 2/255 for SVHN and CIFAR10 datasets, and gradually increase e from 2/255 starting from 11th epoch and until 80th epoch. We also scale the perturbation to 8/255 to validate the effectiveness of pruning under bigger perturbations. The training epochs under 8/255 perturbation is set to 300. After each pruning iteration, we rewind the remaining weights to initial states and reset the optimizer with the initial learning rate and 6.
B Ablation
In this section, conduct. ablation studies mainly the CIFAR10 datasel to further consolidate claims.
60
60
50
VERIFIED ACC.
VERIFIED ACC.
40
40
30
30
20
10
10
10
10
PRUNE TIMES@0.2
PRUNE TIMES@0.2
Finetune
Rewind
Finetune
Rewind
(a) TMP
(b) IMP+NRS
Figure 7: Comparison of finetuning and weight-rewinding verified accuracy v.s. pruning times under auto- LiRPA setting.
Comparison auto-LiRPA and Fast-IBP on CIFAR10 dataset. Note that for HYDRA pruning, we replace the adversarial loss in HYDRA with certified loss.
Table 4:
TRAINING METHOD
LURO-LIRPA
FASTIBP
PRUNING
PRUNING
REMAIN RATIO
REMAIN
TYPE
METHOD
std
ver
RATIO
std
ver
DENSE
54.1
43.0
6.68
1
56.0
43.5
8.42
IMP
0.13
61.0
50.1
6.65
0.04
63.5
53.0
6.17
HYDRA
0.11
60.5
48.3
8.75
0.13
64.0
51.0
6.56
IMS+RS
0.13
58.6
16.3
6.52
0.17
61.5
17.0
5.98
IMP NRSS
0.21
62.2
51.2
6.06
0.17
64.0
54.0
5.91
STRUCTURED
SLIM
0.79
59.2
47.5
5.65
0.44
56.0
46.5
5.53
B.1 Comparison of pruning under different certified training methods
In our main experiments, we choose the auto-LiRPA as the certified training method. The reason we choose this method based on training efficiency and competitive performance, and training efficiency mainly comes from the loss fusion technique as proposed in Xu et al. (2020a). The training efficiency is important in our experiments because iterative training and pruning, which boosts the overall training time
20

---

Published in Transactions on Machine Learning Research (03/2023)
to 16 times longer. We notice that the certified training methodShi al (2021) (denoted FastIBP in the following context) with SOTA performance (i.e. SOTA verified accuracy) claims that loss-fusion has a negative influence on the performance and thus doesn't 't adopt it in their method. We empirically find that without loss-fusion, the training speed of FastIBP is 4 times slower than auto-LiRPA. We thus choose auto-LiRPA as the certified training method our main experiments. However, we here present. a comparison of results (see Table ! of these 2 certified training methods on the CTFAR10 dataset and pruned with several pruning methods, to demonstrate that the improvement of certified robustness brought by pruning is consistent with different certified training methods. The hyperparameter settings the same mentioned in our main experiments. From Table 4 we observe better performance can be obtained with IBP and standard/veriie /verified accuracies are consistently improved with different pruning methods, among which IMP+NRS still achieves the best performance.
B.2 Comparison of finetuning and weight-rewinding for pruning
We empirically find that after each pruning, rewinding the network parameters to their initial states as in Frankle & Carbin (2018) produces better performance than finetuning the parameters as in [Shwwag et al. (2020). Specifically, we follow the experiment setup as in Section 4.1, except that for finetuning mode we don't ro-imitialize the learning rate after pruming. The results are demonstrated in Figure We observe that the finetunigg-base pruning always produces worse performance than weight rewinding- braieiing-bsedd pruning, and its accuracy tends to collapse at 3rd pruning iteration. Therefore conclude that rewindi-e based pruning is more effective than finetuning-base pruning for certified robustnoss.
VERINED ACC.
VERIRED ACC.
25
22
20
12
15
35
10
PRUNE TIME580
MP
PRUNE_ TIMES00.11
-.we D0n5e - Stust" -
(a) IMP
(b) IMP+NRS
Figure 8: Verified Accuracy v.s. iterative pruning times with 8/255 perturbation CIFAR10 dataset. (a) is unstructured pruning under auto-LiRPA training with 0.2 element- wise pruning rate, (b) is neuron pruning under auto-LiRPA training with 0.11 channel-wiss pruning ratc.
55
55
50
VERIFIED ACC.
VERINIED ACC.
45
40
40
30
5
10
15
5
15
PRUNE TIMES@0.2
PRUNE_ PRUNE_TIMESEE TIMES@0.2
- seed100
-e-sod2000
-0-s0ed300
seed100
-eedd000
(a) IMP
(b) IMP+NRS
Figure 9: Verified accuracy v.s. iterative pruning times under different random soods with auto-LiRPA training. (a) IMP pruning and (b) is IMP+NRS pruning.
21

---

Published in Transactions on Machine Learning Research (03/2023)
Table 5: Comparison of CNN-7L and ResNet-18-he on CIFARIO dataset.
A ARCHITECTURE
CNN-7T.
RESNET-I8-NN
PRUNING TYPE
PRUNING METHON
REMAIN RATIO
REMAIN RATIO
std
ver
std
ver
DENSE
54.1
43.0
6.68
53.5
42.4
5.31
IMP
0.13
61.0
50.1
6.65
0.21
59.5
49.1
5.67
SNTP
0.04
59.8
48.4
6.67
0.17
57.2
47.4
5.21
TP
0.05
59.9
47.6
6.02
0.05
56.8
46.2
6.18
UNSTRU-
HYDRA
0.11
48.3
8.75
0.13
58.7
47.0
5.96
CTURED
HYDRA NRSLOSS
0.05
58.0
49.0
8.75
0.05
57.2
17.5
6.12
IMS+RS
0.13
58.6
46.3
6.52
0.44
56.2
46.0
6.87
IMP+NRS
0.21
62.2
51.2
6.06
0.11
60.3
49.6
5.92
STRUCTLTH
0.55
57.5
44.6
3.71
0.70
56.2
43.4
4.10
STRUCTURED
SLIM
0.79
59.2
47.5
5.65
0.79
58.6
46.0
4.54
B.3 Comparision of different architecture
We provide supplemental results comparing the performance of different architectures using the introduced methods on CIFAR10 dalaset. Besides the 7-layer feed-forward CNN (namely CNN-7L) we adopt in the main experiments, also test the recently provided ResNet-18 network (narrowed version) as in the official alpha-beta- CROWN repo and double its network width which leads to 4 times of parameter number. Due to the fact that network depth has more influence on GPU memory occupation, our modified version of ResNet-18 (namely ResNet-11-NTR) has the biggest width that can be fitted 24GB GPU memory, despite that it has smaller parameter number than CNN. We follow the same hyperparmeter setting as Table 2 and the results are shown in Table 5 We observe that the relative performance stable across different pruning methods when we change the network architecture, and IMP+NRS pruning still achieves the best performance.
C will the size of the network or dataset hinder the introduced pruning and verification process?
SOTA complete verification methods such as the Alpha-bbeta-RRON we use in this paper have exponential GPU memory consumption due to the BaB framework, so as the network size grows (especially when growing dooper), the complete verification would be harder be completed due the hardware constraint. Larger dataset typically requires larger networks to achieve good performance, so the verification would also be indirectly affected by dataset size. This common problem faced by vanilla. certified training. However, for subnetworks obtained by neuron pruning during certified training, this problem can be relieved (See Figure 5 for example). For training and inference efficiency, our proposed regularizer has the same complexity with a forward pass of the network since we use TBP to compute the neuron bounds, therefore the training and inference stage of the model with our proposed regularizer won't be affected by the network or datasct size.
Is pruning effective for certified robustness at scale?
In light of exploring whether pruning would be effective for certified robustness at scale, we conduct experiments on the downscaled 64x64 ImageNet Chrabaszez et al.] (017)), following the experiment setting in Table 4 from Xu et al. (2020a). Specifically, there are 1,000 class labels and the Loe input perturbation scale is set to 1/255. We use WideResNet trained with auto-L.RPA and iterative pruning, and also verify using auto-LiRPA incomplete verifier since complete verifiers have OOM issue on WideResNet. The results are shown in Table We observe consistent improvements across different pruning methods even when verified accuracies are
hhttps///gthhhh.com//eriii http://hh....oooooooooooooo/coee http:///mpeeeeeeeeeerr/eeeeeee cwtpspppooooo//eiieeeeee resnet yaml
22

---

Published in Transactions on Machine Learning Research (03/2023)
12
10
VERIFIED ACC.
8
10
PRUNE_TIMES@O.11 StruciLTH
Figure 10: Verified Accuracy iterative pruning times on CIFAR10 dataset of neuron pruning under FGSM training.
Table The incomplete verification results on downscale ImageNet, following the experiment seeting in Table from Xu et al. (2020a). The perturbation is 1/255 and the tested network is WideResNet. The model is trained and (incompletely) verified with Auto-LiRPA. std, adv, ver refer standard accuracy, adversarial accuracy obtained with PGD attack, and verified accuracy
HYDRA
IMP
IMP+
Struct -LTH
Dense
IMP
TP
SNIP
HYDRA
Slim
+NRS
+RS
NRS
Remain Ratio
0.21
0.51
0.32
0.32
0.21
0.40
0.13
0.55
0.35
sid
83.77
86.18
85.57
86.30
85.78
85.96
84.12
86.32
84.76
85.48
adv
81.74
84.23
83.89
84.14
83.67
83.53
83.10
84.64
82.90
83.74
91.27
93.22
92.43
92.66
92.35
92.75
92.07
93.80
91.43
91.27
already high. Our proposed NRSLoss-basee pruning still remains competitive among all pruning methods we tested.
23


Reviews:
[{"review_id": "cW8gc0Xsrq", "reviewer": "Reviewer_xDoJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I know very little about \"Certified Robustness\" literature and will focus on sparsity side of things.\n\n# Strengths\n- Interesting cross-domain work with descent certified robustness improvements and better run-time. I think the research community would find this investigation useful.\n- A new regularization method that provides better pruning results. \n\n# Weaknesses\n- I think it would be better to study practical pruning methods. Both [1, 2] shed light on how so called `lottery tickets` find good solutions. They show that lottery tickets work since they can re-locate where pruning solutions are. In other words often one is best to use the pruning solution found instead of rewinding [3]. It is not clear why authors chose to rewind weights for each pruning algorithms. Findings mentioned above and [3] points out, it's better to continue training with cyclic learning rate schedule after each pruning step. \n- Writing quality is quite low. This can be improved significantly.\n\n[1] https://arxiv.org/abs/2210.03044\n[2] https://arxiv.org/abs/2010.03533\n[3] https://arxiv.org/abs/2003.02389\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies certified robustness for pruned neural networks. Authors highlight the benefits of sparse neural networks for calculating certified robustness (i.e. smaller #connections/branches provide faster verification and resulting bounds are smaller). This hypothesis is supported by experiments which use lottery ticket style pruning. Furthermore authors introduce a new regularizer to encourage robust neurons and achieve higher verified accuracy. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I think writing can be improved significantly. See first sentence of the abstract: \n\n\"With the rapid development of deep learning, the sizes of neural networks become larger and larger so that the training and inference often overwhelm the hardware resources.\"\n\nI couldn't parse this one:\n\n\"..., the model is trained based on a weighted combination of robustness loss and\nNRSLoss, and the magnitude of each trained individual weight reflects its saliency w.r.t. both robustness loss and NRSLoss, i.e. saliency w.r.t. robustness and stability, and by pruning weights with minimal magnitude-based saliency of robustness and stability, we can minimize the negative effects on robustness and stability brought by pruning, and benefit from positive effects of pruning to certified robustness as introduced above.\"\n\nThis phrase exists with same grammatical errors on 2 sections:\n\n\"In fact, this is because they use much larger networks, whereas we focus on complete verification which causes Out-Of-Memory error on large networks, so we only choose small networks for testing, and note that our designed network, though small, is still the largest network we can perform complete verification on a GPU card with 24GB memory.\"\n\nGiven the length of the text and limited time I had, I am not writing them all here, but a strongly recommend authors to use shorter sentences and have a careful grammar pass.\n\n- Please explain robustness metrics used (triangle\" relaxation and linear relaxation) and why they capture robustness.\n- It would be nice to have a direct comparison between magnitude (or Taylor) score and the proposed stability score (Section 3.4.2). For example when W_i=0, then the neuron would have 0 stability, stability-score based pruning would not prune this neuron despite its being dead. Is that correct? Do you use stability score for pruning? \n- In Section 3.4.1 authors say that they keep linear layers dense. This is very unintuitive given that the first linear layer has most #parameters (2048*128) and easy to prune. I think results can be improved significantly if non-uniform distributions like ERK [4] is used.\n- I recommend adding regular iterative pruning experiments (no-rewinding) as they are bring better results using less compute. \n- Why pruning methods use different sparsities on Table:3? I think for comparison, it would be best to use same pruning ratio. Also not clear `std` `ver` and `t` refer, would be best to re-use descriptions in Table:2 here, too.\n- SNIP is introduced as a pruning-before-training method. Do you apply SNIP criteria iteratively? If so, might be best to indicate this clearly and possibly name it as (SNIP-iterative). In general it would be best to make a table with all methods and criterion so that the reader can reproduce results. Also do you plan sharing your code?\n- I think pruning experiments are trained for more epochs. Dense baseline should probably use same amount of epochs as IMP-NRS experiments. Also would be best to add Dense+NRSloss as a second baseline and contrast IMP+NRS results. \n\n# Minor\n- \"Structured Pruning\" is often used for neuron/block and K:N sparsity. I think best would be to use \"neuron pruning\" in section 3.1.1.\n- Please report parameter counts for networks used. This would help reader to contextualize the sentences like \"that our designed network, though small, is still the largest network we can perform ...\"\n- It looks like Table:2 (page:10) is only mentioned at the end of page:12. Would be nice to have this table closer to the section it is discussed.\n- Figure:6 should be in main text, given it is discussed there.\n\n[4] https://arxiv.org/pdf/1911.11134.pdf", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xd1HePwTea", "reviewer": "Reviewer_GDvp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\n\n**An Interesting Problem and interesting findings.** In general the paper asks a very interesting and not yet well-studied question on the impact of network pruning and certifiable robustness. The results shown in Table 2 are very interesting and novel to me. I am surprised to see that there is a ~30% improvement on Verifiable Robust Accuracy (VRA)  for FGSM-trained networks after pruning. In Table 3, it also demonstrates that a pruned network is almost as good or even better than a dense network. \n\n**Runtime Comparison.** I appreciate the author for including detailed runtime and memory usage comparisons, which further show the value of pruning a robust network. \n\n### Weakness and Questions:\n\n**Network Architecture.** The paper finds that a BN layer is pretty necessary for training the subnetwork so it proposes NRL loss. My question is if one adds BN layers into the subnetwork, does this actually introduce a new layer instead of just pruning existing neurons? Can the author also just BN layers into the original architecture and do an apple-to-apple comparison between the pruned and unpruned networks? I would be curious to see if the BN layer also improves the original dense networks in terms of VRA.  \n\n**Why do the authors not directly prune the pre-trained networks that provide the STOA results?** The authors mentioned that their results are lower than the numbers reported in the previous paper and I wonder why you want to train a smaller network instead of directly pruning the existing ones (unless they have not open-sourced the weights).\n\n**Contributions need to be more precise to avoid being over-claimed.** At the beginning of the paper the authors claim that pruning can improve the VRA in general, but the experiments are focused on the $\\ell_\\infty$ threat model and the conclusions are actually that pruning can improve the VRA of robustly-trained networks instead of any networks. However, if the authors also find that pruning can improve the VRA of a standard network, I would be very curious to see the results. In fact, I think highlighting the $\\ell_\\infty$ threat model is important because there are no experiments for the $\\ell_2$ case. Moreover, I think the contribution of the observation of lottery tickets is slightly minor compared to other contributions because it is just a way to phrase that the experiment finds pruning does not hurt but may improve VRA. If there are more concrete theoretical findings on the robust lottery ticket hypothesis I would be convinced that this observation is worthwhile to be highlighted with a bullet point in the introduction section. \n\n**Why is a complete verifier important?** In the beginning of the paper and the abstract the authors highlight the completeness of a verifier but after reading the method and experiments I did not find any discussion on why the paper’s claim will fail if using an incomplete verifier. In fact, I am curious about what the results will look like if using an incomplete verifier. Will pruning decrease the time the robustness is unknown to the verifier? If that is the case, this can be another very interesting observation. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a question that whether or not a pruned neural network is more certifiably robust compared to the unpruned one. To answer this question, the paper investigates many recent network pruning techniques to provide an empirical study. For using Batch Normalization (BN) in retraining the pruned network, the paper proposes a NRL loss for the normalization layer for improving the stability of the output of a BN layer. As a result the paper finds that pruning the adversarially trained networks improves the verifiable robust accuracy with a significant margin to conclude the constructive impact of pruning towards verifiable robustness. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Writing.** I think the presentation of the background and the motivation can be improved. Firstly, some figures are less informative and confusing. For example, the caption of Figure 1 is misleading because Figure 1a and 2d belong to the same situation and the lower and upper bounds have different signs. The differences are the ways of convex relaxation, which are not mentioned in the caption. Moreover, Figure 3 is a bit hard to read. Can you put the unit, i.e. %, to the y-axis for verified acc because in Figure 3(c) the y-axis ranges from 0 to 9 and I was so confused by acc is not between 0 - 1 but later realized this is in %. Secondly, Section 4.1.4 does not have a paragraph. Thirdly, the actual values plus the improvement in green may not be necessary because VRA is as informative as the margin given the VRA of the original dense network. Also, the authors have not explained what the numbers colored in green mean in the caption. I would suggest using the numbers in the parentheses or directly removing the parentheses. Finally, the contribution needs revision, and please refer to my comment in the previous section. \n\nSome potential experiments. As I have mentioned in the previous section, if the authors want to strengthen the contributions or claims, there are some potential experiments but I will leave this optional for the authors to determine. \n", "broader_impact_concerns": "No, this might not be necessary for this paper. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "U093nI7W4S", "reviewer": "Reviewer_vNDf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\nThe experiments conducted in the paper are comprehensive. The authors perform experiments on 3 datasets with a variety of training methods and include several ablation experiments.\n\nTo my knowledge, the specific findings in this paper are novel and interesting: pruning can simultaneously increase the standard accuracy of a network and verified accuracy (under complete verification).\n\n\n**Weaknesses**\nOne weakness of the paper is that experiments are conducted on relatively small networks and datasets. This is understandable due to the computational cost of complete verification. However, the authors may want to consider computing upper and lower bounds on complete verified accuracy on larger networks (using incomplete verifiers and standard attack methods). It would be great if the authors would be able to scale to ImageNet or similar datasets.\n\nThe proposed NRSLoss is certainly an improvement on the relu stability loss, but in my view it is better viewed as an enhancement of the RSLoss than an entirely new method. Since this is the primary methodological contribution of the paper, I view the paper as primarily an empirical study of existing methods.\n\nIn Figure 3, it is unfortunately unclear how the number of pruning iterations affects verified accuracy (specifically for Figure 3 (a)) due to the large fluctuations in verified accuracy. It would be great if the curve could be averaged over many random trials to reveal the underlying trend.\n\nAlthough the presence of certified lottery tickets is presented as a major contribution, the experiments surrounding this are limited. The authors may want to consider additional experiments on this as discussed in the requested changes section.\n\nThe authors only verify over 200 examples for the results in Table 2.\n\nThere are a few grammatical errors in the paper (see the requested changes for more details).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an enhancement (denoted NRSLoss) of the relu stability regularizer proposed in Xu et al. The authors show that the regularizer, combined with a robustness enhancing loss function and iterative pruning method, can yield sparse subnetworks with higher standard and verified accuracy than the network trained without pruning. Based on these experiments, the authors demonstrate that neural networks contain *sparse subnetworks* such that when these subnetworks are trained with a robust training method and the NRSLoss, the resulting network is verifiably robust with high accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical**\nPlease average Figure 3 (specifically Figure 3 (a)) over many random trials so the general trend is clear; right now there are large fluctuations in verified accuracy with the number of pruning iterations.\n\n\n**Would strengthen work**\nIt would be great if the authors could scale to larger model and datasets such as ImageNet by using incomplete verification & attack methods instead of complete verification.\n\nIt would strengthen this work if the authors could show additional analysis of certified lottery tickets. The authors may want to consider conducting additional experiments such as: 1) randomly reinitializing pruned networks and checking to see if they retain high verified accuracy when retrained, 2) measuring verified accuracy of pruned networks when trained under a *different* training method (such as normal training) than used to find the pruned network, 3) visualizing the loss landscape corresponding to the pruned network structure.\n\nIt would help if the authors could fix some of the grammatical issues in the paper. A few of them are listed below:\nIntroduction: \"...estimate the ground-truth bound as close as possible.\"\nIntroduction: \"Moreover, inspired by that sparsity...\"\nSection 2.3: \"...are more prune to adversarial patches.\"\nSection 3.4.1: \"...which is used for sanity check in our experiments.\"\nSection 4.2.1: \"...with every 3 pruning...\"", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all voted to accept the paper.  They all found that the paper addresses a novel question, is backed by extensive experimental evidence and comes to a surprising and broadly interesting conclusion - i.e. that pruning actually improves certified robustness.  The reviewers did find that clarity was an issue and asked for a variety of improvements in writing and presentation.  The authors seem to have addressed these comments in the discussion phase, therefore accept is "as is", but we would request the authors continue to carefully address the feedback for the camera ready version.
Decision: Accept (poster)