Year: 2021

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. Since the data dependent classifier does not directly enjoy sound certification with existing approaches, we propose a memory-enhanced 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 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.

text: 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. Since the data dependent classifier does not directly enjoy sound certification with existing approaches, we propose a memory-enhanced 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 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.

heading: 1 INTRODUCTION
text: 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 a DNN f that correctly classifies an image x, f can be fooled to produce an incorrect prediction for x+ η even when the adversary η is so small that x and x+ η are indistinguishable to the human eye. To circumvent 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 et 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-art certifiable robustness results (Cohen et al., 2019; Lecuyer et al., 2019; Li et al., 2019). In a nutshell, given an input x and a base classifier f , e.g. a DNN, randomized smoothing constructs a “smooth classifier” g(x) = E ∼D [f(x+ )] such that, and under some choices of D, g(x) = g(x+ δ) ∀δ ∈ R. As such, g is certifiable within the certification regionR characterized by x and the smoothing distribution D. While there has been considerable progress in devising a notion of “optimal” smoothing distribution D for whenR is characterized by an `p 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 `2 certificates under D = N (0, σ2I), where σ is a 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 σ2) over the entire input space of x. 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 σ should vary with the input x (data dependent), since using a fixed σ may under-certify inputs (i.e. the constructed smooth classifier g produces smaller certification radii), which are far from the decision boundaries as exemplified by x1 in Figure 1. Moreover, this fixed σ could be large for inputs
x close to the decision boundaries resulting in a smooth classifier g that incorrectly classifies x (refer to x3 in Figure 1).
In this paper, we aim to introduce more structure to the smoothing distribution D by rendering its parameters data dependent. That is to say, the base classifier f is smoothed with a family of smoothing distributions to produce: g(x) = E ∼N (0,σ2xI) [f(x+ )]
1. Note here that the variance of the Gaussian is now dependent on the data input x. Moreover, given that σx varies with x, classical randomized smoothing based certification does not apply directly. We propose a simple memory-based approach to certify the resultant data dependent smooth classifier g. We show that our 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. In particular, given a network f and an input x, we propose to optimize the smoothing distribution parameters for every x, e.g. σ∗x, so they maximize the certification radius. This choice of σ∗x is then used to smooth f at x and construct a smoothed classifier g. Moreover, as the data dependent smooth classifier is not directly certifiable using Cohen et al. (2019) MCMC approaches, we propose a memory-enhanced data dependent smooth classifier 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 on 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 `2 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 COHEN, SMOOTHADV and MACER can further boost results to get certified accuracies of 68.3% on CIFAR10 and 64.2% on ImageNet at `2 perturbations less than 0.25.

heading: 2 RELATED WORK
text: Certified Defenses. 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 a given input (Weng et al., 2018). However, the latter is too expensive for any mixed certification-training routine.
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 `1 certification radius in which the average classifier prediction under this noise is constant. This work was later followed by the tight `2 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
1The paper focuses on Gaussian smoothing, but the idea holds for other parameterized distributions.
guarantees for `1 bounded (Teng et al., 2019), `∞ bounded (Zhang et al., 2019), and `0 bounded (Levine & Feizi, 2020) perturbations. Even more recently, a novel framework that finds the optimal smoothing distribution for a given `p norm (Yang et al., 2020) was proposed showing state-of-art certification results on `1 perturbations. We deviate from the common literature by introducing the notion of smoothing, particularly Gaussian smoothing for `2 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 a larger certification radius) as compared to inputs closer to these boundaries, we optimize for the amount of smoothing per input (specifically σx) 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.

heading: 3 DATA DEPENDENT SMOOTHING

heading: 3.1 PRELIMINARIES AND NOTATIONS
text: We consider the standard classification problem, where x ∈ Rd and the labels y ∈ Y = {1, . . . , k} form the input-label pairs (x, y) sampled from an unknown data distribution. Unless explicitly mentioned, we consider a classifier fθ : Rd → P(Y) parameterized by θ where P(Y) is a probability simplex over k labels. We say that fθ is `rp certifiably accurate for an input x, if and only if, arg maxc f c θ (x) = arg maxc f c θ (x+δ) = y ∀ ‖δ‖p ≤ r, where f cθ is the cth element of fθ. That is to say, the classifier correctly predicts the label of x and enjoys a constant prediction for all perturbations δ that are in the `p ball of radius r from x. As such, the overall `rp 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 `r2 certification.

