Robustness Evaluation Using Local Substitute Networks
Authors: Aleksei Kuvshinov
Crisitan Pavel
Stephan Günnemann
Venue: Submitted to ICLR 2023 (2023)
Keywords: Robustness
verification
pruning
neural networks

Abstract: Robustness of a neural network against adversarial examples is an important topic when a deep classifier is applied in safety critical use cases like health care or autonomous driving. In order to assess the robustness, practitioners use a range of different tools ranging from the adversarial attacks to exact computation of the distance to the decision boundary. We use the fact that robustness of a neural network is a local property and empirically show that computing the same metrics for the smaller local substitute networks yields good estimates of the robustness for lower cost. To construct the substitute network we develop two pruning techniques that preserve the local properties of the initial network around a given anchor point. Our experiments on CIFAR10 and MNIST datasets prove that this approach saves a significant amount of computing time and is especially beneficial for the larger models.

range of Under review as a conference paper at ICLR 2023
ROBUSTNESS EVALUATION USING LOCAL SUBSTITUTE NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Robustness of neural network against adversarial examples is an important topic when a deep classifier is applied in safety critical use cases like health care or autonomous driving. In order to assess the robustness, practitioners different tools ranging from the adversarial attacks to exact computation the dis- tance the decision boundary. We the fact that robustness of neural network is a local property and empirically show that computing the same metrics for the smaller local substitute networks yields good estimates of the robustness for lower cost. To construct the substitute network we develop two pruning techniques that preserve the local properties the initial network around given anchor point. Our experiments MNIST dataset prove that this approach saves significant amount of computing time and especially beneficial for the larger models.
(a) Global, before pruning
(b) Local, before pruning
(c) Global, 12.5% pruned
(d) Local, 12.5% pruned
(e) Global, 50% pruned
(f) Local, 50% pruned
(g) Global, 100% pruned Local, 100% pruned
Figure 1: A toy example in the two-dimensional setting. We show the boundaries classifier, before and Tb) and after the pruning [Tc Th when up the 100% of the hidden neurons removed. The sample we are interested in is marked by the black point and the square around on the plots with the global view [Ta] Ic Ic and Ig shows the local region that depicted the other four plots [b ld. If Th). While the global behaviour changes a lot, the boundary around the chosen anchor point remains similar. Most importantly, the distance the closest adversarial from the anchor point (shown by the black line on the plots [b] Id If and Th) does not change significantly. Note, that this applies even in the extreme case when we prune all the hidden layers and what remains is a linear classifier [1g Th). That means, in order to solve the complex task of finding the distance to the decision boundary for the initial model, we save cost by working with the simple local substitute and still get good approximation of the exact solution.

---

Under review as a conference paper at ICLR 2023
INTRODUCTION
Impressive success neural networks in a variety of complicated tasks makes them irreplaceable for the practitioners in spite of the known flaws. One of the problems that continuously gains more attention is the robustness of the deep neural classifiers. While multiple notions of robustness exist, depending on the use case, we consider the most basic concept of the robustness against adversarial examples small perturbations of the correctly classified samples that lead to false prediction. Presence of the adversarial examples severely limits the application of the neural networks in safety critical tasks like health care and autonomous driving, where the data is collected from sensors and is not acceptable that the same image, for example a road sign, is classified differently depending on the signal noise.
While this problem is widely known, formal robustness verification methods do not allow for an assessment of the classifier's robustness when the network is large or require specific modifications in network's architecture or training procedure. In fact, Katz et al. (2017) show that the exact verification task for the ReLU classifiers is NP-complete Therefore, constructing adversarial attacks and measuring the magnitude of the perturbation, that is required to change the prediction, is still one of the most popular ways to estimate the network's robustness. The farther away the adversarial point is from the initial sample, the more robust behaviour we expect from the network around this point. Unfortunately, the distance to an adversarial point provides only an upper bound on the distance to the decision boundary. On the other side, formal verification methods output a lower bound on that value by certifying a region around the sample as adversarial-fres
In this work we develop a novel inexact robustness assessment method that utilizes both techniques as well as the fact, that robustness of a network against adversarial perturbations around given sample is a local property. That is, it does not depend on the behaviour of the network outside of the sample's 's neighborhood. In other words, two networks with the similar decision boundaries around the same anchor point must have similar robustness properties, despite showing completely different behaviour away from its local neighborhood. Based on these observations we
1. develop a novel method to assess the robustness of the deep neural classifiers based on the local nature of the robustness properties,
2. develop two pruning techniques that remove the non-linear activation functions to reduce the complexity of the verification task, but preserve the local behaviour of the network as much as possible: one that is based on a bound propagation technique and replaces specific activations by constant value, one that preserves the output of the initial network for one adversarial point and replaces activation functions by the linear ones,
3. empirically verify that the robustness metries computed on the pruned substitute net- works are good estimates of the robustness of the initial network by conducting exper- iments on the MNIST dataset and convolutional networks of different sizes.
On Figure [ we show an example of the difference in the decision boundary before and after we apply one of the proposed pruning techniques in the two-dimensional setting. We remove up to all of the hidden neurons while retaining the important properties of the decision boundary locally around the base point.
This work is organized follows. In Section 2 we introduce the necessary notation and formalize the context of our analysis. Section 3 we develop both pruning techniques and explain, how do put the focus on the local neighborhood around the base sample. Further, in Section 4 we set up the experimentation workflow and show the results. In Section [ we mention the relevant related work and, finally, draw the conclusions including options for the future research in Section 6
2 NOTATION
The general idea as well our pruning methods are applicable to any type of deep classifier and the constraints apply depending on the deployed attack, verification and bound propagation approaches. However, in order to allow for a simpler comparison with the existing attacks and verification tech- niques we develop our analysis for the classification networks that Li et al. (2023) use for their comprehensive overview and toolbox of robustness verification approaches.
2

---

Under review as a conference paper at ICLR 2023
We consider a neural network f that consists of L linear layers, dense convolutional, and L activation layers. We denote the number of neurons in each layer 1 as ny for / {O...., L. where the zero's 's layer contains the input neurons. Furthermore, we consider the L -nrm the perturba- tion norm since it is supported by the majority of the verification methods. For a correctly classified anchor point x² E R weight matrices W E R and bias vectors b' E R the output of the i-th neuron in the (-th layer before applying the activation function a is f/' (x²)
and for the last layer (x² w'x b' f(x"). Next, introduce the notation for four metrics that are commonly used to assess the robustness of the given classifier. All these algorithms take the network's parameters (Wi, b¹) )iE((I....L) and x² input.
Pre-activation bounds propagation A pre-activation bounds propagation (of just bounds propa- gation) algorithm B is an algorithm that additionally takes a perturbation budget e as input and returns a set of the lower and upper bounds {a' a' he((......) on the possible pre-activation values it must hold that a' 1- + b'. In other words, for all possible points To with ||=00 2 S a' S w wi b' I a' in every layer I.
Ad Adversarial attack An adversarial attack algorithm A is algorithm that returns point ægdy that is assigned by f to different class than x.. We denote the magnitude of the ad adversarial perturbation ||x=0 1=0-xa0 - llov by A(f) dadv- The smaller the distance dade, the better.
Robustness verification (incomplete) A robustness verification algorithm R. is an algorithm that for a given radius either returns certificate, proving that the neighborhood set B, (xx)) {æ ||æ= - x01o0 S E does not contain any ad adversarial points (that is all points inside get the same label by f). or abstains. The latter might happen either because IB. [x")) does indeed contain an adversarial point or due to the incompleteness of R. We denote the largest such that R outputs the robustness certificate for the corresponding BB (x²)) as R(f)) = dnub-
Distance to the decision boundary Finally, an algorithm D computing the distance to the decision boundary from x." is an algorithm that outputs the distance || Fiay ol to the closest adversarial point 20 Formally, D must solve the following optimization problem.
min min || - 1o s.t. (x² S fy (""), jy #63
(1)
where y the correctly predicted label of x We denote the optimal objective function value of the minimization problem by D(f) dbou-
Note, that for any A, R and D holds that dlob S dond S dadr- When we consider a pair of networks I and we define dutr dmb and dind as A(g), R(g) and D(g) correspondingly.
LOCAL SUBSTITUTES
Given the initial deep classifier, in order construct a neural network that allows for the efficient robustness verification we have to effectively reduce its size. Practitioners pursue the same goal when the network has to be deployed in setting with strictly constrained available memory or when the forward pass during inference must be particularly fast. In these scenarios it is common to prune the network by removing neurons and weights, while keeping the drop in performance on the main task as low as possible and even improve generalization to the new data.
However, these available pruning techniques are not suitable for our application. First, all pruning techniques act globally and take into account the behaviour of the network on the whole available dataset. Instead, we show how to prune the network such that only the vicinity of particular point taken into account that determines its robustness properties. Second, when assess the robustness of a network that is already trained, we do not care about the classification error of the resulting network. The most important goal for us, after reducing the network complexity, is to preserve similar decision boundary in a small region around the anchor point. For more information about the available pruning techniques see Section 5
To achieve the primary goal a faster verification, we have to reduce the number of non- non-linear trans- formations within the neural network. The non-linear nature of the neural networks and the large
3

---

Under review as a conference paper at ICLR 2023
activation function nen activation function
old activation function
n-n activation function
actvetion cutpuE
activtton cuiput
1.4
2.3
2.4
24
12
(x)))) of
f (=
activation imput
activation Input
(a) New constant activation function
(b) New linear activation function
to eliminate the non-linear activation function and the corresponding neuron. On the left, Figure 2a shows the constant function that always outputs the value f (x²). On the right, Figure 2b shows the linear function that defined by preserving the neuron's o's output for two points x. and 2
Figure 2:
Two options
number of the non-linear activation functions in its hidden layers are the main reason why the deep networks are able perform well on complex, high-dimensional data by learning meaningful rep- resentations. On the other hand these non-linear transformations make it hard to explain and verify other properties of the network like robustness. While the exact reasons for that vary depending on the verification approach, common problem is to formally describe the output sets of the points from the neighborhood B, (x The more non- linear transformation does this set undergo, the more complex becomes the output and the worse
the possible approximations, For our task, move the non-linear functions from the network by replacing them by the linear transformations and
removing the corresponding neurons from the network.
3.1 BOUNDS PROPAGATION BASED ITERATIVE PRUNING
Bounds propagation techniques, as defined in Section are widely used in verification literature. The most simple way to utilize them for the ReLU networks is to detect the neurons that does not change their state for the inputs from B. (x*). That is, a < the input to the neuron from layer I is always negative zero and the neuron remains deactivated such that the activation function returns zero for all relevant inputs. Also, if we get the case of 2 0, this neuron is never deactivated and effectively network with exactly the same output g( = f("") for all x0 E (x²)).
as the identity function. By pruning these stable neurons, we get the smaller
Unfortunately, this does not work for the not piece-wise linear activation functions like sigmoid. Moreover, in this procedure the only parameter that controls the number of the removed non-linear transformations is that defines the size of (x.)). The smaller the input region around x the tighter are the bounds q/, a/, such that less of the neurons remain in the undecided state a S 0 S a!- However, use this parameter specify the region that we take into account for pruning. When e is chosen too small to remove more neurons, we risk that the decision boundary around x." will lie completely outside of B. (x:) meaning that the whole set will be assigned to the same class as " This is not desirable since the computation of the bounds in B does not account for the behaviour of the network at the points outside of the given e-neighborhood around x", which, in this case, does determine the network's robustness properties. That means would miss essential information about the network when computing the bounds a' a in the first place.
Instead, first set davv by rumning attack A. This way ensure, that (x is not too small and provably contains the decision boundary between the points with different predicted classes at and o (both are points from B, (x:")). Second, given user defined ratio r (0, 1) of

---

Under review as a conference paper at ICLR 2023
the neurons to be pruned, we apply the bounds propagation algorithm B and remove the neurons with the smallest difference a: a; that we use as a measure of the neuron's variability given the input perturbation budget daty. That is, prune the neurons with the least variable output, considered the inputs from Bd (x"). ). In order to actually remove the neuron, we replace the activation function by the constant value (x²") that this neuron outputs at x". Figure 2a shows how the activation function changes first layer have a and a with the smallest gap due to the magnification during bounds estimation when a and g are propagated in and become looser. Therefore, to prevent the elimination of the neurons exclusively from the first layers, apply the pruning iteratively by removing small portion at a time and then recomputing the pre-activation bounds. This way, each time we prune neurons with the most reliable bounds and distribute the removed neurons more evenly throughout the layers. We present the pseudo code for the described method Algorithm
the example of ReLU neuron. Finally, observe that the neurons of the
Algorithm 1: Bounds propagation based iterative pruning
1: Input: Algorithms A, B, network ʃ. point "R 1) and "o < T
2: Output: Network with at most (1 (m + ... + n2) neurons.
3: Compute dadv A(f).
4: Compute a', a¹ using B with c = dadv. initialize = 1.
5: repeat
6: Compute the threshold ō as the qu-qunntile of the values a¹ a. for {2...., L} and
E (1,...,711}
7:
for 2, ,,...,..,. do
8:
Define 1' {True, False)") " the indicator vector of the remaining neurons: 1 = = -!!- and J as J = =
9:
Update the current layer: W W Jt; and b' b¹
10:
ir < then
Update the next layer: W w and b bl+1 + w f(="),) where update bl+1 in order to account for the non-zero output value of the removed neurons.
11:
end if'
13:
Update k = k + end for
15:
until (1 11)) 2212-- 1-
16:
Return: Network with the new weights W
By applying this pruning method we achieve the following. 1. We preserve local behaviour of the network around x by setting the output of the least uncertain neurons to constant, while we don't 't take into account the points outside of Bz,.. (x=). 2. We preserve the value of the network at x since g(x")= fxx" by construction of g. maintaining it's predicted label. 3. We have dedicated parameter 7 to set the desired amount of the pruned neurons.
3.2
ADVERSARIAL PRESERVING LAYERWISE PRUNING
One problem that seems to be unavoidable for any type of pruning is what we call boundary collapse. When we prune too much, for example when 7 chosen too large for the pruner described in Section
3.1 the resulting network g becomes not expressive enough to maintain non-trivial boundary even locally around x². In this case the prediction region grows and the classifier outputs the same label for every point becoming useless for the robustness assessment of the initial network. However, develop a simple way to solve this problem and to ensure, that even under severe simplification of the decision boundary, it does not collapse, but remains in the vicinity of x
Again, as for the bounds propagation based pruner, we use an adversarial attack A to determine the radius datv of the relevant neighborhood around z Now, we do not only ensure that the network's output at the base point x remains the same, but also at the point Ih that is assigned to a different class. That means, we force g output the same value f in the center of B (x") and at one point on its boundary. Therefore, must assign these points to the different classes and have the decision boundary between them like
5

---

Under review as a conference paper at ICLR 2023
To enforce this adversarial preserving property replace the non-linear activation function by lin- ear function that has the same output for the points x" and a Figure shows an example of the new activation function for a ReLU neuron. Note, that there is always exactly one linear function that (ar )) unless f((") (= ). in which case we set the new activation function to be constant as we do it above for the bounds propagation based pruner. Unlike before, we do not choose the neurons to prune according to any criterion, but instead just prune an entire layer or a set of layers specified by the user. While pruning individual neurons is possible, it leads network with skip connections, that are not supported by many verification algorithms. We summarize the adversarial preserving pruning procedure in Algorithm 2
satisfies this property and goes through the points (f1)),, (f) (x²))) and (=( ), o (f
Algorithm 2: Adversarial preserving pruning
1: Input: Algorithms A, network f. point a E R",, layer to prune (multiple layers are pruned
one by one).
2: Output: Network without the initial layer I.
3: Compute dadv A(f).
4: Compute the coefficients c, d E IR such that
(x²" + d: = (f(()))) and (ar + dd; = (
for all i E {I,...,my) m.. In the only case of multiple solutions, when 5((x²) (a define
C 0 and d, = ((
5: Replace the linear transformations and I + 1 (as well as the activation layer) by the following single linear layer: W W (c) W W' and b' w diag(c)b' + - d b
diag(c) Network with the new weights W b'
6: Return:
This adversarial preserving pruning method has the following advantages. 1. We ensure that outputs the same value at xt and, additionally, at æddy at the boundary of Ba (s²). 2. By maintaining g predicted label at these points we implicitly enforce that the decision boundary does not move farther away than x: adyy"
EXPERIMENTS
Setup We conduct the experiments using five convolutional networks with ReI.U activations pub- licly provided by Li et al. (2023) that are pretrained on the MNIST dataset (LeCun 1998). We call them according to authors' notation A-E, where A is the smallest network with 8000 parameters and E the largest with 600000 parameters. We evaluate the training time of all approaches on a machine with a single NVIDIA GTX 1080 Ti GPU with 11 GB memory. For the algorithms A. B, R and D use the following popular approaches correspondingly (all available within the unified toolbox by Li et al. (2023)) projected gradient descent (PGD) attack, FastLinlBB interval bound propaga- tion (combination of the methods by Weng al. (2018) and Gowal et al. (2018). dual verification approach based on the linear relaxations of ReLU by Wong & Kolter (2018), MILP-basee exact verification by Tjeng al. (2018). All third-party methods are used with the default parameters by
Li et 2023
Procedure The goal is to get a good estimate of doand or deeb without running D and R on the full network. Therefore, for each network we apply both pruning methods (Sections 3.1 and 3.2 with varying magnitude. For our bounds propagation based pruner we use the parameters (0.5, 0.75,,..0 0.9, 0.95). We do not prune the neurons from the first layer, as it is reported severely constraint the resulting network by other works (see Section 5). For the adversarial preserving layerwise pruning we prune an increasing number of layers starting with the second one.
Before and after the pruning, (due to the long runtime of the exact verification) we run D on the small models A. B and R on the models C, D. E on 100 samples. randomly chosen from the training set. For all the pruned networks we compute the mean absolute difference |doad dumal / dand or Idrah - d depending on the verification method used on the corresponding model. Since the fastest method to assess the robustness of network is to perform adversarial attack,

---

Under review as a conference paper at ICLR 2023
130
120
0.5
MLtPaaaee Diferec
821
0.1
(a) Model A
(b) Model
Lovel Eww.thoeeee
21
Board
(c) Model C
Model
(e) Model E
Figure 3:
Experiment results showing the average absolute relative difference between the robust- ness metrics computed on the pruned and unpruned model.
Idui deoal/ /dudd and Iduar drubl/ drob the baseline. That means, the goal is to construct an estimate that is closer to drob and dond than duiv. but to do it faster than R and D when applied on the initial model.
Results Figure g shows the results for each of the models. Each point on the plot represents an evaluation of one pruned network. The z-coordinate is the average runtime of the verification procedure including pruning. Vertical lines represent the runtime of the same algorithm (without pruning) on the initial network as well as 50%, 25% and 10% speed-up marks. The y-coordinate the average absolute relative difference in verification metries before and after the pruning as described above. Numbers at each of the points show the amount of pruning applied to the model (y for the IBP-based pruner and the numbers of the removed layers by the adversarial preserving pruner). Finally, we show the baseline performance achieved by AA by the solid horizontal line. That means a good estimator would result in point lying in the bottom left part of the plot.
Results clearly show, that the proposed method achieve consistent speedup of the verification procedure by at least a factor of two. Depending on the pruning magnitude, even faster verification possible with less than 10% of the initial runtime.
7

---

Under review as a conference paper at ICLR 2023
Looking at the difference of the robustness verification metries before and after the pruning report that it improves with the size of the initial network. IBP-based pruning does not lead to any useful approximations of dpnd for models A and B the relative difference is 10 or higher, while the baseline result being less than 1. However, it significantly improves for the models C, D and E. There, IBP-based pruner outperforms the adversarial baseline, except for the large values of where the results are similar to the baseline. Overall, for the larger networks this pruner achieves at least twice the speed-up when used with 7 E (0.5, 0.7) while outperforming the baseline.
The adversarial preserving pruner yields even better results. Already by removing one or two layers, it achieves a significantly lower average runtime of 50% 25% of the runtime on the full model. At the same time, B and D, when applied to the pruned networks, return good estimates of the robustness of the initial models. The relative difference in dhos and doma is around 0.1 when we remove less than three layers. This pruner consistently outperforms the baseline, even when the most of the neurons are pruned, as its decision boundary is always closer to the base point x. than the adversarial point <ddv by construction (see Section 3.2 Overall, the adversarial preserving pruner provides an excellent tool for the practitioners who is not interested in the exact verification of their network, but need faster way to estimate the robustness better than the PGD attack.
5 RELATED WORK
When talking about robustness verification, there are two main families of methods used in prac- tice: complete (or exact) and incomplete methods. Complete verification techniques verify exactly whether an adversarial example exists inside the given perturbation budget. The main theoretical formulation of this direction uses the mixed integer linear programming (MILP) framework, for which multiple solvers are available based on either satisfiability modulo theory (SMT) Katz et al.
(017)) or integer programming methods (Tjeng & Tedrake 2017: Dutta et al. (017))
Incomplete verification techniques relax the constraints that are put on the activations of each layer in the neural network. An example is the work by WWon & Kolter (2018). where the authors replace ReLU activations with a convex substitute, and, to further increase the efficiency of the method, use the dual formulation of the obtained relaxed linear programming (LP) problem. [Ehler (2017) use similar approximation of the ReLU. However, they do not optimize over the dual LP and solve the problem using SMT. Following this direction |Weng et al. (2018); Zhang al.] (2018) approximate the ReI.U activation functions and propagate the possible bounds of the input to the final layer. Other approaches use semi-definite programming (Raghunathan et al., 2018a Sal b). Lipschitz constant (Weng et al.] 2018 Hein & Andriushchenko 20h7g et al. 2019] [ suzuku et al.) 2018) and
abstraction of the network (Gehr et al.) 2018 Similar to our work, Croce et al. (2019) look at the local area around the base point and in particular utilize the fact that (in case of ReLU activations) it consists of regions, where the network act as a linear function. Their verification method R utilizes
this fact and the authors additionally propose robust training loss.
All incomplete verification approaches provide a lower bound on the distance to the decision bound- ary, which is strongly dependant the tightness of the used relaxation and the way each algorithm computes the bounds on the pre-activation values in each layer. [i et al.] (2023) provide a detailed overview of the verification methods including a proposed taxonomy as well as a publicly available verification toolbox.
Pruning methods allow for minimizing the size of the models only a small cost of their accuracy. They eliminate weights, neurons or layers, such that the output changes as little as possible. Hoefler al. (202I) divide the pruning methods into two categories: data independent pruning and data dependent pruning. The first group consists of pruning methods that does not explicitly use the training data. These methods consider the weights and nodes of the network after training and heuristically find maximal subset of them that have the minimal impact on the final accuracy (Li et al. 2016 Han et al., 2015 Jonathan & Michael 2019). Shumailov et al. (2019) consider the transferability of adversarial examples between the pruned (Han et al.) 2015 and initial model. Their findings are connected to our work, since we also deal with the transferability of the robustness properties to the network after pruning. However, the authors suggest that adversarial examples are interchangeable only at the low levels of sparsity, which unfortunately limits the potential gain in computational cost.
8

---

Under review as a conference paper at ICLR 2023
Data dependent pruning methods consider the effect of the training data the network's output, when making the decision of which neurons or weights to prune. Specifically, these methods take into consideration the influence of the training data either the output, the activations or the deriva- tives of the network and eliminate the extraneous parts of the network, without using its weights and biases directly. This idea do not apply well our scenario, the training data can not be used for pruning while preserving the decision boundary locally. We mention them, as they are successful in accuracy-preserving pruning (Lee et al. 2019 Wang et al. 2020 Evci et al. 2020).
Finally, another method to create a small network with the similar robustness properties as the ini- tial large network, to train it from scratch. For example, using the initial network's 's output to guide the training process. Papernot et al.] (2016) use this approach to create a substitute network for attacking the initial model in black-box environment (that means without the access to its gra- dients). They specifically train the substitute to mimic the initial network on carefully selected data points, iteratively picked by going towards the decision boundary using the gradient information of the substitute network. This method seems very promising, as they also look at the problem in terms of creating a network with a similar decision boundary as the initial one. However, we abstain from performing training in Papernot et al. (2016), who train a single substitute network) that is potentially even slower than the verification
case since must do it for each of the considered base points (unlike
6 CONCLUSION
We develop novel framework to estimate the robustness of a deep classifier around a given base point. Using the available methods for the exact and inexact robustness verification we apply these to specifically constructed local substitute network. We observe, that the decision boundary of the initial network far away from the base point does not affect its robustness against adversarial perturbations in the local neighborhood, and develop properties of the network while reducing its overall complexity. This idea allows for a more efficient application of the verification methods B and D (on the pruned models) while the resulting metrics are good estimates for the robustness of the initial network because of the similarity in the local behavior. We conduct the experiments on MNIST dataset and variety of convolutional networks. The results show that in particular the adversarial preserving pruner (see Section 3.2) achieves good approximation of dnub and dpou (around 10% relative difference, when one or two layers are removed) with a significant speed-up compared to B and 'D applied on the initial model. In summary, the proposed technique allows the practitioners who is interested in faster inexact robustness assessment to get better evaluation of the robustness properties then provided by an adversarial attack.
pruning techniques that preserve local
Future work The success of the presented approach indicates an intriguing direction for the future work towards larger networks and datasets. Also, conducting the experiments with different R. and D should verify that our approach is agnostic to the applied verification methods. Furthermore, we think about combining both pruning techniques from Section selectively pruning the least vari- able neurons and at the same time retain the adversarial point o The resulting pruning approach should have the merits of the both proposed methods.
REPRODUCIBILITY STATEMENT
We clearly and thoroughly describe the developed pruning strategies in Section See Algorithms and for the detailed descriptions. The datasets and networks that we use are publicly available and referenced in the main text. The same applies the attack and verification algorithms deploy. We will provide a link to the repository that contains the project code.
REFERENCES
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu net- works via maximization of linear regions. In the 22nd International Conference on Artificial Intelligence and Statistics, pp. 2057-2066. PMLR, 2019.
Souradeep Dutta, Susmit Jha. Sriram Sanakaranarayanan, and Ashish Tiwari. Output range analysis for deep neural networks, arXiv preprint arXiv: XXXvx:7709.00 1709.09130. 2017.

---

Under review as a conference paper at ICLR 2023
Ruediger Ehlers. Formal verification of piece-wist linear feed forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference Machine Learning, pp. 2943-244222222 2943-2952. P, 2020.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract in- terpretation. In 2018 IEEE Symposium Security and Privacy (SP), pp. 3-18, 2018. doi: 10.1109/SP.2018.0000 2000000
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic. Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 2018.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 2015.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. Advances in neural information processing systems, 30, 2017.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(241): 1-244, 2021.
Frankle Jonathan and Carbin Michael. The lottery ticket hypothesis: Training pruned neural net- works. In Proceedings of the 7th International Conference on Learning Representations (ICLR). New Orleans, Louisiana, pp. 1-4,, 2019.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. Computer Aided Verification, pp. 97-117, 2017.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: SINGLE-SHOT NETWORK
PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference on Learn- ing Representations, 2019, URL /ttp:////eeeeeeeeeeee net/ Eorummruruoo 2id=BIVZqjAcYXX
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint 1rXiv:1608.087100 2016.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In 44th IEEE Symposium Security and Privacy, SP 2023, San Francisco, CA, USA, 22-26 May 2023. IEEE, 2023.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against deep learning systems using adversarial examples. arXiv preprint arxiv:1602.02697 1(2):3, 2016.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint arXiv: 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances in Neural Information Processing Systems, 31, 2018b.
Ilia Shumailov, Yiren Zhao, Robert Mullins, and Ross Anderson. To compress not to compress: Understanding the interactions between adversarial attacks and neural network compression. Pro- ceedings of Machine Learning and Systems, 1:230-240, 2019.
10

---

Under review as a conference paper at ICLR 2023
Vincent Tjeng and Russ Tedrake. Verifying neural networks with mixed integer programming. CoRR, abs/1711.07356, 2017. httptttppp/pa...og////tp//o
07356
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed
integer programming. In International Conference on Learning Representations, 2018.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certi-
fication of perturbation invariance for deep neural networks. Advances in Neural Information Processing Systems 3/, pp. 6541-6550, 2018.
Chaoqi Wang, Guodong Zhang, and Roger Baker Grosse. Picking winning tickets before training by preserving gradient flow. CoRR, abs/2002.07377, 2020. URL httpss///axxiv.orr//ass/
2002.07378
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 Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 5276-5265 5285. PMLR, 10-15 Jul 2018. URL httphttts////cceeel/// wttp://msw........eeee...eeeee/e wttpp/eeeee/eeeegllllr Ba html
www.
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.
Huan Zhang, Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. Advances in Neural Information Processing Systems 31, pp. 1939-4948, 2018.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5757-5764, 2019.
11


Reviews:
[{"review_id": "YjjJNa3DhrT", "reviewer": "Reviewer_Eo7V", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tries to speed up adversarial/certified robustness assessment by pruning the original large models to smaller sizes. Two different pruning algorithms are proposed targeting certified robustness and adversarial robustness.", "summary_of_the_review": "Overall, the paper proposes an interesting direction but fails to provide experimental evaluations against SOTA verifiers and robustness-related pruning approaches. Also, a large body of recent works is missing in related works.", "strength_and_weaknesses": "### Strength\n- It is quite an interesting direction to accelerate robustness evaluation.\n\n### Weakness\n- The proposed pruning methods should be directly compared with SOTA robustness-related pruning methods, e.g., Hydra is one of the representatives supporting both adversarial and certifiable robustness [A]. Nothing pruning-related approaches are compared in the paper.\n- No SOTA certification methods have been compared. Recently SOTA certification methods have achieved great improvements in scaling to larger models and speeding up certifications. Representative works include the recent VNN-COMP winner alpha-beta-crown, as well as other participants OVAL, VeriNet, Marabou, ERAN, etc (see VNN-COMP21 report [B] for details and VNN-COMP22 for updates). As a certification paper, the paper neither compares with any of them in evaluation nor discusses them in related work.\n- To make the results more convincing, it is quite necessary to evaluate the proposed methods on the standard robustness certification benchmarks (e.g., see VNN-COMP or SOTA papers like alpha-beta-crown) such that we can have a good understanding of how much time one can save by using the proposed local substitute networks.\n- The proposed pruning methods are local, i.e., pruning the model for each data point. The pruning cost should also be comprehensively discussed in terms of robustness evaluation time.\n- Many related works should be mentioned and appreciated in Section 1&2 instead of just citing one SoK paper. Also, the papers considered in related works are quite outdated (mostly before 2019) while many certification papers are proposed in recent years with thousands of certification efficiency improvements.\n- Lastly, I am concerned with the certified robustness achieved by the proposed methods since it can only estimate the certified robustness performance without guarantee. However, the sound guarantee is the key factor for certification.\n\n[A] \"On Pruning Adversarially Robust Neural Networks\", NeurIPS’20\n\n[B] \"The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Results\", arXiv’21.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "WRspsiGyfD", "reviewer": "Reviewer_E3L3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to prune a neural network for a given data point such that the nearest decision boundary of the pruned network stays approximately the same as the original network. The intended application is robustness evaluation: the proposal is to use the pruned network as a surrogate and thereby save compute.", "summary_of_the_review": "This paper is unfortunately working on a wrong problem.", "strength_and_weaknesses": "This paper is unfortunately working on a wrong problem. Even if the proposed pruning works perfectly, we still need to prune for each data point and create a different network each time. The over all cost is high and could be higher than simply attacking the original model. It's unclear that we'll save any time or computing resource. On top of this, we'll lose accuracy of the robustness evaluation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "P1hWlpE9hiV", "reviewer": "Reviewer_zHRW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies way of measuring the robustness of neural networks. \nThe goal of the paper is to provide a method to assess the local robustness of the paper at a lower cost than existing methods.\nThe suggested method consists in creating another, pruned neural network, that is much smaller but should be a good approximation of the original network, even if the approximation is only valid in a small area around a given point. Applying robustness measurements techniques to the smaller network is then faster than applying them to the large original network.\n\nTwo different strategies are proposed. Either a proportion of neurons are pruned in each layer, prioritizing the ones that have the smallest gap between lower bound and upper bound (because they have the least amount of variability) and replacing them by constant values. This  pruning strategy is designed such that the prediction at the original point $x_0$ does not get affected.\nThe other strategy consists in fusing two layers (and eliminating the non-linearity in between them). This is based by finding the linear replacement that will maintain evaluation at both the original point $x_0$ and a found adversarial example $x_\\text{adv}$.\n\nExperiments are performed on several convolutional network performing MNIST classificiation.", "summary_of_the_review": "As it is, the paper does not motivate why their approach should be followed and is not providing a thorough enough evaluation to convince people to follow their approach.", "strength_and_weaknesses": "I identify two main weakness of the paper.\n\n# Lack of justification for the approach.\nIf I use a complete verification method, like a MIP solver, I can get an exact measurement of the robustness of my model around a given point. If I use an adversarial attack evaluation, I get an upper bound on the robustness of my model around a given point, telling me that my model is definitely not robust beyond a given point. If I use an incomplete verification method based on bounding, I get a lower bound on the robustness of my model, telling me that as long as perturbation are smaller than a certain amount, I'm safe.\nOn the other hand, if I use this method, the result that I get after running the method is.... a number. Is it an upper bound, a lower bound? We don't know. At that point, I'm uncertain as to how this information can be used. The authors claims at the end of Section 4. that it's \"A faster way to estimate the robustness better than the PGD attack\" but there is no real argument for why this is the case.\n\n# Problem with the evaluation and experimental results.\n- I feel like returning the information as a mean absolute difference obfuscate a lot of the details. How often is the result an overapproximation vs. an under-approximation? Are there outliers?\n- For the method that is based on linear activations, the results are going to be dependent on what is the adversarial example found by the  PGD attack. How do the results vary if you rerun the method several times?\n- The adversarial baseline is marked in all the results as a straight horizontal line. However, it presumably also has a specific runtime and present a valid estimate of the robustness, so it would be meaningful to represent it as a point. (I assume that the adversarial baseline is actually significantly faster than the whole compression + MIP or compression + bound).\n- Any dots on the graph that is above the level of 1 is essentially vacuous. If you returned as compressed network a network that is constant and always return the wrong class everywhere, you get a $\\hat{d}_bnd$ or a $\\hat{d}_rob$ that is equal to 0, leading to a relative difference of 1. On Model A and Model B, we can therefore observe that the Bounds Iterative method should definitely not be used. This is problematic because this corresponds to the model where the reference is a valid measurement (the exact, closest adversarial example.)\n- The evaluation of Model C, D and E on the other hand has a problem because here, the reference point is the bound computed on the full model. This is an overapproximation of the true robustness. As it is, it makes the adversarial baseline look worse. You could imagine the case where the adversarial baseline would find the true closest adversarial example, but would then get a poor score due to being far away from the bound.\n\nIt is also problematic that all evaluations is only performed on MNIST, which is known to be quite a particular dataset.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8wTWubWPMM", "reviewer": "Reviewer_qDPG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces two pruning techniques removing non-linearities in a network while preserving local behavior, with an eye towards producing good estimates of the true robust distance $d_{bnd}$ more quickly. The paper empirically evaluates their performance by computing a relative error between \"ground truth robust distance\" (specifically, lower bounds on the true robust distance, computed using existing verification algorithms) and \"estimates on robust distance\" (bounds from running the verification algorithms on pruned versions of the original network). The **average** value of the relative error is shown be lower than that where the estimate is obtained using an adversarial attack.", "summary_of_the_review": "I am recommending rejection of this paper primarily on the basis that improving the relative error to the true robust distance is not useful without a sense for how often this error is an estimate or overestimate. Other aspects of the paper can be improved too, and I've provided more detail (and hopefully constructive suggestions) in the \"Clarity, Quality, Novelty and Reproducibility\" section.", "strength_and_weaknesses": "The key weakness of the paper is that the estimates computed by running the verification algorithm on local substitutes are neither provably overestimates or underestimates for the original network. Without bounds on how bad the estimates can get (either for individual samples, or on the average estimate for a collection of samples), the estimates would not really be useful for comparing the performance of two different robust networks. It seems possible that a local substitute for a non-robust network would be _more_ robust (e.g. the linear local substitute for a non-robust network).\n\nIf the goal is merely to compute an unbiased estimator of the $d_{bnd}$, scaling $d_{adv}$ (which is known to be an overestimate of $d_{bnd}$) could work better.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject