On Explaining Neural Network Robustness with Activation Path
Authors: Ziping Jiang
Venue: ICLR 2023 poster (2023)
Keywords: Randomized Smoothing
Robustness
Neural Network

Abstract: Despite their verified performance, neural networks are prone to be misled by maliciously designed adversarial examples. This work investigates the robustness of neural networks from the activation pattern perspective. We find that despite the complex structure of the deep neural network, most of the neurons provide locally stable contributions to the output, while the minority, which we refer to as float neurons, can greatly affect the prediction. We decompose the computational graph of the neural network into the fixed path and float path and investigate their role in generating adversarial examples. Based on our analysis, we categorize the vulnerable examples into Lipschitz vulnerability and float neuron vulnerability. We show that the boost of robust accuracy from randomized smoothing is the result of correcting the latter. We then propose an SC-RFP (smoothed classifier with repressed float path) to further reduce the instability of the float neurons and show that our result can provide a higher certified radius as well as accuracy. 

Published as a conference paper at ICLR 2023
ON EXPLAINING NEURAL NETWORK ROBUSTNESS WITH ACTIVATION PATH
Ziping Jiang"
School of Computing and Communications, Lancaster University (z. (ing)))) e ancaster. ac. uk
ABSTRACT
Despite their verified performance, neural networks are prone to be misled by maliciously designed adversarial examples. This work investigates the robustness of neural networks from the activation pattern perspective. We find that despite the complex structure of the deep neural network, most of the neurons provide locally stable contributions to the output, while the minority, which we refer to as float neurons, can greatly affect the prediction. We decompose the computational graph of the neural network into the fixed paths and float paths and investigate their role in generating adversarial examples. Based on analysis, we categorize the vulnerable examples into Lipschitz vulnerability and float neuron vulnerability. We show that the boost of robust accuracy from randomized smoothing is the result of correcting the latter. We then propose an SC-RFP (smoothed classifier with repressed float path) to further reduce the instability of the float neurons and show that our result can provide a higher certified radius as well as accuracy.
INTRODUCTION
Despite their verified performance, neural networks are prone to be misled by maliciously designed adversarial examples. In response to this issue, many studies focus on defensive algorithms that aim increase the robustness of deep neural networks. One of the emerging topics in this field is certifiable methods that aim to construct guaranteed region, within which classifiers are able to provide stable results regardless of the perturbation. The certifiable methods appear in two different forms: verifiable training and randomized smoothing.
This work introduces an SC-RFP (smoothed classifier with repressed float path) which builds on randomized smoothing algorithms and is able to further improve their robustness accuracy. We decompose the local mapping function into fixed paths and float paths according to the stability of neurons on the path. The fixed paths have stable mapping relationship between input and output, while the float paths can result in a sudden change of the mapping function and alter the result. We categorize the adversarial examples into Lipschitz vulnerable and float neuron vulnerable. With respect to the ability of randomized classifiers in correcting misclassified data, we conclude that the essence of the smoothed classifier is average the contribution of the float path and achieve locally stable result. Based on this, we further repress the float paths of the network and show that such classifier can achieve better performance.
The theoretical basis of this work developed from the analysis of the activation region that was ini- tially proposed for explaining the performance of neural network with piecewise linear activation function. The input domain of such a neural network N is separated into many regions, within which the mapping of N is piecewise linear. Previous investigation of this field includes the expressivity, sensitivity, and potential issues of the network. However, due to the complexity of neural network, the theoretical investigation only provides insights into the neural network but has yet to deployed downstream. In this work, we use the theory to explain the model robustness and introduce a novel way to apply the complex theory to practical.
The contributions of this work are: (1) we introduce complete framework to describe and decom- pose the neural network according to the activation status of each neuron; (2) we provide an explana-
"Ziping Jiang is with the LIRA Center, Lancaster University.

---