heading: 3.2 OVERVIEW OF RANDOMIZED SMOOTHING
text: Randomized smoothing constructs a certifiable classifier gθ by smoothing a base classifier fθ. That is to say, for any σ > 0, the smooth classifier is defined as follows: gθ(x) = E ∼N (0,σ2I) [fθ(x+ )]. Let gθ predict label cA for input x with some confidence, i.e. E [f cAθ (x + )] = pA ≥ pB = maxc6=cA E [f cθ (x+ )], then, gθ is certifiably robust at x with certification radius:
R = σ
2
( Φ−1(pA)− Φ−1(pB) ) . (1)
Here, g(x+ δ) = g(x) ∀‖δ‖2 ≤ R, where Φ is the CDF of the standard Gaussian.

heading: 3.3 ROBUSTNESS-ACCURACY TRADE-OFF
text: Note that Equation 1 holds regardless of the prediction cA made by the smooth classifier gθ. This suggests that one can perhaps improve the robustness of gθ, i.e. increase certification radius R where gθ is constant, by increasing the hyper parameter σ in Equation 1. However, to reason about `r2 certification accuracy, it is not enough to increase the certification radius R, as this requires cA to be the correct prediction for x by gθ. This reveals the robustness-accuracy trade-off as one cannot improve `r2 certified accuracy by only increasing the certification radius R (robustness) through the increase in σ. This is because it comes at the expense of requiring a classifier gθ that correctly classifies x with correct label y under large Gaussian perturbations (accuracy). As such, the following inequality should hold E [fyθ (x+ )] ≥ pA ≥ pB ≥ maxc 6=y E [f c(x+ )].

