Incremental Randomized Smoothing Certification
Authors: Shubham Ugare
Tarun Suresh
Debangshu Banerjee
Gagandeep Singh
Sasa Misailovic
Venue: ICLR 2024 poster (2024)
Keywords: Robustness
Verification
Certification
Approximation
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Randomized smoothing-based certification is an effective approach for obtaining robustness certificates of deep neural networks (DNNs) against adversarial attacks. This method constructs a smoothed DNN model and certifies its robustness through statistical sampling, but it is computationally expensive, especially when certifying with a large number of samples. Furthermore, when the smoothed model is modified (e.g., quantized or pruned), certification guarantees may not hold for the modified DNN, and recertifying from scratch can be prohibitively expensive.

We present the first approach for incremental robustness certification for randomized smoothing, IRS. We show how to reuse the certification guarantees for the original smoothed model to certify an approximated model with very few samples. IRS significantly reduces the computational cost of certifying modified DNNs while maintaining strong robustness guarantees. We experimentally demonstrate the effectiveness of our approach, showing up to 4.1x certification speedup over the certification that applies randomized smoothing of the approximate model from scratch.

Published as a conference paper at ICLR 2024
INCREMENTAL RANDOMIZED SMOOTHING CERTIFICATION
Shubham Ugare', Tarun Suresh', Debangshu Banerjee', Gagandeep Singh 12, Sasa Misailovic' 'University Illinois Urbana- Chaama-Champ VVWare Research [sugare2, tsuresh3, db21, ggnds, mi misailo]s@e... www.oo/iiiiiinss......oeeo....ee edu
ABSTRACT
Randomized smoothing- -based certification an effective approach for obtaining robustness certificates of deep neural networks (DNNs) against adversarial attacks. This method constructs a smoothed DNN model and certifies its robustness through statistical sampling, but it is computationally expensive, especially when certifying with a large number of samples. Furthermore, when the smoothed model is modified (e.g., quantized or pruned), certification guarantees may not hold for the modified DNN, and recertifying from scratch can be prohibitively expensive.
We present the first approach for incremental robustness certification for random- ized smoothing, IRS. We show how to reuse the certification guarantees for the original smoothed model to certify approximated model with very few samples. IRS significantly reduces the computational cost certifying modified DNNs while maintaining strong robustness guarantees. We experimentally demonstrate the ef- fectiveness of our approach, showing up to 4. Ix certification speedup over the cer- tification that applies randomized smoothing of approximate model from seratch.
INTRODUCTION
Ensuring the robustness of deep neural networks (DNNs) to input perturbations is gaining increased attention from both users and regulators in various application domains (Bojarski et al. 2016 Amato et al. 2013 Julian et al., 2018 ISO). Out of many techniques for obtaining robustness certificaties, statistical methods currently offer the greatest scalability. Randomized smoothing (RS) a popular statistical certification method by constructing a smoothed model from a base network f under noise (Cohen et al., ) To certify the model g on an input, RS certification checks if the estimated lower bound on the probability of the top class is greater than the upper bound on the probability of the runner-up class (with high confidence). RS certification computes the certified accuracy metric the DNN on the set of test inputs as proxy for the DNN robustness. However, despite its effectiveness, RS-based certification can be computationally expensive as it requires DNN inference on a large number of corruptions per input.
The high cost of certification complicates the DNN deployment process, which has become increas- ingly iterative: the networks often modified post-training improve their execution time and/or accuracy. Especially, deploying DNNs on real-world systems with bounded computing resources (e.g.. edge devices or GPUs with limited memory), has led to various techniques for approximating DNNs. Common approximation techniques include quantization reducing the numerical precision of weights (Fiesler et al. 1990, Balzer al. 1991), and pruning removing weights that have minimal impact on accuracy (Janowsky 1989
Reed 1993).
Common to all of these approximations is that the network behavior (c.g., the classifications) remains the same on most inputs, its architecture does not change, and many weights are only slightly changed. When user seeks select a robust and accurate DNN from these possible approximations, RS needs to be performed to compute the robustness of all candidate networks. For instance, in the context of approximation tuning, there are multiple choices for approximation where different quantization or pruning strategies are applied at different layers. Tools such as (Chen al. 20 8b Sharif et al.) 2019 Zhao et al., 2023) use approximations iteratively and test the network at each step. To ensure DNN robustness when using such tools, one would need to check certified accuracy, computed using RS on test data in each step. However, performing RS to compute certified accuracy from scratch can take hours shown in experiments even for single network (with only 500 test images).

---