Published as a conference paper at ICLR 2023
tion of adversarial examples and discuss the role of smoothed classifiers well as their contribution in correcting misclassified example; (3) we introduce SC-RFP that achieves better performance in certifying the network.
RELATED WORKS
The adversarial examples are malicious inputs that are formed by applying an imperceptible pertur- bation to the original inputs but result in misclassification of well-trained network (Biggio et al. (013); [Szegedy et al. (201)). To explain the existence of adversarial example, previous works presented several hypotheses, such as linearity hypothesis (Szegedy et al. (2013); Luo et al. (2015))
and Evolutionary stalling (Rozsa et al. (2016)). Early works increasing the robustness of neuron networks focused on adversarial training methods (Goodfellow et al. (2014); Wong et al. (2020);
Tramer et al. (2017); Dong al. (2018); Kurakin et al. (2016)), while recent investigation shows adversarial training methods can be broken by more advanced attacks.
To address the issue, certifiable training and randomized smoothing methods aim to provide cer- tified region, within which the input data are free from attack. By viewing the training as a convex optimization problem, dual relaxation approaches apply duality to provide a solid bound for train- ing as well as verify the network (Wong & Kolter (2018); WWng et al. (2018). An alternative is estimate the Lipschitz boundary of the network and introduce constraints on either objective loss Tsuzuku et al.. (2018)) or forward propagation (Lee et al. (2020); Weng et al. (018); /Zhang et al. 2019); Huang et al. (202T)). As verifiable training methods often come with compromise of performance, recent works focus on bridging the gap between adversarial and verifiable training to address the scalability and accuracy issue (Xiao et (2018): Balunović & Vechev (2020) De Palma
al. )2022)) )
On the other hand, randomized smoothing introduces a smoothed classifier to the base classifier, therefore has limited effect the performance of standard models. Cao & Gong (2017) first propose to ensemble the information around input data to smooth the prediction, but fail to provide theoretical guarantee the result. [ecuyyrr et al. (2019) certify the result of the smoothed classifier with differential privacy. Coohen et al. (2019) provides a theoretical analysis of the certifiable with Monte Carlo, followed by| Levine et al. 2019 Li al. 2019). Jeong & Shin (2020) introduces regularized to improve the prediction constantly over noise, Jeong et al. (2021) trains the model on
convex combination samples and Salman al. (2019) employs PGD attack with randomized
smoothing to further increases the robustness accuracy.
Another related topic is the explainability of neuron networks. Lin al. 2017 Hornk al. (1989) and Park et al. (2020) investigate how deep models approximate an objective function. An inspiring observation that the network piecewise linear (Pascanu et al.] (2013)) The number of linear regions is then adopted as a proxy of network complexity (Montufar al.] (2014); |Hanin Rolnick] (2019a(b), Novak al.) (2018) studies the network sensitivity by countering the transition density of trajectory in the input space. activation patterns globally to study the limitation of deep neural network. Inspired by the theoretical investigation, Jordan et al. (2019) introduces an algorithm named GeoCert that computes the lp bound of the network with a piecewise linear activation function. /Zhang et al.] (2022) proposes algorithm that systematically searches the adversarial example based on the activation space ReLU network.
piecewise function when the activation function is
Jiang et al. (2022) compares the similarity
3 PRELIMINARIES
3.1 NOTATIONS
Let N be a block feedforward neural network for classification task with measure zero parameter set 0 with respect to Lebesgue measure. Each of the block h;; consists of linear affine di, an optional batch-normalization layer 1h, and piecewise linear activation function d,, while the last block ha omits the activation function. Consider D the distribution of classification problem with e classes from R to = (1,2,...,oe network N computes a function f R - R where f is composition of d blocks f = hn o h ... h1-
2

---

Published as a conference paper at ICLR 2023
For every (2t, y) D, the network computes a probability for each class f(z) R and predicts the label of x as the class with the highest probability: D = arg maxmey fm((), (2), where fm is the m- th element of the network output vector. We use (2; 0), (2; 8) and 2; 0) denote the input, output, and pre-activation value of block for data Tuple pair (i,j) and set I ( {I.... ni) denote the j-th neuron of layer i and all the neurons in intermediate layers respectively, where nH is the output size of layer i.
3.2 RANDOMIZED CERTIFIABLE CLASSIFIER
The research certifiable training aims provide guaranteed region for its input x, within which a classifier always provide stationary result. To be specific, a classifier is regarded as robust for an input x for perturbation of size if:
arg max fm arg max (m),,, Ya' Bp(r,r) mEY
m
where Bp (z) := {a' ||'
- =lpp S r) the sphere with radius r measured by the metric induced by p-norm. By taking the standard performance of the classifier into account, the robust accuracy of with radius r is then defined as:
R(F) = E (aw))D arg max fm((')= Val Bp(a,r)
mEY
However, robust models often incur increased stableness and impaired expressivity. As a concession for that, randomized algorithms are proposed to verify the network with sound theoretical bound at the cost of slight additional computation other than model performance.
Let g be randomized algorithm constructed based on classifier f. Given data (x, D, employs a certain degree of randomness during the induction of f. For instance, smoothed classifier g computes the probability of fz + +) belongs to class given E (0, o I)CCheen et al. (2019)):
ge (x) P(arg max fm(r +)) i), o2), mEy
With certain confidence level a, the lower bound of PA of random variable (y(x) and the upper bound pD of the probability of second possible class maxm E Y (z) can be computed. This induces certified radius of classifier g(z):
④ (ps) Φ- (ps))
(4)
For every x' B2(x, r). if arg maxmey 9m (x) = Y, then arg max 9m (x') = y. In other words, with confidence level a, every x' within the radius can be correctly classifier by the smoothed classifier. The smoothed classifier can also appear other forms depends on the randomness and training algorithm (Levine al. (2019); Salman et al. (2019)) Jeong & Shin (2020)).
3.3
ACTIVATION PATTERN AND COMPUTATIONAL PATH
The input space is partitioned into small linear regions by neural network with piecewise linear activation function. Each of the regions is initially referred to as an activation region. Previous works mostly focused on the general properties of linear regions in investigating the expressivity and limitation of neural network. As our objective is to study the unit-wise reaction towards perturbation, introducing additional notations to describe the neurons is necessary for our analysis.
Definition (Generalized Activation Pattern / Region). Let N be network defined as Section 3.1 }yp } as a set of breakpoints that separates the domain of activation function
Denote I {71, 72. {21 into q + intervals U = (Uo, U!,...,U?!! A generalized activation pattern of N is assignment to each neuron of label:
A = {aiz lais 10.1,...,gh, (i. Z).
Given an activation pattern A, the activation region of A is defined as:
R(A:0, {ar Rd mig (x Ung aij A)
(5)

---

Published as a conference paper at ICLR 2023
Activation Region Operator. The generalized activation pattern describes the activation status of each unit at the intermediate layers. Given an activation pattern A and fixed dependencies, R(A) can be viewed as operator that finds the region, such that, for every R(A), the pre-activation value of each neuron Ziy (z; 0) locates within the interval Vay that determined by its pattern dij E {0, 1 ................ 9). However, the scale of the network grows, the mean volume of single activation region decreases exponentially and can hardly provide insights into model robustness. Therefore, it necessary to generalize our investigation from single region its neighbor.
From Single Region to its Neighbor Equation suggests that the essence of operator R(-) is find all the that satisfies certain constraint determined by the activation pattern. can be expressed as the intersection of a sequence of subspaces:
R(A) = n far E R' (x))) E U.u)).
Vi.j
Given a subset of indexes, removing the intersection operations on those neurons defines a larger region that contains ((A). This implies that adjacent activation regions can be merged into one by releasing constraints on certain neurons. We described it with an incomplete activation pattern:
Definition 2. Let N be network defined as Section Given an activation pattern A and a subset of the index set I E I, we denote AT C. A an incomplete activation pattern of A:
Az = {ais laij E (i,i)) ( T
The merged activation region of AT is denoted as:
R(Az.) = N fo Rin R E Uaigh
(K.))E
In the following section, delve into such merged region to investigate model robustness.
FROM FLOAT PATH TO MODEL ROBUSTNESS
4.1 FLOAT NEURON AND PATH
Merged activation regions are irregularly shaped as it is defined by the aost-activation of neurons, while regular subspace, such as sphere B(x, r), is preferred in analyzing the properties of net- work. Definition 3 introduces float neurons and fixed neurons to describe the status of neurons in regular subspace, followed by Lemma D which builds a connection between Definitions P
and
Definition 3 (Float and Fixed Neuron). Let N be a network defined as Section 3.1 For any space R R if a neuron has the same pattern for any x E R. we refer it as fixed neuron of R. otherwise a float neuron. denote the collection of fixed neurons and float neurons in region R as I (R) and I (R), respectively:
Ix =(i,)) R01, 22 E R,agg(e) # (z)()2)
Is IT(R)= ((i.f) Vo,, F2 E R, any (x1) = (x2))
The following lemma shows that: (1) the fixed and float neurons are complementary sets in I and (2) any subset R. E : can be covered by merged region defined by the fixed neurons of R.
Lemma 1. Let N be neural network defined as Section 3.1 Given C. R denote X and IT the set of float neuron and fixed neuron in R. Then:
1. (R)
2. RC R(A7x).
Now that we have described the status of neurons and illustrated their geometric relationship, we introduce following definitions with the goal of decomposing the computational graph of A
AAppendix A provides additional discussion regarding activation pattern and geometric intuition.
Appendix B explains the computational graph of network with more details.
4

---

Published as a conference paper at ICLR 2023
Definition 4 (Path), Let N be network defined Section 3.1 path of N is of neurons:
::= (:)l 0,1,...,, d,,,,,,,, Co (1, ni),
where is the number of neurons in layer i. The value of path is defined as:
A(x,A) 3Co
II m=1
dam.cm
W (mmcha 1). x. E R.
where FC,, is the Sy-th element of input, W is the equivalent matrix linear transformation dy 0i, am Sm. is the activation pattern of neuron (m, Sm) and dem.cm is the slope of activation o within Om..6.. -th interval.
Definition 5 (Float Path and Fixed Path.. Let N be neural network defined as Section 3.7 Given
subspace R E R a path Ç of N a float path in R if there exist neuron (i, (.) Ç is a float neuron, otherwise it is fixed path:
float path in R: (CI3G E G, (
(9)
fixed path in := (CIVG E E,, (i,C)) (H)).
The value of float paths and float paths in R are denoted as:
zt A:
E
A(x,
z" (:
E ((r,
float path in n
float path n
Figure [ illustrate the proposed concepts with a simple network with 2D input, 4D output and hidden layer. Neuron (1, 4) is the only float neuron in region B(x;, r)- As all the other neurons fixed, the only non-linearity is provided by neuron (1,4). The computational graph of A can be decomposed into float paths and fixed paths according whether (1, 4) on the path.
Sphare Bix,
Layer
(3) Nouron
Layer
Activated Neuron
Deactivated Neuron
Layer
Float Path
Layer
Fixed
Input Space
Figure I:
An illustration of the fixed (float) path and neuron of a neural network with 2D input, 4D output, and hidden layer. (1) The 2D input space: (2) A sphere centered at æ; (3) A float neuron with index (1,4) in the network.
By removing the constraint of neuron (1,4) in Equation an incomplete activation pattern Az- defines merged activation region R(AAx) from green and pink, where I [/{(1,4)) is subset of neurons without neuron (1, 4). As Lemma suggests, region R(Axx) covers (x,rr) Moreover, according Definition the activation pattern of neurons
fixed paths remains unchanged for every R(A7x).. Therefore, given æ, x' B(x, r) with different activation patterns, the value of their fixed paths is linear according Equation 8 The following theorem generalizes the above discussion by aggregating the value of all fixed and float paths with Definition 5
Theorem 1. Let N be a neural network defined as Section 3
Given R C R the following
statements hold for any x, x' with activation pattern A and A':
1. f(x) (x, 2T 2T
5

---

Published as a conference paper at ICLR 2023
2. f(x)= J() x²) (z A: R) (T
where (x) is the Jacobian matrix of f at
Statement 1 decomposes the computational graph of (a) into linear function 2 (x, and an unstable function g (x,,A; R.) with high non-linearity. Given z, x' E R. f(x)) - f(a') can also be written the sum of fixed part and float part by substitution with Statement We rearrange the equation so that the fixed part can represented by the Jacobian matrix at æ, while the float part can be viewed as general instability caused by float neurons.
4.2 FLOAT PATH AND NETWORK ROBUSTNESS
Now that we have stated the motivation and properties of proposed concepts, the remaining question is how float and fixed paths affect the model robustness and randomized smoothing algorithms.
Lipschitz Vulnerable. We start with investigating the fixed part (x) x'). which is determined by both local Lipschitz constant and the scale of perturbation. Intuitively, given sphere (zz, r), if the Lipschitz constant larger enough, the fixed part in f(x') -f (xx itself can alter the prediction of x. The threshold of [xx]] is determined by the sum of prediction margin (ff(x).)) == miny' #n (x), ;- f=),, and upper bound of float path z² z² A: B(x, r)) - 2 (x', A'; r)r, We refer such an a' as Lipschitz vulnerable data. In particular, taking expectation on above sum, we have the following theorem.
Theorem 2. Let J be the base classifier. Given (Ir, ~ D with ((x 1f
|| M(f(z).g) E[M(ZT A: A:R),
then for any smoothed classifier g defined above, there exist x' B(x,r) such that g(x') + y-
||
(z')
+ ZT
(x')
7)
f(x)]
Lipschitz Constant
Accuracy J (Tadd)
7
0.05
0.10
0.15
0.20
0.25
f(x)
2 3(Zadv))
Clean
19.28
19.28
19.28
19.28
19.29
17.06
93.05
0.00
85.08
0.12
17.14
16.84
16.57
16.33
16.12
4.99
86.25
12.54
65.90
0.25
3.74
3.63
3.53
3.45
3.39
2.88
73.59
19.53
50.98
Table 1: Experiment results for VGG16 trained on CIFARI0 with noise at different scales.
The above theorem suggests that randomized smoothing fails to correct misclassified data æ if x has an extremely large Lipschitz constant. Empirically, randomized smoothing cannot provide certified radius for models trained with clean data, while can achieve minor accuracy on models trained with slightly perturbed data. The second set in Table I suggests that training models with noised sample can compress the Lipschitz constant therefore enables the effect of smoothed classifier.
Float Neuron Vulnerable. On the other hand, the float part contributes to f(x') f(x differently. The last set in Table [ presents the accuracy of FGSM (Goodfellow et al. (2014) examples Tode with e 8/255 under foo norm and the accuracy of sum of fixed paths Zt (²(Fodu) between {a', ,z). It shows that by removing the float paths between x and z', significant accuracy boost can be achieved. This suggests that the unstable part of the network can greatly affect the prediction of network. We refer x' as float neuron vulnerable data if arg max 2 (xr) y while (a:") is
misclassified. Given x' float vulnerable, if the smoothed classifier corrected the prediction of x'. then the majority of the neighbor of z' are voting for the correct label. In other word, the instability caused by float paths is smoothed by additional samples around x'.
SC-RFP. Above discussion suggests that smoothed classifier fails to boost the performance of Lips- chitz vulnerable example, but is able to correct float neuron vulnerable data by smoothing the sudden change of float path in region. Moreover, sampling more data shows that, the better smoothing is performed, the higher certified radius and accuracy can be achieved (Cohen et al. (2019)). other words, randomized smoothing provides robustness by restricting the instability the network locally.

---

Published as a conference paper at ICLR 2023
Based on this insight, SC-RFP introduces manual repression the local instability caused by float path into the smoothing classifier. The first set of Table [ shows the averaged 4 norm of difference between expectation of repressed prediction E[Z' (1-))
(x')l and f(z). where
x' is perturbed by e ~ (0, 0.25) with g(x') = y. At each x', we sample 2550 samples around a' and compute the averaged distance (a)). We find that: (1) the clean model has high Lipschitz constant while repressing the instability from float path cannot reduce the prediction gap, and (2) for other models, repressing the instability drives the prediction of smoothed classifier towards original prediction fx)). The results support above discussion. Algorithm describes SC-RFP in detail
At each block, we first compute the pre-activation value of and c. Prior to passes to the activation function, we compare the activation pattern between 24 (x) and 2, + e) according to the separation r, and use repression factor v to reduce the value of float path.
Algorithm Smoothed Classifier with Repressed Float Path Inputs: Network / with parameter 6, randomized algorithm g. input æ; repress ratio 1). Outputs: Predicted label y
while sample noise do for Block in Block 1, ......... do
If < A(=((:) # A(=(( +))
e) (x) 2.
+ +c) (xx I
I x
14+1(1 + (2
end for counts ( + +))
end while
ČA, + top two indices in counls
n. âg t counts(ca], counts(Cp)
if BinomPV Paaeeeaaallaaaaaaa ( n + ng, 0.5) S a then return čд else return Abstain
end if
Intuitively, manipulating the computational graph can greatly change the prediction result, while we show that there are only a small proportion of path are affected by our method. Segure[ppeseee the proportion of fixed neuron between z and + of VGG16 network trained on CIFARIO. It shows that models trained with noised sample have relatively more stable activation pattern, as the ratio of fixed neurons lower. In particular, the model trained with clean data has average fixed ratio around 72%, while after adding a minimum scale of noise = 0.05, it increases to around 90%.
1.30
0.95
0.35
#fbed netion 14 reurgrs
0.90
0.90
0.85
0.85
stued nesion
0.80
0.75
0.75
0./0
0.65
0.65
0.60
0.80
0.10
0.255
0.10
Model
Model
0.10
(b) N (0, 0.25)
Figure 2: Proportion of fixed neuron between and + for VGG16 models trained CIFAR10
with noised data at different scales: clean data, o = 0.05, o = 0.10 and o = 0.25. Figure ((a) and
2(b) show the ratio given e N(0, 0.1) and (0,00.25)
At the end of this section, we present Theorem 3 to link the certifiable boundary of proposed algo- rithm with previous works.
Code provided http://ggghbbbcoommmmmmggga////f
7

---

Published as a conference paper at ICLR 2023
Theorem 3. Let N be network defined as Section 3.1 Let g be smoothed classifier that samples noise from distribution Dnoiee and g' is the SC-RFP built on g. Given ~ Dnoises assume that the direction of is uniformly distributed:
w|mnil = ||eell = P,
= mm) = P |
72).
(10)
|ell
arg max fy(a)) y, then
P'A > PA.PB < PB,
(11)
where A'A PA are the lower bound of gy (x) and 9y (r). ps PB are the upper bound of Smezy (x) and Fmzzy ()). Moreover, if arg max meY g x)) = y. g (xxz) has certified radius no less than R, where
R
2 ② (pA) - - (TB)).
(12)
Notice that in the above theorem, we do not specify the randomized classifier g but introduce constraint of the randomness of g. This means that the theorem holds for not only the naive smoothed classifier, but also its variants. However, it does not hold for the classifiers that sample directed noise.
EXPERIMENTS
As SC-RFP is built on a base smoothed classi- fier, we measure the method on different model structures and randomized smoothing algorithms. The experiments are performed on CIFARIO and ImageNet datasets. For the CIFARIO 10 dataset, we compare our method with the benchmark classi- fier proposed by Cohen al. (2019) with VGG16 network to show the effectiveness of our method. For the ImageNet dataset, choose ResNet50 as model architecture and add the adversarial smoothed classifier [Salman al. (2019) the base model. We also compare our model with recent works (Jeong & Shin (2020); Jeong et al. (221)) to obtain general evaluation. In line with previous works, we use certifiable accuracy dif- ferent radius computed by Cohen et al. (209)) as the metric.
0.7
oeal 30m
0.6
Coren chall 5CRPP
0.4
0.1
35
1.5
2.0
Radius
(a) 6 (0,
Figure 3: Certified Accuracy of base meth- ods and SC-RFP (n 0.1) with different level of noise on CIFAR10. The solid and dashed lines represent benchmark and SC- RFP.
CIFAR1O. We train the VGG16 network with dif- ferent scales of noisy samples. Each of the models is trained for 200 epochs with SGD optimizer and an initial learning rate of 0.1, which decays after 60, 120, and 160 epochs with rate of 0.2. Table 2 compares the robust accuracy of SC-RFP and benchmark. Generally, our SC-RFP increases have an increasingly robust accuracy between 6% to 10% compared with the benchmark. We notice that by repressing the float path, SC-RFP is able improve the accuracy of clean data, which supports our analysis that the float neuron vulnerability is one of the causes of misclassification. Figure present the robust accuracy different noise scale. We find that the performance boost from RF- increases as the radius increases for all the models.
Method
0.25
0.5
0.75
1.0
1.25
1.5
2.0
2.5
Clean
Cohen et al. 2019)
66.0
50.2
44.2
25.4
19.5
19.5
6.9
4.5
75.3
SC-RFP
69.4
58.3
52.7
34.9
29.5
29.5
12.9
9.5
77.2
Table 2: Certified robust accuracy for Benchmark and SC-RFP (1 = 0.1) on CIFARIO.
Experiments on ImageNet. We train ResNet50 using the benchmark model (Cohen et al. 2019 and SmoothAdy (Salman et al. (2019) ImageNet-2012 for 80 epochs with same training sched- uler and optimizers as the original work. Each of the model are certified with same level of noise as they were trained.
8

---

Published as a conference paper at ICLR 2023
144
3E3
2.01 0200
10V71110.000
63
(a) 0 0.25
(b) 0 0.5
(c) o 1.0
Figure 4: Certified Accuracy of base methods and SC-RFP on ImageNet. Model are trained and tested with (a) a 0.25, (b) 0.5 and (c) o 1.0. The solid and dashed lines represent benchmark and SC-RFP with different repression factor.
Table 3 compares the certified robust accuracy of different models at different radius ImageNet. shows that when deployed on the PGD+noise training (Salman et al. (2019)) the SC-RFP has the highest robust accuracy all the radius. Moreover, increasing boost in the robust accuracy is observed as the radius increase, which consistent with our previous analysis of CIFAR10 result.
Figure provides
experiments. For noise level of 0.25, SmoothAdv and SmoothAdy + SC-RFP has neglectable difference, while in Figure 4(c) the SC-RFP (a = 0.25) increases the robust accuracy by around 5%. By introducing SC-RFP (a 0.1) to the benchmark
details
classifier, it achieves comparable results with other state-of-ar -art models when l radius is around 1.5.
l2 radius
0.25
0.5
0.75
1.0
1.5
2.0
Clean
Jeong & Shin
(020
59.8
49.8
44.7
39.3
28.1
22.6
Jeong et al.
2021
46.7
38.2
30.3
26.8
15.7
12.1
Cohen et al.
(2019)
57.9
46.4
41.9
32.6
22.8
15.6
66.1
SC-RFF (ours)
59.4
50.3
41.5
35.6
26.1
20.2
65.8
Salman et al.
(0019)
59.2
54.1
51.5
39.6
26.2
20.1
63.6
PPCRRF (ours)
59.8
55.4
53.6
42.0
29.6
25.2
63.9
Table 3: Certified robust accuracy for models with different methods on ImageNet
We find two insightful observations from the above results. First, introducing the repression factor to the float path has a minimum negative effect on the standard accuracy, while can greatly boost the robust accuracy. This supports our discussion that float neuron vulnerable examples are caused by the float path, and can be cured by reducing their contribution. Second, we find that as the radius grows, the boost from our method increases. This is consistent with the theoretical basis of SC-RFP as well as the result from CIFARIO 10 dataset. When size of the perturbation grows, the uncertainty of randomized algorithm increases along with the number float paths as Figure 2 suggests. This results in higher abstain rate and higher possibility of misclassification. By repressing the value of the float path, the deviation of g(r r + e) from f(x is reduced, therefore a more stable result can be achieved.
CONCLUSION
In this work, we introduce SC-RFP algorithm that can improve the performance of randomized smoothing classifier. We first introduce a framework for describing the local activation status of neurons and show that most of the neurons are locally stable, while the others greatly affect the model prediction. By decomposing the computational graph of the network, we find that the boost of robust accuracy provided by the smoothed classifier is averaging the deviation of float paths. Based on this, we suggest further repressing the value of float paths with SC-RFP method. The experiments show that method can improve the performance of smoothing models.

---

Published as a conference paper at ICLR 2023
REFERENCES
Mislav Balunović and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In 8th International Conference on Learning Representations (ICLR (020)v)) International Conference on Learning Representations, 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks to deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, pp. 278-287277788 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M Pawan Kumar, and Robert Stan- forth. 1bp regularization for verified adversarial robustness via branch-and-bound, arXiv e-prints, pp. arXiv- 2206, 2022.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boost- ing adversarial attacks with momentum. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9185-9193, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pp. 2596-2604, 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, pp. 361-370, 2019b.
Kurt Horiik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366, 1989.
Yujia Huang, Huan Zhang, Yuanyuan Shi. J Zico Kolter, and Anima Anandkumar. Training certifi- ably robust neural networks with efficient local lipschitz bounds. Advances Neural Information Processing Systems, 34:22745-2217 2021.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, 33:10558-10570 2020.
Jongheon Jeong, Sejun Park, Minkyu Kim, Heung- Moag--hang Lee, Do-Guk Kim, and Jinwoo Shin. Smoothmix: Training confidence-calliratted smoothed classifiers for certified robustness. Ad- vances Neural Information Processing Systems, 34:30153-30168, 2021.
Ziping Jiang, Yunpeng Wang, Chang-Tsun Li, Plamen Angelov, and Richard Jiang. Delve into activations: Towards understanding dying neuron. IEEE Transactions Artificial Intelligence, 2022.
Matt Jordan, Justin Lewis, and Alexandros G Dimakis. Provable certificates for adversarial exam- ples: Fitting a ball in the union of polytopes. Advances in neural information processing systems, 32, 2019.
Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al. Adversarial examples in the physical world, 2016.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEFE, 2019.
10

---

Published as a conference paper at ICLR 2023
Sungyoon Lee, Jaewook Lee, and Saerom Park. Lipschitz-certifaable training with tight outer bound. Advances in Neural Information Processing Systems, 33: 1389111666990, 2020.
Alexander Levine, Sahil Singla, and Soheil Feizi. Certifiably robust interpretation in deep learning. arXiv preprini 19X.::990..120000 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. Advances in neural information processing systems, 32, 2019.
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work well? Journal of Statistical Physics, 168(6):1233-124) 2017.
Yan Luo, Xavier Boix, Gemma Roig. Tomaso Poggio, and Qi Zhao. Foveation-based mechanisms alleviate adversarial examples. arXiv preprint arXiv:1511.06299 2015.
Guido Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp- 2924-2932, 2014.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: empirical study. arXiv preprint arXiv:1802.008660 2018.
Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. arXiv preprint arXiv:2006.00 9,885,,00008889, 2020.
Razvan Pascamu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. arXiv preprint arXiv: 2013.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Gohl-Dickstein. On the ex- pressive power of deep neural networks. In international conference on machine learning, pp. 2847-2854. PMLR, 2017.
Andras Rozsa, Manuel Gunther, and Terrance E Boult. Towards robust deep neural networks with bang. arXiv preprint arXiv: 1111v:1612.00136 2016.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Ad- vances in Neural Information Processing Systems, 32, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.611 2013.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXiv: 2017.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: scalable certifica- tion of perturbation invariance for deep neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 6542 6551, 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. 9276-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 I Zico Kolter. Scaling provable adversarial defenses. Advances in Neural Information Processing Systems, 31, 2018.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint 2001 (039944 2020.
11

---

Published as a conference paper at ICLR 2023
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. International Conference on Learning Representations, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv:1906.063/1 2019.
Huan Zhang. Shiqi Wang. Kaidi Xu, Yihan Wang, Suman Jana, Cho-Jui Hsich, and Zico Kolter. A branch and bound framework for stronger adversarial attacks of relu networks. In International Conference Machine Learning, pp. 16591-26600 PMLR, 2022.
APPENDIX
The Appendix contains four sections. Section further discusses the geometric intuition following
Section 3.3
Section B provides proofs of the decomposition of computational graph following
further invesitgates the properties of proposed SC-RFP algorithm. At last, Section provide supplementary experiment results for Section
Section
Section C
A GEOMETRIC ILLUSTRATION
This section provides geometric illustration of the proposed framework. For the completeness of definition of activation region, we discuss the case that pre-activation value 2iy(x) locates within none of the intervals. In other words, we consider the case that 2ig (z; 0) E {71, :.......gh.h
Definition (Generalized Activation Pattern Region (Restate)). Let N be a network defined as in Section 3.1 Denote
T= 72, "...., 7,9
as of breakpoints that separates the domain of activation function into q + intervals
= (Uo, U1,...,ūg) U,).
An activation pattern of N is defined as an indexed family that assigns each neuron sign to repre- sent the status of its pre-activation in U:
A {aiz |a:j E (0. (2, EIJ
Given activation pattern A, the activation region of A is defined as:
R(A:B,o, == {a R (2xy(:; 0) Uay ais A}
(13)
Conversely, given x Rin denote the activation pattern of neuron (i, as:
i, (x; f) E U..
{abstain,,
(14)
abstain, 25(l;; 0) E {yi, 72...., 79
The activation pattern of x is the collection of the all the pattern of neurons:
A(z;0.o,1)) = (ā, E I)
(15)
Inverse of activation region operator. The generalized activation pattern describes the activation status of each unit at the intermediate layers. Given activation pattern, R(-) finds the region, such that, for every x E R(AA; 0, a, I). the pre-activation value of each neuron Zzy (z; f) locates within the interval Ua., that determined by its pattern a; E 10. g}. However, the activation pattern of given 2;y(0) E 72,...... ) cannot be determined under previous definition as well as previous al. (2017)) Therefore, introduce inverse operator Á(x; 0, 1,) that computes the activation pattern of an input x e 1o in Definition This allows us to fill the completeness with the framework.
works(Hanin & Rolnick (2019)
Next, we consider the set {a| (zrlzz (I)) E {%1 72.....
7.
Under trivial assumption that the proba-
bility distribution of parameter set {Ø} has no atom:
IP(0 0o) 0, v0. R, 0 E {theta).
12

---

Published as a conference paper at ICLR 2023
The Lebesgue measure of (x)) 17.22. .2..... point of view, the collection those x partition the input space R into numerous regions by a set of hyperplanes (H) where:
................................ .9 is O in R dimension. From geometric
Hiju (0) = {s E U| (2; 7,
is determined by neuron (i.j) and breakpoint "/a- Each of the region, as Definition I is an activation region. The following figure presents geometric illustration similar to that in the Section but with the description of hot-hhypepplans.
Sphare Bix,
Layer
(3) Neuron
Layer
Activated Neuron
(4) Bont-hyperplane
Deactivated Nouron
Layer
Float Path
Layer
Fixed Path
Input Space
Figure 5: An illustration of the fixed (float) path and neuron of a neural network with 2D input, 4D output, and hidden layer. (1) The 2D input space: (3) sphere centered at x; (4) float neuron with index (1,4) in the network.; (4) A bent-hyperplane defined by H = 2121, = 0;
Figure presents an illustration of the key concepts of this work. Consider N neural network with 2D input, 4D output and hidden layer with 4 neurons. Assume that N has ReLU activation function. The input space partitioned into several regions by set of hyperplanes. Each of the region is referred as an activation region that marked in unique color, within which the mapping function is linear.
For example, the pink and green region are divided by the bent-hpyerplane H = 2 (x) 0, where 21,4 4 the pre-activation value of 4-th neuron in the layer. Now we consider a sphere B(x, r) centered at with radius (xx, r) is covered by the union of pink and green region. Since the two regions can be merged into one by removing the hyperplane, then the incomplete activation pattern of the merged region is I (1, 4)). Therefore, (1, is the only float neuron in B(x, r). This means that for every x E B(x, r), all the neuron has same activation pattern expect for the neuron (1,
Now we consider the computational path of x E B(x,r), r). Given a path Ç. neuron (1, 4) is not on this path, then ( is fixed path, which the black lines in the figure. This means that for every x E (xx, r), the value of those fixed path are linear function with respect to æ. On the other hand, all the non-linearity of function (x) ) for E ((x,r) r) are contributed by the float path (Orange lines).
With the illustration above, we proof Lemma D as follows.
Lemma 1 (Restated). Let N be neural network defined as Section 3.1 Given R C R denote X and IT are the set of float neuron and fixed neuron R. Then:
1. Ix (R) I
2. RC R(Azx)
Proof. Given a neuron (i.j) and a region E Roo For any & E R, we use (zy(x). Since 2x)(x) (-oc, oo), the pattern of x is either index of the region when 215(x) E Ux -1 when k}.
Zi)(x) locate on the bent-hyperplane Hijk == {0/221(()
This means every neuron has pattern for R. for every R the pattern of neuron (i.j) remains the same, then (i.j) is a fixed neuron. Otherwise, it is a float neuron. In other words, neuron is either fixed or float in R. This implies that I (R) UTT ( I.
13

---

Published as a conference paper at ICLR 2023
Now consider statement 2. For any 21,22 R. and an index of neuron (f.j)- If (ry ag (22). (i,5) is fixed neuron in R: (i,j) E 1x Denote the pattern a.j. Then for all R, Rijan, 8 = Z- Therefore, E R((A)).
B DECOMPOSING THE NETWORK
Before we delve into details, we have to restate the definition of path and introduce definition of sub-path. This enables us to take the bias, the computational graph of which starts at middle of the network instead of the beginning, into account. We start with introducing sub-path of network N.
Definition 6 (Sub-path). A sub-path of path consists of several consecutive elements of
((5.5) {St Sj+1 5
(16)
We use (x) to represent the computation graph from (i. to (i)::):
(ı(x) = ((i.)) o (,,(())
(17)
Definition 4 (Path (Restate)). Let N be network defined as Section 3.1 A path of N is set of neurons:
:: ((i, Gi = 0, 1,,.......yy di, S E (1,2.....n,k
(18)
where ny is the number neurons in layer i. The value of path is defined as:
4 II m=j+1
(H, A): =
d.A. 6m.
Wm(mm) (Km
(19)
where Fc, is the Sy-th element of input, Wi(i) is the equivalent matrix linear transformation ihy db, am is the activation pattern of neuron (m, Sm) and dam.co. is the slope of activation a within
am.... interval.
Next, we consider the mapping from v, which can be either from x or bias at intermediate layers, to output of i-th layer yi.
Given activation pattern A, for any x E [R T.T.. The k-th component of output vector of layer can be represented as:
Lemma 2. Let N be neural network defined Section 3.1
(ia(x)=
Σ YCE
II m==+1
d'A..cm
W. (mm)(m-1)
Σ
II m=0+1
d.A..cm
W.(m)
(Cmikm-1) (20)
D= 4GI=k
where Ejsc, is the Çi-th element of input in layer j. W and g are the equivalent matrix and bias of linear transformation the o Am.Co is the activation pattern of Sm-th component of luyer i and d Am..K is the slope of pattern Am...i d.A..cm. == of df), Umm.c..
Proof (Lemmaa 2 We first show that the pre-activation transformation can be represented by matrix. As oi is a linear affine, we denote @.(x) W,,, Combing with batch normalization layer, the mapping from imput I; pre-activation is:
2, =
dc(x))
+ +
7 (x( σ
7/ θ
+ Di W
7p + 3
(21)
where D;(-) is the diagonal operator, á and â are the mean and variance parameter of the dh Denote Wii) W,, 3 (3) 2/ ) We proof this byh deduction. For 1:
24 (1)) dA., Joj + ni x (000
where Ar, is the activation pattern of 21c- ((1,), (2, i), (no, (mn, i)). Equation 20 holds.
Since all the path in layer i ends at i are
14

---

Published as a conference paper at ICLR 2023
Now assume equation holds for i p.
ni
w
+ x g(6)
Epi
==0
Σ
(r(()) 1/ + 144 18/
)=
wr(t) dAA.. 1, + x 88
J=0
(22)
w dA.s Σ J55 II
dan, 6m
Whlm)
(Smi 1)
)=0
vC:
m=p
d dA Sm fm 11) (g((())
Willm)
o=p-1 VGz=k
172 m1++1
p-1
W dm II m==+1
Σ
dmm..cm II o=j O= m=0+1
Wr(m)) (6mi6m-1)
(m-
KCp
Lemma decomposes the computational graph of network N, while Theorem categorize the paths of f(x) into fixed part and float part. Moreover, it describes the model robustness with by divide the variant of f into a linear part as well as non-linear part.
Theorem (Restate). Let N be neural network defined as with activation pattern A and A', we have
Given R C X, for any x, x R
1. f(x) 2' (2, A:R) + (7,
2. f(x) f(x') ((x) - -0) + 2J (z)
where Z A; = E<EZ ((x, A), 2 Ax - (REZT(RE) ((r, are the sum of fixed path and float path given the region R, J(x) is the Jacobian matrix of f at x.
Before we proof above Theorem, we use the following Lemma to show that every fixed path in region linear regardless of the activation pattern.
Lemma 3. Let N be a network defined as Section 3.3 Let be fixed path in R C Rng- Then A'), Moreover, Z (x', R) =
for any x. x' E with activation pattern A,A', <( 2 (x', A'; R).
Proof (Lemma
Given & E with activation pattern A,
d ((x,A) :0 II d.n..cm W=(m) (mmm)m-1))
m=1
Since is fixed path in R. then every neuron alone Ç is fixed neuron, the activation pattern of (m, 5m) is same regardless of input Therefore, d.A.s... is constant for any E R. Then Ç(x, A) is a linear function of x C(x, = ((x). In other words, the change of activation pattern does not affect the neurons on therefore the slope of this path does not change. ((x) is dependent on æ in region R. This means that Ç(x', = Ç(z', ,') for any x, x' E RR with activation pattern A,
z z'(x' (x,,A; R, is the aggregation of all the fixed path above. Since the summation of linear function is still linear, we have:
2' (: = (2',
Proof (Theorem D. From Lemmal 7 every neuron is either fixed neuron or float neuron. For the neurons in path C, if there exists a float neuron, then the path is float path. Otherwise, it is fixed path. The float path and fixed path are complementary set on the set of all paths.
Lemma decomposes the f(x) into summation of paths. As each path is either float fixed, have
f(x) (x, + 2 (x.
15

---

Published as a conference paper at ICLR 2023
For statement 2, we have:
f(x) - f(x')
(T) ((" + ZT ((;A) 2' (:R) - (: +
(Z' R) +) (z,
(23)
Az: (z
Notice that, Z'(x' (x', A: R is the collection of all fixed path, therefore is unrelated with the change of A. We have (s', (s',A:R) [x) - x'), which reaches to statement 4.
(s'',, A R). The former part of above equation is equals to
C MODEL ROBUSTNESS
C.I LIPSCHITZ VULNERABLE AND FLOAT NEURON VULNERABLE
In Section 4.2 we discuss two kinds of vulnerable data and discuss our motivation of SC-REP. In this section, we present formally statements of the proposed idea.
Before we move to Theorem 2 we need the following two lemmas. Lemma 5 suggests that, given a fixed path C. the expectation for the randomized algorithm g({(z)) is equal to the ((x) when satisfies certain conditions. In fact, the condition here just assume that the randomly sampled noise has equal probability at each direction, which is natural assumption for most sampling procedure.
Lemma 4. Denote N as neural network as Definition 3 with mapping function f, S is fixed puth in B2 (2, p). Assume g a randomized algorithm that applies noise from certain distribution Dnoise on the compulation path of Ç:
g(((x)) Ca,i(Si,o(z +e), E 10, 1}, e ~ Dnoise
(24)
If the direction of c. uniformly distributed, then the expectation of g(((x)) is equals ((x), that is:
V|mll |mell = P.
= m2) P
Elg(5(x))] =((x),
(25)
where is the noise generated for randomized algorithm g.
Proof. Assume that g samples noise at layer k. Then for any g, Çkk 0) = g(Gr,o), which we denote as Tg. Since the activation function is piecewise linear, the mapping of Cd, linear. We have:
1k 8y = 0.
Σ
(26)
Oz
Sa,s is harmonic. Therefore, given any B(x,r) with radius 0:
(a.
JOB(a.r) Çdo,
(27)
TWATn
where W,, the volume of the unit ball in dimensions, is the (n 1) dimensional surface measure. Now we consider the expectation of g(x):
E(g(x)) = p(c)Cal(Ex +cdd
(28)
He|er I
p(e)Sa, piesslaa
c)dudr,
where μ is the probubility measure of Dnnisc As the noise sumpling is assumed to be direction irrelevant, the measure of p(e]]le||2 =) is uniformly distributed given radius r. Therefore:
ple = P([le]12 raak-
(29)
|eller
Equation 28 then equals:
B(g(z)) = p(e)Cau(<x + e)du
/
P([|c]22 dr
(30)
(a.
16

---

Published as a conference paper at ICLR 2023
Lemma 5. Let f and g be the mapping function and randomized classifier defined as above. Given radius r such that, almost surely. 2' (B((,,))) = 0, (z, v) D. then the accuracy of base classi- fier and the naive smoothed classifier same, that is:
(a.y)>
arg max 9m 9m(() y mEY
E (may)~
arg max fm( y/ mEY
Lemma 5 is the achieved by directly applying Lemma 4 the all the computational graph of the network. shows that all the neurons have locally stable activation pattern with respect to the distribution of dataset, the smoothed classifier provides identical accuracy with the base classifier.
Next, we present the proof of Theorem 2
Theorem 2. Let f be the base classifier. Given (a. 3) ~ D with f(z) = y. denote Mff(x). y) =
miny's #y fx)) fx))g) as the margin operator of prediction vector. If
|[(=)||> M({()),) + E[M AR),
then for any smoothed classifier g defined above, there exist x' B(x,r) such that g(x') # y.
Proof. Statement 4 of suggests:
f(x) f(z') = J(x) x') + 2 (z' A:R) 2 (d',
(31)
As [|](x)| M(ffe there exist x' and such that:
f((x)) > fo(z') + E (I. R) 27_ (z, A:
(32)
Therefore,
(((x) (x(2)) gy (x( 9y(x)) M()()).)) (x(x') 9u
(33)
Next, consider the case that is adversarial example that mislead f but correctly classified by g. which we referred to as a float neuron vulnerable example. The following theorem suggests that, the float path at are the cause of the altered prediction. In other words, the network is locally correct around x, while there are sudden change from the float path that causes the misclassification.
Theorem 4. Let f and g be the base and smoothed classifier defined above. Given (x, ~ D, denote x' E Bxx,r) without abstain:
adversarial example that mislead the base classifier but corrected by
arg max fm = i,
arg max 9m (x) = -.i+v
(34)
mEY
mEY
then loss of float path is higher than that of g=
CE(ZT (x', A; R),, onchot(y)) > CE(g(Z (e', A: R)), onehot(y))
(35)
where CE(,,)) is the cross entropy loss, onehotly) is the one hot embedding of label y.
Proof (Theorem 4p. Since arg max fm(z) + y, arg maxmey 9m 9m((2) (2) = y. there exist i
c]:
(y(2) >z(())
(36)
9x(x) <f((x)
Then have:
(x(2) (x) 2 fy(x) (((x))
(37)
Introducing Statement 4 of Lemma 1 and Lemma 5
9x(2T Ar)) 9y (y (ZT A R)) 2, (z, A; (2,
(38)
Moreover, since the prediction not abstained.
[z) 1,0) ti.
(39)
This directly leady the result.
17

---

Published as a conference paper at ICLR 2023
(a) Prediction Surface
(b) Float Computation
(c) SC-RFP Surface
Figure 6: The value of first element prediction vector from VGG16 model trained on CIFARIO given 2D slice centered random data from test set. (a) The wireframe represents the prediction f(z) while the surface is the sum fixed path Z (z. R). respectively. (b) The sum of float path
(x) zt (ar, A; R.). (c) The wireframe and surface prediction of SC-REP: 2 (x, A: R. + 17 (z R) with < and sum of fixed path same as (a).
zdd [x, A; R)
Theorem 2 and Theorem show that a smoothed classifier is not able to boost the performance of fixed path, while it is applied reduce the sudden change of float path in region. To be specific, if x' can be corrected by g. it is resulted from the sudden change provided by the float path. A higher confidence score of g(x") can be achieved by reducing the weight of float path during the computation path. On the other hand, if x' is Lipschitz vulnerable, then regardless of the form of smoothed classifier, cannot be fixed. This lead us the theoretical basis of SC-RFP algorithm.
Figure(ojillustie illustratts the SC-RFP by showing the prediction, fixed path and float path. We first present the prediction and the fixed path value in Figure 6(a) The float path value is then computed as z (xx A; = f(x) 2 (I, in Figure 6(b)
At last, by repressing the float value, we
achieve locally stable prediction from SC-RFP.
C.2 VERIFIABLE RADIUS
At the end of section 4.2 we propose Theorem 3 to describe the upper and lower bound of SC-RFP well the certified radius. We present the proof of Theorem Jbelow.
Theorem 3. Let N be network defined as Section 3.1 Let g be smoothed classifier that samples noise from distribution Dnoise and g' is the SC-RFP built on g. Assume that the direction of is uniformly distributed.
Al|m = |1 P( ||ll
= m)) P( |ell 12),
(40)
If arg max fy(x) = y, then
P'A > PA. < PB.
(41)
where P'A-PA are the lower bound of (x) and (x),,, FB. ps are the upper bound of D'mepy (z)) Smzzy (r)). Moreover, arg max Y (x) y for all ||e|| < R.
R = - x - (pA) -0- -
(42)
The proof of Theorem 3 can be divided into three steps. First, we show that given D Dnoises the expectation of fixed paths for the any E[ 1Z* (x + E)) = Z x (z). Consider Ç is fixed path on region R, then from Lemma
Proof.
Elg({(x))) ((x)).
(43)
Notice that, since the SC-RFP does not affect the sample of noise, then above equation holds for both g and g':
[[()))(=))) ((x))
(44)
18

---

Published as a conference paper at ICLR 2023
By applying randomized smoothing statement 1 of Lemma B(g(z)) Blg( + (z,
7 we have:
(45)
(x) Eíg' (2' (x.
where we use g' R)) to denote applying smoothing algorithm on deterministic function
(r, R:R.) Since z (R) the aggregation of all the fixed path, with Equation 43 and 44
we have:
(z,
EEg((Z (z, (x,
(46)
This means that the difference between E(g(z)) and E(g(z)) is same with that of g(2"((2) and g' (2" (x, A,
(x, (x; A))
Next, discuss how the float path affect the prediction of g(Z""(( A;R)) and g' A: (2; Given E ~ Dosise. we denote P1 as the event that fy(r + > fy(x). Since we have excluded the fixed path, P1 holds means that the float path boosts the probability of fy(x + c). However, arg max m. E Y fx(r)
repressing the float path does not alter the prediction of fy(x'). On the other hand, we denote P2 as the event that fy(x + e) fy(x). This means that the float path zT (x e,A; R)
and negalively contributes to the prediction. Then repressing the float path means that can increase the probability of y.
In other words, for any x a- repressing the float path between and x' can increase the predicted fa( + e). We assume that Pi and P2 happens with probability pı and then given certain number of sampling.
E(g)(x))) > (x), Var(g'(()) < Var(gy(2))
By applying Chebyshev Inequality, we have p'A > PA. Similarly, we also have F'B PB. Therefore, conclude the lower bound p' is larger than that of Pa. and similar to P'g.
Computing the certified radius of x then is same with that Cohen et al. 2019). Since both g and g' random function that sample noise from same distribution, the Neyman-Pearson theorem holds for both and g' Therefore, the certified radius remains unchanged.
D EXTRA TABLES AND FIGURES
This section present the complete experiment results. Table shows the certified accuracy at differ- la radius level.
Table 5 presents the experiment result of our model certified with different repression rate. Among the different repression rate, find that when 7) 0.25 SC-RFP provides the best performance increasing the model robust accuracy for perturbation with large size, while the standard accuracy and are slightly damaged. This is also observed on previous works.
Method
0.25
0.5
0.75
1.0
1.25
1.5
2.0
2.5
Clean
0.25
Cohen et al.
2019
66.0
50.2
44.2
0.0
0.0
0.0
0.0
0.0
75.3
SC
RFP
69.4
58.3
52.7
0.0
0.0
0.0
0.0
0.0
77.2
0.50
Cohen (2019)
53.4
44.7
34.0
25.4
19.5
19.5
0.0
0.0
60.3
+ SC RFP
57.3
50.5
42.4
34.9
29.5
29.5
0.0
0.0
62.7
1.00
Cohen et al. (2019)
31.2
27.1
23.2
19.3
15.3
11.9
6.9
4.5
34.7
+ SC-RFP
36.0
32.6
29.4
25.9
22.2
18.4
12.9
9.5
39.1
Table 4: Certified robust accuracy for models with different methods on CIFAR10 dataset.
Figure 7 present model trained with = 0.05 and a 0.25, but under different level of noise. We find the model trained with slightly noised sample can provide effective robustness.
19

---

Published as a conference paper at ICLR 2023
0
2 radius
0.25
0.5
0.75
1.0
1.5
2.0
Clean
0.25
Jeong & Shin
22020
59.8
49.8
Jeong et al.
2021
46.7
38.2
Cohen et al.
2019
57.9
46.4
66.1 1
+ SC-RFF
(ours)
59.4
50.3
65.8
Salman al.
(2019)
59.2
54.1
63.6
+
SC-RFP (ours 0.05)
59.6
54.5
63.8
SC-RFP (ours 0.10)
59.5
54.8
63.9
+
SC-RFP (ours 0.25)
59.8
55.4
63.6
0.50
Jeong & Shin 2020
53.7
49.9
44.7
39.3
Jeong al.
2021
39.1
34.9
30.3
26.8
Cohen et al.
2019
51.3
46.1
39.9
32.6
56.5
+ SC-RIPP
(ours)
51.1
47.3
41.5
35.6
55.9
Salman al.
(0099
52.6
48.7
44.0
39.6
56.0
+
SCCRFF (ours 0.05)
52.7
49.1
45.2
40.5
56.4
SC-RFP (ours 0.10)
52.9
49.4
45.4
40.8
56.2
SC-RFP (ours 0.25)
52.8
49.6
46.0
42.0
55.2
1.00
Jeong & Shin (2020)
40.0
38.5
35.4
32.6
28.1 1
22.6
Jeong al.
2021
29.7
26.2
23.0
20.6
15.7
12.1
Cohen et al.
2019
39.1
36.1
32.5
29.1
22.8
15.6
42.4
+ SC-RFP (ours)
39.9
36.5
33.9
31.5
25.6
19.9
42.9
Salman et al.
(2019)
39.5
37.1
34.7
31.8
26.2
20.1
42.0
+
SC-RFP (ours 0.05)
40.2
37.5
35.2
33.3
28.0
21.8
42.2
SC-RFP (ours 0.10)
39.9
38.1
35.7
33.4
28.9
23.
41.9
SC-RFP (ours 0.25)
39.7
37.8
35.9
34.2
29.6
25.2
41.6
Table 5: Certified robust accuracy for models with different methods ImageNet dataset
85 0.0
(a) ((0,0.0
(b) e N(0, 0.1)
Figure 7: Certified Accuracy of base methods and SCRFP (1 = 0.1) with different level of noise
CIFAR10. The solid and dashed lines represent benchmark and SC-RFP. The models are tested under different level of noise.
20


Reviews:
[{"review_id": "r0qdlpFEXW", "reviewer": "Reviewer_2h1E", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents SC-RFP, a novel algorithm to enhance the empirical performance (certified accuracy) of classifiers based on randomized smoothing. SC-RFP operates by reducing the contribution of neurons that change activation phase across perturbations, and is demonstrated to positively affect performance.", "summary_of_the_review": "While the algorithmic idea behind SC-RFP is novel and empirically effective, I do not believe the paper is publishable in the present form due to the quality of its presentation. However, I am willing to increase my score if the authors addressed the major weaknesses of the presentation.", "strength_and_weaknesses": "The authors divide neurons of piecewise-linear networks into \"fixed\" and \"float\" neurons, depending on whether their activation phase changes within the perturbation radius, and point out that randomized smoothing can only affect the contribution of float neurons to adversarial vulnerability. Starting from this rather intuitive observation, the authors propose to keep track of float neurons, and to reduce their effect, hence further smoothing the resulting classifier.\n\nThe empirical performance of the method (at seemingly no additional cost) is definitely appealing. The method only relies on simple intuition (a strength), but does not (as far as I understand) provide any theoretical result backing the empirical performance.\nThe randomized smoothing literature (e.g., Cohen et al 2019) provides a tight upper bound on the robustness of the smoothed classifier. Does SC-RFP alter this upper bound? \nIn Cohen et al 2019 the reported certified accuracy is the \"approximate certified test set accuracy\", which is a high-probability lower bound on the true certified accuracy. Is this the case for the provided results? Could the authors provide additional information on which statements from Cohen et al 2019 hold for SC-RFP, along with a short proof? (I believe porting some of the results will be quite immediate)\nIn general, the poor presentation of the paper makes it hard to adequately assess the authors' claims.\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bMB69dcc8A", "reviewer": "Reviewer_EMXC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 begins by defining the activation path/neuron and categorize them into fixed and float path/neuron. Then they show that smoothed classifiers cannot boost the performance of fixed paths. Based on this observation, they then proposed their algorithm -- SC-RFP. SC-RFP down weights the float paths, in other words, they want the smooth out the float paths. Experimentally, they report the proportion of fixed neurons and concluded that majority of the neurons are not affected by SC-RFP. They also show that their method (SC-RFP) can achieve a better certified robustness on ImageNet comparing with many recent works.", "summary_of_the_review": "This is a solid paper. The reasoning makes sense, and the proposed algorithm has decent improvement.", "strength_and_weaknesses": "Strength:\n- Claims are well supported and the design of SC-RFP is reasonable.\n- SC-RFP provides decent improvement over some prior work. \n\nWeakness:\n- One major concern is the lack of comparison with related work [1]. I believe this work also decompose the ReLU network in to regions formed by linear hyperplanes (although they are not based on smoothing).\n- What is the shift parameter of \\phi_i? \n\n[1] Jordan, Matt, Justin Lewis, and Alexandros G. Dimakis. \"Provable certificates for adversarial examples: Fitting a ball in the union of polytopes.\" Advances in neural information processing systems 32 (2019).\n\nMinor:\n- For the definition of U_i in page 3, should s_i be \\gamma_i instead?\n- There are many notations, having some figures to make the definition and lemmas more intuitive would be great.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KRFaEY0mGV", "reviewer": "Reviewer_Aniy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a framework to decompose a neural network based on its neurons' activation status. Then the authors tried to explain adversarial examples and randomized smoothing based on this framework, and proposed a method to repress the float path to achieve better certified robustness.", "summary_of_the_review": "In general, I think the author's high-level intuition is interesting and this is a good research perspective. But I found some flaws in the author's claims. So I encourage the authors to clarify them in a revised version.", "strength_and_weaknesses": "Strength:\nRecently researchers started to look at the activation space of neural nets for adversarial robustness. This paper is also from this perspective but combines it with randomized smoothing. \n\nWeakness:\n1. I found some notation issues in the paper. For example:\n1.1 in equation (4), the expectation $E[g_m(x')=y]$ is unclear to me. Should there be an indicator function, as $1_{g_m(x')=y}$ in the expectation? Also, I think it should be $\\forall x'\\in B $ instead of $\\forall x\\in B $.\n1.2 In Definition 1, the meaning of $(i, j)\\in \\mathcal{I}$ also seems unclear to me (does that mean \"index\"?). I think it would be better to define it in the statement.\n1.3 In Equation (8), the authors used $\\cap$ (intersection) instead of $\\cup$ (union), which contradicts the sentence above it. I assume the sentence above Eq (8) should be \"intersection\".\n1.4 It seems to me that the authors used $\\mathcal{R}$ and $\\mathbb{R}$ interchangeably for the activation region.\n2. In the proof of Lemma 1 the authors use batch normalization, but the conditions of Lemma 1 do not include it. I am wondering why batch normalization is needed in the proof.\n3. Statement 4 of Lemma 2 is unclear to me. Proof of it in the appendix is also not so convincing. Do the authors assume the activation is always ReLU in this Lemma, or it can be any function such as sigmoid? If it is not linear, I don't think we can replace a finite difference with a simple Jacobian, which is claimed in the proof. Also, even if its a fixed path, the output can also change because the activation is not constant. So the statement that $Z^I(x',A,R)=Z^I(x',A',R)$ is not clear to me. Did I miss anything here?\n4. I think there is an important reference missed: Zhang et al \"A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks\", ICML 2022. This work also studied the adversarial examples in the activation space of ReLU networks.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AnaRKkZflVF", "reviewer": "Reviewer_UkvR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 divide computational graph of the neural network into the fixed path and float path and then shows the improvement of robust accuracy is mainly gained from correcting the vulnerability floating neurons. Specifically, the neural network graph is first divided into several activation regions and thus the output of layer i could be decomposed into the combination on those regions. Then based on whether the prediction would change or not, it defines the float and fixed neurons. The float path then could defined if there exists any neurons in the paths. According to the definition, the margin change in the output could be found not related with the fixed path. Therefore, the paper proposes SCRFP that empirically count those neurons that the change of prediction is in a certain region by adding Gaussian noise. The experiment shows the proposed method achieve a better clean accuracy with the same robust radius.", "summary_of_the_review": "The paper proposes an interesting perspective to understand different neurons' roles in the random smoothing procedure and then proposes a way to increase the performance of random smoothing. The proposed method is novel and could be impactful. However, the paper lacks clarity on how the lemma and definition and make the paper not easy to follow.", "strength_and_weaknesses": "Pros:\n1. The proposed idea is quite novel and could be impactful to understand the model's robustness.\n2. The proposed method is backed with comprehensive theoretical analysis.\n3. The proposed method shows a clear improvement on the clean accuracy.\n\n\nCons:\n1. It is not clear whether the proposed assumption that there only exists fixed and float path is true. Or in other words, it is not trivial to set a threshold to determine which neurons would be regarded as float neurons or fixed neurons. The BinomPValue is used however it is not sure it matches the definition in the theoretical analysis.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster