Data-Dependent Randomized Smoothing
Authors: Motasem Alfarra
Adel Bibi
Philip Torr
Bernard Ghanem
Venue: ICLR 2022 Submitted (2022)
Keywords: Network Certification
Randomized Smoothing

Abstract: Randomized smoothing is a recent technique that achieves state-of-art performance in training certifiably robust deep neural networks. While the smoothing family of distributions is often connected to the choice of the norm used for certification, the parameters of these distributions are always set as global hyper parameters independent from the input data on which a network is certified. In this work, we revisit Gaussian randomized smoothing and show that the variance of the Gaussian distribution can be optimized at each input so as to maximize the certification radius for the construction of the smooth classifier. We also propose a simple memory-based approach to certifying the resultant smooth classifier. This new approach is generic, parameter-free, and easy to implement. In fact, we show that our data dependent framework can be seamlessly incorporated into 3 randomized smoothing approaches, leading to consistent improved certified accuracy. When this framework is used in the training routine of these approaches followed by a data dependent certification, we achieve 9% and 6% improvement over the certified accuracy of the strongest baseline for a radius of 0.5 on CIFAR10 and ImageNet. 

Under review as a conference paper at ICLR 2022
DATA DEPENDENT RANDOMIZED SMOOTHING
Anonymous authors Paper under double-blind review
ABSTRACT
Randomized smoothing is recent technique that achieves state-of-art performance in training certifiably robust deep neural networks. While the smoothing family of distributions is often connected to the choice of the norm used for certification, the parameters of these distributions are always set as global hyper parameters independent from the input data on which network certified. In this work, we revisit Gaussian randomized smoothing and show that the variance of the Gaussian distribution can be optimized each imput so as maximize the certification radius for the construction of the smooth classifier. Since the data dependent classifier does not directly enjoy sound certification with existing approaches, we propose memory-enhance data dependent smooth classifier that is certifiable by construction. This new approach is generic, parameter-free, and easy to implement. In fact, we show that our data dependent framework can be seamlessly incorporated into randomized smoothing approaches, leading to consistent improved certified accuracy. When this framework is used in the training routine of these approaches followed by a data dependent certification, we achieve 9% and 6% improvement over the certified accuracy of the strongest baseline for radius of 0.5 on CIFAR10 and ImageNet.
INTRODUCTION
Despite the success of Deep Neural Networks (DNNs) in various learning tasks (Krizhevsky et al., 2012; Long et al., 2015), they were shown to be vulnerable to small carefully crafted adversarial perturbations (Goodfellow et al., 2015; Szegedy et al., 2013). For DNN f that correctly classifies an image f can be fooled to produce an incorrect prediction for I + even when the adversary is so small that æ and 7) are indistinguishable the human eye. To eircumvent this nuisance, there have been several works proposing heuristic training procedures to build networks that are robust against such perturbations (Cisse et al., 2017: Madry al., 2018). However, many of these works provided a false sense of security as they were subsequently broken, i.e. shown to be ineffective against stronger adversaries (Athalye et al., 2018; Tramer et al., 2020; Uesato et al., 2018). This has inspired researchers to develop networks that are certifiably robust, i.e. networks that provably output constant predictions over a characterized region around every input. Among many certification methods, a probabilistic approach to certification called randomized smoothing has demonstrated impressive state-of-the-aae certifiable robustness results (Cohen et al., 2019; Lecuyer et al., 2019; Li al., 2019). In nutshell, given an input x and base classifier e.g. DNN, randomized smoothing constructs a "smooth classifier" g(x)
EE-D [f(x + c)] such that, and under some choices of D, g(xx) = g( 8) Vő R. As such, y is certifiable within the certification region R characterized by x and the smoothing distribution D. While there has been considerable progress in devising a notion of "optimal"" smoothing distribution D for when R is characterized by an l, certificate (Yang et al., 2020), a common trait among all works in the literature is that the choice of D is independent from the input x. For example, one of the earliest works on randomized smoothing grants la certificates under D = (O, TT)), where is free parameter that is constant for all x (Cohen et al., 2019). That is to say, the classifier f is smoothed to a classifier g uniformly (same variance o²) over the entire input space of z. The choice of used for certification is often set either arbitrarily or via cross validation to obtain best certification results (Salman et al., 2019a). We believe this is suboptimal and that a should vary with the input (data dependent), since using fixed may under-certify inputs (i.e. the constructed smooth classifier g produces smaller certification radii), which are far from the decision boundaries exemplified by 2 in Figure 1. Moreover, this fixed a could be large for inputs

---

Under review as a conference paper at ICLR 2022
Fixed
Data dependent o
f+
C1
C2
Figure 1: From fixed to data dependent smoothing. Using fixed to smooth fo for all inputs may under certify inputs (results in smaller certification radii), which are far from the decision boundary e.g. 21, decrease prediction confidence egg. T2, or produce incorrect predictions egg. Zz. Thus, smoothing should vary per input (right figure) to alleviate the aforementioned issues.
close to the decision boundaries resulting smooth classifier g that incorrectly classifies x (refer to 3y in Figure 1).
In this paper, we aim to introduce more structure to the smoothing distribution DD by rendering its parameters data dependent. That is to say, the base classifier f is smoothed with family of smoothing distributions to produce: g(x) = E [0,.20 [f + +]] '. Note here that the variance of the Gaussian is now dependent on the data input 2. Moreover, given that oR varies with classical randomized smoothing based certification does not apply directly. We propose a simple memory-basee approach to certify the resultant data dependent smooth classifier g. We show that memory-enhanced data dependent smooth classifier can boost certification performance of several randomized smoothing techniques. Our contributions can thus be summarized in three folds. (i) We propose a parameter free and generic framework that can easily turn several randomized smoothing techniques into their data dependent variants. particular, given a network f and an input æ, we propose to optimize the smoothing distribution parameters for every 2, e.g. of, so they maximize the certification radius. This choice of o is then used to smooth ff at x and construct a smoothed classifier g. Moreover, as the data dependent smooth classifier is not directly certifiable using Cohen data dependent smooth classifier
et al. (2019) MCMC approaches, we propose a memory-enhanee for certification. (ii) We demonstrate the effectiveness of our memory-enhanced data dependent smoothing by showing that we can improve the certified accuracy of several models, specifically models trained with Gaussian augmentation (COHen) (Cohen et al., 2019), adversaries the smoothed classifier (SMOOTHADV) (Salman et al., 2019a), and radius regularization (MACER) (Zhai et al., 2020) without any model retraining. We boost the certified accuracy of the best baseline by 5.4% on CIFAR10 and by 2.8% on ImageNet for l perturbations with less than 0.5 (=127/255) ball radius. (iii) We show that incorporating the proposed data dependent smoothing in the training pipeline of COIIEN, SMOOTIIADY and MACER can further boost results to get certified accuracies of 68.3% on CIFARIO and 64.2% on ImageNet bg perturbations less than 0.25.
RELATED WORK
Certified defenses aim to guarantee that an adversary does not exist in a certain region around a given input. Certified defenses can be divided into exact (Cheng et al., 2017; Lomuscio & Maganti, 2017: Huang et al., 2017; Ehlers, 2017) and relaxed certification (Salman et al., 2019b; Wong & Kolter, 2018). Generally, exact certification suffers from poor scalability with networks that are at most 3 hidden layers deep (Tjeng et al., 2019). On the other hand, relaxed methods resolve this issue by aiming at finding an upper bound to the worst adversarial loss over all possible bounded perturbations around given input (Weng et al., 2018). However, the latter is too expensive for any mixed certification--raine training routine.
Certified Defenses.
Randomized Smoothing, The earliest work on randomized smoothing (Lecuyer et al., 2019) was from a differential privacy perspective, where it was demonstrated that adding Laplacian noise enjoys an ε certification radius in which the average classifier prediction under this noise is constant. This work was later followed by the tight & certificate radius for Gaussian smoothing (Cohen et al., 2019). Since then, there has been a body of work on randomized smoothing with empirical defenses (Salman et al., 2019a) to certify black box classifiers (Salman et al., 2020). Other works derived certification 'The paper focuses on Gaussian smoothing, but the idea holds for other parameterized distributions.
2

---