heading: 3.4 DATA DEPENDENT SMOOTHING FOR CERTIFICATION
text: The certification regionR = {δ : ‖δ‖2 ≤ R} at an input x is fully characterized by the classifier fθ and the standard deviation of the Gaussian distribution σ. Moreover, for a given fθ, the certification regionR varies at different x, when σ is fixed, due to the nonlinear dependence of the prediction gap Φ−1(pA(x;σ))−Φ−1(pB(x;σ)) on x. This hints that, for a given fθ, different inputs x may enjoy a different optimal σ∗x that maximizes the certification region through radiusR. To see this, consider the three inputs x1, x2 and x3 all correctly classified by the binary classifier fθ as C1 in Figure 1. Using a fixed σ to smooth the predictions of fθ, i.e. predict with gθ, reveals that inputs, depending on how close they are from the decision boundaries, can enjoy different levels of smoothing without affecting the prediction of gθ. For instance, as shown in Figure 1 for constant σ, the input far from the decision
boundary x1 could have still been classified correctly with similarly large prediction gap even if fθ were to be smoothed with a larger σ. This indicates that perhaps the certification radius at x1 could have been enlarged with a larger smoothing σ. As for x2, we can observe that while the prediction under this choice of σ by gθ is still correct, the prediction gap Φ−1(pA(x;σ)) − Φ−1(pB(x;σ)) drops, due to having more Gaussian samples fall in the C2 region. This indicates that a different choice of σ could have been used to trade-off the drop in prediction gap and certification radius.
Algorithm 1: Data Dependent Certification Function OptimizeSigma(fθ , x, α, σ0, n):
Initialize: σ0x ← σ0, K for k = 0 . . .K − 1 do
sample ̂1, . . . ̂n ∼ N (0, I) ψ(σkx) = 1 n ∑n i=1 fθ(x+ σ k x ̂i) EA(σ k x) = maxc ψ c; yA = arg maxc ψ c; EB(σ k x) = maxc6=yA ψ c R(σkx) = σkx 2 ( Φ−1(EA)− Φ−1(EB)
) σk+1x ← σkx + α∇σkxR(σ k x)
σ∗x ← σKx return σ∗x Last, for the input x3 that is very close to the decision boundary, the sub optimal choice of σ (too large for x3) could result in an incorrect prediction by gθ. Despite the observations that σ plays a significant role in `r2 certification accuracy, certification methods generally (i) choose σ arbitrarily and (ii) set it to be constant for all x. Based on this observation, for a given smooth classifier with a specific σ0, where σ0 can be zero reducing the smooth classifier to fθ, we seek to construct another smooth classifier with parameter σ∗x for every input x such that: (i) the prediction of both smooth classifiers (smoothing with σ0 and σ∗x) is identical for all x. (ii) The certification radius of the new smooth classifier at every x is maximized. To construct a classifier smoothed with σ∗x enjoying the two previous properties, let cA be the prediction under σ0 smoothing, i.e. cA = arg maxc E ∼N (0,σ0I)[f c(x+ )]. We directly maximize the radius R in Equation 1 over σ for every x by solving the following optimization:
σ∗x = arg max σ
σ
2
( Φ−1 ( E ∼N (0,σ2I)[f cAθ (x+ )] ) − Φ−1 ( max c6=cA E ∼N (0,σ2I)[f cθ (x+ )] )) .
(2) Since Φ−1 is a strictly increasing function, it is important to note that solving Equation 2 for a fixed cA can at worst yield a smooth classifier of an identical radius to when the classifier is smoothed with σ0 with both classifiers predicting cA for x.
Solver. While our proposed Objective 2 has a similar form to the MACER regularizer (Zhai et al., 2020) used during training, ours differs in that we optimize σ for every x and not the network parameters θ, which are 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 kth iteration will be approximated as follows: ∇σk σ k
2
[ Φ−1 ( γcA(σk) ) − Φ−1 ( maxc 6=cA γ c(σk) )] ,
where γc(σk) = 1n ∑n i=1 f
c(x+ i) for 1, . . . , n ∼ N (0, (σk)2I). However, this estimation of the gradient suffers from high variance due to the dependence of the expectation on the optimization variable σ that parameterizes the smoothing distribution N (0, σ2I) (Williams, 1992). To alleviate this, we use the reparameterization trick suggested by Kingma & Welling (2014); Rezende et al. (2014) to compute a lower variance gradient estimate for our Objective 2. In particular, with the change of variable = σ̂ where ̂ ∼ N (0, I), Objective 2 is now equivalent to:
σ∗x = arg max σ
σ
2
( Φ−1 ( Ê∼N (0,I)[f cAθ (x+ σ̂)] ) − Φ−1 ( max c 6=cA Ê∼N (0,I)[f cθ (x+ σ̂)] ))
(3) Note that, unlike before, the expectation over the distribution ̂ ∼ N (0, I) no longer depends on the optimization variable σ. 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 1 summarizes the updates for optimizing σ for each x by solving 3 with K steps of stochastic gradient ascent. It is worthwhile to mention that the function OptimizeSigma in Algorithm 1 is agnostic of the choice of architecture fθ and of the training procedure that constructed fθ.

heading: 3.5 MEMORY-BASED CERTIFICATION FOR DATA DEPENDENT CLASSIFIERS
text: Unlike previous approaches where σ is constant for all inputs, the data dependent classifier gθ with varying σ per input can not be directly certified by the classical Monte Carlo algorithms
proposed by Cohen et al. (2019). This is since the data dependent classifier gθ does not enjoy a constant σ within the given certification region, i.e. gθ tailors a new σx for every input x including within the certified region of x. Informally, let R(σ∗x1) be the radius of certification at x1 granted by the data dependent classifier gθ. The data dependent classifier does not guarantee that there can not exist x2 within the region of certification of x1, i.e. ‖x1 − x2‖2 ≤ R(σ∗x1), where gθ with σ ∗ x2 predicts x2 differently from x1 breaking the soundness of certification.
Algorithm 2: Training with Data Dependent σxi Function TrainBatch(fθ , {xi, yi}Bi=1, {σxi}Bi=1, α, n):
for i = 1, . . . , B do σ∗xi = OptimizeSigma(fθ, xi, α, σxi , n)
TrainFunction ( {xi, yi}Bi=1, {σ∗xi} B i=1 ) // any
training routine e.g. MACER To circumvent this problem, we propose a memory-based procedure to certifying our proposed data dependent classifier. Let {xi}Ni=1 be a set of previously predicted inputs and {Ci}Ni=1 be their corresponding predictions with mutually exclusive `2 certified regionsRi for differently predicted inputs, i.e. Ri ∩Rj = ∅ ∀i 6= j, Ci 6= Cj . Let xN+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 gθ with prediction CN+1. If there exists an i such thatRN+1 ∩Ri 6= ∅, xN+1 ∈ Ri, and CN+1 6= Ci, we adjust the prediction of the data dependent classifier gθ to be Ci and update RN+1 to be the largest subset of RN+1 that is a subset ofRi (see middle example in Figure 2). On the other hand, ifRN+1 ∩Ri 6= ∅, xN+1 /∈ Ri, and that CN+1 6= Ci, we updateRN+1 to be the largest subset ofRN+1 not intersecting withRi (see right example in Figure 2). We perform the previous operations for all elements in the memory and add xN+1, CN+1,RN+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-based certification is essential for a sound certification, empirically, we never found in any of the later experiments a case where two inputs predicted differently suffer from intersecting certified regions. That is to say while our sound certificate works on the memoryenhanced 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 to the memory-enhanced data dependent smooth classifier and data dependent smooth classifier interchangeably. We elaborate more on this and provide an algorithm in the Appendix.