Published as a conference paper at ICLR 2024
Therefore, major encumbrance of almost all existing RS-based certification practices in the above setting, is that the expensive certification needs to be re-rum from scratch for each approximate network. Overcoming this main limitation requires addressing the following fundamental problem:
How can we leverage the information generated while certifying a given network to speed up the certification of similar networks?
This Work. We present the first incremental RS-based certification framework called Incremental Randomized Smoothing (IRS) to answer this question. The primary objective of our work is to improve the sample complexity of the certification process of similar networks on a predefined test set. Improved sample complexity results in overall speedup in certification, and it reduces the energy requirement and memory footprint of the certification. Given a network and its smoothed version and modified network f" with its smoothed version g IRS incrementally certifies the robustness of g" by reusing the information from the execution of RS certification on
IRS optimizes the process of certifying the robustness of smoothed classifier g" on an input æ, by estimating the disparity (z the upper bound on the probability that outputs of f and fr are distinct. Our new algorithm is based on three key insights about disparity:
1. Common approximations yield small Sz values - for instance, it is below 0.01 for int8 quantization for multiple large networks in our experiments.
2. Estimating &z through binomial confidence interval requires fewer samples it is close to 0 it is, therefore, less expensive to certify with this probability than directly working with lower and upper probability bounds in the original RS algorithm.
3. We can leverage Sz alongside the bounds in the certified radius of g around x to compute the certified radius for g" thus soundly reusing the samples from certifying g-
We extensively evaluate the performance of IRS when applying several common DNN approximations such pruning and quantization on state-of-the-arr DNNs on CIFARIO (ResNet-20, ResNet-1 and ImageNet (ResNet-50) datasets.
Contributions. The main contributions of this paper are:
We propose a novel concept of incremental RS certification of the robustness of the updated smoothed classifier by reusing the certification guarantees for the original smoothed classifier.
We design the first algorithm IRS for incremental RS that efficiently computes the certified radius of the updated smoothed classifier.
We present an extensive evaluation of the performance of IRS speedups of to 4.1x over the standard non-incremental RS baseline on state-of-the-ar classification models.
IRS code is available at paattp:://gitubee htt.:hhh.coooooceoeoooooeeeeeeee wwwp///....ooe.e.ee..oooo......e www.ar/ennnnneeaaaae -DN-------NNN---NN ONN-Verlficat
BACKGROUND
Randomized Smoothing, Let f R" + y be an ordinary classifier. A smoothed classifier g 1 y can be obtained from calculating the most likely result of f(*+e) where (0,00
g(x) == arg max (f( + c) =
cEY/
The smoothed network g satisties following guarantee for a single network f: Theorem 1. [From (Chhen et al. 2019 Suppose E Y. PA PB E [0, if
Pelf(z + ca) 2 PA 2 PB 2 max P. (f + + = c).
then g(x + + CA for all 5 satisying ||0||2 S ( (PA) - (PB)) --1(BB) where -- denotes the inverse of the standard Gaussian CDF.
Computing the exact probabilities P.(f(z +)= is generally intractable. Thus, for practical applications, CERTIFY (Cohen et al. 2019) (Algorithm[] T utilizes sampling: First, takes no samples to determine the majority class, then samples to compute a lower bound PA to the success probability with confidence 1 a via the Clopper-Pearson lemma (Clopper and Pearson 1934). If pA > 0.5, we
set = 1 PA and obtain radius R = e.e- -.- 1-11ppp... (Px)) via Theorem else we return ABSTAIN.
2

---

Published as a conference paper at ICLR 2024
IRS
P
f
Smooth
Certify
0 (p:) 1 (pa)
10,
2
Certified Radlus for
Compute 5,
Update
Pufee Pl+ 6
( [1b7pp (ps G, (og + (,)
Cortify
2
f
g
Certified Radius for g
Figure 1: Workflow of IRS from left to right. IRS takes the classifier f and input x. IRS reuses the PA and PB estimates computed for f on by RS. IRS estimate Ç. from f and f". For the smoothed classifier gd obtained from any of the approximate classifiers f computes the certified radius by combining PA and pB with Ez.
DNN approximation. DNN weights need to be quantized to the appropriate datatype for deploying them various edge de- vices. DNN approximations are used to compress the model size the time of de- ployment, to allow inference speedup and energy savings without significant accuracy loss. While IRS can work with most of these approximations, for the evaluation, we fo- cus on quantization and pruning as these are the most common ones (Zhou et al. 2017 Frankle and Carbin 2019p.
Algorithm RS certification (Cohen al. 2019)
Inputs: DNN, a: standard deviation, a: input to the DNN. no: number of samples to predict the top class, n. number of samples for computing PA. a: confidence parameter
1: function CERTIFY(J; æ, rAp, n, (:)
2: counts + SampleUnderNoise(ff.. no,
3: c + index in countsa
4: counts SampleUnderNoise(ff.
5:
PA < LoverContddeeeeBouuccoou....
6: PA then
7:
return prediction é^ and radius - (pa)
8: else
9: return ABSTAIN
INCREMENTAL RANDOMIZED SMOOTHING
Figure SaureTilluee iillsttrates the high-level idea behind the workings of IRS. It takes as input the classifier f. the updated classifier f", and input æ. Let y and g" denote the smoothed network obtained from and fr using RS respectively. IRS reuses the PA and pg estimates computed for g to compute the certified radius for g".
3.1 MOTIVATION
Insight 1: Similarity in approximate networks We observe that for many practical approximations, and fP produce the same result on most inputs. Table 1: Average Ce with 1000
In this experiment, we estimate the disparity between and fo on Gaussian corruptions of the input x. We compute lower confidence bound Eu such that (f([(x +e) f2( + +)) S C. for (0,
samples for various approximations.
CIFAR10 ResNet-110 10
ImageNet
ResNet-50
Table 1 presents empirical average C. for int8 quantization and pruning 10% lowest magnitude weights for some of the networks in experiments computed over 500 inputs. We compute S. value as the binomial confidence upper limit using (Clopper and Pearson 1934 method with 1000 samples with 1. The results show that the value is quite small in all the cases.
in18 prune
0.009
0.006
0.010
0.008
Insight 2: Sample reduction through Sa estimation We demonstrate that Ço estimation for ap- proximate networks is more efficient than running certification from scratch. Fig. 2 shows that for the fixed target error X. confidence (1 - a) and estimation technique, the number samples required for estimation peaks, when the actual parameter value is around 0.5 and is smallest around
3

---

Published as a conference paper at ICLR 2024
the boundaries. For example, when x 0.5% and 0.01 estimating the unknown binomial proportion will take 41, 500 samples the actual parameter value is 0.05 while achieving the same target error and confidence takes 216, 900 samples (5.22x higher) if the actual parameter value is 0,5. As observed in the previous section, Sx 's value for many practical approximations is close to O.
Leveraging the observation shown in Fig. and given actual value S is close O, estimating Se with existing binomial proportion estimation techniques is efficient and requires a smaller number of samples. In Appendix A.7] we show the distribution of PA and pn for various cases. We see that PA and pa do not always lie close to O or and have a more dispersed distribution. Thus, estimating those requires more samples. Prior work (Thulin) 2013) has the- oretically shown that the expected length of the confidence interval for Clopper-Pearson fol- lows a similar trend as in Fig- 2 This theoretical result supports our observation. We show in Appendix A.I] that this observation is not contingent on a specific estimation method and holds for other popular estimation techniques, e.g.. (Wilson. 1927). (Agresti and Coull 1998).
Insight 3: Computing the approximate network's cer- tified radius using Eo For certification of the approximate network g". our main insight is that estimating Sa and using that value to compute the certified radius is more efficient than computing RS certified radius from scratch. The next theorem shows how to use estimated value of Ca to certify gd (the proof is in Appendix (A2):
20000
Required Sample Size
1.00
130000
100000
000c0
Theorem 2. If classifier fe is such that for all x E RT. ,P,((( + E) * fo(r + E)) S Su. and classi-
fier f satisfies (f(f(x + E) = CA) 2 PA 2 PB Z
Actual Binomial Proportion Value
maxeter P.(f(z + c) = c) and PA S5 2 PB
then 9d satisfies gx + 6) = CA for all 8 satisying
Figure 2: The number of samples for the Clopper-Pearson method to achieve a target error X with confidence (1 a)..
|10||2 S ( (x)) + "pp + (.))
Theorem D considers standard RS for a single network. Our Theorem shows how to use the estimated value of Eo to transfer the certification guarantees across two networks f and fP.
3.2 IRS CERTIFICATION ALGORITHM
The Aggorithmpprestt presents the pseudocode for the IRS algorithm, which extends RS certi- fication from Algorithm [ The algorithm takes the modified classifier f and certifies the robustness of g" around x. The input n denotes the number of Gaussian corruptions used by the algorithm.
Algorithm IRS algorithm: Certification with cache
Inputs: f": DNN obtained from approximating f. a: stan- dard deviation, x: input to the DNN, ny: numher of Gaussian samples used for certification, Cy: stores the information be reused from certification of f. and ac: confidence parameters. 7: threshold hyperparameter to switch between estimation methods
1: function CERTIFYIRS((") a. Mp:
The IRS algorithm utilizes cache Cj. which
2:
ćΛ < top index in Cý [x]
stores information obtained from the RS exe-
3:
Pa <- lower confidence of from [w]
cution of the classifier for each input x. The cached information is crucial for the opera- tion of IRS. Cj stores the top predicted class
4:
PA < < then
5:
C. < Fstimatc7cta(fP.og o,,, mp. Cc,)
6:
if PA S > 1/2 then
index e and its lower confidence bound PA for f on input x.
7:
return prediction éλ and radius o.- -p- (x)
8:
else
The standard RS algorithm takes conser-
9:
counts +- SannpeeUnderNoise( ( np: 0)
vative value of pB by letting PB This works reasonably well in practice and
PA-
10:
P'A + LLooeronnideeeeeooee
11:
coants((a), np, (a: + ac²)
simplifies the computation of certified radius
12:
if P'A > 1/2 then
- - --1(pp) {(0-1(pa) to o (pA). We make a similar choice in IRS, which sim- plifies the certified radius calculation from { 'pp - (.)- $- (pn + (2)) of Theorem 2 to o 'PAA - (x) as we state in the next theorem
13:
return prediction ĆΛ and radius oD (P'a)
14: return ABSTAIN
(the proof is in Appendix A.2
4

---

Published as a conference paper at ICLR 2024
Theorem 3. PA Sx 2 then o
10p0pppp.. '(PA (x)
'pA (x)
+
(PD + Sx))
As per our insight 2 (Section 3.1 binomial confidence interval estimation requires fewer samples for binomial with actual probability close to or 1. IRS can take advtange of this when PA is not close to 1. However, when PA is close to then there is no benefit of using Ca-based certified radius for g". Therefore, the algorithm uses threshold hyperparameter y close to that is used to switch between certified radius from Theorem@aan and standard RS from Theorem
the PA is less than the threshold y, then an estimate of So for classifier f and the classifier of is computed using the EstimateZZea function. We discuss EstimateZZeaa procedure in the next section. the PA Sr is greater than
2' then the top predicted class in the cache is returned as the prediction with the radius σ b (pA - ()) as computed in Theorem
In case, PA is greater than the threshold 7, similar standard RS, the IRS algorithm draws n2 samples of fx <) by running n" noise-corrupted copies of x through the classifier f". The function SampleUnderNoise((
Rp. or) in the pseudocode draws ny samples of noise, 61 c.... Cnp ~ (0,, o² runs each + through the classifier f", and returns a vector of class counts. If the lower confidence bound is greater than 1. the top predicted class is returned as the prediction with a radius based on the lower confidence bound PA-
the function does certify the input in both of the above cases, returns ABSTAIN.
The hyperparameters and og denote confidence of IRS results. The IRS algorithm result is correct with confidence at least - (a + ac)) For the case PA 2 ", this holds since we follow the same steps as standard RS. The function LowerContideneeBBunddcooo countss Np, 1 - (a + ac)) in the pseudocode returns one-sided 1 (a ag) lower confidence interval for the Binomial parameter p given a sample counts[čal ~ Binomiia (nip. pp.p. p). We next state the theorem that shows the confidence of IRS results in the other case when PA (the proof is in Appendix A.2
Theorem 4. (f +c) f=(x + c)) > 1- - Ce with confidence at least 1 - ozę- If classifier satisfies [f( + CA) 2 PA with confidence at least 1 Then for classifier f", P. + cA) 2 PA Se with confidence at least (a aa)
3.3 ESTIMATING THE UPPER CONFIDENCE BOUND Cx
In this section, we present our method for estimating Gr such that IP. (f( fP o)) G with high confidence (Algorithm 3p. We use the Clopper-Pearson (Clopper and Pearson 1934) method to estimate the upper confidence bound Ça.
We store the seeds used for randomly gener- ating Gaussian samples while certifying the function f in the cache, and we reuse these seeds to generate the same Gaussian samples. seeds(0 [i] stores the seed used for generating i-th sample in the RS execution of f, and predictions{i] stores the prediction of f on the corrsponding + e. We evaluate fr on each corruption generated from seeds and match them to predictions by f. cy and cyr represent the top class prediction by f and fr respectively. n. is the count of the number of corruptions e such that f and fP not match on æ +
Algorithm 3 Estimate Sx.
Inputs: f": DNN obtained from approximating f. stan- dard deviation, input the DNN, ny: number of Gaussian samples used estimating Çe, Cy: stores the information to be reused from certification of J. ax:: confidence parameter Output: Estimated value of &x
1: function ESTIMATEZETA((" o, J. Thp Cpp,Cy,,o ac)
2: n& +0
3: seeds seeds for original samples from [xc
4: predictions +- f's predictions on samples from Cy [x]
5: for E (1.... do
6:
~ (0, o²1) using seeds[i]
7:
Cj +- predictions(]]
8:
cfr + (x f"
9: na c na + [(ey # cyp)
The function UpperConffidnceeBundrrss pp. 1 - ox)) in the pseudocode returns one- sided - ag upper confidence interval for the Binomial parameter given a sample na ~ Binomial np. p). We compute this upper confidence bound using the Clopper-Pearson method. This is similar to how the lower confidence bound is computed in the standard RS Algorithm | is sound since the Clopper-Peand Pearson method is conservative.
return UpperCoofideneeBundlraa Up. ac)
5

---

Published as a conference paper at ICLR 2024
Reusing the seeds for generating noisy samples does not change the certified radius and is 2x faster compared to naive Monte Carlo estimation of (e with fresh Gaussian samples. Storing the seeds used in the cache results in small memory overhead (less than 2MBs for our largest benchmark). We use the same Gaussian samples for estimations of PA and C.- This is equivalent to estimating two functions, p(X) and (X),, of a random variable X, where the same set of samples of X can be employed for their respective estimations. Theorem makes no assumptions about the independence of estimating PA and Sa. thus we can soundly reuse the same Gaussian samples for both estimations.
4 EXPERIMENTAL METHODOLOGGY
Networks and Datasets. We evaluate IRS on CIFAR-I0 (Krizhevsky et al.) and ImageNet (Deng et al.] (2009). On each dataset, we use several classifiers, each with a different a's. For an experiment that adds Gaussian corruptions with a to the input, we use the network that trained with Gaussian augmentation with variance a². On CIFAR-10 we use the base classifier a 20-layer and 1 110-layer residual network. On ImageNet our base classifier is a ResNet-50.
Network Approxinations. We evaluate IRS multiple approximations. We consider 16 (fp16), 6 (b and int8 quantizations (Section 5.1] We show the effectiveness of IRS on pruning approximation in Section 5.3 For int8 quantization, we use dynamic per-channel quantization mode. from (asske et al. 2019 library. For float16 and bfloat16 quantization, we change the data type of the DNN weights from float32 to the respective types. We perform float32, float16, and 6 inferences on the GPU and int8 inferences on CPU since Pytorch does not support int8 quantization for GPUs yet (PyTorch). For the pruning experiment, perform the lowest weight magnitude (LWM) pruning. The top-1 accuracy of the networks used in the evaluation and the approximate networks is discussed in Appendix A..3
Experimental Setup. We ran experiments on a 48-core Intel Xeon Silver 4214R CPU with 2 NVidia RTX A5000 GPUs. IRS implemented in Python and uses PyTorch 2.0.1. Paszke al. 2019).
Hyperparameters. We use confidence parameters a 0.001 for the certification of g. and ag = 0.001 for the estimation of Çz. To establish a fair comparison, we set the bascline confidence with og = + ag- = 0.002. This choice ensures that both the baseline and IRS, provide certified radii with equal confidence. We use grid search to choose an effective value for 7/. A detailed description of our hyperparameter search and its results are described in Section 5.4
Average Certified Radius. We compute the certified radius r when the certification algorithm did not abstain and returned the correct class with radius r, for both IRS (Algorithm 2 and the baseline (Algorithm Tp. In other cases, we say that the certified radius r = O. We compute the average certified radius (ACR) by taking the mean of certified radii computed for inputs in the test set. Higher ACR indicates stronger robustness certification guarantees.
Speedup. IRS is applicable while certifying multiple similar networks, where it can reuse the certifi- cation of one of the networks for faster certification of all other similar networks. We demonstrate the effectiveness of IRS by comparing IRS's certification time for these other similar networks with the baseline certification from scratch. We do not include the certification time of the first network in the comparison it adds the same time for both IRS and baseline.
5 EXPERIMENTAL RESULTS
We now present our main evaluation results. We consider the float32 representation of the DNN as f and a particular approximation as f2. However, IRS can be used with any similar and fPs, e.g.. where f is an int8 quantized network and f" is the float32 network. In all of our experiments, we follow a specific procedure:
1. We certify the smoothed classifier g using standard RS with sample size of n.
We approximate the base classifier f with fr.
Using the IRS, we certify smoothed classifier gd by employing Algorithm 2 and utilizing the cached information C, obtained from the certification of g-
We compare IRS to the bascline that uses standard non- con-incremental RS (Algorithm I. to certify g". Our results compare ACR and certification time between IRS and the baseline for various no values.

---

Published as a conference paper at ICLR 2024
5.1 EFFECTIVENESS OF IRS
We compare the ACR and the certification time of the baseline and IRS for the common int8 quantization. We use n = 10 samples for certification of g. For certifying g", we consider Up values from (5%.... .50%) of n and a = 1. We perform experiments on 500 images and compute the total time for certifying g".
3.0
2.0
3.0
80
0390
2345
03300
2.555
0,990
2.35
US82
0.59
0.58
3.99
EWITgE
eseraee
(a) ResNet-110 CIFAR-10
(b) ResNett-S on ImageNet
Figure Total certification time versus ACR with 1.0.
Figure presents the comparison between IRS and RS for int8 quantization. The x-axis displays the ACR and the y-axis displays the certification time. The plot consists of 10 markers each for the IRS and the baseline representing specific value of ny. Expectedly, the higher the value of np. the higher the average time and ACR. The marker coordinate denotes the ACR and the time for an experiment. In all the cases, IRS consistently takes less certification time to obtain the same ACR.
Figure 3a for ResNet- 10 on CIFAR10 10, shows that IRS reduced the certification time from 2.91 hours (baseline) 0.71 hours, resulting in time savings of 2.12 hours (4. Ix faster). Moreover, we see that IRS achieves an ACR of more than 0.565, whereas the baseline does not reach this ACR for any of the Up values in our experiments.
Figure 3b for ResNet-50 on ImageNet, for certifying ACR of 0.875, IRS substantially reduced certification time from 27.82 hours (baseline) to 22.45 hours, saving approximately 5.36 hours (1.24x faster). Additionally, IRS achieved an ACR of 0.90 and reduced the certification time from 53.93 hours (baseline) to 40.58 hours, resulting in substantial time savings of 13.35 hours (1.33x faster).
5.2 IRS SPEEDUPS ON DIFFERENT QUANTIZATIONS
Next, we study if IRS can handle other kinds of quantization. We perform exper- iments for 10 different values of n. along with distinct approximations, and 3 values of Since this would take months of ex- periment time with n and Пp values from Section for the rest the experiments we use smaller values for these parame- ters. In these experiments, we compute the relative speedup due to IRS in com- parison the baseline. We use n 104 for samples for certification of For cer- tifying gd, we consider np values from f1%... 10%) of For CIFAR10, we consider a E {0.25, 0.5, 1.0), and for Ima- geNet, consider
Table 2: Average IRS speedup for combinations of quan- tizations and a's.
Dataset
Architecture
Quantization
fp16
bf16
int8
0.25
1.37x
1.29x
1.3x
CIFARIO
ResNet-20
0.5
1.79x
1.7x
1.77x
1.0
2.85x
2.41x
2.65x
0.25
1.42x
1.35x
1.29x
CIFARIO
ResNet-110
0.5
1.97x
1.74x
1.77x
1.0
3.02x
2.6x
2.6x
0.5
1.2x
1.14x
1.19x
ImageNet
ResNet-50
1.0
1.43x
1.31x
1.43x
2.0
2.04x
1.69x
1.80x
We validated that the speedups for int8 quantization in this section for MirNNet-5-ImmageNe and ResNet-110-CIFAAIIO
{0.5, 1.0, 2.0} as in the previous Cohkn et al.
2019
similar to those studied in Section
To quantify IRS's average speedup over the baseline, we employ an approximate area under the curve (AOC) analysis. Specifically, plot the certification time against the ACR. In most cases, IRS
7

---

Published as a conference paper at ICLR 2024
certifies larger ACR compared to the baseline, resulting in regions the x-axis where IRS exists but the baseline does not. To ensure a conservative estimation, we calculate the speedup only within the range where both IRS and the baseline exist. We determine the speedup by computing the ratio of the AOC for IRS to the AOC for the baseline within this common range. Table 2table2[summn summarizes the average speedups for all quantization experiments.
We observe that IRS gets larger speedup for smoothing with larger a since on average the PA values smaller. Appendix A.7 presents further justification for this observation. Appendix A.9 presents further experiments with all combinations of DNNs, o, and quantizations.
5.3 IRS SPEEDUPS ON PRUNED MODELS
In this experiment, we study IRS's abil- ity to certify beyond quantized models. We employ 4 unstructured pruning, which prunes the fraction of the lowest 4 mag- nitude weights from the DNN. Table presents the average IRS speedup for DNNs obtained by pruning 5%, 10% and 20% weights. The speedups range from 0.99x to 2.7x. As the DNN is pruned more aggressively, it's expected that IRS's speedup will be lower. This is due to higher values C. associated with aggres- sive pruning. In Appendix A.4 we provide average &a values for all approximations. Compared to pruning, quantization typi- cally yields smaller far values, making IRS more effective for quantization.
Table 3: Average IRS speedup for combinations of prun- ing ratio and a's.
Dataset
Architecture
Prune
5%
10%
20%
0.25
1.3x
1 1.25x
0.99x
CIFARIO
ResNet-20
0.5
1,63x
1.39x
1.13x
1.0
2.5x
2.09x
1.39x
0.25
1,35x
1.24x
1.04x
CIFARIO
ResNet-1
0.5
1,83x
1.6x
1.23x
1.0
2.7x
2.25x
1.63x
0.5
1.19x
1.04x
0.87x
ImageNet
ResNet-50
1.0
1.36x
1.15x
0.87x
2.0
1.87x
1.54x
1.01x
5.4 ABLATION STUDIES
Next, we show the effect of y on ACR. In Appendix A.5
we show IRS speedup on distinct values of n.
Sensitivity to threshold y. For each DNN archi- tecture, we chose the hyperparameter 7 by run- ning IRS to certify a small subset of the valida- tion set images for certifying the int8 quantized DNN and comparing the ACR. The choice of 7 has no effect on certification time, we perform
Table 4: ACR for each 7.
7
CIFAR10
CIFARIO ResNet-110
ImageNet
ResNet-20
ResNet-50
0.9
0.438
0.436
0.458
0.95
0.442
0.439
0.464
0.975
0.445
0,441
0.465
n, inferences in both cases, PA < Y and Pa 7
0.99
0.446
0.443
0.466
We use the same for each DNN irrespective of
0.995
0.445
0.442
0.467
the approximation and a. We use the grid search
0.999
0.444
0,442
0.464
to choose the best value of gamma from the set (0.9, 0.95, 0.975, 0.99, 0.999). Table presents the ACR obtained for each 7. We chose as 0.99
for CIFAR10 networks and 0.995 for the ImageNet networks since they result in the highest ACR.
RELATED WORK
Incremental Program Verification. The scalability of traditional program verification has been significantly improved by incremental verification, which has been applied on an industrial scale (Johnson et al. 2013 O'Hearn| 2018: Stein al.) (02T). D.. Incremental program analysis tasks achieve faster analysis of individual commits by reusing partial results (Yang al. 2009), constraints (Visser ct al. 2012), and precision information (Beyer et al. 2013) from previous runs.
Incremental DNN Certification.
Several methods have been introduced in recent years to certify
the properties of DNNs deterministically (Tjeng et al. 2017 Bunel et al., 2020 Katz et al. 2017 Wang et al. 2021b Laurel et al. [2022] 2023) and probabilistiely (Cohen al. (209). Researchers
used incremental certification speed up DNN certification (Fischer et al.] 2022b 2 Ugare et al. 2022
Wei and Liu 2021
Ugare al. 2023 Ugare al.) these works apply complete and incomplete
8

---

Published as a conference paper at ICLR 2024
deterministic certification using formal logic cannot scale to e.g., ImageNet. In contrast, propose incremental probabilisticc certification with Randomized Smoothing, which enables much greater scalability.
Randomized Smoothing, Cohen ct al. 2019) introduced the addition of Gaussian noise to achieve
12-robustness results. Several extensions this technique utilize different types of noise distributions and radius calculations to determine certificates for general 1,-balls. Yang et al. (2020) and Zhang (2019), Wang
al. (2020) derived recipes for determining certificates for p = 1, 2, and xc. Lee
et al. (2221a,, and Schuchardt et al. (2021) presented extensions to discrete perturbations such as To perpeurrbaaions, while Bojchheski al. (2023), Gao et al. (2020). Levine and Feizi (2020), and Liu et al. (202T) explored extensions to graphs, patches, and point cloud manipulations. Dvijotham et al. (2020) presented theoretical derivations for the application of both continuous and discrete smoothing measures, Mohhaaaaa et al. (2020) improved certificates by using gradient information. Horváth al. 2022) used ensembles to improve the certificate.
Beyond norm-balls certificates, Fischer et al. (2020) and Li et al. 2021 presented how geometric operations such as rotation or translation can be certified via Randomized Smoothing. yyh Chiang et al. (2022) and Fischer et al. (2022a) demonstrated how the certificates can be extended from the setting of classification to regression (and object detection) and segmentation, respectively. For classification, Jia et al. (2020) extended certificates from just the top-1 class to the top-k classes, while Kumar et al. (2020) certified the confidence of the classifier, not just the top-class prediction. Rosenfeld et al. (2020) used Randomized Smoothing defend against data poisoning attacks. These RS extensions (using different noise distributions, perturbations, and geometric operations) are orthogonal the standard RS approach from Cohen al. (2019). While these extensions have been shown to improve the overall bredth of RS, IRS is complementary to these extensions.
7 LIMITATIONS
We showed that IRS effective certifying the smoothed version of the approximated DNN. However, there are certain limitations to the effectiveness of IRS. First, the IRS algorithm requires a cache with the top predicted class index, its lower confidence bound, and the seeds for Gaussian corrptiion obtained from the RS execution of the original classifier. However, storing this additional information is reasonable since it has negligible memory overhead and is a byproduct of certification (as trustworthy ML matures, anticipate that this information will be shipped with pre-certified networks for reproducibility purposes).
The smoothing parameter used in IRS affects its efficiency, with larger values of a generally leading to better results. As a consequence, we observed a smaller speedup when using a smaller value of (e.g., 0.25 on CIFAR compared to a larger value (e.g., 1 on CIFAR10). The value of offers trade-off between robustness and accuracy. By choosing a larger a, one can improve robustness but it may lead to a loss of accuracy in the model.
IRS targets fast certification while maintaining a sufficiently large radius. Therefore, we considered np smaller than 50% of for our evaluation. However, IRS certified radius can be smaller than the non-incremental RS, provided the user has a larger sample budget. In our experiment in Appendix A.6 A.6 we test IRS on larger np and observe that IRS is better than baseline for np less than 70% of n. This is particularly advantageous when computational resources are limited.
CONCLUSION
We propose IRS, the first incremental approach for probabilistic DNN certification. IRS leverages the certification guarantees obtained from the smoothed model to certify smoothed approximated model with very few samples. Reusing the computation of original guarantees significantly reduces the computational cost of certification while maintaining strong robustness guarantees. IRS speeds up certification up to 4x over the standard non-incremental RS baseline on state-of-the-a classification models. We anticipate that IRS can be particularly useful for approximate tuning when the users need to analyze the robustness of multiple similar networks. Further, one can easily ship the certification cache allow other users to further modify these networks based on their specific device and application needs and recertify the new network. We believe that our approach paves the way for efficient and effective certification of DNNs in real-world applications.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their comments. This research was supported in part by NSF Grants No. CCF-1846354, CCF-2217144, CCF-2238079, CCF-2313028, CCF-2316233, CNS- 2 2148583, USDA NIFA Grant No. NIFA-2024827 and Google Research Scholar award.
REFERENCES
Alan Agresti and Brent A. Coull. Approximate better than "exact" for interval estimation of binomial proportions. The American Statistician, 52(2):199-226, 1998. doi: 10. 10.100000003 1305. 10480000, /ttp:tttee///.a..////0000000/000
998 19t.............1..11 10480550
Filippo Amato, Alberto López, Eladia María Peña--Mndez, Petr Vañhara, Aleš Hampl, and Josef Havel. Artificial neural networks in medical diagnosis. Journal of Applied Biomedicine, 1 11(2): 47-58, 2013.
Wolfgang Balzer, Masanobu Takahashi, Jun Ohta, and Kazuo Kyuma. Weight quantization in boltzmann machines. Neural Networks, 4(3):455-40, 1991.
Dirk Beyer, Stefan Löwe, Evgeny Novikov, Andreas Stahlbauer, and Philipp Wendler. Precision reuse for efficient regression verification. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, page 389-399, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781 9781450322379. doi: 10.1145/2411411.249 URL [RRLhhtts::/ddee 1ttp////....11//111111111111111.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Berhaard Firner, Beat Flepp, Prasoon Goyal, Lawrence Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et End end learning for self-driving cars. arXiv preprint arXiv: 1604.07316, 2016.
Alcksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-awand randomized smoothing for graphs, images and more, 2023.
Rudy Bunel, Jingyue Lu, llker Turkaslan, Pushmeet Kohli, P Torr, and P Mudigonda. Branch and bound for piecewise linear neural network verification. Journal of Machine Learning Research, 21 (2020), 2020.
Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy, Tym: An automated end-to-end optimizing compiler for deep learning. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation, OSDI' 18, page 579-594, USA, 2018a. USENIX Association. ISBN 9781931971478.
Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Learning to optimize tensor programs. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 3393-3404, Red Hook, NY, USA, 2018b. Curran Associates Inc.
C. J. Clopper and E. S. Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404 413, 1934. ISSN 00063444, URL URL http:://www //www//wwww////.mm/ jstor brq/
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9- June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages PMLR, 2019. URL http:httt///cceeeeeeeeee ngs ml pwwss/eessse... cww.nnchcnnccccoo 9c. html
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pages 255. leee, 2009.
10

---

Published as a conference paper at ICLR 2024
Krishnamurthy (Dj) Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference on Learning Representations, 2020. URL wtt.httpps///oppeeeeeee
net forum? i d= 1rkkFFr
Emile Fiesler, Amar Choudry, and H John Caulfield. Weight discretization paradigm for optical neural networks. In Optical interconnections and networks, volume 1281, pages 164-173, SPIE, 1990.
Marc Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transformations via randomized smoothing. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8404-8417. Cur- ran Associates, Inc., 2020. URL U / 01
cttpppccccppppppp files/
Mare Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing, 2022a.
Marc Fischer, Christian Sprecher, Dimitar I. Dimitrov, Gagandeep Singh, and Martin T. Vechev. Shared certificates for neural network verification. In Sharon Shoham and Yakir Vizel, editors, Computer Aided Verification 34th International Conference, CAV 2022, Haifa, Israel, August 7-10, 2022, Proceedings. Part 1, volume 13371 of Lecture Notes in Computer Science. pages 127 148 Springer, 2022b. doi: 10.10077978-3-055 1---000--111-----11- 1V_7 7. URL /ttps::/doi..re 031 1318311-31111111
10. 10.1007/978
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In Proc. International Conference on Learning Representations (ICLR), 2019.
Zhidong Gao, Rui Hu, and Yanmin Gong, Certified robustness of graph classification against topology attack with randomized smoothing. In GLOBECOM 2020 2020 IEEE Globul Communications Conference, pages 1-6, 2020. doi: 10. 10.1009900BBE000422220000000 202..93227..
Miklós Z. Horváth, Mark Niklas Mueller, Mare Fischer, and Martin Vechev. Boosting randomized smoothing with variance reduced classifiers. In International Conference on Learning Representa- tions, 2022. URL httt:ttt//ppeeeeeeeeeeee htw.rppeeeeeieeeeeeeeeeerereeree www.:eetooouue iidrummiddduu
ISO. Assessment of the robustness of neural networks. Standard, International Organization for Standardization, March 2021.
Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, (92))6600,, 1989.
Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In International Conference on Learning Representations, 2020. CRLlttps. http://:///peeeee.....oo forum??
ld BB-BBk6W6WW
Kenneth Johnson, Radu Calinescu, and Shinji Kikuchi. An incremental verification framework for component-based software systems. In Proceedings of the 16th International ACM Sigsoft Symposium Component-Bacd Based Software Engineering, CBSE '13 page 33-42, New York, NY, doi: 10.1145/2465449.
USA, 2013. Association for Computing Machinery. ISBN 078145032122 1228. 2465456. htRphhttts///oiii org 115522.44111///449494994 2465456
Kyle D. Julian, Mykel Kochenderfer, and Michael P. Owen. Deep neural network compression for aircraft collision avoidance systems. CoRR, abs/ 1ass//810.4440, 2018.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Computer Aided Verification 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I, volume 10426 of Lecture Notes in Computer Science, 2017. doi:
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- (canadian institute for advanced research). URL U //www//wwwt///w////////////// Cs. petrrntto.dd//krriii/// far. html

---

Published as a conference paper at ICLR 2024
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5165-5177. Curran Asso- wwtpapeerrell_/_aaaaaaalaeeeeeee
ciates, Inc., 2020. 7200077f00.aastc44eddd0556122222
fi 1esl/appe
Jacob Laurel, Rem Yang. Shubham Ugare, Robert Nagel, Gagandeep Singh, and Sasa Misailovic. A general construction for abstract interpretation of higher-order automatic differentiation. Proc.
ACM Program. Lang., 6(0OPSLA2), oct 2022. doi: 10.1145/3563324, URL https://dot
org
Jacob Laurel, Siyuan Brant Qian, Gagandeep Singh, and Sasa Misailovic. Synthesizing precise static analyzers for automatic differentiation. Proc. ACM Program. Lang.. 7(00PSLA2), oct 2023. doi:
10.1145/322287. URL stttps://doi.. org.l..rg/// 10. /rt..//0///..11//22555
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certifi- cates of adversarial robustness for randomly smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. "'lché-Buc, E. Fox, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: htttps::/pprceeediiin
wwwrips..c/eepppeeee.ee cc/paper fi es/paper/20197 File/ FLLe/2222ccc33112211133333222222 Pap.esb.b--ppp.pp...
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tieeh Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL
neurips. cc pttppppppr//222//aaatt. html
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. Tss: Transformation-specffee smoothing for robustness certification. In Proceed- ings of the 2021 ACM SIGSAC Conference Computer and Communications Security, CCS '21, page 535-557, New York, NY, USA, 2021. Association for Computing Machinery. ISBN doi: 10.1145/3460100.3485777
9781450384544.
URL
34 3460122 0160120..0 3485258
Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. Pointguard: Provably robust 3d point cloud classification, 2021.
Jeet Mohapatra, Ching Yun Ko, Tsui- Wei Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing, 2020.
Peter W. O'Hearn. Continuous reasoning: Scaling the impact of formal methods. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 02- 2018, pages 13 25. ACM, 2018. doi: BtLhhtts:://dde org.l.rr///i 11.00.1155/5 001114///29000 020.0099111000000090912 3209109
011144/3229008.20090
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages www.eees.......ppaaaaeee 9015 htwp::/eeeee.ett...eeeeceeeeeeee
8024 8035. Curran Associates, Inc., 2019. URL
library.
pdf
PyTorch. Torch quantization support. https//gtthbbboooooyoccccyyxasss
Russell Reed. Pruning algorithms-a survey. IEEE transactions Neural Networks, 4(5):740-747, 1993.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing, 2020.
12

---

Published as a conference paper at ICLR 2024
Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference Learning Representations, 2021. URL https:://////...... http://:///.oeeeeeee.eeeeeeeeeee
(d=UT.QdiUTHe-)
Hashim Sharif, Prakalp Srivastava, Muhammad Huzaifa, Maria Kotsifakou, Keyur Joshi, Yasmin Sarita, Nathan Zhao, Vikram S. Adve. Sasa Misailovic, and Sarita Adve. Approxhpvm: A portable compiler ir for accuracy-awan optimizations. Proc. ACM Program. Lang., 3(OOPSLA), oct 2019. www.:ii..rg..... 1145/ /344563
doi: 10.1145/336061.. URL
Benno Stein, Bor- Yuh Evan Chang. and Manu Sridharan. Demanded abstract interpretation. In Stephen N. Freund and Eran Yahav, editors, PLDI '21: 42nd ACM SIGPLAN International Conference Programming Language Design and Implementation, Virtual Event, Canada,
June 20-25, 2021, pages 282-295. 295. ACM, 2021. doi: 10. R..144//455383334544042 URLhttp 3454044
Mäns Thulin. The cost of using exact confidence intervals for a binomial proportion. Electronic Journal of Statistics, 8, 03 2013. doi: 10.1219/14-JS909.
Vincent Tjeng. Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356 2017.
Shubham Ugare, Dehangshu Banerjee, Tarun Suresh, Sasa Misailovic, and Gagandeep Singh. Toward
continuous verification of dnns.
Shubham Ugare, Gagandeep Singh, and Sasa Misailovic. Proof transfer for fast certification of
multiple approximate neural networks. Proc. ACM Program. Lang., 6(00PSLA):1-29) 2022. doi: 10.1145/3527319
Shubham Ugare, Debangshu Banerjee, Sasa Misailovic, and Gagandeep Singh. Incremental verifica- tion of neural networks. Proc. ACM Program. Lang., 7(PLDI), 2023. doi: 10. 10.1145/3591299
URL https:://oi..rz/ 13993//3999901111/33399999999999
1145/
Willem Visser, Jaco Geldenhuys, and Matthew B. Dwyer. Green: Reducing, reusing and recy- cling constraints in program analysis. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering, FSE '12, New York, NY, USA, 2012. Association for Computing Machinery, ISBN 9781450316119, doi: 1011145239339662293665
URL /Mttpp/s/ooooorrr//0111///333339 239366666399239665
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph
neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM
SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, page (645-1653, New
York, NY, USA, 2021a. Association for Computing Machinery. ISBN 97814303833 doi:
01144/344754..4472222 URL URR.https:://// htt.tt::::doo.og///tttt wrgg 1011115/44455 .4 67295
Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin. Suman Jana, Cho-Jui Hsich, and J Zico Kolter. Beta- crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification. arXiv preprint arXiv: 103.::20:03332:24 2021b.
Tianhao Wei and Changliu Liu. Online verification of deep neural networks under domain or weight shift. CoRR, abs/2106. 12732, 2021. Utttttts:///axxi wwt.:oorr/abbbaaaoaaa 2et.//226.111222222
Edwin B. Wilson. Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158):209-22, 1927. ISSN 01621459. URL http:
7 wwww. jstor. org.oogg/oooo.... hwwp:jstor.oog/staaee/////
Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes, 2020.
Guowei Yang, Matthew B. Dwyer, and Gregg Rothermel. Regression model checking. In 2009 IEEE International Conference on Software Maintenance, pages 124, 2009. doi: 10. 109/CSMM. 2009.5306334.
13

---

Published as a conference paper at ICLR 2024
Ping yeh Chiang, Michael J. Curry, Ahmed Abdelkader, Aoumon Kumar, John Dickerson, and Tom Goldstein. Detection as regression: Certified object detection by median smoothing, 2022.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box cer- tification with randomized smoothing: A functional optimization based framework. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neu- ral Information Processing Systems, volume 33, pages wtwpurips.cccpaapppepeeeeeeppppp #1le/199a3bbf3055 6dd643ba6 4666433 Pawpedd..-apppppppp.......
Curran Associates, Inc.. Files/paper/2020/
2020. URL
Yifan Zhao, Hashim Sharif, Peter Pao-Huang, Vatsin Shah, Arun Narenthiran Sivakumar, Mateus Valverde Gasparino, Abdulrahman Mahmoud, Nathan Zhao, Sarita Adve, Girish Chowdhary, et al. Approxcaliper: programmable framework for application- aware neural network optimization. Proceedings of Machine Learning and Systems, 5, 2023.
Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen. Incremental network quantization: Towards lossless CNNs with low-precision weights. In International Conference on Learning Representations, 2017. URL / htt.://wwwaaa.aeee//oooooooooann
14

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1 OBSERVATION FOR BINOMTAL. CONFIDENCE INTERVAL. METHODS
In this section, show the plots for the number of samples required to estimate unknown binomial proportion parameter through two popular estimation techniques the Wilson (Wilson 1927) and Agresti-Coull method (Agresti and Coull 1998). For this experiment,
three different values of the target error = 0.5 %, 0.75 %, and 1.0 % and a fixed confidence value (1 - a) = 0.99 for both estimation methods. As shown in Fig 4 for fixed target error X, confidence (1 - a),, and estimation technique, the number of samples required for estimation peaks, when the actual parameter value around 0.5 and is the smallest around the boundaries. This is consistent with the observation described in Section 3.1
Required Sample Size
Required Sample Size
150000
150000
30000
50000
0.0
0.4
0.2
0.0
0.2
04
0.6
1.0
Actual Binomial Proportion Value
Actual Binomial Proportion Value
(a) Agresti-Coull method
(b) Wilson method
Figure 4: The number of samples for the Agresti-Coull Coull and Wilson method to achieve a target error X with confidence (1 a)) where a = 0.01. The plots show that the number of required samples for different methods peaks at 0.5 and decreases towards the boundaries.
A.2 THEOREMS
Theorem 2. If a classifier fr is such that for all x E R" P, + +c) # [((++() S Sn. and classifier I satisfies Pe[ +) cA) 2 PA 2 pn 2 maxetea (s( +6) =)) and PA - G 2
PB PB+ Su then gd satisfies (x = far all 5 satisying ||0||2 I { ( (p- (pA-<e) --))- --
Proof. If f(x = Ca and +)) f(x + then (() Thus, f2 +e) * CA then f(z cΛ or (( Using union bound,
+
+
[BC0: -
-|(-0/= (c)
PA -
Similarly, if f(r +) * then
//==
Hence, using union bound.
c) + P f((++()
(-- (()++)))
-
(CC/=++00002(((0+00=0++++++++000 f((+
max ofcs
max P. P. (f pB +
Hence, using Theorem gd satisfies (x - 6) = CA for all satisying | s - -pA - (c)
s Φ- + ())
15

---

Published as a conference paper at ICLR 2024
Theorem 3. PA Sx 2 2: then o 'ps (x) (0 'pa (x) ②
'(p + Sz)
Proof. Since PA - <2 2 2 - PA S and G 2 0, we get 0 1 P4 - 52 3 1
And since 1 PA 2 PB. we get pB + م v 2 and thus, 0 - PB + <. S 1
Since Φ (1 - t) - (t)
s ppg (x) -1
PB (x)
=--- pp) -c)
Since 1 - PA PB
S - - 'pp (x)
Hence,
4 (pA - (e) s - pp + (x)
Φ (PA (x) S $ (7B (x)
2
Adding 2 1p - (x) on both sides,
o (ps (z) 2 ( ( 2
(ps - -G)=-
-3--0 --- - + (x)
with confidence at least 1 - agg. If classifier satisfies Pf[ + t) = cs) 2 PA with confidence at least 1 - a. Then for classifier fe, Pelf(( = cA) PA - &e with confidence at least (a + ac)
Theorem 4. =()=)))))(())------=))))))))))))
Proof. Suppose f and fr are classifiers such that for a fixed x E RR' (f = =AA) 2 PA and Pe + c) = f2 +)) > 1 - Se- Note that this is true by the definition of PA, and is a separate PA for each The statement is not true for all æ with single PA
Let Ej denote the event that (f(x + e) ca) PA-
Let Eg denote the event that (f(ff
(x)+)(())))) > Cc.
By Theorem 2
Pc( cA) P. + 6) PP + ((x+
PA 4.
CA)
Let Ey denote the event that PA So S Pp(f((2 = CA)
Since, Ei and Eg imply Eg i.e. E1 n E2 C Eg.
PP(2s) 2 P(E n Fe)
By the additive rule of probability.
P(E, n E2) = (PEE) + +(E)) - EE U UE) P(E3) 2 - (1-
P(Ea) 2 21
Hence, for classifier (f CA) 2 PA Co has confidence at least 1 (a + ac)
16

---

Published as a conference paper at ICLR 2024
A.3 EVALUATION NETWORKS
Table and Table 6 respectively present the standard top-1 accuracy of the original and approximated base classifiers and smoothed classifiers respectively.
Table Standard top-1 accuracy for (non-smoothed) networks for combinations of approximations and d's.
Dataset
Architecture
original
Quantization
Prunc
fp16
bf16
int8
5%
10%
20%
0.25
67.2
67.2
66.8
67.2
67.4
66.6
66.6
CIFARIO
ResNet-20
56.8
56.8
56.8
1.0
47.2
47.2
47.0
47.2
47
46.2
45.2
0.25
69.0
69.0
69.4
69.0
69.2
68.8
68.2
CIFARIO
ResNet-110
0.5
59.4
59.4
59.4
59.4
59.6
59
58.8
47.0
47.0
46.8
46.8
46.8
0.5
24.2
24.2
24.4
24.2
24.2
24.4
24.2
ImageNet
ResNet-50
1.0
9.6
9.6
9.6
9.6
9.6
9.6
9.6
2.0
6.4
6.4
6.4
6.4
6.4
6.4
6.4
Table 6: standard top-1 accuracy for smoothed networks for combinations of approximations and a's.
Dataset
Architecture
original
Quantization bfl6
Prune
fp16
int8
5%
10%
20%
0.25
77.2
77
77.2
77.2
77.6
77.2
77.6
CIFARIO
ResNct-20
0.5
67.8
67.4
67.8
67.8
67.8
67.4
67.8
1.0
55.6
55.6
55.6
55.8
$4.8
55.2
55.6
0.25
76.6
76.4
76.2
76.4
76.2
76.2
76.4
CIFARIO
ResNet-110
0.5
66.2
67
68
66.4
67
66.8
66.6
1.0
55.6
55.4
56.2
56.2
55
55
54.8
0.5
63.8
63.4
63.2
63.4
63.6
64
63
ImageNet
ResNet-50
48.8
48.6
48.8
48.6
48.8
48.6
47.8
2.0
34.4
34.2
33.8
34.2
34.2
34.4
33.4
17

---

Published as a conference paper at ICLR 2024
Table 8: <a for approximate networks trained on different Gaussian augmentation o's.
Dataset
Architecture
Quantization
Prune
fp16
b
int8
5%
10%
20%
0.25
0.01
0.01
0.006
0.01
0.02
0.04
CIFARIO
ResNet-20
0.5
0.006
0.008
0.01
0.01
0.02
0.03
1.0
0.006
0.007
0.006
0.007
0.02
0.02
0.25
0,006
0.006
0.009
0.02
0.04
CIFARIO ResNet-110
0.5
0.006
0.006
0.006
0.008
0.02
0.03
1.0
0.006
0.008
0.009
0.007
0.01
0.02
0.5
0.006
0.009
0.006
0.01
0.02
0.09
ImageNet
ResNet-50
1.0
0.007
0.006
0.02
0.08
2.0
0.006
0.01
0.006
0.007
0.02
0.07
A.4 & EVALUATION
We compute &2 value as the binomial confidence upper limit using (Clopper and Pearson 1934) method with n 1000 samples. For experiment that adds Gaussian corruptions with a to the input, we use the network that is trained with Gaussian data augmentation with variance o².
A.5 SENSITIVITY TO CHANGING
In Section 5 save time due to large number of approx- imations and DNNs tested, we used n 10 samples for g's certification. Here, present the effect of certifying with a larger n by comparing the ACR vs certification time the IRS and baseline approaches for ResNet-20 on CIFARIO. 10. On average, for larger n, we demonstrate greater speedup for larger a. For instance, for int8 quan- tization with = 1.0, the speedup for certifying with 10 samples was 5.85x as compared to certification with n = 10s which yielded at 2.65x speedup. However, for smaller a, certification with larger results in less speedup. For o 0.25, we observe speedups from 1.29x to 1.37x for n = 10 whereas from 0.93x to 1.15x for 106.
Table 7: Average IRS speedup for com-
binations of n, a's, and quantizations for ResNet-20 CIFARIO.
Quantization
fpl6
bfl6
int8
0.25
1.37x
1.29x
1.3x
10
0.5
1.79x
1.7x
1.77x
1.0
2.85x
2.41x
2.65x
0.25
1,22x
1.11x
1.27x
10
0.5
1.73x
1.4x
1.86x
1.0
3,88x
2.40x
4.31x
0.25
1.12x
0.93x
1.15x
109
0.5
1.97x
1.04x
2.25x
1.0
4.58x
1.25x
5.85x
A.6 EVALUATION WITH LARGER Tip
The objective of IRS is to certify the approxi- mated DNN with few samples. Thus, con- sider np ranging from 1% to 10%. Nevertheless, we check IRS effectiveness for larger np values in this ablation study.
beneline
Westnge cwntie wation Ormen (ane))
Since, IRS certifies radius σ -1 (.)) that is always smaller than original certified radius. When n, = n, the baseline running from scratch should perform better than IRS, as it will reach a certification radius close to o o (pA).
0.2
000
In this experiment, on CIFAR10 ResNet-20 with σ = 1, we let n.p E (5%, 10%.. 80%) n. Figure shows the ACR vs mean time plot for the baseline and IRS. We see that IRS gives speedup for Rp 70%. For Πp 75% and n, = 80%, we see that baseline ACR is higher and IRS cannot achieve that ACR.
Figure 5: CIFAR10 ResNet-20 with 1, for
np E (5%, 10%..
of 00.%
80%)
18

---

Published as a conference paper at ICLR 2024
A.7
EFFECT OF STANDARD DEVIATION ON IRS SPEEDUP.
20
30
05
64
1.
P6
ResNet- I on CIFAR-10 0.25)
(b) ResNet- 10 CIFAR-10 (o 1.0)
Figure 6: Distribution of PA values greater than 0.5 with different a for ResNet- 10 on CIFAR-10.
oiigiaal network
(rig ctwook
50
20
8.5
(a) ResNet-50 on ImageNet (o = 1.0)
(b) ResNet-50 on ImageNet (ar = 2.0)
Figure 7: Distribution of Pa values greater than 0.5 with different a for ResNet-50 on ImageNet.
Figure and Figure 7 present the PA distribution between 0.5 to 1, for ResNet- 10 on CIFAR-10 and ResNet-50 NetgeNet respectively. The x-axis represents the range of PA values and the y-axis represents their respective proportion. The results show that while certifying larger a, on average the PA values are smaller. As shown in Figure 7al for
0.25, less than 35% of РA values are smaller than 0.95. On the other hand, in Figure 76, when a = 1.0, the distribution is less left-skewed as nearly 75% of PA values are less than 0.95. When the is larger, the values of PA tend to be farther away from 1. Therefore, the estimation of PA is less precise in such cases, as observed in insight 2. As result, non-incremental RS performs poorly compared to IRS in these situations, leading to greater speedup with IRS.
A.8 THRESHOLD PARAMETER
?
Table 9 presents the proportion of cases for which PA > y for the y chosen through hyperparameter search in Section 5,4 for different and networks.
Table 9: Proportion of PA > for different and networks.
Dataset
Architecture
>
0.346
CIFARIO
ResNet-20
0.99
0.5
0.162
1.0
0.034
0.25
0.362
CI
ResNet-110
0.99
0.5
0.146
1.0
0.034
0.5
0.292
ImageNet ResNet-50
0.995
1.0
0.14
2.0
0.04
19

---

Published as a conference paper at ICLR 2024
For CIFARIO ResNet-220. observe that PA > 7 0.346 when 0.25 and PA Y 0.034 when Ø = 1.0. Additionally, for ImageNet ResNet-50, the results show PA > > 0.292 when 0.50 and PΛ > y 0.04 when 2.0. As shown in Section 5 certifying larger yields average smaller PA- Expectedly, we see a smaller proportion of PA for larger a and vice versa.
A.9 QUANTIZATION PLOTS
In this section, we present the ACR vs. time plots for all the quantization experiments. We use 10* for samples for certification of y. For certifying g", consider Up values from (1%.... 10%] of n. Note that these smaller values of n, Up compared to Section 5.T allow us to perform a large number of experiments.
(a) fp16
(b) bf16
(c) int8
Figure 8: ResNet-20 CIFARIO with 0.25.
(a) fp16
(b) břl6
(c) int8
Figure 9: ResNet--20 CIFAR10 with 0.5.
(a) fp16
(b) bí16
(c) int8
Figure 10: ResNet-20 on CIFARIO with 1.0.
20

---

Published as a conference paper at ICLR 2024
(a) fp16
(b) bf16
(c) int8
Figure 11: ResNet-110 on CIFARIO with σ 0.25.
103 230
211
6/0
(a) fp16
(b) bíl6
(c) int8
Figure 12: ResNet- 110 on CIFARI0 with a = 0.5.
BAC
(a) fp16
(b) bf16
(c) int8
Figure 13: ResNet-110 on CIFARIO with a = 1.0.
21

---

Published as a conference paper at ICLR 2024
340
(a) fp16
(b) bf16
(c) int8
Figure 14: ResNet-50 on ImageNet with a 0.5.
650
130
(a) fp16
(b) bF16
(c) int8
Figure 15: ResNet-50 on ImageNet with 1.0.
(a) fp16
(b) bf16
(c) int8
Figure 16: ResNet-50 on ImageNet with 2.0.
22


Reviews:
[{"review_id": "UHYhbidiT5", "reviewer": "Reviewer_7muz", "summary": "This work studies the efficiency of robustness certification in the case of approximated models by reusing the robustness guarantees in the original models. Specifically, the disparity between the original smoothed classifier and the approximated smoothed one is estimated to speed up the whole certification as it is relatively close to 0. The experiments show that the speed-up is obvious on different datasets with different models and smoothing parameters.", "questions": "See Weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow. The motivation is clear and important.\n- The methodology is sound and it is friendly to read although it can be formally expressed with more complicated notations.\n- The experiment is extensive and validates the effectiveness and efficiency of the method.", "weaknesses": "- Insight 1 in Section 3.1 is not very convincing in the sense of a single setting of n=1k and $\\sigma=1$, where it usually costs 10k-100k samples for Monte Carlo sampling in estimation. More examples can be given to show $\\zeta$ is small.\n- For insight 2 and Figure 2, although the needed samples are much less compared to 0.5, it still needs 41.5k and there is no significant reduction compred to naive Monte Carlo randomized smoothing (10k-100k). A better way is to use an example of current estimation of $p_A$ and to show the needed samples are much less when estimating $\\zeta$ compared to $p_A$.\n- The choice of threshold $\\gamma$ seems to be critical from the experiment results and the authors use grid search to optimize it. If I understand it correctly, whether to estimate $\\zeta$ actually depends on whether $\\zeta$ is closer to 0 than $p_A$ is to 1. So ideally, there can be some theoretical analysis for choosing $\\gamma$ in terms of $\\zeta$ and $p_A$.\n- I think there is a missing ablation study of directly using naive Monte Carlo to estimate $\\zeta$ instead of reusing seeds in terms of both certified radius and certification time.\n- There are some typos and text messed up in the last two paragraphs in Section 3.2, e.g. In case, ... are correct with...", "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": "", "extra_scores": {}}, {"review_id": "0MiEYTecC0", "reviewer": "Reviewer_VbzH", "summary": "This work proposed how to certify a similar neural network via randomized smoothing by re-using the certification result from the original neural network. An IRS certification algorithm is provided in Algorithm 2 and its theory is provided in Theorem 2. The experiments on Cifar10 and ImageNet dataset showed the efficiency of the proposed algorithm for certifying different quantization models (fp16, bf16 and int8) and pruned models.", "questions": "See weakness above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work proposed a first incremental approach for randomized smoothing to certify a similar (compressed) version of the original neural network with improved efficiency by re-using the certification results. \n2. The experiments results seem to be promising.", "weaknesses": "1. Demanding prerequisite: I am not sure how likely IRS algorithm is applicable in practice. It seems like IRS will require many prerequisite. For example, IRS needs to know the certification cache from the original neural network, which makes the requirement more demanding. If there is no such information, regular RS is still needed. As another requirement, IRS needs the modified network to be a good approximation of the original neural network. Otherwise, the accuracy might be reduced per theorem 2.\n2. Novelty issue with the theory: for the theory part, most of the theorems are built upon theorem 1 in [Cohen et al 2019] and are direct application of that theorem, hence raising a novelty issue.", "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": "", "extra_scores": {}}, {"review_id": "kBSjxfv0oV", "reviewer": "Reviewer_6uEd", "summary": "The paper deals with the problem of providing randomized smoothing-based certificates for modified neural networks. Given a modified version of a base model $f_p$ for some original base model $f$, the task is to provide a robustness certificate for the prediction of smoothed model $g_p$ at a point $x$ by efficiently reusing the values observed when calculating the certificate for smoothed model $g$ at the same $x$. The authors propose to do this using the fact that the difference between the value $g(x + \\epsilon)$ and $g_p(x + \\epsilon)$ around any point $x$ is very small (close to $0$) and the fact that the number of binomial samples required to estimate a parameter close to 0 is much smaller than the number of samples needed to estimate a binomial parameter close to 0.5. Given the difference in the value of $g$ and $g_p$ around a point $x$ and the certificate for $g(x)$, the authors give a formula to bound the certificate for $g_p$ at $x$.", "questions": "Please refer to the weaknesses section for questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The idea of reusing the observations for calculating the certificate for $g$ to calculate the certificate of $g_p$ is novel and interesting. \n- The authors also use a great insight that it is more efficient to estimate binomial parameters at extreme ends than near the middle.\n- The paper is well-written and easy to understand.", "weaknesses": "- The practical usefulness of the proposed method is not clear. As randomized smoothing produces certificates at inference time, in order to calculate the certificate around a given point in this approach, the edge device would need access to both the original as well as the modified neural network models, which is not feasible.", "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": "", "extra_scores": {}}, {"review_id": "dwNQ1BCnmw", "reviewer": "Reviewer_qzcN", "summary": "This paper study certified robustness with randomized smoothing. The authors present a method that decreases the sample complexity of randomized smoothing in the setting where there is a classifier $f$ and an approximation of the same classifier $f^p$ (for example, $f^p$ is a quantized version of $f$). The method, called Incremental Randomized Smoothing, proposes to compute the certification of $f^p$ via the certificate of $f$. The method relies on estimating the disparity $\\zeta_x$ which is the upper bound on the probability that outputs of $f$ and $f^p$ are distinct.", "questions": "- Why the authors use the same Gaussian samples (same seed) in Algorithm 3? Is there any benefit?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Randomized smoothing is an important method, and currently the state-of-the-art approach, for certified robustness. Given the computational cost of this method, it is important to investigate how to make randomized more efficient. This paper investigates how to reduce the number of samples necessary for computing the certificate via Monte Carlo sampling. \n- The paper is well-written, the theorems and algorithm are clear.", "weaknesses": "**Main Comment**.\nI don't understand the main premise and setting used in this paper. I find one of the assumptions very strong and the practical implications of the method very limited. More detail below. \n\nThe authors state the following sentence in the abstract:\n\n_``[...] when the smoothed model is modified (e.g., quantized or pruned), certification guarantees may not hold for the modified DNN, and recertifying from scratch can be prohibitively expensive.``_\n\nLet $f$ be a base classifier, $f^p$ be a quantized version of $f$, and let $g$ be the smooth version of $f$ and $g^p$ be the smooth version of $f^p$. \nIt is true that a certificate computed from the _base model_ $f$ will not hold for the quantized version $f^p$. However, it would be possible to apply randomized smoothing directly to the quantized version $f^p$ via:\n$$\ng^p(x) = \\underset{c \\in \\mathcal{Y}}{\\operatorname{argmax}} \\ \\mathbb{P}_\\epsilon [\\ f^p(x + \\epsilon) = c\\ ]\n$$\n\nInstead, the authors propose to compute the certificate of $f^p$ by first computing the certificate for $f$ (which is the unquantized model and therefore expensive to run) and then computing the disparity $\\zeta_x$, which is an upper bound on the probability that the outputs of $f$ and $f^p$ are different.  \n$\\rightarrow$ It seems to me that this method is more expensive than computing the certificate directly on the quantized version $f^p$. \n\nTo claim that the approach is more efficient, the authors **assume** that the certificates for $f$ are available **for all $x$**, and therefore only the disparity $\\zeta_x$ is needed to compute the new certificate. The authors state:  \n\n_``The IRS algorithm utilizes a cache $C_f$, which stores information obtained from the RS execution of the classifier $f$ for each input $x$. The cached information is crucial for the operation of IRS. $C_f$ stores the top predicted class index and its lower confidence bound $\\underline{p_A}$ for $f$ on input $x$.``_\n\n$\\rightarrow$ The authors assume that the test data is already available and that the certificates have already been computed. I don't see how this can be realistic, especially since the authors mention that the quantized version $f^p$ can be used on edge devices, except perhaps if the model is only used for a limited set of inputs that are known in advance.\n\nCan the authors comment on this and provide a practical use case that I may have missed?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)