Under review as a conference paper at ICLR 2022
guarantees for l bounded (Teng et al., 2019), foc bounded (Zhang et al., 2019), and Eo bounded (Levine & Feizi, 2020) perturbations. Even more recently, a novel framework that finds the optimal smoothing distribution for given C, norm (Yang et al., 2020) was proposed showing state-of-art certification results on & perturbations. We deviate from the common literature by introducing the notion of smoothing, particularly Gaussian smoothing for & perturbations, which varies depending on the input. In particular, since an input x that is far from the decision boundaries should tolerate larger smoothing (and equivalently have larger certification radius) as compared to inputs closer to these boundaries, we optimize for the amount of smoothing per input (specifically σ₂) that maximizes the certification radius. This proposed process is denoted as data dependent smoothing where we provide a procedure for certifying the resultant smooth classifier.
DATA DEPENDENT SMOOTHING
3.1 PRELIMINARIES AND NOTATIONS
We consider the standard classification problem, where x E Rdd and the labels y E = (1, (1....,k) form the input-label pairs (I,z) 3) sampled from unknown data distribution. Unless explicitly mentioned, we consider a classifier fo Rd + P()) parameterized by where P())) is a probability simplex over & labels. We say that so is fg certifiably accurate for an input x, if and only if,
arg max, fz) arg max, (xx+0) = y Y "|olíp S r. where fă the et element of fe. That is to say, the classifier correctly predicts the label of x and enjoys a constant prediction for all perturbations 6 that are in the l, ball of radius r from æ. As such, the overall f certification accuracy is defined as the average certified accuracy over the data distribution. In this paper and following previous works (Cohen et al., 2019; Salman et al., 2019a; Zhai et al., 2020), we focus on Eg certification.
3.2 OVERVIEW OF RANDOMIZED SMOOTHING
Randomized smoothing constructs certifiable classifier go by smoothing a base classifier fo. That is to say, for any σ > 0, the smooth classifier is defined as follows: go(x) = E.-N((0.02)) [fe (z + c)].
Let go predict label Ca for input x with some confidence, i.e. R. (x + c)] = PA 2 PB =
maxa4ca B, (fā + <)), then, Jo is certifiably robust at with certification radius:
R=
( (ps) (pB()
Here, g(x + =0 g(x) V|[8||2 S R, where t is the CDF of the standard Gaussian.
3.3 ROBUSTNESS-ACCURACE TRADE-OFF
Note that Equation I holds regardless of the prediction Ca made by the smooth classifier ga- This suggests that one can perhaps improve the robustness of ge. i.e. increase certification radius R where Io constant, by increasing the hyper parameter in Equation 1. However, to reason about fy certification accuracy, it is not enough to increase the certification radius R, as this requires Ca to be the correct prediction for x by go. This reveals the rybustness-cceuracy trade-off as cannot improve E certified accuracy by only increasing the certification radius R (robustness) through the increase in a. This is because it comes the expense of requiring a classifier go that correctly classifies with correct label y under large Gaussian perturbations (accuracy). As such, the following inequality should hold E. [f (z + +c]
PA 2 PB Z maxe [z + e)].
3.4 DATA DEPENDENT SMOOTHING FOR CERTIFICATION
The certification region R = {8 1100|2 < R} at an input x is fully characterized by the classifier fo and the standard deviation of the Gaussian distribution a. Moreover, for given fo, the certification region R varies at different x, when a is fixed, due to the nonlinear dependence of the prediction gap (pA (x; o)) - Φ (p o)) on x. This hints that, for a given fe. different inputs x may enjoy a different optimal o that maximizes the certification region through radius R. To see this, consider the three inputs 11, I2 and Iy all correctly classified by the binary classifier fe as C₁ in Figure 1. Using fixed o to smooth the predictions of fe, f.e. predict with ge, reveals that inputs, depending close they are from the decision boundaries, can enjoy different levels of smoothing without affecting the prediction of go- For instance, as shown in Figure for constant a, the input far from the decision
how
3

---

Under review as a conference paper at ICLR 2022
boundary xi could have still been classified correctly with similarly large prediction gap even if fo were to be smoothed with a larger a. This indicates that perhaps the certification radius at 21 could have been enlarged with larger smoothing As for 22. we can observe that while the prediction under this choice of a by Jo is still correct, the prediction gap & Φ (pA(pa r) Φ (pn (x; a)) drops, due having more Gaussian samples fall in the C2 region. This indicates that different choice of a could have been used to trade-off the drop in prediction gap and certification radius. Last, for the input 23 that is very close to the decision boundary, the sub optimal choice of a (too large for 2:)) could result in an incorrect prediction by ga. Despite the observations that plays a significant role E certification accu- racy, certification methods generally (i) choose a arbitrarily and (ii) set it to be constant for all Based on this observation, for a given smooth classifier with a specific Fn. where do can be zero reducing the smooth classifier to fo, seek to construct another smooth classifier with parameter o for every input such that: (i) the prediction of both smooth classifiers (smoothing with dg and o²)) identical for all z. (ii) The certification radius of the new smooth classifier at every x maximized. To construct a classi- fier smoothed with of enjoying the two previous properties, let CA be the prediction under on smoothing, i.e. CA = arg max, Eo.,N We directly maximize the radius R in Equation I over for every x by solving the following optimization:
Algorithm 1: Data Dependent Certification
imi Function Cptimi zesi gma (Js. I, a, 0o. n)):
Initialize: a <- do. K
for 0...
do
sample E1, ......... En ~ (O(
((+)) = ; Di=1 so f + o
Ea(o=) = max. 3:: ya arg max, vf:
Eg(a²) maxx+va v6"
R(o*) = (FA) 4 -- (FBB)
T
k+1 c- + +vV 1(
0 + ox return d;
K
(f + e)].
0 = arg max 2 1 "Bens(OO000011 (a e)) - --' "'"(max Ee- (o))))(oo)))))))))))))
(CFcA
(2) Since & 1 is a strictly increasing function, it is important to note that solving Equation for fixed Ca can at worst yield smooth classifier of an identical radius when the classifier is smoothed with Ty with both classifiers predicting CA for x.
Solver. While our proposed Objective 2 has similar form to the MACER regularizer (Zhai et al., 2020) used during training, ours differs in that we optimize a for every & and not the network parameters 0, which fixed here. A natural solver for 2 is stochastic gradient ascent with the expectation approximated with n Monte Carlo samples. As such, the gradient of the objective at the 4t iteration will be approximated as follows: Vor [ (f"a(a") + (maxeefca (o)))]
where (aa))) 1 Em= +x) for El,..., En NO0, (a"))1)). However, this estimation the gradient suffers from high variance due to the dependence of the expectation on the optimization variable that parameterizes the smoothing distribution N(0, r² (Williams, 1992). To alleviate this, we use the reparameterization trick suggested by Kingma & Welling (2014); Rezende et al. (2014) to compute lower variance gradient estimate for our Objective 2. In particular, with the change of variable
oē where é ~ NN( /), Objective 2 is now equivalent to:
( + (B-NNoioon) oē)) -4-1 max Ea-.ronn +0) ( 2
T- = arg max
ofoA
(3)
Note that, unlike before, the expectation over the distribution é ~ (0, no longer depends the optimization variable a. This allows the gradient of 3 to enjoy a lower variance compared to the gradient of 2 (Kingma & Welling, 2014; Rezende et al., 2014). Algorithm I summarizes the updates for optimizing a for each z by solving 3 with K steps of stochastic gradient ascent. It is worthwhile to mention that the function Opt wwwiiiiiiiiiiiie imeagmma/ in Algorithm 1 is agnostic of the choice of architecture fo and of the training procedure that constructed fo.
3.5 MEMORY-BASER CERTIFICATION FOR DATA DEPENDENT CLASSIFIERS
Unlike previous approaches where a is constant for all inputs, the data dependent classifier ge with varying per input not be directly certified by the classical Monte Carlo algorithms
4

---

Under review as a conference paper at ICLR 2022
R1
R₂
R1
R1
R1
R₂
R1
R2
R2
R2
C2
C1
C2
C
C2
Ci
C1
C2
C1
Figure 2: Memory-based certification of the data dependent classifier. Given memory of an input in with a certified region R₁ and another input z2 with a certified region R2. Three scenarios could arise where Ri and R₂ intersect. Left: The certified regions intersect while both #1 and 2y share the same prediction. In this case, Iy along with its certified region are directly added to memory. Middle: I2 lies inside R₁ with a different prediction from 21. In this case, 22 is predicted with the same prediction with the largest subset of R2 that is within R1. Right: 22 lies outside the R2 with different prediction from 21 this case, 22 with its prediction are added to memory along with the largest certified region in R2 not intersecting with R1-
21 and added to memory along
proposed by Cohen et al. (2019). This is since the data dependent classifier go does not en- joy constant within the given certification region, i.e. go tailors a new or for every input including within the certified region of x. Informally, let R(o",) ) be the radius of certifica- tion at z1 granted by the data dependent classifier go. The data dependent classifier does not - guarantee that there can not exist 22 within the region of certification of 21, i.e. ||| x2112 S R(ot,), where go with or predicts 22 differently from Tj breaking the soundness of certification. To circumvent this problem, we pro- pose memory-based procedure to certifyyng our proposed data depen- dent classifier. Let { be a set of previously predicted inputs and [C,) be their corresponding pre- dictions with mutually exclusive lz certified regions R2 for differently pre-
Algorithm 2: Training with Data Dependent Ox,
Function TrainBatch (fe. fai, Ve } (oa, 1 a n): for = I,..., B do
L oz = ppptimizeSSiima(fff
TrainFunction ((#;, y (oi,) // any
training routine c.g. MACER
dicted inputs, i.e. R2 R, 0 Vi +
j. C, # Cj. Let #N+1 be a new input with a certified region RN+1 computed by the Monte Carlo algorithms of Cohen et al. (2019) for the data dependent classifier go with prediction CN+1. If there exists an i such that R n R4 + 0, IN++ E RR, and CN+1 A C,, we adjust the prediction of the data dependent classifier go to be C, and update RN+1 to be the largest subset of RN++1 that is a subset of R, (see middle example in Figure 2). On the other hand, if RN n R. + 0, IN41 & Ri, and that CN+11 + C., we update R,++1 to be the largest subset of RN++1 not intersecting with R. (see right example in Figure 2). We perform the previous operations for all elements in the memory and add x +1 CN+1, Ry+1 to memory. The aforementioned procedure grants a sound certification for the data dependent classifier preventing by construction overlapping certified regions with different predictions. While the memory-basee based certification is essential for a sound certification, empirically, never found in any of the later experiments case where two inputs predicted differently suffer from intersecting certified regions. That is to say while our sound certificate works on the memory- enhanced data dependent smooth classifier, we found that the certified radius of the memory classifier for every input is the radius granted by the Monte Carlo certificates of Cohen et al. (2019) for the data dependent classifier. Therefore and throughout, we refer the smooth classifier and data dependent smooth classifier interchangeably. We elaborate more on this and provide an algorithm in the Appendix.
data dependent
3.6 TRAINING WITH DATA DEPENDENT SMOOTHING
Models that enjoy large Ey certification accuracy under the randomized smoothing framework need to enjoy a large certification radius R in Equation I for all r and be able to correctly classify inputs corrupted with Gaussian noise, i.e. (x))) = y. While there are several approaches to train fo (or directly go) so as to output correct predictions for inputs corrupted with noise sampled from (0, I²'), all existing works fix a for all inputs during training. We are interested in complementing these approaches with smoothing distributions that are data dependent. As such, we can employ the training procedure of these approaches but with of computed by Opt imi memizesigmnn gmm. Algorithm summarizes this proposed training pipeline. The function Trainf Faniinuunniion proceeds by performing backpropagation using any training scheme, given the estimated of, for each z,, We note that whenever Algorithm 2 is used, we initialize ax, each epoch with o computed at the previous
5

---

Under review as a conference paper at ICLR 2022
21 Cames 05 4.32
Lonan 1123 Ounen D5 0.25
Centeed sareee
Contiall soueno
Lonien Dollon
0.5
Dutton 05 0039
Centeel
0.4
0.4
0.4
0.2
0
caliao
rulax
0.6
Cohend 20
Cahen-05-0.5
0.6
Cohen-3 3.0 Caten
Cohan Ca Cobons
0.4
Oettied 0.4
Oottod
(28ce-3.2 25
0.5 Sadiia
0.5
15
2
Figure 3: Certified accuracy comparison against COHEN. For several ø values used in training (shown in the legend). compare COHEN against our two variants: COHEN-DE -D with data dependent certification only and COHEN-DS², where data dependency incorporated in both training and certification. We show CIFARIO and ImageNet results in the first and second rows, respectively. The last column shows the envelope across a.
epoch. Since COHEN, SMOOTHADY and MACER are among the most popular approaches that embed randomized smoothing certificates as part of the training routine, TrainFurm Funct ion refers here to any of these three training methods. Empirically, we show that we can boost all three methods even further when models are trained with Algorithm 2.
EXPERIMENTS
We conduct two sets of experiments validate our key contributions. (i) We show that we can boost certified accuracy for several pre-trained models by using Algorithm I for data dependent smoothing only during certification, i.e. without employing any additional training. (ii) Once data dependent smoothing is employed during training, we can improve the certified accuracy even further. Since our framework is agnostic to the training routine, we incorporate it into (i) COHEN (Cohen et al., 2019), (ii) SMOOTIADV (Salman et al., 2019a) and (iii) MACER (Zhai et al., 2020). Throughout, we use DS to refer to when data dependent smoothing is used only in certification and DS² when it used during both training and certification.
Setup. We conduct experiments with ResNet-18 and ReNet-50 (He et al., 2016) on CIFARIO (Krizhevsky & Hinton, 2009) and ImageNet (Russakovsky et al., 2015), respectively. For CIFARIO experiments, we train from scratch for 200 epochs. For ImageNet, we initialize using the net- work parameters provided by the authors. When a is fixed and following prior art, e.g. COHEN, SMOOTHADV, and MACER, we set a E {0.12, 0.25, 0.50] and a E (0.25, 0.50, 1.0) for CI- FARIO and ImageNet, respectively, for training and certification. We a 10-4 in Algorithm I and the initial To to the a used in training the respective model. Unless stated otherwise, we set n in Algorithm 1. Following COHEN and SMOOTHADV, we compare models using the approximate certified accuracy curve (simply referred to as certified accuracy) followed by the envelope curve over all a. We also report the Average Certified Radius (ACR) proposed by MACER 1/SSccael Σ Di R(fo, (f). 1: (arg max, (xx) = v}. where 1 1-) is an indicator function. Follow- ing COHEN2 and all randomized smoothing methods, we certify all results using No- = 100 Monte Carlo samples for prediction and N = 100, 000 estimation samples to estimate the radius with failure probability of 0.001 given a smoothing o.
4.1 COHEN + DS
We combine data dependent smoothing with COHEN. Following Gaussian augmentation, this method trains fo on (x + c), where e (0, I), with the cross entropy loss.
DS for certification only. We first certify the trained models with the same fixed used in training for all inputs, dubbed COHEN. Then, we certify using the memory based certification the same trained models with the proposed data dependent of produced by Algorithm 1, which we refer to as COHEN-DS. Figure plots the certified accuracy for CIFARIO and ImageNet in the first and second rows, respectively. Even though the base classifier fo is identical for COHEN and COHEN-DS, Figure
We use the available code of Cohen al. (2019) to report all centification results in the paper for given a.

---

Under review as a conference paper at ICLR 2022
Table Best certified accuracy per radius and ACR COHEN, COHEN-DS and COHEN DSS FS denotes a fixed a in smoothing. DS denotes the use of a data-dependent a.
Radius
CIFARIO
Train
Certify
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
2.25
ACR
COHEN
F8
79,9
58.3
29.2
20.2
13.1
7.3
0.0
0.591
COHEN-DS
ES
DS
77.2
64.5
47.8
38.3
27.6
16.5
8.0
3.2
1.2
0.7
0.784
COHEN-DS"
DS
DS
79.8
66.5
50.4
39.2
29.1
18.3
8.8
3.8
1.4
0.6
0.764
Radius
ImageNet
Train
Certify
0.0
0.25
0.50
0.75
1,00
1.50
2.0
2.5
3.0
3.50
ACR
COHEN COHEN DS
FS
F8
66.6
58.2
49.0
42.4
37.4
27.8
19.4
14.4
12.0
8.6
1.098
FS
DS
67.8
61.4
53.6
45.6
42,0
30.4
23.4
18.8
14.6
10.2
1.257
COREN-DS
DS
DS
67.4
64.2
58.4
47.4
41.8
31.8
25.0
21.2
17.2
11.0
1,319
0.6
Smastass- 15
0.8
Enookatt 3X Srowiilis----..55
0.5
Emoohaara to Smwwthatt--i---
0.6
Centtal soreyy
Oirttel evene
Ocilied auuina exuey
6
SerouiMee 9:32
0.6
Snowthate
0.5
Srowthiddy o5" 0.38
moothio
R
94
0.2
0.2
02
055
0.5
3.5
0.5
2.5
0.5
1.5
2.5
cadrax
13
Aab 3.0
SmootrAa
Serottiidt es
Ovettedemm
0.4
Sreettweh-B5--..
Coretedd
0.4
22
Smoothidb-2--0 25-0.25
SmootiidttCC ES-250
STO0FFAO0 0:25
Smoomaaa 0.50
Sualio
Eadieo
Figure 4: Certified accuracy comparison against SMOOTHADV. We compare SMOOTHADV against SMOOTHADV-DE and SMOOTHADV-DS' We show CIFARIO and ImageNet results in the first and second rows, respectively. The last column shows the envelope across d.
3 shows that COHEN-DS is superior to COHEN in certified accuracy across almost all radii and for all training a both datasets. This is also evident from the envelope plots in the last column of Figure 3. In Table 1, we report the best certified accuracy per radius over all training a for COHEN (envelope figure) against our best COHEN-DS, cross-validated over all training o and the number of iterations in Algorithm 1 K, accompanied with the corresponding ACR score. For instance, we observe that data dependent certification COHEN-DE can significantly boost certified accuracy at radii 0.5 and 0.75 by 7.7% (from 40.1 to 47.8) and 9.1% (from 29.2% to 38.3%), respectively, and by 0.193 ACR points on CIFAR 10. Moreover, we boost the certified accuracy on ImageNet by 4.6% and 3.2% at 0.5 and 0.75 radii, respectively, and by 0.159 ACR points.
DS for training and certification. We employ data dependent smoothing in both training and certification for COHEN models (denoted COHEN-DS by rumning Algorithm 2. For CIFAR 100 we train COHEN first with fixed a for 50 epochs, f.e. K = 0 in Algorithm 1, and then we perform data dependent smoothing with K 1 for the remaining 150 epochs. For ImageNet experiments, we only finetune the provided models for 30 epochs using Algorithm with K = 1. Once training is complete, we certify all trained models with Algorithm I using the memory based certification. In Figure 3, we observe that COHEN-DS' can further improve certified accuracy across all trained models on both CIFARIO and ImageNet. This is also evident in the last column of Figure that shows the best certified accuracy per radius (envelope) over all training a. We note that COHEN-DS" improves the certification accuracy of COHEN-DS by 2.6% and by 0.9% at radii 0.5 and 0.75 respectively on CIFAR1O 10, and by 4.8% and 1.8% at radii 0.5 and 0.75 respectively on ImageNet. The improvements are consistently present over a wide range of radii on both datasets. We do observe that the ACR score for COHEN-DS² on CIFARIO marginally drops compared to COHEN-DS. We believe that this is due to the fact that some inputs that are classified correctly at the small radii have an overall larger certification radius for COHEN-DS compared to COHEN-DS* on CIFAR1O. Regardless, COHEN-DS* substantially outperforms COHEN by 0.173 ACR points. As compared to COHEN-DS, COHEN-DS* improves the ACR on ImageNet from 1.257 to 1.319.
4.2 SMOOTHADY + DS
We combine data dependent smoothing strategy with the more effective SMOOTHADV, which trains the smoothed classifier for every x on the adversarial example & that maximizes log B,~N((0,02)) [5 (a' + e)), where ||a' - x ç.For CIFAR10 experiments, we follow the train-
7

---

Under review as a conference paper at ICLR 2022
Table 2: Best certified accuracy per radius and ACR of SMOOTHADW, SMOOTHADV-DS and
SMOOTHADV-DS"
Radius
CIFARIO
Train
Certify
0.0
0.25
0.50
0.75
1,00
1.25
1.50
1.75
2.00
2.25
ACR
SMOOTHADV
FS
76.0
62.4
46.7
19.5
12.9
SMOOTHADY- DD
FS
DS
75.7
66.4
52.1
18.8
30.6
22.2
15.0
8.5
4.2
1.8
0.799
SMOOTHADY-DS
DS
DS
76.2
66.8
52.8
39.3
30.8
22.6
15.1
8.8
4.3
2.0
0.812
Radius
ImageNet
Train
Certify
0.0
0.25
0.50
0.75
1,00
1.50
2.0
2.5
3.0
3.50
ACR
SMOOTHADV SMOOTHADY- DS
FS
60.8
57.8
54.6
50.4
42.2
35.6
25.6
20.4
18.0
14.2
1.287
FS
DS
62.0
60.4
57.4
53.2
47.0
39.2
29.2
23.8
19.6
15.2
1,445
SMOOTHADY-DSS
DS
DS
62.2
60.6
58.8
54.2
48.2
43.0
30.6
25.4
21.6
18.6
1.514
0.8
0.8
0.8
0.0
0.6
NACER-OG 06-0.12
HACER O6' 9.12
Oheiltad axnun
0.6
HAZER 05 0.25
HACER D5' 0:25
Cheiitel asurce
0.6
WACER
VACER D6" 0.30
06-0.5
Cheiltee axaur
0.6
WWCER- 0S
VACER DS
Oritted
0.4
0.4
0.4
0.7
02
02
3
Sandiss
Figure 5: Certified accuracy comparison against MACER. We compare MACER against MACER-DS
and MACER-DS for several a on CIFARIO. The last column shows the envelope.
ing procedure of SMOOTHADV, where the adversary å is computed with PGD (proximal gradient descent) steps with 0.25 and one augmented sample estimate the expectation. For ImageNet experiments, we use the best reported models, in terms of certified accuracy, provided by the authors, which correspond Ç 0.5 for 0.25 and Ç = 1.0 for {00.5, 1.03.
DS for certification only. Similar to COHEN, we first certify SMOOTHADV models trained with the same fixed σ. Then, we certify the proposed data dependent of models using the memory- based certification, which we refer to as SMOOTH In Figure 4, we show the certified accuracy for both CIFAR1O 100 and ImageNet the first and second rows, respectively. The last column shows the envelopes per radius. Even though they both share the same classifier fe, SMOOTHADV-DS significantly improves upon SMOOTHADV over all radii and all values of a in training for both 0.25, SMOOTHADV achieves
CIFAR 10 and ImageNet. In particular, for models trained with zero certified accuracy for large certification radii (2 1.0), while SMOOTHADV-DS achieves non- trivial certified accuracy in these cases. Similar to the earlier setup, report the best certified accuracy along with the ACR scores in Table 2. We improve over SMOOTHADV by large margins. For example, the certified accuracy at 0.5 radius increases by 5.4% and 2.8% on CIFARIO and Imagenet, respectively. The improvement is consistent over all radii. The ACR also improves by 0.118 and 0.158 on CIFARIO and ImageNet, respectively.
DS for training and certification. We fine tune the SMOOTHADV trained models (either the retrained CIFAR 10 models or the ImageNet models provided by SMOOTHADV) using Algorithm 2, where o is computed using Algorithm 1. We report the per certification accuracy comparing SMOOTHADV-DS' (certified also using memory based certification) to both SMOOTHADY-DS and SMOOTIADY. SMOOTIAADV-DS further improves the certified accuracy as compared to SMOOTHAAVV-DS with performance gains more prominent on ImageNet. While the improvement of SMOOTHADV-DS DS2 over SMOOTHADV -DS is indeed small, e.g. 0.7% at radius 0.5 on CIFARIO. 10, observe that the performance gaps much larger ImageNet reaching 1.4% at 0.5 radius as shown in Table 2. We see a similar trend in ACR with improvements of 0.013 and 0.069 on CIFARI0 and ImageNet, respectively. SMOOTHADV-
boosts the certified accuracy of SMOOTHADW at radius 0.5 by 6.1% and 4.2% on CIFAR 10 and ImageNet, respectively.
4.3 MACER + DS
We integrate data dependent smoothing within MACER which trains go by minimizing over the Ag parameters 0 the following objective loog (z) + 2 max (? 28 0) 1 max, (6(x) = y). where R also depends on 9. While this seems to be similar in spirit to our approach, we in fact maximize the certification radius over with fixed parameters 0 for every x. We conduct experiments
8

---

Under review as a conference paper at ICLR 2022
Table
Best certified accuracy per radius and ACR MACER, MACER-DD DS and MACER-DO DS*..
Radius Train
CI
Certify
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
MACER MACER-DS
FS
FS
78.8
59.3
43.6
34.7
26.6
19.4
13.0
7.50
0.0
0.0
0.702
FS
DS
79.5
66.7
52.3
43.0
30.8
19.5
12.8
7.55
3.97
1.67
0.841
MACER DS"
DS
52.7
43.5
31.7
7.92
3.65
1.39
Figure 6: Qualitative examples of estimated og for different inputs. From left to right: the set three images on the left: clean image, fixed a = 0.5, and estimated 0² = 0.368 that maximizes the certification radius. Similarly for second set but with a 0.25 and o 0.423. This demonstrates that 0 which maximizes the certification radius, can vary significantly w.r.t. input on CIFARIO* following the training procedure of MACER estimating the expectation with 64 samples, A = 12, and 7 = 8. We set n = 8 in Algorithm with ablations on n = 1 in the appendix. DS for certification only. Similar the earlier setup in COHEN and SMOOTHADV, we certify models with fixed a and then with data dependent o using the memory based certification, referred to as MACER-DS. In Figure 5, we observe that MACER-DS significantly outperforms MACER particularly in the large radius region. This can also be seen in the envelope figure reporting the best certified accuracy per radius over a. Similarly, Table 3 demonstrates the benefits of data dependent smoothing, where it boosts certified accuracy by 7.4% (from 59.3% to 66.7%) and 8. 8.7% (43.6 to 52.3) at 0.25 and 0.5 radii, respectively. Moreover, we improve ACR by 0.139 points.
DS for training and certification. We incorporate data dependent smoothing as part of MACER training and certification in a similar fashion to the earlier setup, dubbed MACER-DS". Figure shows the improvement of MACERDDS* over the certification only MACER-DS over all trained models. Table 3 summarizes the best certified accuracy per radius. Overall, we find that the performance is comparable or slightly better than MACÉR-DS, which is still significantly better than MACER by 8.67% at radius 0.5. We also observe that MACER-DS enjoys better ACR than MACER -D22 with both being far better than the MACER baseline.
4.4 DISCUSSION AND ABLATION
0.8
SmoothAdv
Varying K. We pose the question: does attaining better solutions to our proposed Objective improve certified accuracy? To an- swer this, we control the solution quality of o by certifying trained
Certified ancuryy
0.6
+os itr 300
+05
0.4
+D5 -b57--
models with a varying number of stochastic gradient ascent itera- tions K in Algorithm 1. In particular, we certify the trained mod- els SMOOTHADY-DS and SMOOTHADY-DS on CIFARIO and Im- ageNet, respectively, with varying K. We leave the rest of the experiments for other models to the appendix. We observe in Figure 7 that the certified accuracy per radius consistently improves as K increases, particularly in the large radius regime. This is expected, since Algorithm 1 produces better optimal smoothing of per input with larger K, which in turn improves the certification radius leaving room for improvements with more powerful optimizers*.
DD-2-tr0000
0.2
E cuiliux
0.6
Ceriifed scmvey
0.4
SmoothAdvv
+DS-itr-100
+DS-It-200
+DS-1t-300
Visualizing o. We show the variation of oF that maximizes the cer- tification radius over different inputs æ. Figure shows two examples, where the first and fourth columns contain the clean images. In the second column, a choice of fixed a = 0.5 is too large compared to our estimated of 0.368 that maximizes the certification radius as per Algorithm I. As for the fifth column, we observe that a constant 0.25 is far less than of 0.423. This indicates that indeed the a maximizing the certification radius varies significantly over inputs.
+D5 -DS-ttr-000
0.5
F radius
Figure 7: Varying K in Al-
gorithm 2. Top figure shows certification with au 0.12 on CIFARIO and du 0.5 Im- ageNet shown at the bottom.
*ResNet-50 trained models on ImageNet are not provided by the authors. 'Greedy heuristics solving Equation? 3 are in the appendix, as they perform far worse than our approach.

---

Under review as a conference paper at ICLR 2022
5 REPRODUCIBILITY STATEMENT
This work has two main components to reproducing our experimental results; Algorithm and the memory-basee certification. In the setup paragraph our experimental section, we mentioned all necessary implementation details for Algorithm 1. Nonetheless, we provide implementation using PyTorch (Paszke et al., 2019) of Algorithm
Appendix A. As for memory based certification, provide detailed algorithm supported with Py PyTorch implementation of memory based certification in Appendix C. Algorithm 2 is based on publically available code training with links in the appendix. Moreover, since used trained models with different frameworks, links to the corresponding Github public repositories in Appendix A. We also attach code reproducing some of the experimetns in the zip file attached in the submission. The full code will be released in the future.
provide the
6 ETHICS STATEMENT
Since work has an experimental nature where all of experiments computational, believe that our work did not raise any ethical concerns. In particular, we did not include any human subjects, any potential harmful insights, nor discrimination.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. International Conference on Machine Learning (ICML), 2018.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience artificial neural networks. In International Symposium on Aulomated Technology for Verification and Analysis, 2017. 2
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. International Conference on Machine Learning (ICMI.,, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICMI.), 2019. 1, 2, 3, 5, 6, 13, 15, 17, 18
Ruediger Ehlers. Formal verification of piece-wise wise linear feed forward neural networks. In Interna- fional Symposium on Automated Technology for Verification and Analysis, 2017. 2
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations (ICLR), 2015. 1
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016. 6
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference Computer Aided Verification, 2017.
Diederik P Kingma and Max Welling, Auto-encoding variational bayes. International Conference on Learning Representations (ICLR), 2014.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2012.
10

---

Under review as a conference paper at ICLR 2022
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy (SP). IEEE, 2019. 1,2
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by ran- domized ablation. In Association for the Advancement of Artificial Intelligence (AAAI), 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Alessio Lomuscio and Lalit Maganti. An approach reachability analysis for feed-forward relu neural networks. arXiv preprint (o.xv:/706.073355 2017. 2
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR), 2018.
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 Vetoto Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high high-peerfrmancc deep learning library. Advances in Neural Information Processing Systems (NeurIPS), 2019. 10, 13
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. International Conference Machine Learning (ICML), 2014. 4
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision (IJCV), 2015. 6
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang. Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems (NeurIPS), 2019a. 1, 2, 3, 6, 13, 18
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification of neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2019b. 2
Hadi Salman, Mingjie Sun, Greg Yang. Ashish Kapoor, and Zico Kolter. Black-box smoothing: provable defense for pretrained classifiers. arXiv preprint arXiv:2003.01908 2020. 2
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.61999 2013.
Jiaye Teng, Guang-He Lee, and Yang Yuan. & adversarial robustness certificates: randomized smoothing approach. https: /pwpreveeeeeeeeeeeoe/ee/ee wwwppeeewwwwnee/eoooooooooeeeeee wwwp/eet/o/iieeeeeeeeeeeeeeeeeee
wttp://wwww/eoooooooooooooooooo. www.gd/s,........o.oo. 2019. 2019.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed
integer programming. International Conference on Learning Representations (ICLR), 2019. 2
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint 2rXiv:2002.08347, 2020.
Jonathan Uesato, Brendan O' O'Donoghue, Aaron den Oord, and Pushmeet Kohli. Adversarial risk and the dangers of evaluating against weak attacks. International Conference on Machine Learning (ICMI), 2018. 2018.
11

---

Under review as a conference paper at ICLR 2022
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation certified robustness for relu networks. International Conference Machine Learning (ICML), 2018. 2
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 1992. 4
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning (ICML), 2018. 2
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. International Conference Machine Learning (ICML), 2020.
1,3,27 27
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsich, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. International Conference on Learning Representations (ICLR), 2020. 2, 3, 4, 6, 24
Dinghuai Zhang. Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Filling the soap bubbles: Efficient black-box adversarial certification with non-gaussian smoothing. https: //openreview..o net foormm id- Skg8gJBFvr, 2019. 3
12

---

Under review as a conference paper at ICLR 2022
A IMPLEMENTATION DETAILS
For reproducibility, we will release the full code upon acceptance, Nevertheless, we give the detailed implementation of Algorithm I in PyTorch Paszke et al. (2019) below.
import terch
from torch. autograd import Variable
from torch, di sttributions normal import Normal def Opt mzesi gma (model, batch, alpha, sig_0, K, n)
device-' :''
batch_size batch.shaper
(eriires_rra-Truee view (batch_sike size, 1, 1, 1) m = Normal (torch. zeros saatch_size] to (device), torch. ones tbatch_sizee .to (device))
sig Variable(sig__)
11
#Reshaping for
12
new_shape [batch_size + n] new new_shape.extee (batch_siaa _izee
13
new_batch batchhrrpeaa ((I,,, 1, 1)) wiww
ripea_re sig. reg.repeat ((1, n, 1, 11) wi..www(-1,,,1111
16
17
for in range (K)
18
eps = torch. randn_like like (new_batch) +sigma
Reparamitrizatioo trick
19
out model (new_batch eps) reshape (batch_size, n, 10) mean (1)
for CIFAR10
20
vals, torch. topk (out, 2) vals. talsssrraspose_(0, 1)
23
gap m. icdf (vals[0] clamp_ 02, 0. ) m. m.iedf (vals [1] claapp_ 10.02, 0.98))
24
radius sig. reshape (-1)
gap The radius formula grad - torch.autog autograd grad (radius. sum (), sig)
27
sig. data += aipha.grad
Gradient Ascent step
28
return rig.ppess
For comparisons against Cohen et al. (2019), we followed their official code in https:/ githuk www.ooooooooooooo http//oousaab///e aawaaabbmmoottiing We also followed the common practice in using their provided code for certifying all models in all of our experiments. For comparisons against SmoothAdv (Salman al., 2019a), we also followed their official implementation in https: github. com/ Hadi sa ham.d/d/oommm//mm/t/aaaaaaaa / //github. wttchuu..oo//utttteeeeeeeee comm//antiin//mmccee.. wtt.:/oooiiiaattesssriieaee and similarly for MACER https:
B DATA DEPENDENT GREEDY SEARCH OVER Ø
We observe that the optimization problem equation 3 that solve for every input is one dimensional in of In this section, we show that heuristic grid search procedures are far inferior to solving Equation equation with our solver in Algorithm 1. In particular, sample complexity as our approach for data dependent certification a trivial heuristic grid search as baseline does not work. We conduct experiments where we only certify with data dependent smoothing a pre-trained model SmoothAdv with training E {0..12 0.25.0.50) on CIFAR10 10. We examine a single model SmoothAdv-DS which is certified with K 100 iterations and with n = to approximate the expectation in Algorithm 1. Observe that since n = 1, and including the forward and backward passes computation, our data dependent certification of SmoothAdv-DD has a total of 200, since K 100, evaluations for every given before performing the certification with the optimized o. To that end, we compare against crude grid search baseline over σ and for a fair comparison, with total of 200 evaluations. We restrict the grid search to o [0, 1] with resolution of 1/200 so that the total number of evaluations is always exactly 200 similar to our SmoothAdy-Di That is say, the grid heuristic search solves the following problem:
show that under the same
13

---

Under review as a conference paper at ICLR 2022
204
1.5
07
05
22
1.5
Figure 8: Certified accuracy per radius per o comparison of SmoothAdy against greedy search heuristic data dependent smoothing on CIFARIO. We observe that when the number of samples n in Equation 4 the better the performance. Moreover, and despite that the total number of evaluations of the data dependent certification matches approach SmoothAdv-DS reported in Figure 4, the performance is still far inferior to even data dependent certification as also evident from the last envelope figure.
n
0
arg max
Oi 2
$
S0 (xr + oz(1] - Φ- Σ
max oRCA
fā + o:ē)]
6 200 200
200
(4)
We also explore with the number of samples to E {1, 10} for the grid search pipeline. Note that this trades-off the accuracy of the expectation approximation the resolution of the solution o
We summarize our results in Figure 8. Note that in the first three figures, report certified accuracies for when the model is certified with the same o {0, 12, 0.25, 0.50} used in training without data dependent smoothing, i.e. fixed for all inputs. We refer to these plots as SmoothAdy-ke 1ooothAdv-0112. 121, SmoothAdv-0.25 and SmoothAdv-0.50 grid search heuristic as Saarthhdy-GDSaae addition, we refer to data dependent baseline AmoothAdv-GDD--ee
An-othhdv-GDDS-oeee and SmoothAdv-GDS-n 10 where n refers to the number of samples approximating the expectation in Equation equation 4. We report the envelops in the last figure.
At first we observe that the larger n used to approximate the expectation, the better the overall certification accuracy. This is regardless of the used train the model. However, the performance still far inferior to the baseline that data independent which is inferior to our approach. This is also evident from the envelope last figure. This indicates that while data dependent smoothing is essential towards improving performance, a careful optimization necessary for to work. We reiterate here that both the grid search heuristic and our approach use the same number of evaluations, i.e. 200, when certifying the model; however, our approach reported in Figure 4 are far more superior.
C MEMORY-BASED CERTIFICATION FOR DATA DEPENDENT CLASSIFIERS
Algorithm 3: Memory-Baat Based Certification
Input: input point ZN+1, certified region Rg+1, prediction CN+1, and memory M Result: Prediction for 21 and certified region at # that does not intersect with any certified region in M.
for C,, RR) E M do if CNC+1 + C, then
if xN++1 E R; then
RN41 LaggestttnSubbetttt RN41),
RN41 t RN+1;
Cx+1 C C,
else if Intersect(Rwnt R.) then
R' La Tiargesttoutttussee(RR RN+1);
RN+1 R'
end
add (IN=1,CN+1, RN+1) to M;
return Cx+1. RN+1;
14

---

Under review as a conference paper at ICLR 2022
Let M = {(1,, C2, R be set of the triplets: the input I;, the prediction of z; denoted by Ca and the certification region at 2, denoted as R; which is characterized by the certification radius R, and the center 2;- Moreover, we assume that R2 n R 0, Vi # j.C. * Cj. That is to say, none of the certification regions of the inputs stored in the memory M intersect for inputs with different predictions. This is the key property for a sound certification procedure. Otherwise, if such property does not hold, then this implies that the data dependent classifier produces different predictions within the same certified region. In what follows, and cireumvent this nuisance in the data dependent classifier go. we rely on updating the memory while enforcing this property to hold. In particular, we certify the data dependent classifier using the classical Monte Carlo approach by Cohen et al. (2019) while guaranteeing that the certified regions does not intersect with the certification region of any previously predicted inputs.
In what follows, we present Algorithm 3 that enforces the non-intersection property of certified regions M. Let RN++1 be the certified region at IN+1 of go. (i) If NN+1 E RR and arg max, (x # C,, we find the largest RN+1 such that the following two properties hold Rv++1 C Rvy11 and RN+1 C R2. For when the certified regions R. are simple Ez-balls, finding the largest RN+1 satisfying previous two properties is straightforward. We denote this with the function LazgestIn (second example in Figure 2). We then update R with the refined RN+1 and change CN+11 to C,, (ii) Otherwise, if R1 n R2 * 0 where #1 $ R. and arg max (1) o C.. we find R'++1 such that Rxx+1 S Rx is the largest subset of RN++1 non-intersecting with Ri. We denote this function La hargesttut.tSusset R' Moreover, computing Largest Out Subset t for when R, are f2-balls is straightforward. At last, note that Intersect is function that returns whether two 2--balls intersect. At last, we then add C RN+1) to memory. We provide below a pytorch implementation of the memory- based certification of the pseudo alguoritg
(third example in Figure 2). We then update RN++1 with the refined
While the memory- based certification is essential for a sound certification, empirically on CIFARIO and ImageNet, we never found in any of the experiments a case where two inputs predicted differently suffer from intersecting certified regions. That is to say, the certified regions in the memory for every input is the certified regions granted by the Monte Carlo certificates of Cohen et al. (2019) for the data dependent classifier. We hypothesize that this is due to the following reasons: (i) Image datasets have very high dimensionality, resulting in samples very far apart, compared with the certified radius that randomized smoothing could provide. Thus, it is very unlikely to find two samples that have intersecting certified regions. (fi) Even if the rare case where two image inputs are close to one another that their certified regions intersect, we found that the data dependent classifier go predicts these inputs similarly (the left example of Figure 2). This is since the data dependent classifier trained to output smooth prediction, i.e. prediction changes are small for small input changes, resulting in a shared prediction. (iii) To maintain reasonable test accuracy on clean samples, the values of a, and correspondingly optimized of used in smoothing are moderately low (oz S 1.0). This results in limited smaller certified regions, &y balls of radii z 4o"; which is much smaller than the distance between inputs in higher dimensional data (e.g. ImageNet).
It is worthwhile mentioning that while the memory- based certificate could work, in principle, inde- pendently without being combined with the data dependent smooth classifier under any arbitrary choice of certification radius for every input; this results in sub-optimal certification. This is since this may result in one of the following situations: (i) Assigning large radii for every input will yield classifier that is very robust, but inaccurate. This is since several new points to be certified later will more likely fall in the certification region requiring either changing their prediction (inaccurate predictions) reducing their certification radius. Therefore, measuring the certified accuracy for such a classifier will be very poor since it counts for both accuracy and robustness. (ii) Assigning, on the other hand, small certified radii for every input will result in highly accurate classifier but very low robustness. Hence, this also results in a very small certified accuracy at large radii. Therefore, we combine the memory based certificate with our data-dependent smooth classifier that has better robustness/accuracy tradeoff.
For completeness, we provide the full implementation of the memory- algorithm using Py Torch.
import torch
class Memory Memory_Based__ Cwwtificatinn (object)
def _ inii :
se1 f. sawedaavdd_aade []
15

---

Under review as a conference paper at ICLR 2022
images prod.
def Linternal_adjustnen (self, img, rad, pre)
diff torch. (img- reshape (1, -1] torch. corch.stackssell (self.
saved_ images) reshape (Len (self saald..avved__adiii_
-1), dim=1)
11
12
#nere_overiap ditt (torch, tensor (selt. raave__addi) rad)
#Check whether this image is with overiap with any other instances
14
if where_overlap.any preds_overlap self. saved_ o [where_overlap] where_overlap diff class pverlpp != pre
15
16
18
#Check whether this image is with overlap with instances with different prediction
19
if aave__addiiwitth_overrtie self. self.saved_radi. [where_overlag]
())
#Get the radii, differences where the overlap
22
dif_with - diff diff [where_overlapp]
25
preds_ sartllp_witth__m with diff class preds_overiapl
there_overraa__dee class
25
rad_with_overlegp [ed__itth_ovrrla__ddif__.cll savedradii.wiith_over..g
where__verlap__dfff_cc
d1f_with__ovrlee_ddfff...lk dif_with_overlapl where__oeerla__dfff.ccm
27
28
rad, rad idx =
rad tad_with__oerlaaddffffcc
30
if rtem)) pre
31
ff_class ass [ [rad_idx]
32
rad corch.abe (rad) item
return rad, pre
35
36
def adjust radius (self, img, rad, pre):
#The ing already exists in the saved dictienary if img in self sale_savee_images: idx self. return self. safe.saved (idk), self, savod_ddctccciicotiooon [idx]
img
40
41
if self. saved_vadiidd != []: #Saved dictionaries not empty
rad, pre delff_interrall_djjsteee
(ing, rad, pre)
44
45
radavid_rddii..eee agpei (rad)
46
self.save imw.em..aae..._. append (ing)
self self.saved_pred itioons append (pre)
return rad, pre
D ADDITIONAL VISUALIZATIONS
Here, we show similar results to the one Figure Similar the earlier observations, while model parameters are fixed, optimal smoothing parameters vary per sample.
E LIMITATIONS, BROADER IMPACT AND COMPUTE POWERS USED.
Limitations. Similar to any certification framework, the main limitation of this kind of work is its running time to compute the certified radius. The proposed memory-based certification is
16

---

Under review as a conference paper at ICLR 2022
Clean image
du = 0.25
0: 0.392
Clean image
du 0.25
0 0.169
Clean image
07 = 0.50
0 0.705
Clean image
Tg 0.50
0 0.368
Clean image
0g 1.00
6 1.267
Clean image
ag 1.00
6 0.813
Clean image
0.25
0.423
Clcan image
0.25
0.174
Clean image
0.50
0.705
Clean image
0.50
a. 0.374
Clean image
1.00
1.249
Clean image
1.00
0.831
Figure 10: Visualizing the extreme o. We report the visual comparison between the constant on and the optimal attained of for Cohen Models (first three rows) and SmoothAdv (last three rows) both ImageNet.
the cost of both memory and computational complexity. While the memory cost of order O(N) the computational complexity is more involved. Let p be the probability that new point EN+1 be in one of the certification regions R,, n is the complexity computing a certification region at J4 i.e. RN-I, using the classical Monte Carlo Algorithms of Cohen et al. (2019), then the expected computational complexity of prediction or certification will be O(N (1 (2N + n)). The factor 2N + n is due to performing N comparisons to check that 2N+1 not in any R., then computing R of complexity n, and at last a complexity of N for computing Ry Informally, for larger N and in small dimensional input, p leading complexity of order N. When N
17

---

Under review as a conference paper at ICLR 2022
is smaller compared to the imput dimension, we have with expected complexity of order 2N + n. Moreover, the memory-but basod data dependent smooth classifier is order dependent. That is, the certified accuracy depends on the order at which the data at test time is presented. However, this is not the case if there is no overlap between the certified regions differently predicted inputs (middle and right scenarios of Figure 2 do not occur). We found that is the case in all of experiments making our memory-enhancee data dependent smooth classifier order invariant. We elaborated on why we believe that the case in Appendix C. We plan in future extension to delve into more practical solution to this problem. We postpone the design for more efficient algorithms that validate the soundness of data dependent certification future work.
Broader Impact. While the performance of Deep Neural networks is dominating several fields, the existence adversarial examples hinders their deployment in lots of applications. This raise the attention build networks that are not only accurate, but also robust such perturbations. This work takes a step towards a remedy for this nuisance by improving the certified robustmess of deep neural networks.
Compute Powers. In our experiment on CIFARIO, we used either NVIDIA Quadro RTX-600 GPU or NVIDIA 1080TI GPU. For ImageNet experiments, we used NVIDIA- VV00 GPU. Note that one GPU was enough to run any of our experiments.
F DETAILED ABLATIONS
F.1 COHEN VS COHEN-DS VS COHEN-DS
this section, we detail certified accuracy per radius for all trained models per a for Cohen and per and number of iterations K for Cohen al. (2019), Cohen-DS and Cohen-DS2 in Algorithm 1 on both CIFAR10 and ImageNet.
F.2 SMOOTHADV VS SMOOTHADN-DS vs SMOOTHADY-DS
In similar spirit to the previous section, we report the certified accuracy for the SmoothAdy variants, namely, SmoothAdv Salman et al. (2019a), SmoothAdy-DS and SmoothAdv-DS" on CIFAR10 and ImageNet.
18

---

Under review as a conference paper at ICLR 2022
Table 4: Certified accuracy per radius on CIFARIO. We compare Cohen against Cohen-DS under varying a and number of iterations in Algorithm
2 (CIFARIO)
0.0
0.25
0.50
0.75
1.00)
1.25
1.50
1.75
2.00
2.25
2.50
Cohen
0.12
79.89
56.26
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.25
74.45
58.34
40.13
22.85
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0 0.50
63.72
52.15
40.13
29.17
20.18
13.08
7.33
3.33
0.0
a =0.2
K=100
77.19
61.27
20.8
5.47
1.23
0.02
0.0
о =0.12
K=200
74.98
60.67
19.75
4.05
0.94
0.22
0.01
0.0
0.0
0.0
0.0
σ =0.12
K=300
73.56
60.08
19.63
4.37
1.12
0.36
0.08
0.0
0.0
0.0
0.0
=0.12
K=400
72.11
59.38
19.58
4.27
1.39
0.58
0.13
0.0
0.0
0.0
0.0
σ =0.12
K=500
70.78
58.77
19.5
4.77
1.51
0.68
0.14
0.0
0.0
0.0
0 =0.12
K=600
70.17
58.46
19.51
4.75
1.63
0.85
0.18
0.03
0.0
0.0
0.0
a =0.12
K=700
69.83
58.25
19.91
5.05
1.83
0.88
0.21
0.04
0.0
0.0
0.0
=0.12
K=800
69.25
$7.97
19.75
5.04
1.99
0.95
0.17
0.03
0.0
0.0
0.0
=0.12
K=900
68.27
57.51
19.91
5.07
1.94
0.93
0.21
0.04
0.0
0.0
0.0
a =025
K=100
73.17
64.54
47.48
22.58
1.82
0.47
o =025
K=200
71.62
64.2
47.3
21.66
5.45
1.15
0.34
0.13
0.06
0.01
0.0
=025
K=300
70.23
63.91
47.44
21.75
5.38
1.37
0.43
0.21
0.13
0.04
0.02
Cohen-DDS
=0.25
K=400
69.41
63.42
47.43
22.23
5.83
1.38
0.49
0.26
0.1
0.04
0.02
=0.25
K=500
68.88
63.53
47.56
22.19
5.8
1.54
0.53
0.26
0.06
0.03
a =0.25
K=600
68.09
63.21
47.78
22.05
6.16
1.59
0.51
0.25
0.12
0.07
0.02
a =0.55
K=700
67.57
63.02
47.6
22.25
5.97
1.63
0.57
0.29
0.11
0.04
0.02
=0.25
K=800
67.36
62.93
47.64
22.04
6.29
1.62
0.6
0.27
0.11
0.04
0.02
=0.25
K=900
67.22
62.93
47.45
22.55
6.19
1.62
0.54
0.26
0.11
0.05
0.03
α =0.50
K=100
63.18
55.88
47.07
37.2
26.56
16.43
8.0
0.55
0.19
σ =0,50
K=200
61.26
55.08
47.25
37.86
27.25
16.49
7.49
2.56
1.07
0.53
0.23
σ 0.50
K=300
59.52
54.25
47.35
38.28
27.29
16.23
7.16
2.39
0.96
0.48
0.24
=0.50
K=400
58.29
53.67
47.19
38.05
27.45
16.39
7.41
2.44
0.93
0.45
0.24
=0.50
K=500
57.46
53.53
47.38
38.28
27.47
16.45
7.38
2.38
0.87
0.48
0.24
σ =0.50
K=600
56.68
53.11
47.04
38.21
27.47
16.34
2.37
0.55
0.32
σ 0,50
K=700
55.83
52.37
46.88
38.12
27.43
16.37
7.21
2.3
1.01
0.57
0.37
0.50
K=800
55.26
52.11
46.8
38.3
27.26
16.19
7.18
2.45
1.04
0.62
0.4
0.50
K=900
54.83
51.83
46.62
38.15
27.55
16.5
7.37
2.52
1.21
0.69
0.5
19

---

Under review as a conference paper at ICLR 2022
Table 5: Certified accuracy per radius CIFAR10. We report Cohen-DS* under varying and
number iterations K Algorithm 1.
& (CIFARIO)
0.25
0.50
0.75
1.00
1.50
1.75
2.00
2.25
2.50
a =0.1
K=100
60.56
26.87
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0 =0.12
K=100
79.8
60.56
26.87
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=200
79.83
62.05
28.13
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=300
79.74
62.81
26.96
0.03
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=400
79.56
63.07
25.47
6.66
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a
K=500
79.4
63.24
24.23
7.74
0.0
0.0
0.0
0.0
0.0
0.0
о =0.12
K=600
79.14
63.23
23.58
7.5
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=700
78.95
63.34
22.96
7.12
0.86
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=800
78.77
63.34
22.57
6.48
1.26
0.0
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=900
79.06
64.6
22.69
6.61
1.68
0.01
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=1000
79.02
64.54
22.27
6.27
1.69
0.02
0.0
0.0
0.0
0.0
0.0
a =0.12
K=1100
78.81
64.41
21.9
$.89
1.58
0.22
0.0
0.0
0.0
0.0
0.0
-0.12
K=1200
78.7
64.37
21.88
5.45
1.42
0.27
0.0
0.0
0.0
0.0
0.0
=0.12
K=1300
78.53
64.39
21.67
5.15
1.31
0.26
0.0
0.0
0.0
0.0
0.0
a =0.2
K=1400
78.39
64.46
21.55
4.96
1.13
0.01
0.0
0.0
0.0
0.0
σ =012
K=1500
78.31
64.41
21.56
4.73
1.05
0.3
0.03
0.0
0.0
0.0
0.0
=025
K=100
74.99
61.47
43,92
24.54
7.93
0.0
0.0
0.0
0.0
0.0
0.0
=025
K=200
75.13
63.21
45.94
25.75
9.35
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=300
75.0
64.03
46.96
25.96
10.05
0.0
0.0
0.0
0.0
0.0
a =0.25
K=400
75.04
64.58
47.59
25.63
9,93
1.92
0.0
0.0
0.0
0.0
0.0
σ =0.25
K=500
74.79
64.9
47.85
25.41
9,42
2.6
0.0
0.0
0.0
0.0
0.0
=0.25
K=600
74.7
65.15
48.38
25.05
8.88
2.69
0.0
0.0
0.0
0.0
0.0
=0.25
K=700
74.51
65.35
48.47
24.71
8.34
2.62
0.01
0.0
0.0
0.0
0.0
K=800
74.46
65.42
48.5
24.72
7.98
2.43
0.52
0.0
0.0
0.0
σ =0.5
K=900
74.58
66.42
50.23
25.57
8.25
2.83
0.74
0.0
0.0
0.0
0.0
α =0.55
K=1000
74.39
66.47
50.17
25.41
7.9
2.63
0.75
0.01
0.0
0.0
0.0
=0.25
K=1100
74.2
66.42
50.31
25.13
7.65
2.41
0.72
0.14
0.0
0.0
0.0
=0.25
K=1200
74.12
66.37
50.37
24.92
7.36
2.31
0.65
0.18
0.0
0.0
0.0
Cohen-DS DS
a =0.25
K=1300
73.98
66.41
50.38
24.75
7.14
2.25
0.58
0.19
0.0
0.0
0.0
a =0.25
K=1400
73.81
66.39
50.41
24.79
6,85
2.2
0.51
0.15
0.03
0.0
0.0
-0.55
K=1500
73.67
66.33
50.31
24.63
6.68
2.03
0.54
0.19
0.03
0.0
0.0
=0.50
K=100
63.92
53.49
42.6
31.83
22.15
14.12
7.48
3.51
0.0
0.0
0.0
a =0.50
K=200
64.14
$4.36
44.3
33.52
23.79
15.14
7.93
3.6
1.09
0.0
0.0
a =0.50
K=300
64.21
54.95
45.32
35.04
24.71
15.81
8.16
3.65
1.36
0.0
0.0
a =0.50
K=400
64.22
55.56
45.92
35.86
25.45
16.28
8.35
3.79
1.41
0.0
0.0
=0.50
K=500
64.14
55.84
46.35
36.29
25.88
16.56
8.39
3.69
1.42
0.3
0.0
=0.50
K=600
64.14
$6.07
46.7
36.71
26.18
16.76
8.48
3.61
1.41
0.45
0.0
α =0.50
K=700
64.04
56.2
46.94
37.09
26.54
16.76
3.63
1.37
0.45
σ 0050
K=800
63.93
56.32
47.23
37.33
26.69
16.91
8.35
3.46
1.28
0.5
0.09
σ 0.50
K=900
64.26
57.26
48.27
38.85
28.41
17.97
8.82
3.66
1.37
0.58
0.14
=0.0
K=1000
64.06
57.26
48.41
38.96
28.49
18.1
8.65
3,64
1.33
0.6
0.21
σ =050
K=1100
57.21
48.47
28.69
18.26
8.57
3.55
1.36
0.59
0.2
σ =0.50
K=1200
63.56
57.15
48.67
38.96
28.81
18.18
8.53
3.52
1.32
0.58
0.23
σ 0.50
K=1300
63.29
57.01
48.81
39.07
28.98
18.31
8.44
3.44
1.3
0.6
0.21
0.50
K=1400
63.09
56.9
48.88
39.11
29.07
18.22
8.62
3.3
1.34
0.56
0.22
0.50
K=1500
62.94
56.87
48.9
39.21
29.04
18.1
8.55
3.27
1.28
0.53
0.23
20

---

Under review as a conference paper at ICLR 2022
Table 6: Certified accuracy per radius on ImageNet. We compare Cohen against Cohen-DS and Cohen-DS' under varying a and number of iterations in Algorithm 1.
E (ImageNet)
0.0
0.25
0.50
0.75
1.00
1.50
2.0
2.5
3.0
3.50
4.0
Cohen
0.25
66.6
58.2
49.0
38.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
ar 0,50
51.4
45.8
42.4
37.4
27.8
0.0
0.0
0.0
0.0
0.0
a
43.6
37.8
35.4
32.6
25.8
19.4
14.4
12.0
8.6
0.0
=0.5
K=100
67.8
61.0
42.8
18.8
0.0
0.0
0.0
0.0
0.0
0.0
о =0.55
K=200
67.0
61.4
53.6
43.0
18.0
0.0
0.0
0.0
0.0
0.0
0.0
о 00.5
K=300
66.8
61.2
53.4
42.2
18.6
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=400
66.2
61.4
53.2
42.2
18.0
0.0
0.0
0.0
0.0
0.0
0.0
Cohen-ID DS
=0.50
K=100
58.4
54.0
48.2
45.2
40.6
30.4
1.8
0.0
0.0
0.0
0.0
a =0.50
K=200
58.0
53.4
48.2
45.2
41.4
29.8
9.0
0.0
0.0
0.0
0.0
a =0550
K=300
58.0
54.0
48.8
45.4
41.4
30.2
9.0
0.0
0.0
0.0
0.0
0.50
K=400
57.8
53.8
48.8
45.6
42.0
30.4
8.2
0.0
0.0
0.0
0.0
11.0
K=100
45.0
42.6
40.4
39.0
36.4
29.6
22.4
17.8
13.8
10.0
0.2
1.0
K=200
45.2
43.0
41.8
39.4
36.8
29.6
23.0
18.6
14.2
10.2
0.6
a 1.0
K=300
45.0
43.4
41.2
39.6
37.2
30.0
23.4
18.8
14.4
9.4
2.0
= 1.0
K=400
44.8
43.2
41.4
39.6
37.2
30.4
23.2
18.8
14.6
9.8
1.8
a =0.25
K=100
67.2
64.2
58.4
45.4
17.8
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=200
66.8
64.2
58.2
45.6
18.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.5
K=300
66.6
64.2
58.0
45.2
18.4
0.0
0.0
0.0
0.0
0.0
0.0
a =025
K=400
45.0
18.0
0.0
0.0
0.0
0.0
0.0
0.0
Cohen-DS²
σ -050
K=100
58.0
55.2
51.6
46.2
41.2
30.2
2.2
0.0
0.0
0.0
0.0
a =0.50
K=200
57.6
55.2
51.8
47.0
41.8
30.4
8.0
0.0
0.0
0.0
0.0
=0.50
K=300
57.6
55.0
51.8
46.8
41.8
30.4
8.0
0.0
0.0
0.0
0.0
=0.50
K=400
57.4
55.4
51.6
47.4
41.8
30.6
8.2
0.0
0.0
0.0
0.0
K=100
44.6
41.4
38.6
37.2
31.4
24.8
20.6
16.6
11.0
0.4
1.0
K=200
46.6
44.4
42.0
39.2
37.6
31.2
25.0
20.8
17.0
10.8
0.4
1.0
K=300
46.0
44.6
41.8
39.2
37.4
31.4
24.6
20.8
17.2
11.0
1.8
1.0
K=400
46.8
45.0
42.6
39.4
37.6
31.8
24.8
21.2
16.8
11.0
2.0
21

---

Under review as a conference paper at ICLR 2022
Table 7: Certified accuracy per radius on CIFARIO. We compare SmoothAdy against SmoothAdy-De and SmoothAdv-DS' under varying a and number of iterations K in Algorithm 1.
E (CIFARIO)
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
SmoothAdy
0.12
75.97
62.44
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.25
70.82
59.55
46.71
33.66
0.0
0,0
0.0
0.0
0.0
0.0
0.0
0.50
60.96
52.6
43.5
34.62
26.53
19.49
12.9
7.47
0.0
0.0
0.0
-0122
K=100
75.74
63.58
40.88
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=200
75.7
45.05
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=300
75.69
64.97
46.13
0.55
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=400
75.73
65.43
46.39
22.49
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=500
75.74
65.75
46.57
25.06
0.03
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=600
75.72
66.04
46.64
25.16
0.24
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=700
75.66
46.74
24.64
7.26
0.0
0.0
0.0
0.0
0.0
о =0112
K=800
75.65
66.3
46.61
23.97
11.54
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=900
75.64
66.44
46.43
23.48
11.75
0.03
0.0
0.0
0.0
0.0
0.0
=0.25
K=100
71.34
60.81
48.38
35.14
17.76
0.0
0.0
0.0
0.0
0.0
0.0
a =0.25
K=200
71.32
61.38
49.44
36.24
20.71
0.01
0.0
0.0
0.0
0.0
SmoothAdy-Dn -DS
a =0.25
K=300
71.3
62.01
50.16
36.9
21.69
0.28
0.0
0.0
0.0
0.0
0.0
a =0.25
K=400
71.32
62.45
50.76
37.24
22.33
8.37
0.01
0.0
0.0
0.0
0.0
=0.25
K=500
71.23
62.82
51.27
37.46
22.42
10.67
0.01
0.0
0.0
0.0
0.0
=0.25
K=600
71,26
63.02
51.66
37.66
22.04
11.06
0.06
0.0
0.0
0.0
0.0
=0.25
K=700
71.12
63.26
51.72
37.61
21.82
11.0
0.52
0.0
0.0
0.0
0.0
a =0.55
K=800
71.07
63.4
51.94
37.5
21.43
10.6
4.26
0.0
0.0
0.0
0.0
a =025
K=900
71.04
63.54
52.1
37.38
21.18
10.1
4.63
0.0
0.0
0.0
0.0
=0.50
K=100
61.16
53.06
44.28
35.42
27.29
20.18
13.6
7.82
0.02
0.0
0.0
a =0.50
K=200
61.22
53.44
44.96
36.11
28.0
20.81
13.98
8.25
2.85
0.0
0.0
σ =0.50
K=300
61.24
53.74
45.39
36.81
28.72
21.21
14.23
8.29
3.29
0.0
0.0
σ =050
K=400
61,22
53.95
45.65
37.29
29.22
21.58
14.53
8.42
3.78
0.05
0.0
0.50
K=500
61.21
54.15
46.03
37.8
29.54
21.72
14.73
8.43
3,99
1.02
0.0
=0500
K=600
61.2
54.3
46.42
38.11
29.83
21.94
14.95
8.42
4.07
1.57
0.0
0 0.50
K=700
61.23
54.47
46.58
38.39
30.24
22.04
14.95
8.5
4.12
1.77
0.03
0 -0,00
K=800
61.19
54.58
46.73
38.65
30,39
22.15
14.86
8.49
4.09
1.83
0.43
σ 0.50
K=900
61.25
54.65
46.88
38.82
30.6
22.19
14.89
8.49
4.17
1.84
0.6
a =0.12
K=100
76.04
63.62
41.88
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=200
76.03
64.54
46.4
0.01
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=300
76.0
65.36
47.36
0.82
0.0
0.0
0.0
0.0
0.0
0.0
0.0
σ =0.2
K=400
75.99
65.85
47.98
23.18
0.0
0.0
0.0
0.0
0.0
σ =0.2
K=500
76.11
66.15
48.16
26.09
0.07
0.0
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=600
76.14
66.39
48.13
26.08
0.47
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=700
76.15
66.52
48.1
25.73
7.99
0.0
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=800
76.15
66.69
47.84
25.16
11.89
0.02
0.0
0.0
0.0
0.0
0.0
K=900
76.05
66.77
47.9
24.34
11.82
0.06
0.0
0.0
0.0
0.0
о =025
K=100
71.2
60.56
48.36
35.19
17.76
0.0
0.0
0.0
0.0
0.0
0.0
=0255
K=200
71.27
61.55
49.57
36.45
21.31
0.01
0.0
0.0
0.0
0.0
0.0
SmoothAdv-DS DS
=0.25
K=300
71.3
62.16
50.75
37.41
22.66
0.48
0.0
0.0
0.0
0.0
0.0
a =0.25
K=400
71.41
62.76
51.44
37.85
23.18
9.12
0.01
0.0
0.0
0.0
0.0
a =0.25
K=500
71.37
63.0
51.89
38.06
23.16
11.37
0.04
0.0
0.0
0.0
0.0
a =0.25
K=600
71.37
63.36
52.25
38.31
22.8
11.84
0.16
0.0
0.0
0.0
0.0
=0.25
K=700
71.35
63.45
52.43
38.33
22.58
11.61
0.73
0.0
0.0
0.0
0.0
=0.25
K=800
71,25
63.65
52.67
38.26
22.35
11.17
4.69
0.0
0.0
0.0
0.0
a =0.25
K=900
71.21
63.85
52.81
38.21
22.21
10.75
0.03
0.0
0.0
0.0
a =0550
K=100
61.08
$3.0
44.33
35.59
27.49
20.09
13.74
7.98
0.04
0.0
0.0
=0.50
K=200
61.07
53.41
44.95
36.33
28.39
20.86
14.05
8.22
2.9
0.0
0.0
=0.50
K=300
61.1
53.8
45.61
37.13
28.9
21.5
14.32
8.56
3.57
0.0
0.0
σ =0.50
K=400
61.1
54.14
46.02
37.77
29.3
21.94
14.66
8.63
3.89
0.06
0.0
σ =0.50
K=500
61.15
54.21
46.52
38.15
29.79
22.21
14.91
8.66
4.23
1.05
0.0
σ 0.50
K=600
61.2
54.33
46.89
38.59
30.08
22.35
15.01
8.74
4.28
1.56
0.01
0050
K=700
61.18
54.56
47.11
38.93
30.4
22.51
15.12
8.85
4.34
1.77
0.03
0.50
K=800
61.15
54.72
47.41
39.17
30.59
22.56
15.14
8.75
4.31
1.85
0.53
σ -050
K=900
61.12
54.78
47.62
39.32
30.78
22.64
15.14
8.73
4.26
1.94
0.71
22

---

Under review as a conference paper at ICLR 2022
Table 8: Certified accuracy per radius on ImageNet. We compare SmoothAdy against SmoothAdy-DD and SmoothAdv-DS under varying o and number of iterations K in Algorithm 1.
& (ImageNet)
0.0
0.25
0.50
0.75
1.00
1.50
2.0
2.5
3.0
3.50
4.0
Smooth
0.25
60.8
57.8
54.6
50.4
0.0
0.0
0.0
0.0
0.0
0.0
0.0
ar 0,50
54.6
52.6
48.8
44.6
42.2
35.6
0.0
0.0
0.0
0.0
0.0
1.0
40.6
39.6
38.6
36.4
33.6
29.8
25.6
20.4
18.0
14.2
0.0
=025
K=100
61.6
59.6
56.8
52.6
31.4
0.0
0.0
0.0
0.0
0.0
0.0
о -0255
K=200
61.6
59.8
57.2
52.8
35.8
0.0
0.0
0.0
0.0
0.0
0.0
-0.55
K=300
62.0
60.2
57.2
52.8
36.6
0.0
0.0
0.0
0.0
0.0
0.0
SmoothAdy- DS
=0.25
K=400
61.8
60.4
57.4
53.2
36.8
0.0
0.0
0.0
0.0
0.0
0.0
=0.50
K=100
55.0
53.6
51.2
47.2
45.2
38.0
4.8
0.0
0.0
0.0
0.0
a =0.50
K=200
55.0
53.8
51.6
48.4
46.4
39.2
16.6
0.0
0.0
0.0
0.0
a =0.50
K=300
55.4
54.0
51.6
48.6
47.0
39.2
18.0
0.0
0.0
0.0
0.0
= 0.50
K=400
55.2
54.0
51.6
48.8
47.0
39.0
18.6
0.0
0.0
0.0
0.0
11.
K=100
41.8
41.0
39.4
37.6
35.2
31.6
28.0
22.6
19.2
15.2
0.8
K=200
42.4
41.8
40.2
38.4
36.6
32.4
28.8
23.4
19.0
14.6
1.2
a 1.0
K=300
42.6
41.8
40.4
38.8
36.8
32.4
29.2
23.8
19.6
15.2
6.2
= 1.0
K=400
42.8
42.2
40.8
38.8
37.0
33.2
29.0
23.8
19.6
14.8
6.2
a =0.55
K=100
62.2
60.4
58.8
54.0
27.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=200
62.0
60.6
58.6
54.2
27.4
0.0
0.0
0.0
0.0
0.0
0.0
=0.55
K=300
62.0
60.4
58.8
54.0
27.4
0.0
0.0
0.0
0.0
0.0
0.0
Smooth DS
a =0.55
K=400
58.8
54.0
27.4
0.0
0.0
0.0
0.0
0.0
0.0
о =0550
K=100
55.8
54.2
52.6
50.4
48.2
43.0
7.8
0.0
0.0
0.0
0.0
a =0.50
K=200
55.2
54.0
51.8
49.8
47.8
42.6
14.2
0.0
0.0
0.0
0.0
=0.50
K=300
55.6
54.0
52.0
49.8
47.8
42.6
15.0
0.0
0.0
0.0
0.0
=0.50
K=400
55.6
54.4
52.2
50.2
48.2
43.0
15.0
0.0
0.0
0.0
0.0
K=100
41.2
40.6
38.4
34.6
30.6
25.4
21.6
18.6
1.2
1.0
K=200
44.4
43.2
41.6
40.6
38.6
34.8
30.6
25.0
21.6
18.4
1.6
= 1.0
K=300
44.2
43.0
41.8
41.2
38.6
34.6
30.6
25.2
21.4
17.8
4.2
1.0
K=400
43.8
43.0
41.0
40.8
38.6
34.6
30.2
25.2
21.4
18.2
4.0
23

---

Under review as a conference paper at ICLR 2022
F.3 MACER VS MACER-DS VS MACER-DS' (N=1) vs MACER-DS' (N=8)
We report Eg certified accuracy per radius for MACER (Zhai et al., 2020) variants on CIFARIO. Note that highlighted in the main manuscript, for certification only, i.e. M ACER- DS, we set n = for all experiments in Algorithm 1. Moreover, in the main paper and for ease of computation we set
for when training employed, i.e. DS? In here also explore the variant where when data dependent smoothing is introduced during training we set n = 8 for ablations. We refer to for when data dependent smoothing is used training and certification as MACER ( in = 1) and MACER DS 8), respectively.
when n and
24

---

Under review as a conference paper at ICLR 2022
Table 9: Certified accuracy per radius on CIFARIO. We compare MACER against MACER-DS and MACER-DS = under varying and number of iterations K in Algorithm 1.
E (CIFARIO)
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
MACER
a 0.122
78.75
58.51
0.0
0.0
a = 0.25
72.51
59.25
43.64
28.25
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.50
61.23
52.52
43.44
34.65
26.57
19.39
13.0
7.5
0.0
0.0
0.0
=0.12
K=100
79.21
60.57
30.95
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=200
79.3
60.98
30.18
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0 =0.12
K=300
79.39
61.33
27.9
0.07
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0 =0.12
K=400
79.45
61.27
25.62
10.07
0.0
0.0
0.0
0.0
0.0
σ =0.12
K=500
79.48
61.4
23.43
11.02
0.01
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=600
79.44
61.55
22.22
10.66
0.11
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=700
79.5
61.39
21.79
9.94
3.82
0.0
0.0
0.0
0.0
0.0
0.0
a -012
K=800
79.47
61.25
21.83
9.33
5.38
0.0
0.0
σ =012
K=900
79.48
61.34
21.59
8.89
6.02
0.1
0.0
0.0
0.0
0.0
0.0
a 0.25
K=100
73.41
63.59
46.37
27.96
12.76
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=200
73.72
65.1
47.51
27.19
13.85
0.0
0.0
0.0
0.0
0.0
0.0
MACER-DS
=0.25
K=300
73.9
65.63
47.81
26.42
13.19
0.0
0.0
0.0
0.0
0.0
0.0
a =0.25
K=400
73.96
66.03
48.12
25.14
12.2
4.17
0.0
0.0
0.0
a =0.25
K=500
74.0
66.18
47.97
23.98
11.01
4.59
0.0
0.0
0.0
0.0
0.0
=0.25
K=600
74.04
66.41
48.23
23.4
9.74
4.23
0.0
0.0
0.0
0.0
0.0
=0.25
K=700
74.02
66.47
48.18
22.86
8.65
3.78
0.0
0.0
0.0
0.0
0.0
a =0.25
K=800
74.07
66.68
48.12
22.58
7.62
1.06
0.0
a =0.25
K=900
74.01
66.74
48.24
22.37
6.88
2.74
1.08
0.0
0.0
0.0
0.0
a =0.50
K=100
62.62
55.99
47.65
38.37
28.3
19.54
12.75
7.55
0.0
0.0
0.0
=0.50
K=200
63.07
57.27
49.54
40.25
29.36
19.44
12.35
7.43
3.23
0.0
0.0
=0.50
K=300
63.28
57.91
50.46
41.4
30.0
19.41
11.99
7.08
3.54
0.0
0.0
a =0.50
K=400
63.39
58.25
51.18
41.98
30.22
19.11
11.69
3.97
a =0.50
K=500
63.5
58.51
51.51
42.4
30.66
18.7
11.13
6.73
3.83
1.06
0.0
-.50
K=600
63.57
58.72
51.83
42.62
30.51
18.66
10.85
6.44
3.7
1.61
0.0
0.50
K=700
63.65
58.9
52.06
42.79
30.63
18.25
10.57
6.25
3.53
1.67
0.0
a =.50
K=800
63.74
$9.02
52.19
42.96
30.62
10.18
3.35
0.45
σ =0.50
K=900
63.79
59.09
52.28
43.03
30.75
18.21
9.89
5.53
3.13
1.62
0.52
σ =0.12
K=100
79.57
61.25
34.66
0.0
0.0
о =0.12
K=200
79.58
61.57
36.29
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=300
79.42
61.35
36.21
0.06
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=400
79.44
61.1
35.32
12.32
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0 =0.12
K=500
60.64
34.22
13.65
0.0
0.0
0.0
0.0
0.0
0.0
0.0
σ -0.12
K=600
79.09
60.23
33.75
13.25
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=700
78.98
60.01
32.89
12.66
1.46
0.0
0.0
0.0
0.0
0.0
0.0
-0.12
K=800
78.85
59.65
32.65
12.07
2.24
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=900
78.78
59.52
32.3
11.4
2.25
0.0
0.0
0.0
0.0
0.0
0.0
a =0.22
K=1000
78.73
59.15
31.58
10.63
2.05
0.0
0.0
MACER-DS DS (n=1)
σ =025
K=100
71.45
59.44
45.71
30.76
14.57
0.0
0.0
0.0
0.0
0.0
0.0
=0.55
K-200
71.81
60.13
46.5
31.3
16.2
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=300
71.81
60.13
46.5
31.3
16.2
0.0
0.0
0.0
0.0
0.0
0.0
=0.25
K=400
71.91
60.48
46.51
30.83
16.73
5.66
0.0
0.0
0.0
0.0
0.0
a =0.25
K=500
71.84
60.56
46.3
30.26
16.43
7.07
0.0
0.0
0.0
a =0.25
K=600
71.77
60.38
45,92
29.84
16.11
7.14
0.0
0.0
0.0
0.0
0.0
=0.25
K=700
71.69
60.12
45.66
29.41
15.6
7.0
0.04
0.0
0.0
0.0
0.0
=0.25
K=800
71.73
60.19
45.41
28.91
15.07
6.68
2.15
0.0
0.0
0.0
0.0
a =0.25
K=900
71.68
60.11
45.14
28.51
14.54
6.23
2.34
0.0
a =0.25
K=1000
71.63
59.98
44.97
28.21
14.08
5.9
2.12
0.0
0.0
0.0
0.0
a =0550
K=100
60.96
53.69
44.96
36.64
28.13
20.46
14.44
8.73
0.01
0.0
0.0
=0.50
K=200
61.37
54.35
46.07
37.43
28.55
20.58
14.26
8.65
3.6
0.0
0.0
=0.50
K=300
61.52
54.74
46.53
37.9
28.91
20.62
14.12
8.42
3.9
0.0
0.0
σ =0.50
K=400
61.42
54.81
46.83
38.02
28.98
20.51
13.69
4.27
0.0
a =0.50
K=500
61.39
54.74
47.03
38.2
28.85
20.25
13.45
8.14
4.16
1.0
0.0
0.50
K=600
61.44
54.8
46.96
38.2
28.83
19.97
13.23
7.94
4.1
1.53
0.0
=0550
K=700
61.35
$4.75
46.89
38.04
28.7
19.53
12.95
7.64
3.98
1.7
0.0
σ 0.50
K=800
61.24
$4.75
46.94
38.1
28.49
12.59
7.46
σ 0.50
K=900
61.25
54.73
46.85
37.94
28.19
18.87
12.29
7.13
3.69
1.7
0.51
0 = 0.50
K=1000
61.21
54.72
46.84
37.87
27.97
18.74
12.08
6.82
3.43
1.66
0.71
25

---

Under review as a conference paper at ICLR 2022
Table 10: Certified accuracy per radius on CIFAR1O. We report MACER- DS' varying a and number of iterations in Algorithm
8) under
& (CIFARIO)
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
=0.12
K=100
81.9
62.52
29.38
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=200
82.16
63.09
29.72
0.0
0.0
0.0
0.0
0.0
0.0
0 =0.12
K=300
82.2
63.4
28.47
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =0.12
K=400
82.21
63.51
26.29
6.84
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=500
82.34
63.76
24.13
7.62
0.0
0.0
0.0
0.0
0.0
0.0
0.0
=0.12
K=600
82.34
63.66
22.6
7.05
0.0
0.0
0.0
0.0
0.0
0.0
0.0
a =012
K=700
82.32
63.84
21.61
6.48
0.6
0.0
0.0
σ 0.12
K=800
82.35
63.9
21.06
5.4
0.83
0.0
0.0
0.0
0.0
0.0
0.0
=012
K=900
82.37
63.9
20.79
4.67
0.82
0.0
0.0
0.0
0.0
0.0
0.0
=0122
K=1000
82.39
63.89
20.57
3.88
0.77
0.0
0.0
0.0
0.0
0.0
0.0
MACER DS (1=8)
=0.25
K=100
75.18
64.79
47.14
29.31
12.56
0.0
0.0
0.0
0.0
0.0
σ =0.25
K=200
75.36
66.23
48.55
28.91
13.99
0.0
0.0
a =0.25
K=300
75.53
66.87
49.24
28.31
14.26
0.01
0.0
0.0
0.0
0.0
0.0
=0.25
K=400
75.57
67.36
49.53
27.35
13.94
3.86
0.0
0.0
0.0
0.0
0.0
=0.25
K=500
75.65
67.71
49.59
26.24
13.23
4.68
0.01
0.0
0.0
0.0
0.0
a
K=600
75.72
67.81
49.64
25.46
12.12
0.0
a =0.25
K=700
75.84
67.93
49.85
24.92
11.1
4.58
0.01
0.01
0.0
0.0
0.0
a =0.25
K=800
75.81
68.08
49.84
24.79
10.18
4.33
1.05
0.01
0.0
0.0
0.0
=0.25
K=900
75.87
68.16
49.84
24.53
9.38
3.81
1.02
0.01
0.0
0.0
0.0
=0.25
K=1000
75.87
68.26
49.94
24.27
8.66
3.32
0.93
0.01
0.01
0.0
0.0
a =0.50
K=100
61.79
55.41
47.8
39.03
29.04
20.62
13.83
7.92
a =0.50
K=200
62.11
56.53
49.36
40.68
30.08
20.55
13.38
7.84
3.07
0.0
0.0
-050
K=300
62.31
$7.21
50.54
41.6
30.79
20.46
13.03
7.56
3.44
0.0
0.0
=0.50
K=400
62.49
57.68
51.12
42.08
31.12
20.21
12.45
7.34
3.65
0.0
0.0
K=500
62.62
$7.98
51.61
42.41
31.3
20.13
12.09
3.65
0.74
σ =0.50
K=600
62.71
58.28
51.82
42.85
31.52
19.78
11.58
6.54
3.56
1.28
0.0
σ =0.50
K=700
62.84
58.35
52.15
43.04
31.42
19.6
11.12
6.33
3.29
1.37
0.0
=0.5
K=800
62.91
58.45
52.33
43.29
31.48
19.47
10.62
5.95
3.21
1.39
0.27
=0.50
K=900
62.93
58.54
52.56
43.44
31.49
19.14
10.17
5.73
3.09
1.34
0.38
0.50
K=1000
63.0
58.66
52.67
43.47
31.66
19.04
9.85
5.49
2.85
1.21
0.4
26

---

Under review as a conference paper at ICLR 2022
Table 11: Best certified accuracy per 4 radii and ACR of YANG and YANG-DS.
((CIFARIO)
0.0
0.25
0.5
0.75
1.0
1.5
2.0
ACR
YANG
92
83
75
71
46
0
0
0.775
YANG-DS
92
89
82
76
58
6
2
0.946
(1maageNe))
0.0
0.25
0.5
0.75
1.0
1.5
2.0
ACR
YANG
78
73
67
63
0
0
0.683
YANG-DS
79
76
70
65
46
0
0.729
Yang (a 0.25)
Yang 0.5)
Yang (a 1.0)
Certified accuracy
0.8
Yang (ACR=0.2121
Tang-DS (ACR-0.479)
Certifed accuracy
0.8
Certifed accuracy
0.6
0.6
0.6
Yang (ACR=0.397)
Yeng (ACR=0.737)
0.4
0.4
1ang-D5 (ACR-0.614)
0.4
Yong-DS (ACR-0.88)
0.7
0.2
0.2
0.0
0.0
0.00
0.25
0.50
0.75
1.00
1.2!
0.0
0.5
1.5
0.0
0.5
1.0
1.5
2.0
1 raaduss
f redius
4 radius
Yang (o 0.25)
Yang (d 0.5)
Yang (o 1.0)
Oertiffed accuracy
0.6
Centeeed accuracy
0.6
Certmed accuracy
0.6
0.4
0.4
0.2
0.2
0.2
Yeng (ACR=0.176)
Yang (ACR=0.339)
Yang (ACR=0.644 0.642)
Yang-DS DS (ACR=0.233)
Yang-DS DS (ACR=0.378)
Yang-DS (ACR=0.681)
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.2
0.4 4 radius
0.6
0.00
0.25
0.50
0.75 radius
1.00
1: radius
Figure 11: & Certified accuracy comparison against Yang per radius per a. We compare Yang against Yang-DS. We show CIFARIO and ImageNet results in first and second rows, respectively. Similar to the earlier experiments on lg certificate, deploying data-dependent smoothing with the memory enhanced classifier yields significant improvement for the L certified accuracy in all considered scenarios.
G DATA-DEPEN SMOOTHING FOR & CERTIFICATES.
While indeed we focused both our methodology and experiments on &g certificates, our methodology extendable to any other l, certificate. For that regard and as per reviewer's ''s request, we conducted experiments on & certification. We leveraged the results of Yang et al. (2020) that derived the tightest L certificate using randomized smoothing with uniform distribution 21 [[-,, A]d. The certified radius in that case has the form R₁ = A(pA PB). We replace our objective in Equation equation 3 with:
x = arg max A (Ee (f (x) - max Leax-e-----a (V +c))) esca
A
We solved our objective in an identical fashion to our Algorithm 1 with the same hyperparameters for À E {0.25, 1.0} in certification on both CIFAR10 10 and ImageNet. Further, we combine our data-dependent smooth classifier with the memory based algorithm proposed in Section 3.5. It is worthwhile mentioning that similar to the & case, the memory based algorithm did not find any overlap between the certified regions of any pair of instances. We report the results in Figure 11 and Table 11. We observe that, similar to our extensive experiments on the & certificate, our proposed memory-enhanced data-dependent smoothing yields consistent improvement in the l certified accuracy. We report an improvement of 7% and 3% over the state of the art certified accuracy at & radius of 0.5 on CIFARIO and ImageNet, respectively. At last, we note similar improvement to the l ACR reported in Table 11.
27

---

Under review as a conference paper at ICLR 2022
H RUNTIME
We measure the certification runtime on an NVIDIA Quadro RTX-6000 GPU for our proposed data dependent smoothed classifier (time includes Algorithm in addition the memory based certification) compared to the certification of a fixed a classifier. Certifying one CIFARIO test input with ResNet18 takes 1.6 and an average of 1.8 seconds for fixed a classifier and for the data dependent classifier (K = 9000, respectively. Certifying an ImageNet test input on ResNet50 takes 109.5 and an average of 136 seconds for a fixed classifier and our data dependent classifier (K = 400), respectively. The runtime overhead added by using Algorithm and memory based certification is negligible compared to the gains certified accuracy.
28


Reviews:
[{"review_id": "z6lvOAvzwU1", "reviewer": "Reviewer_y9v6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "The paper is not in my area but I find it easy to read and follow. I agree that the making the variance of the Gaussian noise to be data-dependent has the potential to largely improve the performance of the randomized smoothing classifier. However, it is not clear to me that why maximizing the radius $R$ would be beneficial to the resulting smooth classifier. It would be better if the author(s) could provide more motivation and justification on their proposed objective function. ", "summary_of_the_paper": "The paper focuses on training robust deep neural networks. The author(s) developed a data-dependent randomized smoothing method to certify the DNN classifier. Their proposed methods are evaluated on benchmark datasets and are shown to outperform other baseline approaches. ", "summary_of_the_review": "The author(s) might want to discuss in detail why it is desirable to maximize the radius $R$ in their proposed objective function. ", "strength_and_weaknesses": "", "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": "lb0KdA0v01X", "reviewer": "Reviewer_DGVf", "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": "The paper is well written and the experiments are well developed. \n\nThe main contribution of the paper is to adapt the smoothing parameter $\\sigma$ to every input data point by maximizing the certification radius $R$. This is a natural way to improve the randomized smoothing technique. Some questions are given below.\n\n1. If one data $x$ is close to the boundary and classified incorrectly (e.g., suppose $x_3$ in Fig.1 is classified incorrectly), then in this case optimizing the radius would actually reduce the value of $\\sigma$. So will this approach apply to models that have low classification accuracy?\n\n2. Regarding the runtime/scalability. If we apply this data-dependent randomized smoothing to perform adversarial training, it seems that we need to generate a specialized gaussian noise for every single sample at each time. In the SmoothAdv algorithm, there they can reuse the gaussian noises to corrupt a batch of samples (because $\\sigma$ is fixed). Can the authors comment on the scalability of your approach?\n\n3. The paper discusses $\\ell_2^r$ certification, can the proposed approach extends to more general types of certifications?", "summary_of_the_paper": "This paper proposes a new randomized smoothing technique to improve the robustness of models. Specifically, in the original randomized smoothing approach, we use a fixed variance parameter $\\sigma$ for the Gaussian smoothing. The authors claim that this is in general suboptimal as some data samples far away from the decision boundary can be further smoothed. Motivated by this, the authors propose to optimize the smoothing parameter $\\sigma$ for every data sample, by solving an optimization problem using Monte Carlo approximation and SGD. The paper also provides a simple procedure for the certification of the data dependent smooth classifier. Through extensive experiments, the paper shows the effectiveness of the proposed approach.", "summary_of_the_review": "See the comments.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TBgT6AvruWx", "reviewer": "Reviewer_viFi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles an important problem and aims to address one major limitation of the randomized smoothing framework: the constant variance of the (Gaussian) smoothing distribution. However, I am some concerns about the proposed approach:\n\n1) The core idea of the approach is to optimize the sigma according to Eq. (2). However, this optimization principle assumes the constant-sigma set-up. Thus, I don't see why optimizing this equation is really principled.\n\nIndeed, as described in Sec. 3.5, the resulting radius does NOT guarantee certification. (Side note: I find it a bit surprising to call the solution then the \"radius of certification\" even though it does not lead to a valid certification radius.)\n\nThe memory-based certification looks like an ad-hoc fix to this problem. This, however, leads to multiple further problems as described in the following.\n\n2) The memory-based certification is changing the predictions of the (smooth) classifier. Thus, the final certificate is actually NOT a certificate for the original (smooth) classifier g -- but only for some adaptively changing classifier. Therefore, the original problem setting is actually never solved by the approach.\n\nMoreover: Why should Eq. (2) make any sense for this classifier? Based on my understanding the memory-based principle could theoretically be used with any real number used as a radius. Thus, one could just randomly assign \"radii of certification\" to a new input sample. Put differently: The memory-based certificate is not really making any use of worst-case classifiers or alike.\n\nFinally, since the certificate is given for this \"changing classifier\", I highly question the (practical) use of the certificate at all. The runtime complexity of the classifier -- and not just the certificate -- scales linearly with the number of samples seen. It is even worse than a KNN-classifier since one has to consider all test samples (and not only the training samples). Moreover, the outcome of the resulting (smooth) classifier will depend on the *order* how the test samples arrive. That is, the predictions might be different when a different order is used. Such behavior is very undesired for a classifier operating on iid data. \n\n3) Given that the method is actually certifying some other classifier, I am also wondering whether the experimental comparison provides any insights. At the end, different classifiers are considered.\n", "summary_of_the_paper": "The paper's core contribution is to extend randomized smoothing to a setting where the smoothing depends on the input data. That is, the variance of the smoothing distribution is not constant anymore but depends on the input. To ensure a proper certificate, the authors propose some memory-based technique (which essentially changes the final classifier based on the observed input data so far).", "summary_of_the_review": "Overall, I highly question the use of the certificate. It is not certifying the actual smooth classifier as desired, but it certifies some other classifier (with highly undesired properties) in a non-scalable way. Thus, also the experimental comparison is questionable.\n\nI am currently giving a score of 3. I might be open to increase it in case the authors clearly state that they are actually not certifying the smooth classifier. Put differently: The presentation has to be updated in various places since at the moment it is highly misleading and readers might get a wrong understanding of what is actually certified. Moreover, the authors should elaborate whether the experimental analysis is still useful or not.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "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": "EDvH0HYnrnn", "reviewer": "Reviewer_Xsdx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem is important and the idea of this paper is interesting but seems quite simple, which simply optimizes the certifiable lower bound of randomized smoothing. I found it a big surprising that this has not been done before. Given the certifiable bound is already there, it seems there is not too much technical difficulties for this method, so I wonder why this has not been done before, given the randomized smoothing has been proposed for several years? Can the authors elaborate on this?\n\nAs far as I understand, the method actually seems to be only applicable to the l2 certification, given the bound is only for l2. So it seems a bit over claiming in the abstract that the method is generic. In addition to this, I believe there are bounds for the other norm certification, and I wonder if the proposed method can be applied to those cases? One example and missing reference is the paper by Li et al 2019: Certified Adversarial Robustness with Additive Noise. In that paper, they propose information theoretic analysis and get a more general bound (although the bound seems to be looser than the one by Cohen et al.), which can do L1 certification. I think a study for this would great improve the paper and should be performed empirically. In addition, Li et al also propose an enhanced training strategy called stability training, which is shown to be able to greatly improve the performance. I would suggest the authors to investigate that training strategy, in addition to the current ones using Cohen, smoothadv and macer.\n\nAnother comment is about the setting of the parameter n in Algorithm 1. It seems the authors only consider setting n = 1, which I think is highly inaccurate with high variance. Although the authors provide some results in the appendix with n=8, I think the study is not deep enough. More detailed studies on this parameter and the effect on the accuracy as well as the balance between training time and accurate need to be investigated.\n\nA minor comment: the visualization in Figure 6 does not seem the provide much information. A better visualization I am looking for actually is similar to the illustration in Figure 1, but on a real case. I am expecting the decision boundary can be drawn and the optimized radiuses of different data samples can be shown as well.", "summary_of_the_paper": "This papers proposes to optimize the certified bound of randomized smoothing to get data dependent perturbations for different data. It also proposes a simple memory-based approach to certifying the resultant smooth classifier due to the lack of guarantee on the overlapping of the perturbation regions. The technique is incorporated into 3 randomized smoothing approaches, which shows improvement over existing methods in experiments.", "summary_of_the_review": "The idea of this paper is interesting and the paper itself is a solid work to improve model robustness by optimizing the certified bounds w.r.t. the noise variance. However, there are missing comparisons with existing techniques/methods, which I hope to be solved.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The idea to adapt the noise variance in the certification of a base classifier sounds natural and interesting, but unfortunately fundamentally flawed, as correctly pointed out by Reviewer viFi (also acknowledged in the authors' response): the author's main algorithm does not lead to any theoretical certification while the empirical fix (based on memory), however successful in one's experiment, does not rule out the possibility of failure when future test samples flood in. Incidentally, I believe this fallacy may have also answered Reviewer Xsdx's question (why this has not been done before). I agree with Reviewer viFi that the writing of this work is a bit deceptive and will require significant change. In particular, one cannot wave hands at claims on certification: you need to formally prove the memory-based empirical fix will provably certify a region for what classifier and under what assumption. Therefore, the current draft cannot be accepted. Please consider rethinking about the idea and rewriting the paper according to the reviewers' comments.
Decision: Reject