heading: 3.6 TRAINING WITH DATA DEPENDENT SMOOTHING
text: Models that enjoy a large `r2 certification accuracy under the randomized smoothing framework need to enjoy a large certification radius R in Equation 1 for all x and be able to correctly classify inputs corrupted with Gaussian noise, i.e. gθ(x) = y. While there are several approaches to train fθ (or directly gθ) so as to output correct predictions for inputs corrupted with noise sampled from N (0, σ2I), all existing works fix σ 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 σ∗x computed by OptimizeSigma. Algorithm 2 summarizes this proposed training pipeline. The function TrainFunction proceeds by performing backpropagation using any training scheme, given the estimated σ∗xi for each xi. We note that whenever Algorithm 2 is used, we initialize σxi at each epoch with σ ∗ xi computed at the previous
epoch. Since COHEN, SMOOTHADV and MACER are among the most popular approaches that embed randomized smoothing certificates as part of the training routine, TrainFunction 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.

heading: 4 EXPERIMENTS
text: We conduct two sets of experiments to validate our key contributions. (i) We show that we can boost certified accuracy for several pre-trained models by using Algorithm 1 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) SMOOTHADV (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 DS2 when it is used during both training and certification.
Setup. We conduct experiments with ResNet-18 and ReNet-50 (He et al., 2016) on CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet (Russakovsky et al., 2015), respectively. For CIFAR10 experiments, we train from scratch for 200 epochs. For ImageNet, we initialize using the network parameters provided by the authors. When σ is fixed and following prior art, e.g. COHEN, SMOOTHADV, and MACER, we set σ ∈ {0.12, 0.25, 0.50} and σ ∈ {0.25, 0.50, 1.0} for CIFAR10 and ImageNet, respectively, for training and certification. We set α = 10−4 in Algorithm 1 and the initial σ0 to the σ used in training the respective model. Unless stated otherwise, we set n = 1 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 σ. We also report the Average Certified Radius (ACR) proposed by MACER 1/|Stest| ∑ (x,y)∈Stest R(fθ, x).1{arg maxc g c θ(x) = y}, where 1{.} is an indicator function. Following COHEN2 and all randomized smoothing methods, we certify all results using N0 = 100 Monte Carlo samples for prediction and N = 100, 000 estimation samples to estimate the radius with a failure probability of 0.001 given a smoothing σ.

heading: 4.1 COHEN + DS
text: We combine data dependent smoothing with COHEN. Following Gaussian augmentation, this method trains fθ on (x+ ), where ∼ N (0, σ2I), 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 σ∗x produced by Algorithm 1, which we refer to as COHEN-DS. Figure 3 plots the certified accuracy for CIFAR10 and ImageNet in the first and second rows, respectively. Even though the base classifier fθ is identical for COHEN and COHEN-DS, Figure
2We use the available code of Cohen et al. (2019) to report all certification results in the paper for a given σ.
3 shows that COHEN-DS is superior to COHEN in certified accuracy across almost all radii and for all training σ on 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 σ for COHEN (envelope figure) against our best COHEN-DS, cross-validated over all training σ and the number of iterations in Algorithm 1 K, accompanied with the corresponding ACR score. For instance, we observe that data dependent certification COHEN-DS 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 CIFAR10. 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 as COHEN-DS2) by running Algorithm 2. For CIFAR10, we train COHEN first with fixed σ for 50 epochs, i.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 2 withK = 1. Once training is complete, we certify all trained models with Algorithm 1 using the memory based certification. In Figure 3, we observe that COHEN-DS2 can further improve certified accuracy across all trained models on both CIFAR10 and ImageNet. This is also evident in the last column of Figure 3 that shows the best certified accuracy per radius (envelope) over all training σ. We note that COHEN-DS2 improves the certification accuracy of COHEN-DS by 2.6% and by 0.9% at radii 0.5 and 0.75 respectively on CIFAR10, 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-DS2 on CIFAR10 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-DS2 on CIFAR10. Regardless, COHEN-DS2 substantially outperforms COHEN by 0.173 ACR points. As compared to COHEN-DS, COHEN-DS2 improves the ACR on ImageNet from 1.257 to 1.319.

heading: 4.2 SMOOTHADV + DS
text: We combine our data dependent smoothing strategy with the more effective SMOOTHADV, which trains the smoothed classifier for every x on the adversarial example x̂ that maximizes − logE ∼N (0,σ2I) [fyθ (x′ + )], where ‖x′ − x‖ ≤ ζ .For CIFAR10 experiments, we follow the train-
ing procedure of SMOOTHADV, where the adversary x̂ is computed with 2 PGD (proximal gradient descent) steps with ζ = 0.25 and one augmented sample to estimate the expectation. For ImageNet experiments, we use the best reported models, in terms of certified accuracy, provided by the authors, which correspond to ζ = 0.5 for σ = 0.25 and ζ = 1.0 for σ ∈ {0.5, 1.0}. DS for certification only. Similar to COHEN, we first certify SMOOTHADV models trained with the same fixed σ. Then, we certify the proposed data dependent σ∗x models using the memory-based certification, which we refer to as SMOOTHADV-DS. In Figure 4, we show the certified accuracy for both CIFAR10 and ImageNet in the first and second rows, respectively. The last column shows the envelopes per radius. Even though they both share the same classifier fθ, SMOOTHADV-DS significantly improves upon SMOOTHADV over all radii and all values of σ in training for both CIFAR10 and ImageNet. In particular, for models trained with σ = 0.25, SMOOTHADV achieves a zero certified accuracy for large certification radii (≥ 1.0), while SMOOTHADV-DS achieves nontrivial certified accuracy in these cases. Similar to the earlier setup, we 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 CIFAR10 and Imagenet, respectively. The improvement is consistent over all radii. The ACR also improves by 0.118 and 0.158 on CIFAR10 and ImageNet, respectively. DS for training and certification. We fine tune the SMOOTHADV trained models (either the retrained CIFAR10 models or the ImageNet models provided by SMOOTHADV) using Algorithm 2, where σ∗x is computed using Algorithm 1. We report the per σ certification accuracy comparing SMOOTHADV-DS2 (certified also using memory based certification) to both SMOOTHADV-DS and SMOOTHADV. SMOOTHADV-DS2 further improves the certified accuracy as compared to SMOOTHADV-DS with performance gains more prominent on ImageNet. While the improvement of SMOOTHADV-DS2 over SMOOTHADV-DS is indeed small, e.g. 0.7% at radius 0.5 on CIFAR10, we observe that the performance gaps are much larger on 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 CIFAR10 and ImageNet, respectively. SMOOTHADV-DS2 boosts the certified accuracy of SMOOTHADV at radius 0.5 by 6.1% and 4.2% on CIFAR10 and ImageNet, respectively.

heading: 4.3 MACER + DS
text: We integrate data dependent smoothing within MACER which trains gθ by minimizing over the parameters θ the following objective − log gθ(x) + λσ2 max ( γ − 2Rσ , 0 ) .1{arg maxc gcθ(x) = y}. where R also depends on θ. While this seems to be similar in spirit to our approach, we in fact maximize the certification radius over σ with fixed parameters θ for every x. We conduct experiments
Table 3: Best certified accuracy per radius and ACR of MACER, MACER-DS and MACER-DS2.
CIFAR10 Radius 0.0 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 2.25 ACRTrain Certify
MACER FS FS 78.8 59.3 43.6 34.7 26.6 19.4 13.0 7.50 0.0 0.0 0.702 MACER-DS 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-DS2 DS DS 82.4 68.3 52.7 43.5 31.7 20.6 13.8 7.92 3.65 1.39 0.807
Figure 6: Qualitative examples of estimated σ∗x for different inputs. From left to right: the set of three images on the left: clean image, fixed σ = 0.5, and estimated σ∗x = 0.368 that maximizes the certification radius. Similarly for second set but with σ = 0.25 and σ∗x = 0.423. This demonstrates that σ∗x, which maximizes the certification radius, can vary significantly w.r.t. input x.
on CIFAR103 following the training procedure of MACER estimating the expectation with 64 samples, λ = 12, and γ = 8. We set n = 8 in Algorithm 1 with ablations on n = 1 in the appendix. DS for certification only. Similar to the earlier setup in COHEN and SMOOTHADV, we certify models with fixed σ and then with data dependent σ∗x 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 σ. 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.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-DS2. Figure 5 shows the improvement of MACER-DS2 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 MACER-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-DS2 with both being far better than the MACER baseline.
4.4 DISCUSSION AND ABLATION
Varying K. We pose the question: does attaining better solutions to our proposed Objective 3 improve certified accuracy? To answer this, we control the solution quality of σ∗x by certifying trained models with a varying number of stochastic gradient ascent iterations K in Algorithm 1. In particular, we certify the trained models SMOOTHADV-DS2 and SMOOTHADV-DS on CIFAR10 and ImageNet, respectively, with a 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 σ∗x per input x with larger K, which in turn improves the certification radius leaving room for improvements with more powerful optimizers4. Visualizing σ∗x. We show the variation of σ∗x that maximizes the certification radius over different inputs x. Figure 6 shows two examples, where the first and fourth columns contain the clean images. In the second column, a choice of fixed σ = 0.5 is too large compared to our estimated σ∗x = 0.368 that maximizes the certification radius as per Algorithm 1. As for the fifth column, we observe that a constant σ = 0.25 is far less than σ∗x = 0.423. This indicates that indeed the σ∗x maximizing the certification radius varies significantly over inputs.
3ResNet-50 trained models on ImageNet are not provided by the authors. 4Greedy heuristics solving Equation 3 are in the appendix, as they perform far worse than our approach.

heading: 5 REPRODUCIBILITY STATEMENT
text: This work has two main components to reproducing our experimental results; Algorithm 1 and the memory-based certification. In the setup paragraph in our experimental section, we mentioned all necessary implementation details for Algorithm 1. Nonetheless, we provide an implementation using PyTorch (Paszke et al., 2019) of Algorithm 1 in Appendix A. As for memory based certification, we provide a detailed algorithm supported with PyTorch implementation of our memory-based certification in Appendix C. Algorithm 2 is based on publically available code training with links in the appendix. Moreover, since we used trained models with different frameworks, we provide the 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.

heading: 6 ETHICS STATEMENT
text: Since our work has an experimental nature where all of our experiments are computational, we 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.

heading: C MEMORY-BASED CERTIFICATION FOR DATA DEPENDENT CLASSIFIERS
text: Algorithm 3: Memory-Based Certification Input: input point xN+1, certified regionRN+1, prediction CN+1, and memoryM Result: Prediction for xN+1 and certified region at xN+1 that does not intersect with any certified region inM. for (xi, Ci,Ri) ∈M do
if CN+1 6= Ci then if xN+1 ∈ Ri then R̃N+1 = LargestInSubset(Ri,RN+1), RN+1 ← R̃N+1; CN+1 ← Ci
else if Intersect(RN+1,Ri) then R′N+1 = LargestOutSubset(Ri,RN+1); RN+1 ← R′N+1;
end add (xN+1, CN+1,RN+1) toM; return CN+1,RN+1;
LetM = {(xi, Ci,Ri)}Ni=1 be set of the triplets: the input xi, the prediction of xi denoted by Ci and the certification region at xi denoted asRi which is characterized by the certification radius Ri and the center xi. Moreover, we assume that Ri ∩ Rj = ∅,∀i 6= j, Ci 6= Cj . That is to say, none of the certification regions of the inputs stored in the memoryM intersect for inputs with different predictions. This is the key property for a sound certification procedure. Otherwise, if such a property does not hold, then this implies that the data dependent classifier produces different predictions within the same certified region. In what follows, and to circumvent this nuisance in the data dependent classifier gθ, 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. LetRN+1 be the certified region at xN+1 of gθ. (i) If xN+1 ∈ Ri and arg maxc gcθ(xN+1) 6= Ci, we find the largest R̃N+1 such that the following two properties hold R̃N+1 ⊂ RN+1 and R̃N+1 ⊂ Ri. For when the certified regions Ri are simple `2-balls, finding the largest R̃N+1 satisfying previous two properties is straightforward. We denote this with the function LargestInSubset (second example in Figure 2). We then updateRN+1 with the refined R̃N+1 and change CN+1 to Ci. (ii) Otherwise, ifRN+1 ∩Ri 6= ∅ where xN+1 /∈ Ri and arg maxc gcθ(xN+1) 6= Ci, we findR′N+1 such that R′N+1 ⊆ RN+1 is the largest subset of RN+1 non-intersecting with Ri. We denote this function LargestOutSubset (third example in Figure 2). We then updateRN+1 with the refined R′N+1. Moreover, computing LargestOutSubset for when Ri are `2-balls is straightforward. At last, note that Intersect is a function that returns whether two `2-balls intersect. At last, we then add (xN+1, CN+1,RN+1) to memory. We provide below a pytorch implementation of the memory-based certification of the pseudo-algorithm 3.
While the memory-based certification is essential for a sound certification, empirically on CIFAR10 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. (ii) 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 gθ predicts these inputs similarly (the left example of Figure 2). This is since the data dependent classifier is 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 σ, and correspondingly optimized σ∗x used in smoothing are moderately low (σ ∗ x ≤ 1.0). This results in limited smaller certified regions, `2 balls of radii ≈ 4σ∗x 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, independently without being combined with the data dependent smooth classifier under any arbitrary choice of a certification radius for every input; this results in a sub-optimal certification. This is since this may result in one of the following situations: (i) Assigning large radii for every input will yield a 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) or 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 a 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 a better robustness/accuracy tradeoff.
For completeness, we provide the full implementation of the memory-based algorithm using PyTorch.
1 import torch 2 class Memory_Based_Certification(object): 3 def __init__(self): 4 self.saved_radii = []
5 self.saved_images = [] 6 self.saved_predictions = [] 7
8
9 def _internal_adjustment(self, img, rad, pre): 10 diff = torch.norm(img.reshape(1, -1) - torch.stack(self.
saved_images).reshape(len(self.saved_radii), -1), dim=1) 11
12 where_overlap = diff < (torch.tensor(self.saved_radii) + rad) 13 #Check whether this image is with overlap with any other
instances 14 if where_overlap.any(): 15 preds_overlap = self.saved_predictions[where_overlap] 16 where_overlap_diff_class = preds_overlap != pre 17
18 #Check whether this image is with overlap with instances with different prediction
19 if where_overlap_diff_class.any(): 20 #Get the radii, differences where the overlap 21 saved_radii_with_overlap = self.saved_radii[where_overlap
] 22 dif_with_overlap = diff[where_overlap] 23
24 preds_overlap_with_diff_class = preds_overlap[ where_overlap_diff_class]
25 rad_with_overlap_diff_class = saved_radii_with_overlap[ where_overlap_diff_class]
26 dif_with_overlap_diff_class = dif_with_overlap[ where_overlap_diff_class]
27
28 rad, rad_idx = torch.min(dif_with_overlap_diff_class - rad_with_overlap_diff_class)
29
30 if rad.item() < 0: 31 pre = preds_overlap_with_diff_class[rad_idx] 32
33 rad = torch.abs(rad).item() 34 return rad, pre 35
36 def adjust_radius(self, img, rad, pre): 37 #The img already exists in the saved dictionary 38 if img in self.saved_images: 39 idx = self.saved_images == img 40 return self.saved_radii[idx], self.saved_predictions[idx] 41
42 if self.saved_radii != []: #Saved dictionaries are not empty 43 rad, pre = self._internal_adjustment(img, rad, pre) 44
45 self.saved_radii.append(rad) 46 self.saved_images.append(img) 47 self.saved_predictions.append(pre) 48 return rad, pre

heading: D ADDITIONAL VISUALIZATIONS
text: Here, we show similar results to the one in Figure 6. Similar to the earlier observations, while model parameters are fixed, optimal smoothing parameters vary per sample.

heading: E LIMITATIONS, BROADER IMPACT AND COMPUTE POWERS USED.
text: 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 at
the cost of both memory and computational complexity. While the memory cost is of order O(N) the computational complexity is more involved. Let p be the probability that a new point xN+1 be in one of the certification regions Ri, n is the complexity of computing a certification region at xN+1, i.e. RN+1, using the classical Monte Carlo Algorithms of Cohen et al. (2019), then the expected computational complexity of prediction or certification will be O(Np+ (1− p)(2N + n)). The factor 2N + n is due to performing N comparisons to check that xN+1 is not in anyRi, then computingRN+1 of complexity n, and at last a complexity of N for computingR′N+1. Informally, for larger N and in small dimensional input, p ≈ 1 leading to a complexity of order N . When N
is smaller compared to the input dimension, we have p ≈ 0 with an expected complexity of order 2N + n. Moreover, the memory-based 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 of differently predicted inputs (middle and right scenarios of Figure 2 do not occur). We found that is the case in all of our experiments making our memory-enhanced data dependent smooth classifier order invariant. We elaborated on why we believe that is 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 to future work.
Broader Impact. While the performance of Deep Neural networks is dominating over several fields, the existence of adversarial examples hinders their deployment in lots of applications. This raise the attention to build networks that are not only accurate, but also robust to such perturbations. This work takes a step towards a remedy for this nuisance by improving the certified robustness of deep neural networks.
Compute Powers. In our experiment on CIFAR10, we used either NVIDIA Quadro RTX-600 GPU or NVIDIA 1080TI GPU. For ImageNet experiments, we used NVIDIA-V100 GPU. Note that one GPU was enough to run any of our experiments.

heading: F DETAILED ABLATIONS
text: F.1 COHEN VS COHEN-DS VS COHEN-DS2
In this section, we detail the certified accuracy per radius for all trained models per σ for Cohen and per σ and number of iterations K for Cohen et al. (2019), Cohen-DS and Cohen-DS2 in Algorithm 1 on both CIFAR10 and ImageNet.
F.2 SMOOTHADV VS SMOOTHADV-DS VS SMOOTHADV-DS2
In a similar spirit to the previous section, we report the certified accuracy for the SmoothAdv variants, namely, SmoothAdv Salman et al. (2019a), SmoothAdv-DS and SmoothAdv-DS2 on CIFAR10 and ImageNet.
F.3 MACER VS MACER-DS VS MACER-DS2 (N=1) VS MACER-DS2 (N=8)
We report `r2 certified accuracy per radius r for MACER (Zhai et al., 2020) variants on CIFAR10. Note that as highlighted in the main manuscript, for certification only, i.e. MACER−DS, we set n = 8 for all experiments in Algorithm 1. Moreover, in the main paper and for ease of computation we set n = 1 for when training is employed, i.e. −DS2. In here we also explore the variant where when data dependent smoothing is introduced during training we set n = 8 for ablations. We refer to when n = 1 and n = 8 for when data dependent smoothing is used in training and certification as MACER−DS(n = 1) and MACER−DS(n = 8), respectively.

heading: G DATA-DEPENDENT SMOOTHING FOR `1 CERTIFICATES.
text: While indeed we focused both our methodology and experiments on `2 certificates, our methodology is extendable to any other `p certificate. For that regard and as per reviewer’s request, we conducted experiments on `1 certification. We leveraged the results of Yang et al. (2020) that derived the tightest `1 certificate using randomized smoothing with uniform distribution U [−λ, λ]d. The certified radius in that case has the formR1 = λ(pA − pB). We replace our objective in Equation equation 3 with:
λ∗x = arg max λ λ
( E ∼U [−λ,λ]d(f cAθ (x+ ))−max
c6=cA E ∼U [−λ,λ]d(f cθ (x+ ))
) .
We solved our objective in an identical fashion to our Algorithm 1 with the same hyperparameters for λ ∈ {0.25, 0.5, 1.0} in certification on both CIFAR10 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 `2 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 `2 certificate, our proposed memory-enhanced data-dependent smoothing yields consistent improvement in the `1 certified accuracy. We report an improvement of 7% and 3% over the state of the art certified accuracy at `1 radius of 0.5 on CIFAR10 and ImageNet, respectively. At last, we note similar improvement to the `1 ACR as reported in Table 11.

heading: H RUNTIME
text: We measure the certification runtime on an NVIDIA Quadro RTX-6000 GPU for our proposed data dependent smoothed classifier (time includes Algorithm 1 in addition to the memory based certification) compared to the certification of a fixed σ classifier. Certifying one CIFAR10 test input with ResNet18 takes 1.6 and an average of 1.8 seconds for a fixed σ classifier and for the data dependent classifier (K = 900), 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 1 and memory based certification is negligible compared to the gains in certified accuracy.

Review summaries:
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).

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.

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. 

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.