Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences
Authors: Saiyue Lyu
Shadab Shaikh
Frederick Shpilevskiy
Evan Shelhamer
Mathias Lécuyer
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Robustness
Adversarial examples
Adaptive defenses
Certified test-time defenses
Randomized Smoothing
Primary area: privacy
TL;DR: Adaptive Randomized Smoothing soundly and flexibly certifies the predictions of test-time adaptive models against adversarial examples while improving certified and standard accuracies.

Abstract: We propose Adaptive Randomized Smoothing (ARS) to certify the predictions of our test-time adaptive models against adversarial examples.
ARS extends the analysis of randomized smoothing using $f$-Differential Privacy to certify the adaptive composition of multiple steps.
For the first time, our theory covers the sound adaptive composition of general and high-dimensional functions of noisy inputs.
We instantiate ARS on deep image classification to certify predictions against adversarial examples of bounded $L_{\infty}$ norm.
In the $L_{\infty}$ threat model, ARS enables flexible adaptation through high-dimensional input-dependent masking.
We design adaptivity benchmarks, based on CIFAR-10 and CelebA, and show that ARS improves standard test accuracy by  1 to 15\% points.
On ImageNet, ARS improves certified test accuracy by up to 1.6% points over standard RS without adaptivity. Our code is available at [https://github.com/ubc-systopia/adaptive-randomized-smoothing](https://github.com/ubc-systopia/adaptive-randomized-smoothing).

Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences
Saiyue Lyu't, Shadab Shaikh'', Frederick Shpilevskiy's Evan Shelhamer', Mathias Lécuyer'
*University of British Columbia, Google DeepMind
(saiyuel, shadabs3, Eshpil)@ca.ubc.. shellhamerddeeppind. com, mathias mathias. .lecuyerruuc.cc ca "equal contribution
Abstract
We propose Adaptive Randomized Smoothing (ARS) to certify the predictions of our test-time adaptive models against adversarial examples. ARS extends the analysis of randomized smoothing using f-Differential Privacy to certify the adaptive composition of multiple steps. For the first time, our theory cov- ers the sound adaptive composition of general and high-dimensional functions of noisy inputs. We instantiate ARS on deep image classification to certify predictions against adversarial examples of bounded Loo norm. In the Loo threat model, ARS enables flexible adaptation through high-dimensional input- dependent masking. We design adaptivity benchmarks, based on CIFAR-10 and CelebA, and show that ARS improves standard test accuracy by to 15% points. On ImageNet, ARS improves certified test accuracy by up to 1.6% points over standard RS without adaptivity. Our code available at https: //github. com/ hon/ubc-aae systopia/ wewpptive-randdmieee seadlommzed-mmoothinng.
Introduction
Despite impressive accuracy, deep learning models still show worrying susceptibility adversarial attacks. Such attacks have been shown for a large number of tasks and models (Costa et al., 2023; Chakraborty et al., 2018), including areas where security and safety critical such fraud detection (Pumsirirat and Liu, 2018) or autonomous driving (Cao et al., 2021).
Several rigorous defences have been proposed to certify robustness. Randomized Smoothing (RS) (Lécuyer et al., 2019; Cohen et al., 2019) does so by averaging predictions over noisy versions of the input at test time, and as such can scale to large deep learning models. However, RS has its limitations: it is inflexible and either degrades accuracy or only certifies against small attacks.
To address these shortcomings and improve robustness, there has been recent push to develop defences that adapt to inputs at time Croce al. (2022), including for RS (Alfarra et al., 2022a; Súkeník et al., 2021; Hong et al., 2022). Most such adaptive defences are heuristic, unproven, and subject improved attacks (Croce et al., 2022; Alfarra et al., 2022a; Hong et al., 2022), running the risk of reverting to hopeless cat and mouse game with attackers (Athalye et al., 2018; Tramer et al., 2020), or only provide limited adaptivity (Súkeník et al., 2021; Hong et al., 2022) and gain ($5).
We (re)connect RS to Differential Privacy (DP), after its abandonment for a tighter analysis via hypothesis testing (Cohen et al., 2019), and introduce Adaptive Randomized Smoothing (ARS) to provide test-time adaptivity while preserving rigorous bounds. Specifically, we analyze RS through the lens of f-Differential Privacy (f-DP), and use this connection leverage a key strength of DP: the end-to-end analysis of multi-step adaptive computation using composition results ($2).
We ARS to design two-step defence against Loc adversaries image classification (Figure 1), which is a challenging setting for RS Blum et al. (2020). The first step computes an input mask that
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Poat Pesowmning M.
Add coims
4 of
Mask Model
element-wise
Maak
product
mott-troccosing My.Ms
Prediction
Rh coma
(0 An
argnax, y1
Avarage
Add coiss
Base Classifier
Figure 1: Two-step ARS for Toe -bounded attacks. Step M1 adds noise input X and post-processes the result into mask w(m1). ). Step M2 takes masked input w(m;) @ X and adds noise to get m2. Base classifier g post-processes weighted average of m1, ma output label. RS reduces T2 and w(.) (no M1).
focuses on task-relevant information. This reduces the dimension of the input, which then passed the second step for prediction. Thanks to this adaptive dimension reduction, the second step makes its prediction on a less noisy image, improving the performance and certification radius ($3).
We evaluate our adaptive randomized smoothing method in three settings ($4). For image classifi- cation, we first design a challenging benchmark based on CIFAR-10, 10, and we show that ARS can improve accuracy by up to 15%. For apatially-localize face attribute classification dataset, we show that ARS improves accuracy by up to 7.7%. For large-scale image classification on ImageNet, ARS maintains accuracy and improves certified accuracy by up 1.6%.
the CelebA
2 Theory for Adaptivity via Differential Privacy
After introducing the necessary background and known results on RS and DP ($2.1), we reconnect RS to its DP roots by showing that the tight analysis of Cohen et al. (2019) can be seen as PixeIDP (Lécuyer et al., 2019) using /-Dfffrrental Privacy (Dong et al., 2019; 2022), a hypothesis testing formulation of DP ($2.2). This connection lets us leverage composition results for f-DP to analyze multi-step approaches for provable robustness to adversarial examples, which we name Adaptive Randomized Smoothing (ARS) ($2.3). We leverage ARS to design and analyze a two-step defence against -ounded adversaries ($2.4), which we then instantiate as a deep network ($3).
2.1 Related Work: Adversarial Robustness, Randomized Smoothing, and Differential Privacy
Adversarial Examples (Szegedy et al., 2014): Consider classifier g X + Jr and input X. An adversarial example of radius the Lp threat model, for model y on input X, an input + such that g + e) F g(X), where E (r). where (r) - {a E Rd ||>l|p I r} is the I, ball of radius r. These imputs or attacks are made against classifiers at test time. For more on the active topics of attack and defence, we refer to surveys (Li et al., 2023; Costa et al., 2023; Chakraborty al., 2018) on current attacks and provable defences. In general, provable defences do focus on the largest-scale highest-accuragy classifiers, with the notable exception of randomized smoothing.
Randomized Smoothing (RS) (Lécuyer et al., 2019; Cohen et al., 2019) is scalable approach to certifying model predictions against 12-norm adversaries. Specifically, it certifies robustness any attack B2(rx). The algorithm randomizes base model g by adding spherical Gaussian noise to its input, and produces a smoothed classifier that returns the class with highest expectation over the noise: y+ - arg max P= (9(X + 2) y). The tightest analysis from Cohen et al. (2019) uses hypothesis testing theory to show that, with p+ E [o, 1] such that
P(g(X- + =) W+) 2 p+ 2 p_ 2 maxy tv. P(g(X + 2) = y-), the certificate size for prediction y+ is:
rx
$ (p+)
(())):
(1)
where Φb is the inverse standard Gaussian CDF, p. Nower-bounde the probability of g(X +2) 4+ (the most probable class), and p_ boper-bounds the probability of other classes.

---

While sound, RS is static during testing even though attacks may adapt. Recent work aims to make RS adapt test time (Súkeník et al., 2021; Alfarra al., 2022a; Hong et al., 2022). While pioneering, these works are restricted in either their soundness or their degree of adaptation and resulting improvement. Súkeník et al. (2021) soundly adapt the variance for RS by the distance between test and train inputs. However, this only provides minimal adaptivity, with only minor improvement to certification. Alfarra et al. (2022a) adapt the variance for RS to each test input, but the analysis is not end-to-end, and hence not sound (Súkeník et al., 2021) (except for their memory-basee edition, but this requires storage of all examples), UniCR (Hong et al., 2022) adapts the noise distribution for RS, primarily to the data distribution during training, and optionally to input during testing. The train- time adaptation is sound, but the test-time adaptation is not due to the same issue raised by Súkeník et al. (2021). We propose ARS to advance certified test-time adaptivity: our approach is sound and high-dimensional to flexibly adapt the computation of later steps conditioned on earlier steps by differential privacy theory.
Differential Privacy (DP) is a rigorous notion of privacy. A randomized mechanism .M (c, 5)-DP if, for any neighbouring inputs X and X', and any subset of possible outputs y c (a)g eMM(((X)) E >) + 6. Following Lécuyer et al. (2019), we define neighbouring P(M(X) E >)) S
based on Lp norms: and X' in Rd are Ly neighbours at radius if X X' E Bp(r).
RS was initially analyzed using (e, o)Diffferenti Privacy (Lécuyer et al., 2019). Intuitively, the randomized classifier M(X) 2 g(X + +), ~ (O, o²(1)) acts as a privacy preserving mechanism (the Gaussian mechanism) that provably "hides" small variations in X. This privacy guarantee yields a robustness certificate for the expected predictions.
f-DP (Dong et al., 2019) is a notion of privacy that extends d)DP), and defines privacy a bound on the power of hypothesis tests. Appendix A provides more details on f-DP. The main result we leverage is Theorem 2.7 of Dong et al. (2022) that for Gaussian mechanism M(X) ((X) +
z ~ (O, f ). such that for any neighbouring X", ((X) - 0(X') E (2(r) (i.e., the L2 sensitivity of 0 is r), we have that M is G2-DP with the function Gμ defined as:
Ga(a)= = 1b ( (1- - -n). for a E [0.
(2)
We leverage two key properties of f-DP. First, f-DP is resilient to post-processing, That is, if mechanism M is f-DP. proc o M is also f-DP. Second, f-DP is closed under adaptive composition. We refer to $3 in Dong et al. (2022) for the precise definition and use their Corollary 3.3: the adaptive composition of two Gaussian mechanisms Gμ -DP and Ga -DP is itself G,. with
/
p + 22
f-DP is distinct from the f-divergence from information theory. Dvijotham et al. (2020) use f- divergence bounds between the noise distribution centred on the original input and centred on any perturbed input. This improves RS by broadening the noise distributions and norm-bounds on the adversary that RS can support. In contrast we focus on f-DP, which captures enough information to reconstruct any divergence by post-processing (Proposition B.1. in Dong et al. (2019)). Our main objective is different: we leverage f-DP composition properties to enable multi-step deep learning architectures that adapt the input at test time with robustness guarantees.
2.2 Randomized Smoothing from f-DP
We reconnect RS with DP, using f-DP to yield results as strong as that of Equation (1). We start with general robustness result on fDD classifiers, which we later build on for our main result.
Proposition 2.1 (f-DP Robustness). Let M X + y be f-DP for By(r) neighbourhoods, and let Ms X + arg max P(M(X)= = y) be the associated smoothed classifier. Let y+ & Mx be the prediction on input X, and let p+, p- E [0, 1] be such that P(M(X) = 14) 2 p+ 2 p- N
maxy ((M(X)- = )-) Then:
f(1 (1-p+) p+) 21 f(p-) Ve Bp(r), M3(X + +e) =
Proof. See Appendix BI.
3

---

Let us now instantiate Proposition 2.1 for Gaussian RS (see $2.1):
Corollary 2.2 (RS from f-DP). Let M X - g(X + 2), 2 NN0,0000 I and Ms : X + arg yax (X)
y) be the associated smooth model. Let y+ - Ms(X) be the pre- diction on input X, and let P+iP- E =0,1]] be such that ((M(X) = x+) 2 P+ 2 p- 2
maxy-#v- ((M(X) = y-). Then Ve E B2(re), Ms(X V+, with:
0 rx = 2 1 (p+) Φ (p-))-
Proof. See Appendix B2, Sketch: M is a Gaussian mechanism, and is G -D- for any r (B2(r)
neighhourhood). We apply Proposition 2.1 and maximize such that G (1-2) (1-p+) ) 2 1 1-G G (p-). n
2.3 Adaptive Randomized Smoothing
While Proposition 2.1 is new, far we have only used it to reprove the known result of Corollary 2.2. So why is this connection between f-DP and robustness useful? Our key insight is that we can leverage adaptive composition results the core of DP algorithms certify multi-step methods that adapt to their inputs at test time. Such adaptive defences have seen recent empirical interest, but either lack formal guarantees, or provide only limited adaptivity in practice ($5). For the first time we derive a sound and high-dimensional adaptive method for certification.
We formalize adaptive multi-step step certification as follows. Consider k randomized Gaussian mecha- (our adaptive steps), such that m, ~ (x and for all r 2 0 we have
nisms Mi..... that M; is Gr//, -DP for the (2(r) neighbouring definition. Note that the computation M, can depend on previous results, as long as it is Gr/a. -DP. Further consider (potentially randomized) post-processing classifier g(m,,..., ,.,) - y E
Theorem 2.3 (Main result: Adaptive RS). Using definitions above, let M g(ml,.... ma) E
),, (m...... m)) ~ (M1(X),.. (M,())..,,MM.C. (M)()m)))), and the associated smoothed model be Ms X mrxma F(M(X)
y). Let y+ - MM(X) be the prediction input X, and let
P+.P- E [0, 1] be such that P(M(X)= = v+) 2 p+ 2 p- 2 max ((M(X)== = =y-). Then
de E B2(rx), Mx(X +e) V+, with:
④ (p+) Φ (-((p~))
rx
2 Di= o
Proof. By adaptive composition of Gaussian DP mechanisms (Equation (3)), M is G,-DP with We can then apply Corollary 2.2 with a= 1/ E of
== V 1 =r
E k
We focus on Gaussian RS, but a similar argument applies to general f-DP mechanisms for which we compute fç at any r, and the composition f. @ ... @ fx. potentially using numerical techniques such as that of Gopi et al. (2021). For Gaussian noise, Theorem 2.3 leverages strong results from DP to provide perhaps surprising result: there is cost to adaptivity, in the sense that k independent measurements of input X with Gaussian noise (without adaptivity) of respective variance of can be averaged to one measurement of variance o² = 1/ o, To show this, we can use weighted average minimize variance (see e.g.. Equation in Honaker (2015)), with ej = / o,² yielding x² = Σラ G = Σラ oj -- 2 2) 1/D/ o,
The ARS rx from Theorem 2.3 is identical that of one step RS from Corollary 2.2 using this variance: adaptivity over multi-step computation comes with no decrease in certified radius.
o.
2.4 ARS against L BBuuned Adversaries
How can we leverage the multi-step adaptivity from Theorem 2.3 to increase certified accuracy? We focus on two-step certified defence against -oundded attacks to increase accuracy by adaptivity. Previous work already notes that RS applies to -oundde attackers (Lécuyer et al., 2019; Cohen

---

et al., 2019), using the fact that vX E R", ||x11222 S Vdlj and hence that X X-X' E (x) 7
X - X-X'E B2(vd.r ).). Using Corollary 2.2, this yiclds:
X 2vd ( 1
(p+) x (T-)
While Loo -specifc RS theory exists (Yang al., 2020), further work by Blum et al. (2020) has found that Gaussian RS performs advantageously in practice. However, Blum et al. (2020); Kumar et al. (2020); Wu et al. (2021) show that the vd dependency cannot be avoided for a large family of distributions, leading the authors speculate that RS might be inherently limited for I certification of predictions on high dimensional images. To side-step this issue, we use two-steps adaptivity to first select subsets of the image important to the classification task (thereby reducing dimension). and then make the prediction based on the selected subset. Formally:
Proposition 2.4 (Adaptive RS for Loo). Define the following pair of (adaptive) mechanisms:
M1 Mr:X X X + _ m1,
~ ~1000 o7T))
(5)
Then, with any function w Idd + [0, 11 (interpreted as a mask):
22 ~ NOO [ )ll 03rd)
M2
w(m)) @ X + 22 - m2,
(6)
d
where 3 is the element-wise product; and the final prediction function g g: M1, m2 + y.
Consider the mechanism M that samples my ~ _M1, then my ~ .M2, and finally outputs g(m1 m2):
and the associated smoothed classifier M5 X -> arg maxyey (P(M(X)= = y)- Let y+ _/2 (X(X)
be the prediction on input X, and let p P- E [0, be such that ((M(()= v4) 2 p+ ž p- 2
max P(M(X)- = y-). Then We Boc (rx) Ms(X + +)) y+ with:
(Φ~((p)) - 8- ---()-)
2
d(
Proof. Consider any X' s.t. X X-X'E Boo (r We analyze M1 and M2 in turn. ||
vājx X' so X X' B2 B2( /dr ) and Mi G,,, -DP with 11 = r vd
a
[[w(m)) @ X - w(m) @ 12 = (w(()) @ (x- - -X')l2 S [|w( - X lo0 80 X'E
(1(12( and Ma is G with M22 (e(v1)ll202//
Applying Theorem 2.3 with
concludes the proof.
Important remarks. 1. w(.) is a masking function, adaptively reducing (if w. (m1) < 1) the value of X, and thereby the attack surface of an Loo attacker. This reduces the effective dimension of the input to M2- 2. Reducing the dimension enables a reduction in the noise variance in M2, at fixed privacy guarantee Gug- The variance reduction is enabled for all dimensions in the imput, even those that are not masked (w:(m1) R 1). As a result, the variance of the noise in M2 scales as [[w(m,)]l 2l d. The more masking, the lower the variance. It may help consider the change of variables a < a/Vd in Equation (4), and 012 + T1.2/ /d in Proposition 2.4, remove d from rX and scale the noise variance with d. For RS (Equation (4)), the noise variance scales as d. For ARS, only Equation (5) (the first step) suffers from variance scaled by d, while the second step's s variance (Equation (6)) scales as [/ 1 which can be much smaller than d when large part of the image is masked. Reduced variance translates into higher accuracy, as well as p+ and p- being further apart, for a larger r' The variance reduction due to masking applies in the translation from the B (r bound on the attack to the (r)r) sensitivity used in ARS. This variance reduction would not apply to an Lz-bounded adversary (an attack that only changes pixels with mask values of one yields no sensitivity improvement.. Hence, our two-steps ARS architecture for -boundedd adversaries does not reduce to bounding T. with T.2 as the traditional RS application does, and our gains come explicitly from variance reduction enabled by adaptive masking against an Los attack.
5

---

3 Two-Step ARS for Lo Certification of Image Classification
Figure shows our deep learning architecture based on Proposition 2.4. The first step, M1, adds noise to input X and post-processes the result into a mask w(m1). The second step, M2, takes masked input w(mi) @ X and adds noise. Finally, the base classifier g post-processes a weighted average of m m2 to output a label. The whole model is trained end-to-end on the classification task. In RS, only the path going through M2 is present. This equivalent to setting 02 = a and w(.) = 1, with no M1. In both cases, the final predictions are averaged over the noise to create the smoothed classifier. The ARS architecture introduces several new components, which we next describe.
Budget Splitting: the noise budget (Figure I; red) is split to assign noise levels to the two steps Mi and M2. We parameterize ARS with the same as standard RS then split it by the f-DP composition
formula from Equation (3). In practice, we assign 2 to Mi, and then 02 1/ V o? We
set by either fixing it to a constant or learning it end-to-end.
Masking: the mask model w(-) takes the noisy image from M1 and predicts weighting (one value in [o, 1] per input pixel) that is multiplied with the input element-wise (denoted @ in Proposition 2.4). The model is U-Net architecture, which makes pixel-wise predictions, and acts a post-processing of M₁ in the f-DP analysis. Our masking enables test-time adaptivity to reduce the noise variance for M2, via the mask's dependence on the input through m.
Mechanism output averaging: to fully leverage both steps' information, we take a weighted average of the outputs and ynz before passing the result to the base classifier y. For particular input pixel i, denote X, the value of pixel, wiy E [o. 1] its mask weight (we omit the explicit dependency on mi in w for compactness), and m1.6, m2, the respective values output by Mi and MM.. Then, the final value of pixel in the averaged input will be X, é c1, + m2,
We set C1 C2 such that X, is the unbiased estimate of X; with smallest variance. First, we set C12 + 00;02, = 1, such that B[X,] = cI,;X; + c2 = X;. Second, we minimize the variance. Notice that [[X,] = oî + c2,1luu ||0 (1 w;o2, oo + [/:l/ this is convex function in 02 minimized when its gradient in c is zero Plugging back into the constraint to get C1,5, we | 333
ofte
obtain the following weights: 61 of w 30z
and C, = of
The averaged noisy input X is finally fed to the base classifier for prediction. The smoothed classifier Ms averages predictions (over noise draws) over the entire pipeline. The parameters of w and g (and on if not fixed) are learned during training and are fixed at inferenceecerrtffcatioo time.
Experiments
We evaluate on standard and - -cettifie test accuracy. Certified accuracy at radius 700 is the percentage of test samples that are correctly classified and have an L.o certificate radius rx 2 r Standard accuracy is obtained for 7 = O.
Datasets We evaluate on CIFAR-10 (Krizhevsky, 2009) in $4.1, CelebA (Liu et al., 2015) (specifically the unaligned HD-CelebA-Cropper edition) in $4.2 and ImageNet (Deng et al., 2009) in $4.3. We measure adaptivity on CIFAR-I0 and CelebA by designing challenging benchmarks requiring adaptivity, and measure scalability on ImageNet.
Models We choose the standard ResNet (He et al., 2016) models as base classifiers with ResNet- 110 for CIFAR-10 and ResNet-50 for CelebA and ImageNet. For ARS, our mask model is simplified U-Net (Ronneberger et al., 2015) (see Appendix C. for details). For the noise budget, we find that a
fixed budget split performs reliably, and so in all experiments we split by 01 = 02 = V2a.
We compare to standard and strong static methods, design a baseline specifically for our masking approach, and evaluate the only sound input- dependettnd methods prior to ARS. Cohen er al. is the standard approach to RS (Cohen et al., 2019). UniCR (Hong et al., 2022) learns the noise distribution for RS during training but static during testing (while they propose an input-adaptive variant, it is not sound so we restrict our comparison to the training variant). We tune parametrrs,,,,s, and perform a grid search for 33 (the parameter of the noise distribution) to maximize certified accuracy. We find that 3 = 2 (Gaussian), or 3 2.25 (close to Gaussian.
Methods

---

Selting/Approach
Cohen al.
Static Mask
UniCR
Sūkeník et al.
ARS -
0.25, k 32
70.6 (1.1)
73.9 (0.8)
69.8 (1.4)
68.6 (2.8)
(0.9)
a 0.5, k 32
63.6 (2.0)
64.8(0.9)
62.8 (1.4)
59.1 (1.6)
64 (1.4)
0 1.0,
k = 32
48 (0.7)
47.3 (1.3)
46.1 (0.9)
44.6 (1.0)
49.3 (0.6)
J 0.25,
k = 48
(1.0)
(2.0)
69.7 (0.8)
65 (0.7)
75.5
J = 0.5,
k = 48
64.3 (0.2)
64.1 (1.6)
60.3 (0.6)
53.5 (1.8)
66 (1.6)
1.0, k= 48
(2.1)
(1.2)
44.3 (0.2)
34.1 (1.0)
47.6 (2.0)
0.25, k = 64
(0.9
73.1 (3.1)
67.8
(0.1(
77 (1.8)
0.5, k 64
(1.6)
62.5 (1.7)
58.7 (0.2)
(1.1)
69.9 (1.2)
1.0, k 64
(1.8)
(0.5)
42.2 (0.6)
26.5
50.4 (2.5)
0.25, k 96
61.6
(1.3)
68.8 (1.8)
45.5
78.3 (2.2)
0.5, k 96
(2.4)
59.5 (1.4)
59.7 (1.3)
10.8 (2.3)
69.8 (1.2)
0 1.0, k 96
33.8 (3.8)
(0.5)
41.3 (2.4)
10.4 (0.3)
56.3 (2.3)
Table 1: Standard Accuracy (r 0) on CIFAR-10 (20kBG). Our 20kBG benchmark places CIFAR-10 images on larger background images. We report the mean accuracy and standard deviation over three seeds. ARS achieves higher accuracy across noise a and input dimension ( indicates adaptivity). We provide results with more a levels in Appendix D.
with smaller tails), to perform best in high and low (k, σ) values, respectively (see Appendix D) for details. Static Mask is our baseline that learns a fixed mask during training that does not adapt during testing. The mask is directly parameterized as pixel-wise weights that we multiply with the input and optimize jointly with the base classifier. Relative to ARS in Figure I, this removes MI, sets 02 o, and makes w(.) = W static parameters rather than adaptive prediction. Sūkeník al. (2021) conditions the variance a for RS on the input and is therefore test-time adaptive. We use code provided by the authors as is. Comparing ARS to the static baselines measures the value of test-time adaptivity, and comparing ARS to the variance adaptivity of Súkeník et al. measures the importance of more high-dimensional and expressive adaptation.
4.1 CIFAR-10 Benchmark: Classification with Distractor Backgrounds
Input dimension is key challenge in To certification using RS (see $2.4). We design our 20kBG benchmark to vary this parameter without affecting the task: we superimpose CIFAR-10 images onto a larger distractor background from the 20k background images dataset Li al. (2022a). The backgrounds are split into train and test sets, and resized to k x k pixels (where k 2 32). The CIFAR-I0 image (of dimensions 32 x 32 3) is then placed at random along the edges of the background image to maximize spatial variation. The spurious background increases the dimension (= k 3) of the input when k > 32, making Loo certification with RS more challenging, but is uninformative for the task of CIFAR- 10 by construction. Our mask model (M1) needs to learn to ignore the background to reduce the effective dimension of the input. For computational reasons, we run all certification results on 200 sample subset of the CIFAR- 10 test set. Appendix D shows extended results, details about hyperparameter tuning (C.3), and results on larger test-sets (D.1). We set the failure probability of the certification procedure to 0.05, use 100 samples to select the most probable class, and 50,000 samples for the Monte Carlo estimate of p..
Table 1 summarizes the standard accuracy (r = 0) of each approach on the different settings. We vary in (0.25, 0.5, 1.0) and l: in {32, 48, 64, 96} to show the effect of noise levels and dimensionality on the accuracy of different approaches (k- = 32 corresponds original CIFAR-10 images). Figure shows the certified test accuracy at different radii 7: for ARS and all baselines we consider.
We make three observations. First, ARS outperforms all the baselines under distractor backgrounds (k > 32). Static mask is slightly better at & = 32, probably because CIFAR- 10 images lack enough "irrelevant" information for ARS to discard. This is precisely why introduce this benchmark, where we explicitly add such irrelevant information to input images. Indeed, at k > 32, we observe that the standard accuracy of ARS improves, translating certification levels, since more accurate and confident predictions give a larger certified radius x0
improved certified accuracy at all
Second, as we grow the input dimension k, the accuracy of ARS remains either stable or increases.
whereas that of other baselines goes down, resulting in an increasing gap. For instance, at a = 1.0, the gap between ARS and the best baseline is 1.3% points for k 32, 2.5% points for k 48,
7

---

1.0
1.0
1.0
Certifie Accuracy
(ours)
Certifed Accurary
(ours)
Cartired Accurary
(ours]
0.8
Cohen et el.
0.8
Cohen et
0.8
Cohen et ell
0.6
Mesk
0.6
Møsk
0.6
Mask
Sukerik et al: UniCR
Sukenik et
Sukerik el al: UniCR
0.4
0.4
UniCR
0.4
0.2
0..00
08.00
08.00
0.02
L. redius
L. redius
L. redius
(a)
32,
0.5
(b) k 18, 0.5
(c) 96,
0.5
1.0
1.0
1.0
Cortified Accuracy
ARS tours]
Cortified Accurayy
ARS lours)
Contried Accurayy
ARS tours)
Cohen
Cohen
Cohen
0.6
Static Mask
0.6
Static Mask
Static Mask
Sukenik
Sukceiic
Sukaniik
0.4
UniCR
0.4
UniCR
0.4
UniCR
0.2
0.2
0.2
8.00
0.02
0.04
08.00
0.02
0.04
0800
0.02
0.04
L.
L.
(d) A- 64,0 σ = 0.25
(e) k 64, o = 0.5
(1) 64, a = 1.0
Figure 2: Certified Test Accuracy on CIFAR-10 (20kBG), (a)-(c) show the effect of dimensionality for (a) no background/ / k = 32, (b) k = 48, and (c) k = 96 for constant o = 0.5. (d)-(f) show the effect of noise for (d) 0.25, (c) 0.5 and (f) 1.0 with dimensionality fixed to & 64. Each line is the mean and the seeds.
shaded interval covers +/- standard deviation
Input Images
ARS Masks
32
64
96
Figure 3: (left) Original CIFAR-10 images superimposed on backgrounds for different l (except k = 32 which is background), and (right) their corresponding masks (grayscale) inferred by our mask model All masks are for 0.5. Appendix D.2 shows all the corresponding images across our multi-step architecture.
As l grows, the amount of relevant information (a 32 x 32 x 3 CIFAR-10 image) remains the same, whereas the amount of spurious background information increases. ARS' mask is able to rule out spurious pixels, reducing the noise in the second step (Figure 3). Thanks to this masking, ARS is much less sensitive to increases in dimensionality.
8.2% points for k 64 and 15% points for
Third, we observe that except
32, ARS improves (1=1.00 noise regimes. In fact, this trend continues to persist in higher noise regimes (Appendix D). Similar to previous observations, we notice that we increase a, other baselines's is accuracy drops significantly whereas ARS accuracy drops much less, displaying higher noise tolerance.
all the baselines in low (a 0.25) to high
ARS training and inference requires additional computation. To certify single input (k = 32), Cohen et al. (2019) takes 1-2 seconds while ARS takes ~26 seconds (as measured on an NVIDIA A100 80Gb GPU). This 2x overhead does however yield improved certified accuracy.
4.2 CelebA Benchmark: Classification Without Spatial Alignment
To evaluate ARS on a more realistic task with natural spatial variation, we use the CelebA face dataset in its unaligned version. We focus on the "mouth slightly open" (label 21) binary classification task because mouth location and shape vary. The input part relevant to this task likely well-localized, which affords an opportunity for the mask model to reduce the effective input dimension. The dataset
8

---

Setting/Approach
Cohen et al.
Static Mask
ARS
CelebA, 0 = 0.25
94.3 (0.5)
93.0
97.0 (0.8)
CelebA, a = 0.5
91.0 (0.8)
(0.7
94.3 (0.9)
CelebA, o= 1.0
83.3 (0.9)
(2.6)
91.0 (1.6)
Table 2: Standard test accuracy (r = 0) on CelebA (unaligned and cropped). ARS is equal or better.
Adaptivity handles the higher spatial dimensions (160 x 160) and variation of these inputs.
0.8
0.8
0.5
0.6
0.6
Cohen et al.
Certified
static mask
0.2
0.2
0.2
00000
0.005
0.010
0.000
0.005
0.020
0.015
0
0.000
0.005
0.010
0.015
L. radius
L. redius
L. radius
(a)
0.25
(b) a 0.5
(c)
Figure 4: Certified test accuracy on CelebA (unaligned and cropped). We evaluate static methods and ARS measure the value adaptivity. Each line is mean and the shading covers standard deviation across three seeds. Adaptivity helps at all noise levels.
consists of images with varied resolution, and meta-data about the position of different features, including the mouth. To create a challenging benchmark, we randomly crop all images to 160 x 160 pixels, which creates spatial variation in the mouth's position. The only crop constraint is that the mouth is 2 10 pixels from the edge to ensure sufficient input to solve the task. Figure shows example images from the test set, their respective masks from ARS. and the baseline static mask. Input images
Figure shows the certified accuracy for ARS, Cohen et al. (2019), and static mask, for three levels of the noise a. First, both baselines per- form very similarly. We can see from Figure 5 that the static mask is approximately identity (notice the 0.99 scale), with only very slight dimming on the edges. This is because the mouth is not centred in benchmark, there is no one-size-fits-all mask. Second, ARS is able predict sparse mask that focuses areas likely to have the mouth. The mask adapts to each input at test time, which is what enables the sparsity without performance degradation. Third, this sparse mask leads large noise reduction, enabling ARS to drastically improve both standard and certified accuracy. For instance, with = 0.5, ARS improves the standard accuracy from 91.0% to 94.3% (a 3.3 point improvement), while the certified accuracy at x = 0.004 jumps from 45.0% to 79.3% (a more than 30 point improvement)). At lower noise (o 0.25) there is still an increase standard accuracy from 94.3% to 97. 97.0% and an increase in certified accuracy from 68.3% to 84.7% at n 0.002). At larger noise (a = 1.0), ARS sees significant increases (7. 77% points in standard accuracy, and from 21.3% to 49. 49.3% certified accuracy at 00 0.008).
Static Mask
ARS Masks
0.99
1.00
Figure 5: ARS masks are localized and input specific.
4.3 ImageNet Benchmark: Classification on the Standard Large-Scale Dataset
To evaluate the scalability ARS we experiment on ImageNet (without any modification) with 0.25, 0.5, 1.0. For each noise level, compare with Cohen et al. (2019), which we reproduce for this large-scale setting. We evaluate two versions of ARS: our regular setting (End-To-End), and a version that fixes the base classifier to the model trained as in Cohen et al. (2019), and only trains mask model for 10 epochs (Pretrain). The certified accuracy is plotted in Figure and the standard accuracy is reported in Table 3.
When only training the mask model, certified accuracy remains close to that Cohen et (2019) at all radii and noise levels. ARS trained end-to-end improves both standard and certified accuracy.

---

Setting/Approach
Cohen et al.
ARS (Pretrain)
ARS (End-To-
ImageNet, = 0.25
66.5 (0.009)
67.4 (0.002)
65.7 (0,006)
ImageNet, o = 0.5
57.2 (0.009)
56.0 (0.003)
57.4 (0.010)
ImageNet, = 1.0
43.6 (0.005)
43.8 (0.002)
44,5 (0.010)
Table 3: Standard test accuracy (r 0) on ImageNet. ARS maintains standard accuracy.
The standard accuracy (at r 0) increases from 57.2% to 57.4% and from 43.6% to 44.5% when 0.5 and α = respectively. For a 0.25, standard accuracy for ARS is close but slightly lower than Cohen et al. (2019), while the pretrained ARS outperforms Cohen et al. (2019) from 66.5% to 67.4%. Appendix F discusses other ARS improvements without certification.
Certified accuracy increases at larger a. For instance at a = 0.5, ARS improves certified accuracy 7 0.001 from 48.9% to 50.5%. At larger noise a 1.0, ARS improves certified accuracy at r = 0.005 from 21.7% to 23.1%. This shows that ARS* adaptivity generalizes outside of the specialized benchmarks we designed, and can scale large datasets and complex classification tasks.
1.0
Cartfled Accuracy
(endDend)
Certifted Accuracy
ARS (wdd2end)
Certiffed Accuracy
ARS (end)eed)
0.8
ARS (gretrain
AR5 pressaint
AA5 (pecraint
Coberr stal
Coren at
Comen at
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
00000
0.000
0.000
L. radius
L. radius
L. radius
0 0.25
(h) 0.5
(c) 1.0
Figure 6: Certified test accuracy ImtgeNet for 0.25, 0.5, 1. We plot the mean and the shading covers 11 standard deviation for three seeds. ARS is equal or better than non-adaptive RS (Cohen al.) at large scale.
Discussion
Limitations:
The multi-step adaptivity of ARS improves certification the cost of increased model size and computation for RS. This impacts both training and testing computation, and is especially costly in the context of RS due to the Monte Carlo estimation of the model's s expected predictions (over several forward passes at inference time). While we empirically show improvement by ARS, it would interesting and important to investigate how combines with other RS improvements such as adversarial training (Salman et al., 2019), consistency regularization (Jcong and Shin, 2020), higher order certification (Mohapatra et al., 2020), double sampling (Li et al., 2022b), and denoising by adaptive masking technique provides improved certificates
diffuuion (Carlini et al., 2022). Lastly, for the Lx norm, but does not have the same effect for other norms such as L2 (see remarks $2.4). It is plausible that ARS' adaptivity can lead to improvements under alternative norms, by leveraging different DP mechanisms and updates. We leave this exploration for future work.
Revisiting heuristic adaptive defences (as surveyed in Croce et al. (2022)) through the lens of ARS could help improve the empirical performance of provable defences. ARS may require extensions, but could eventually enable the formal analysis of input purification (e.g., Song and Kim (2018); Nie et al. (2022); Yoon et al. (2021)), or leverage DP-SGD (Abadi et al., 2016) to analyze defences that update by test-time optimization (Alfarra et al., 2022b; Hwang et al., 2022; Mao et al., 2021). Going further, one could leverage the vast DP literature to extend ARS, enabling fully-adaptive variance defences inspired by Alfarra al. (2022a) by leveraging privacy odometers (Rogers et al., 2016; Lécuyer, 2021; Whitehouse et al., 2023).
Implications:
To conclude: we introduced Adaptive Randomized Smoothing (ARS) to reconnect RS with DP theory, to propose a new two-step defence for deep image classification, and to rigorously analyze such adaptive defences that condition on inputs at test time. This framework opens promising avenues for designing models that are adaptively and soundly robust with provable guarantees about their updates on natural and adversarial inputs.
10

---

Acknowledgments and Disclosure of Funding
We thank Krishnamurthy Dvijotham and lan Goodfellow for reviewing and providing feedback during the Google DeepMind publication process. We thank Motasem Alfarra for discussing variations on input-dependent variance for randomized smoothing. We are grateful for the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) [reference number RGPIN-2022- 04469], as well as Google Research Scholar award. This research was enabled by computational support provided by the Digital Research Alliance of Canada (alliancecan.ca).
References
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016.
Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem. Data dependent randomized smoothing. Uncertainty in Artificial Intelligence, pages 64-74. PMLR, 2022a.
Motasem Alfarra, Juan C. Perez, Ali Thabet, Adel Bibi, Philip H.S. Torr, and Bernard Ghanem. Combating adversaries with anti-adversaries. Proceedings of the AAAI Conference on Artificial Intelligence, 2022b.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International conference machine learning, 2018.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify loo robustness for high-dimensional images. The Journal of Machine Learning Research, 2020.
Yulong Cao, Ningfei Wang, Chaowei Xiao, Dawei Yang, Jin Fang, Ruigang Yang, Qi Alfred Chen, Mingyan Liu, and Bo Li. Invisible for both camera and lidar: Security of multi-sensor fusion based perception autonomous driving under physical worldd attacks. 2021 IEEE Symposium on Security and Privacy (SP), 2021.
Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter. (certified!!) adversarial robustness for free! In The Eleventh International Conference on Learning Representations, 2022.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey. arXiv preprini arXiv: 180.00066, 2018.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320. PMLR, 2019.
Joana Costa, Tiago Roxo, Hugo Proença, and Pedro RM Inácio. How deep learning sees the world: A survey on adversarial attacks & defenses. arXiv preprint 2rXiv:2305.10862. 2023.
Francesco Croce, Sven Gowal, Thomas Brunner, Evan Shelhamer, Matthias Hein, and Taylan Cemgil. Evaluating the adversarial robustness of adaptive test-time defenses. In International Conference on Machine Learning. pages
PMLR, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition. leee, 2009.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. arXiv preprint arXiv: 2019.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2022.

---

Krishnamurthy (Dj) Dvijotham, Jamie Hayes, Borja Balle. Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference on Learning Representations, 2020.
URL. hwtph:ttp///t pttttt:::///peneevviiie wttp:/vwwwwweeettneeeeeeee ratt/forrmmideSSSKKSPPP
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 2021.
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.
James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2015.
Hanbin Hong, Binghui Wang, and Yuan Hong. Unicr: Universally approximated certified robustness via randomized smoothing. In European Conference on Computer Vision. Springer, 2022.
Duhun Hwang, Eunjung Lee, and Wonjong Rhee. Aid-purifier: A light auxiliary network for boosting adversarial defense. 2022 26th International Conference on Pattern Recognition (ICPR), 2022.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. URL https:
//api. //apii.smmntee... www.eetiisccooar.nooooo Cwa.llarrrrr//Copussllll.. ID: 18268744.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning. PMLR, 2020.
Mathias Lécuyer.
Practical privacy filters and odometers with rényi differential privacy and applica- tions to differentially private deep learning. arXiv preprint arXiv:2/03.01379, 2021.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE symposium on security and privacy (SP), pages 556-672, IEEE, 2019.
Jizhizi Li, Jing Zhang, Stephen J Maybank, and Dacheng Tao. Bridging composite and real: towards end-to-end deep image matting. International Journal of Computer Vision, 2022a.
Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double sampling randomized smoothing. In International Conference on Machine Learning. PMLR, 2022b.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In 2023 IEEE symposium on security and privacy (SP), 2023.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
C. Mao, M. Chiquier, H. Wang, J. Yang, and C. Vondrick. Adversarial attacks are reversible with natural supervision. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
Jeet Mohapatra, Ching- Yun Ko, Tsui- Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. Advances in Neural Information Processing Systems, 2020.
Weili Nie, Brandon Guo, Yujia Huang, Chaowei Xiao, Arash Vahdat, and Animashree Anandkumar. Diffusion models for adversarial purification. International Conference on Machine Learning, 2022.
Apapan Pumsirirat and Yan Liu. Credit card fraud detection using deep learning based on auto- encoder and restricted boltzmann machine. International Journal of advanced computer science and applications, 2018
12

---

Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-ge composition. Advances Neural Information Processing Systems, 2016.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-asiisted intervention-MICCAL 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18. Springer, 2015.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in neural information processing systems, 2019.
Yang Song and Taesup Kim. Sebastian nowozin stefano ermon nate kushman. pixeldefend: Leverag- ing generative models to understand and defend against adversarial examples. In International Conference on Learning Representations, 2018.
Peter Súkeník, Aleksei Kuvshinov, and Stephan Günneemann Intriguing properties of input-dependent randomized smoothing. arXiv preprint urXiv:2110.05365, 2021.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014. URL http: :tstt::///rree //trx/aaavvv////////a//eaaaaaava org abs/1312/111111//////////////11/ 6199.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in neural information processing systems, 33:1633-1645, 2020.
Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu. Fully-adaptive composition in differential privacy. In International Conference Machine Learning, 2023.
Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large fam- ily of distributions. In Proceedings of The 24th International Conference on Artificial In- telligence and Statistics, Proceedings of Machine Learning Research. PMLR, 2021. URL mlr press/vv30/wws hemid..tml..
Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning. PMLR, 2020.
Jongmin Yoon, Sung Hwang, and Juho Lee. Adversarial purification with score-based generative models. In Proceedings of the 38th International Conference on Machine Learning, 2021.
13

---

A f-DP Background
For this background
the DP mechanism terminology. A mechanism .M.) is randomized computation taking an input and returning one sample from the distribution of outputs for this input: m (Mx)) with imput x and output m. In ARS, each model step corresponds an f-DP mechanism.
Definitions. Dong et al. (2019; 2022) formalize privacy as a bound on the power of hypothesis tests. Consider any two neighbouring inputs: in the most common DP applications, X, X' are two databases differing in one element; in the case of ARS against an Lp adversary, X, X' E R2 are any two inputs such that X - -X' (r(r). Intuitively a randomized mechanism M is private if, for any such neighbouring inputs, the distributions (XX) and M(X') are hard to distinguish. That is, by looking a sample output from mechanism M, it is hard to guess whether M ran on X
X".
In f-DP (Dong et al., 2019; 2022) "hard to distinguish" is defined by a hypothesis testing problem:
Ho : the input was X
vs.
H1 : the input was X'.
The output m .M serves as input rejection rule p(.) E [0, 1] (note: to preserve typical notations, lower-case & is the rejection rule, and upper-case + is the standard normal CDF). The rejection rule rejects Ho with probability d(m), so ((m) = 0 predicts that X was the input, and Φ(m) = that X' was.
Given a rejection rule o. we define its Type I error as and type II error (or one minus the power of the rule) 3 as:
as Em=-M(()(((m))
B 2 1- [o(m)]
Intuitively, as is the expected amount of rejection of H. when the hypothesis correct (X was in input, but we think X' was), also called the level of the rejection rulc. On the flip side, 8s is the expected amount of non-rejection under Hi (X' was in input, but we think X was). 1- 3g is called the power of the rejection rule.
For any two distributions M(X) and M(X',, we define the trade-off function T (M(X). M(X'))
[0, 1] + [0, 1] that quantifies the minimum amount of type II error achievable at each value of type I error by any (mcasurable) rule; or equivalently the maximum power of any rule at each level:
Ya E [0, ( (ax) inf : as S a}
Now we define f-DP: for any trade-off function f, mechanism M f-DP if, for any neighbouring inputs X, X',
T(M(X), 2
These definitions the main technical tools we need to prove Proposition 2.1. Corollary 2.2 only adds the formula for f for the Gaussian mechanism, given in Section 2.1.
Composition. All other results rely on the above plus the adaptive composition of f-DP mecha- nisms. Such composition is key to all DP theory and algorithm design. Consider a sequence of N mechanisms M,, such that each mechanism is fDP with regards to X,X', and depends on the neigh- bouring input as well as the output of all previous mechanisms. More formally, under Ho we have my ~ M,(,, mz;), and under H. we have my ~ MX, me;), where mcs & (m1,..., ......,,,,11... m2-1). Coneretely, each M, is fDPDP with regards to X, X' for f. known in advance, but the actual compu- tation made by M, can depend on mes (as long as is fi-DP). We leverage this adaptivity to lower the noise variance in our method's 's second step while keeping f2 fixed (see $3).
We need two more results to define the composition of sequence of mechanisms. First, Proposition 2.2 in Dong et al. (2019; 2022) shows that for any trade-off function f. there exist two distributions Pr. such that T(P,.Qr) = f. Call any such pair of distributions a representative pair of f. Second, we define the composition operator & by ʃ @ g T(P; x Pg- Q, Qa). That is, the composition operator between two trade-off functions is the trade-off function between the product distributions on their representative pair. Then Theorem 3.2 in Dong al. (2019; 2022) shows that:
M: X + (X)(X)...,, M,. )) is f1 ....
....6 @ JN-
Concretely, the mechanism that returns the sequence of results for all compute adaptive MN is Ji 80 ...... < DP. The previous definitions, as well as this composition result, what we use to prove Theorem 2.3 and Proposition 2.4.
14

---

B Proofs
Proposition 2.1 (f-DP Robustness). Let M : X +Y be f-DP for By(r) neighbourhoods. and lel Mg X + arg maxyey P(M(X) - y) be the associated smooth classifter. Let y+ _ (X) be the prediction on inpul X, and let p+,p- E [0,1] be such that P(M(X) y+) 2 p+ p- Z
-a F(M(X)= = --)) Then:
f(1- f(p-) = Ve E Bp(r), Ms +x) +c) y+
Proof. Let us first consider any runner-up class y-. Calling M the random variable for M's
prediction, consider the rejection rule o = { = y- where 1 is the indicator function. Denoting
(mxx)(0), and using the fact that M is f f-DP for Bp(r) neighbourhoods, we have that de E (y(r):
P(M(X +c) (o)
(8)
S f(a)= 51-f(p=)
where the last inequality is because a = (Ø) = P(M(X) = v-) S p-, and f is non- increasing so [(a)= 2 /(p-) and hence 1 -
S 5(a) -(-)).
Let us now consider the predicted class y/+. Keeping the same notations, and defining the rule o' 1 * y+} 1 1[M y+ Then a' Em(x)(d')= P(M(X) = y+) S p++
and (0') 11 f(a') S 1- - f(1 - -p+), yielding:
P(M(X + +)) = v+) = 1 - (M(x+t)(0''
2 f(1 - Pp))
Putting Equations (8) and (9) together, we have that P P(M( = y+) f(1-p+) 2 1-1(p=)2 P(M(X- + e) y-) and thus ms(X + e) y-
Note that we do not have to chose a rule e E {0, 1}. but could instead return any number in [0, 1]. such as the logits of the base classification model, yielding the following definition for the smoothed classifier Ms: : X - arg maxyey (x)))
Proposition 2.2 (RS from f-DP). Let M: X + g + +2), ~ NNO,,021) and Ms X +
arg ma (X) y) be the associated smooth model. Let yt & Ms(X) be the pre- diction on input X, and let Pt. E [0 be such that PP(M(X) = 34) 2 p+ 2 p z
maxy+ P(M(X)- = y-). Then Ve E (2(r2), Ms(X + = V+, with:
rx = x - (p-))
x
2 NO, d²) is a Gaussian mechanism. By Equation (2), for the (r) neighbouring definition, is GDP By post-processing M is also DD
Proof.
Applying Proposition 2.1, we have that G5 - (1-p+) 1 G= (T- = Ve E B2(r), ms(X +e) = y+. Let us find rx- = sup {r G1 - p+) 2 G monotonously decreasing this will happen at G.x (1 p+) = 1 G.x (p-),
Since G. (.) as function of is
), that is:
T ④ (p+)
7x
$ ④ 11 p-)
rx
0
Φ 1 (p+)
rx
Φ 1(1 - --) +
Tx
0
+ o 1-1 1 (p+)
7x
x 1- -1((p-))))))))) Tx
rx
0
(p_)
Φ - (p-)):
2
where the first implication holds because by symmetry of the standard normal 1 +(x) ((-x). and because & is strictly monotonous; the second because similarly, 4 - - p) = - (p)). 0
15

---

C Experiment Details
C.1 Mask Architecture
Figure 7 shows the architecture of our Mask model w (M1). We adapt a UNet architecture to preserve dimensions, and use Sigmoid layer the end of the model to output values between 0 and 1 for mask weights. We set up UNet hyperparameters as in in_channels=3, out out_channels= (to out put
a mask), base_ cuse_channe==3, channe__mul==1224.
Conv
Downsample
Upsample
Sigmold
Figure 7: UNet structure
CIFAR-I0
CelebA
ImageNet
GPU epoch
single 24G RTX4090
single 24G
RTX4090
single 80G A100
100
24
100 10+90)
train batch size test batch size
256
64
300
20
100
100
base channel optimizer
64
16
Adam
SGD
Mask Model
Ir weight decay
lc-3
Se-2
5e-2
lc-4
lc-4
(UNet)
momentum
0.9
0.9
step size gamma model optimizer Ir weight decay
40
30
ResNetT10
ResNet50
ResNet50
AdamW
SGD
SGD
Base
le-2
Se-2
le-1
Classifier
le.4
le.4
momentum
0.9
0.9
step size
30
garmma
0.8
Table 4: Hyperparameters for training ARS. Check Appendix C.3 for more details of CIFAR-10 hyperparameters.
C.2 Hyperparameter tuning for CelebA
Table 4 provides the details of our ARS models' syper-parameters. On the CelebA dataset, we tune the hyper-parameters the ARS, Cohen et (2019), and static mask settings settings, we settle on SGD with learning rate 0.05 and step learning rate scheduler (step size of and 7 = 0.8) for the base classifier. In the static mask setting, we use SGD with learning rate 0.01.
0.75. In all
C.3 Hyperparameter tuning for CIFAR-10 BG20k
For the base classifier in Cohen et al. (2019), Static Mask and ARS experiments, we tune the optimizer and its hyperparameters using = 64, a = 1.5 as the testbed. Based on these tuning experiments, chose AdamW the optimizer with an initial learning rate of 0.01 and weight decay to 0.0001. We scale the learning rate by 0.1 every 30th epoch, with a batch size of 256. For the mask model in ARS experiments, 0.001, weight decay of 0.0001, whilst scaling the learning rate by 0.5 every 40th epoch. We used the same hyperparameters for all k's and ''s for these setups.
again used the AdamW optimizer with initial learning rate of
For Súkeník et (2021), for = 32, 48, 64, we tune the hyperparameters using = 64 as testbed. We kept the optimizer same used in the author's code (SGD), setting the initial learning rate to 0.01, momentum 0.9 and weight decay to O. We scaled the learning rate by every 30th epoch. We tune & 96's parameters separately. We start with an initial learning rate 0.1. keeping
16

---

the rest of hyperparameters same as for k = 32, 48, 64. Note that for lo = 96, we could not get the
standard accuracy to improve upon random baseline for o {0.5, 0.75, 1.0, 1.5). despite extensively tuning the learning rate.
8
a
0.12
=
0.25
a = 0.5
0 = 0.75
d = 1.0
0 = 1.5
32
2.25
2.25
2.25
2.25
2.25
2.25
2.0
2.0
2.25
2.25
2.0
2.0
96
2.0
2.0
2.25
2.25
2.25
2.25
Table 5: UniCR chosen for each setting.
For UniCR, we tune (the parameter of the generalized normal distribution for the noise) using 0.75 and k 48 as the testbed. We perform grid search on 3 and find that 3 = 2.0 or /3 = 2.25 Gaussian, but with wider more and shorted tails) perform best. For each k, setting, we train 3 models with / = 2.25 and 2.0 and choose the 3 giving highest mean standard accuracy. The chosen / for each setting given Table For each setting we also tune optimizer preeepparamttes. At k 32, use SGD optimizer. We use learning rate of 0.01, momentum of 0.9 and weight decay of 0.0005 with step learning rate scheduler (30 step and y 0.1). At k = 48, 64, 96 we training batch size 256, 100 epochs, and AdamW optimizer. We use learning rate 0.001 with step learning rate scheduler (30 step size and 7 = 0.5).
(Gaussian and close
17

---

1.0
1.0
Certines Accuracy
(ours)
Certifed Accurary
(ours)
Cortinied Accuracy
0.8
Cohen et
0.8
Cohen et
0.8
Cohen et al.
0.8
Mask
0.6
Møsk
0.6
Sukerii al. UniCR
Sukenik et
Sukceik et al. UniCR
0.4
0.4
UniCR
0.4
88.00
08.00
88.00
L. radius
L. redius
Lu radius
0.12
0.25
(c) 0.5
1.0
1.0
1.0
Cortrled Accunicy
ARS lours)
ARS (ours)
Certifted focuracy
ARS (ours)
Static Mask
Static Mask
0.6
Static Mask
UniCR
Sukrenik
Certified
0.4
Sukenik
UnICR
0.4
UnCRR
Sukenik al.
0.2
0.2
02
98
0.02
0.04
8.00
0.02
0.04
08.00
0.02
0.04
radius
radius
radius
(d) a = 0.75
(c) a 1.0
a 1.5
Figure 8: = 32 certified test accuracy results CIFAR-10 (20kBG) (a)-(f) show the effect increasing a. These results are in our 20kBG setting where= a CIFAR-10 image is placed randomly along the edges of a background image. Each line is the mean and the shaded interval covers +/- one standard deviation across seeds.
D Additional Results CIFARIO BG20k Benchmark
We show here full sweep of results for CIFAR-I0 Bg20k benchmark for A 32, 48, 64, 96 and a = 0.12, 0.25, 0.5, 0.75, 1.0, 1.5 for all our baselines and ARS. Similar to results presented in Table report the mean accuracy and standard deviation over three seeds.
k
Cohen et al.
Static Mask
UniCR
Súkeník al." A
ARS
0.12
(0.7)
78.6 (0.9)
(I.)
71.8
(0.7)
0.25
(1.)
73.9 (0.8)
69.8 (1.4)
68.6 (2.8)
72.6
0.5
63.6 (2.)
64.8 (0.9)
62.8 (0.8)
59.1
(1.4)
32
0.75
55.5 (0.8)
57.8 (0.8)
53.1 (0.8)
49.3 (0.2)
57.3 (0.6)
1.0
48 (0.7)
47.3 (1.3)
46.1 (0.9)
41.0
49.3 (0.6)
1.5
(0.2)
39.1 (0.8)
36.8 (0.8)
36.9 (0.1)
38.3 (1.0)
0.12
80.1
80.9 (0.7)
(2.9)
(0.1
83.6
0.25
71.6
(2.0)
69.7 (0.8)
(0.07)
75.5 (1.0)
0.5
(0.2)
64.1
60.3 (0.6)
53.5
66.0 (0.8)
48
0.75
51.5
(0.8)
52.7 (0.6)
(2.4)
57.6
1.0
(2.1)
(1.1
44.3 (0.2)
34.1
47.6 (2.1)
1.5
30.8
34.9 (2.4)
32,3 (0.2)
21.5
34.1 (2.9)
0.12
(0.9
(1.0)
76.7 (0.8)
(3.8
(1.0)
0.25
71.67 (0.9)
(3.2)
67.8 (0.5)
(0.1
77 (1.8)
0.5
61.6
(1.4)
58.7 (0.2)
41.1
65.4
64
0.75
(2)4
51.6
50.7 (0.2)
31.3
56.5 (2.6)
1.0
(1.8
(0.5)
42.2 (0.6)
(6.5
50.4 50.5
1.5
(0.2)
(3.9)
30.0 (1.8)
12.8
30.6 (1.0)
0.12
(9.8
79.6 (0.4)
(1.1)
(6.7)
83.7
0.25
(1.6
(1.3)
(1.8)
40.9
(2.2)
0.5
(2.4)
59.5 (1.4)
59.7 (1.3)
10.8 (2.3)
69.8 (1.2)
96
0.75
45.3 (3.4)
48 (4.3)
50.2 (0.5)
10.2 (0.4)
63.6 (3.5)
1.0
33.8 (3.8)
36.9 (0.5)
41.3 (2.4)
10.4 (0.3)
56.3 (2.3)
1.5
(1.4)
25.1 (0.6)
31.0 (1.4)
10.8 (1.4)
39.1 (2.5)
Table 6: Standard Accuracy (r = 0) on CIFAR-10 (20kBG). Our 20kBG benchmark places CIFAR-I1
images on larger background images. We report the mean accuracy and standard deviation over three seeds. ARS achieves higher accuracy across noise and input dimension k. indicates adaptivity.
18

---

1.0
1.0
Cortines Accuracy
(ours)
Centifed Accurary
(ours)
Cortified Accuracy
ARS lours]
0.8
Cohen et
0.8
Cohen et
0.8
Cohen et al.
0.6
Static Mask
0.6
Mask
0.6
Sukerik et al.
Sukenik et
Sukenik et al. UniCR
0.4
UniCR
0.4
UniCR
0.4
0.2
98.00
08.00
0.02
08.00
0.02
0.04
L. radius
L. redius
Lu radius
σ 0.12
(b) 0.25
(c) 0.5
1.0
1.0
1.0
Cortrleed Accunccy
ARS lours)
ARS (ours)
Certifted focuracy
ARS (ours)
Cohen
Cohen al.
Cohen
Static Mask
Static Mask
0.6
Static Mask
Sukceiik
Sukenik et
Sukenik al.
0.4
UniCR
Certified
0.4
UniCR
0.4
UnCR
0.2
0.2
02
98
0.02
0.04
0..0
0.02
0.04
08.00
0.02
0.04
radius
radius
radius
(d) a = 0.75
(c) a 1.0
a = 1.5
Figure 9: k = 48 certified test accuracy results CIFAR-10 (20kBG) (a)-(f) show the effect of increasing a. These results are in our 20kBG setting where a CIFAR-10 image is placed randomly along the edges of a background image. Each line is the mean and the shaded interval covers +/- one standard deviation across seeds.
1.0
1.0
1.0
Cartheed Accurscy
ARS (ours)
Cantfrid Accuracy
ARS (ours)
Cortifeed Accuracy
ARS tours]
Cohen al.
Cohen al.
Cohen et al.
0.6
Static Mask Sukenik al. UniCR
0.6
Static Mask
Static Mask Sukenik et UniCR
Sukcnik UniCR
0.4
0.4
0.4
0.2
0.2
0.2
08.00
08.00
98.00
0.02
0.04
0.02
0.04
0.02
0.04
radius
L. radius
radius
(a) 0 0.12
(b) a = 0.25
(c) r 0.5
1.0
1.0
1.0
Cortitee Accurcy
0.8
ARS lours)
Cohan et
Certifeed Accuracy
0.8
ARS (ours)
al.
Certifted Accuracy
0.8
ARS (ours)
Stabic Mask
Static Mask
Static Mask
Sukenik et UniCR
et
Sukenik al.
UniCR
0.4
UniCR
0.2
0.2
0.2
08.00
0.02
0.04
8.00
0.02
0.04
%8.00
0.04
L. radius
L- redius
C. radius
(d) 0 = 0.75
(c) a = 1.0
(f) a 1.5
Figure 10: 1: = 64 certified test accuracy results for CIFAR-10 (20kBG) (a)-(f) show the effect of increasing These results are in our 20kBG setting where CIFAR-10 image is placed randomly along the edges of background image. Each line the mean and the shaded interval covers +/- standard deviation across seeds.
D.1 Impact of Certification Test-set Size
The baseline results in Table 6 are lower than those reported by Cohen et al. (2019) (Figure 6). This is result of our certifying over smaller subset of the test set (the released code from Cohen et al. (2019)' uses a subset of size 500, while the paper says the certification was on the full test set). In Table we report the standard accuracy (r 0) the same 500 samples subset of the CIFAR-10 test set as used in the code released by Cohen et al. (2019). We show results for = 32, which is the plain CIFAR- 10 task, using both the byper-parameters from Cohen al. (2019), our (the most notable change is that we use AdamW), and ARS. We
own optimized make three observations. First, it turns out, 200 samples subset used for results in Table 6
experiments. MD
19

---

1.0
1.0
Certines Accuracy
(ours)
Cortifed Accurary
(ours)
Cortinied Accuracy
0.8
Cohen et
0.8
Cohen et
0.8
Cohen et al.
0.8
Mask
0.6
Møsk
0.6
Sukerii al. UniCR
Sukenik et
Sukenik et al. UniCR
0.4
0.4
UniCR
0.4
88.00
0..00
%8.00
L. radius
L. redius
Lu radius
0.12
0.25
(c) 0.5
1.0
1.0
1.0
Cortfled Accuncyy
ARS lours)
ARS (ours)
Certifted Rocuracy
ARS (ours)
Static Mask
Static Mask
0.6
Static Mask
Sukrenik
Sukenik
Sukenik al.
UniCR
Certified
0.4
UniCR
0.4
UnCRR
0.2
0.2
02
98
0.02
0.04
8.00
0.02
0.04
08.00
0.02
0.04
radius
radius
radius
(d) a = 0.75
(c) a 1.0
a 1.5
Figure 11: = certified test accuracy results CIFAR-10 (20kBG) (a)-(f) show the effect of increasing a. These results are in our 20kBG setting where a CIFAR-10 image is placed randomly along the edges of background image. Each line is the mean and the shaded interval covers +/- one standard deviation across seeds.
Approach
Samples
Cohen et al.
Cohen et al. w/ AdamW
ARS
200
77.2 (2.7)
79.0 (0.7)
78.5 (0.7)
0.12
500
79.6 (2.1)
82.1 (0.4)
82.3 (1.1)
10k
80.3 (0.6)
82.7 (0.6)
83.4 (0.5)
200
70.7 (3.7)
70.6 (1.0)
72.6 (0.9)
0.25
500
(2.6)
75.6 (0.9)
75.9 (0.9)
10k
73.7 (2.6)
77.2 (0.2)
77.7 (0.1)
200
(0.4)
63.6 (2.0)
(1.4)
0.5
500
63.1 (0.7)
65.2 (0.9)
65,9 (0.7)
10k
64.3 (0.5)
66.1 (0.3)
67.9 (0.3)
200
45.0 (1.5)
48.0 (0.7)
49.3 (0.6)
1.0
500
45.9 (1.6)
49.1 (0.4)
50.5 (0.8)
10k
46.8 (1.7)
50.0 (0.5)
51.5 (0.4)
Table 7:
on CIFAR-10 (20kBG), We report the mean accuracy and standard deviation over three seeds. We compare three approaches: Cohen et al. (2019) trained with the hyper-paramcten they report in their GitHub repository, Cohen et al. (2019) trained with the hyper-paramcten we report in 4, and ARS. We train models with each approach at 0.12, 0.25, 0.5, 1.0. The corresponding models certified 200, S00, and 10,000 samples.
standard accuracy
is more challenging, and accuracy values are systematically lower (by about 2% points) than over 500 samples and the full test set (10k samples). Using the same 500 samples subset yields accuracy values very close to those reported by Cohen et al. (2019) on their all samples sizes 200, 500. and 10k, our hyper-parameters significantly improve the accuracy of RS (by about 3% points consistently), confirming that we are making a fair comparison between the best RS models we could find and ARS. Third, tuned RS, as CIFAR-10 images are well cropped and low-diment www-dimesioonl,, providing less opportunity for dimension reduction through masking, and hence lower ARS improvements.
Second, over
ARS provides modest improvements over
D.2 CIFAR-10 BG20k figures
Figure 12, Figure 13, Figure 14 and Figure 15 shows figures of different stages in our ARS architecture (Figure 1). In all these figures, 1s row corresponds input images X, 2nd row corresponds to images right after Mj. 3rd row corresponds ARS masks, 4t row corresponds to clement-wise
20

---

(a) o 0.25
(b) σ 1.0
Figure 12: Figures different stages in our ARS architecture for CIEAR-10 l 32 input images. Check
Appendix D.2 for detailed information about each row
(a) a 0.25
(b) 1.0
Figure 13: Figures at different stages in our ARS architecture for CIFAR-10 BG20k k = 18 input images. Check Appendix D.2 for detailed information about each row
product of input and ARS masks, 5th row corresponds to images right after M2 and 6th row corresponds to images right after averaging M1,
21

---

(a) o = 0.25
(b) = 1.0
Figure 14: Figures at different stages in our ARS architecture for CIEAR-10 BG20k k: 64 input images. Check Appendix D.2 for detailed information about each row
(a) σ 0.25
(b) σ = 1.0
Figure 15: Figures at different stages in our ARS architecture for CIFAR-10 BG20k k: 96 input images.
Check Appendix D.2 for detailed information about each row
22

---

E
Additional Results on CelebA
Input images
First query noised images
ARS Masks
Second query noised images after averaging
Figure 16: The localized ARS masks produce un-noised mouth regions after averaging.
Figure 16 shows how adaptive masking reduces the noise around areas that are important classi- fication. The images follow our architecture visualized Figure 1. The mask model is provided the first query noised images as input. The learned masks, presented in the bottom left, are sparse and highly concentrated around the area of interest-the the mouth area. The second query noised images (after weighted average) use the mask clearly reduce the noise around the mouth. This large noise reduction enables ARS to outperform static masking and Cohen al. (2019), as shown on Figure 4.
We show here a full set of results for the CelebA benchmark over all 0.12, 0.25, 0.5, 0.75, 1.0, 1.5 for Cohen al. (2019), static masking. and ARS. Similarly to the results in Table we report the mean standard accuracy and standard deviation over three seeds in Table 8. The certified accuracies plotted in Figure 17. see that at all a, ARS has the high- est standard accuracy.
Cohen al.
Static Mask
ARS
0.12
94.7 (0.5)
95.7 (1.2)
96.3 (0.9)
0.25
94.3 (0.5)
93.0 (0.8)
97.0 (0.8)
0.5
91.0 (0.8)
91.7 (0.9)
94.3 (0.9)
0.75
88.7 (1.2)
89.0 (1.4)
92.3 (0.9)
1.0
83.3 (0.9)
84.7 (2.6)
91.0 (1.6)
1.5
77.7 (2.5)
74.3 (1.7)
81.0 (2.2)
Table 8: Standard Accuracy (r = 0) on CelebA (unaligned and cropped). We report the mean accuracy and standard deviation over three seeds.
1.0
1.0
1.0
Cortified Accuracy
Cohen et al.
0.6
statti mask
0.6
0.6
0.4
0.4
0.4
08000
0.005
0.010
0.015
0
0.000
0.005
0.010
0:015
0.000
0.005
0.010
0.015
radius
L. radius
L. radius
(a)
0.12
(b) 0.25
(c) 0.5
1.0
1.0
1.0
Certifted Accuracy
0.8
Cohen et al. mask
ARS (ours)
0.8
0.8
0.4
0.2
0.2
0.2
00000
0.005
0.010
0.015
00000
0.005
0.010
0.015
0
0.005
0.010
0.015
radius
radius
radius
(d)
0.75
(c) a = 1.0
(f)
1.5
Figure 17: Certified test accuracy on CelebA (unaligned and cropped). Each line is the mean and the shading covers +1 standard deviation across three seeds. Adaptivity helps at all noise levels.
23

---

Additional Results on ImageNet
Input images
First query noised images
Masks
Second query noised images after averaging
Figure 18: The localized ARS masks produce un-noised object regions after averaging. For
Input images
First query noised images
ARS Masks
Second query noised images after averaging
Figure 19; For 0.5.
Input images
First query noised images
ARS Masks
Second query noised images after averaging
Figure 20: For σ = 0.25.
Figures 18 20 show how adaptive masking reduces the noise around areas that important classification for ImageNet. The images follow our architecture visualized Figure 1. The mask model provided the first query noised images input. The learned masks, presented in the bottom left, are sparse and concentrated around the area of interest (the bird, or any labelled object). The second query noised images after weighted average the mask clearly reduce the noise around the bird.
Setring/Approach
Cohen et al.
ARS (Pretrain)
ARS (End- To- To-End)
ImageNet, 0.25
68.5 (0.1)
69.5 (0.0)
70.1 (0.2)
ImageNet, 0.5
60.7 (0.5)
63.2 (0.1)
64.2 (0.2)
ImageNet, a 1.0
47.9 (0.1)
52.1 (0.0)
53.8 (0.3)
Table 9: Test accuracy without certification ImageNet.
An interesting observation is that on ImageNet, ARS yields larger improvements to the test accuracy without certification. We follow the certification procedure of Cohen al. (2019), which first determines the predicted class, and then certifies it if and only if the probability of this predicted class such that p+ 2 0.5 (that is, groups all other classes into one non- non-predicted class). If this is the case, the prediction will count not certified
even if the predicted class is still correct. We keep this procedure for consistency with prior work, but on a task with a large number classes like in ImageNet, the accuracy
can be much lower the non-certified accuracy.
noticed that ARS significantly improves this non certified accuracy, while not improving the accuracy at 0 as much (see Section 4.3). In effect ARS leads to more correct predictions, but

---

this (correct) predicted class has P+ < 0.5, so the accuracy at = 0 does not increase. Table shows this effect by comparing the test accuracy (no certification at all) across all methods. Under ARS, the test accuracy increases from 68.5% 70.1% 1% when o 0.25, from 60.7% 64.2% when = 0.5, and from 47.9% 53.8% for a = 1.0. In summary, ARS achieves best test accuracy (without certification) for all the noise levels. This suggests that ARS helps more than shown by the default certification approach, and that a finer analysis that accounts for the probability of all classes could yield further improvements certified accuracy.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction identify the purpose of our paper and our theoretical, technical, and empirical contributions. We provide theoretical results in Section 2 with detailed proofs, and comprehensive experimental results in Section to support our technical claims and contributions for test-time adaptive certification for robustness. Our choice of theoretical framework, task scope, and evaluation datasets are all present in the abstract.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We identify limitations in Section and in particular call out computational overhead and the need to assess the combination of ARS with other improvements to RS (which are compatible in principle, but require experiment to measure and verify).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
26

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We present the theoretical results in Section 2, where we cover the main results, and provide Appendix B with further detailed assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The method described in the text, and to ensure sufficient detail, we addi- tionally provide appendices and supplementary material that includes the anonymized code for our method. The experiments identify their settings and hyperparameters, such as noise levels and input image dimensions, and these settings can be verified by inspection of the results for our method and the baselines like Cohen al. (2019). By relying on standard base models, such ResNet-50, our work is made more reproducible by following the conventions of cxisting papers. For modeling specific to our contribution, such as a the mask model, we have taken care provide more detail in the appendix. Our adaptivity benchmarks, while our own design, are simple to implement (through padding and cropping) and our choices of how to transform the base public datasets described in the text. In addition, we have incorporated reviewers feedback in the camera ready version.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
27

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submit our codes and necessary command in a zip file. For the camera ready version, we have open sourced our code https:// github. com/ubc- systopia/ wwezzeddsmoottte smoothing/ teteeeeeaaaaee main.. The hyperparameter settings are listed in Table 4. The datasets used are cited and has open access the public..
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (kttps://nips.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cc/public/gus mublic/guides: /et.ddd///oeeeuumiiiie SoodeeubmissionPPP
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We detail our experimental setting at a high-level in Section and then elabo- rate in each subsection. We list our experimental setting in Section 4 and the hyperparameters in Table For baselines, we rely on the reference hyperparameter settings from the papers for Cohen al. (2019), rely code and dyper-parameter shared by the authors for Sūkeník et al. (2021) (the code not public), and tune hyper-paramette and / for Hong et al. (2022) (details in $C).
Guidelines:
The answer NA means that the paper does not include experiments.
28

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We ran all experiments end-to-end over three different seeds, and show both mean and standard deviation plots and tables (except ImageNet, for resources reasons). The factors of variability are those that are standard and natural to deep learning and robustness randomized smoothing: initialization of parameters, train-time sampling the data, train-time sampling of augmentations, and test-time sampling of noise for certification.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computing resources are included in Table 4. The resources are single
GPUs, which while required are sufficiently standard for this field as to be understandable and accessible.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: attps://neurips.. http:p////nurrpp..cppplblllcll.a http://ccccppppoceciicciicooeaea
Question:
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and confirm that conform to them in every respect when we conducted research the paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper improves the robustness existing machine learning models to adversarial examples. Adversarial examples have been proposed for a limited number of beneficial use cases, such as censorship or surveillance evasion, but overall more robust and trustworthy ML models can benefit the increasingly broad deployment of machine learning, including in security and safety-critical applications. As paper with a theoretical emphasis and empirical evaluation well-established benchmarks, this work does not have additional societal impact beyond the norm.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not have a high risk for misuse, given its theoretical portion on proofs for robustness, and empirical portion on the robustness evaluation standard image classifiers. As such no special safeguards needed.
30

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All papers, code, and assets, etc. have been properly cited in the paper. We make use of the the reference code provided by the eited papers by their authors. We make use of standard and existing datasets, and therefore do not collect or introduce additional assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URI..
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, phcode thcode. com dan/aatasess
has curated licenses for some datasets. Their licensing guide can help determine license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not collect or include new assets. To the extent that our own method code asset, it is the creation of the authors, and it is included anonymously and confidentially in our supplementary materials. accepted, the code will be released under open license such BSD-2.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
31

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "OzT6gTLgel", "reviewer": "Reviewer_NkYs", "summary": "The paper uses tools from differential privacy (f-DP relating privacy to hypothesis testing, and also compositional rule of DP) to design a differentially private  2-step mechanism. The first step is interpreted here as creating a mask, and the second step is the \"standard randomized smoothing\" on the masked input, so it potentially greatly reduces the dimensionality.", "questions": "-", "limitations": "-", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main result is Proposition 2.4, where it is shown that we can use two step randomized smoothing, where in the first step we effectively obtain a mask to mask out some of the input pixels, and by this effectivelly escaping the curse of dimensionality we have in randomized smoothing and the we use the standard smoothing on the masked input. The soundness is guaranteed by tools from differential privacy, framing the adversarial problem in the privacy language and use the standard (i suppose) tools to perform a private compositional test. The neighbouring databases (in the privacy sense) are formulated as $\\ell_\\infty$ distance in the image space, which exactly matches the setting of adversarial robustness (this was considered in the very first RS paper already that also took the DP approach to randomized smoothing).\n\nThe originality comes from bringing standard tools from a different field and demonstrates that they are effective here. Quality is high, the results and ideas are fresh and new in the field and improve on SotA. Clarity is somewhat good but not perfect, the authors seem to come from DP community (I'm from robustness) so It requires some effort and reading other papers for me to follow. Significance is on the higher end of the randomized smoothing papers in the recent years, the results might seem incremental on benchmarks, but the actual techniques are new so it will likely attract attention. The downside is not convincing empirical evaluation (is limited and in the standard settings the improvements are very mild, the main benefits are demonstrated on CELEBA benchmark), overall the empirical evaluation does not convince me that this approach outperforms SotA by a non-trivial margin. This being said, the work (mainly the tools used) is clearly interesting enough to be accepted.\n\n\n\n\nvery minor:\n* f-DP is not really introduced I think, the $f$ appears in prop 2.1 without any explanation, right?\n* unify Dong 2019 and Dong 2022 citations. I think they are the same?\n* \" adaptivity over multi-step computation comes with no increase in certified radius\" - no decrease?", "weaknesses": "^", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We will add a background section on f-DP in the appendix and forward reference it before Prop 2.1 to provide more context. We will unify the citations to prefer the published edition (2022) over the arXiv edition (2019). Thank you for catching our increase/decrease typo! It is indeed no decrease.\n\n> [...] in the standard settings the improvements are very mild, the main benefits are demonstrated on CELEBA benchmark) [...]\n> This being said, the work (mainly the tools used) is clearly interesting enough to be accepted\n\nIn the attached pdf, we provide further results for CIFAR-10 with no background and large background (to emphasize the importance of dimensionality). We investigated the degree of improvement on CIFAR-10, and found a pre-processing inconsistency between steps that led to suboptimal masks (this only affected CIFAR-10 experiments for ARS and no other results). Fixing this led to crisper masks, and improved performance at large $k$ (Figures 11b), where the results are now similar to those of CelebA. On ImageNet, we do not expect such gains as the relevant parts of the image are fairly large compared to the total dimensions. Please note the noise levels in these experiments follow the suggestion of Zvfp, and we will update all the paper results to these standard noise levels with evaluation across three seeds.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u69ecqBNTy", "reviewer": "Reviewer_7UWe", "summary": "This paper proposes a framework to derive robustness certificates for smoothed classifiers based on f-differential privacy (f-DP). The framework achieves the same tight certificate for Gaussian smoothed classifiers as Cohen et al. (2019), while enabling analysis of adaptive multi-step smoothing mechanisms using the adaptive composition theorem for f-DP. To demonstrate the framework, the authors design a two-step smoothing mechanism that effectively performs adaptive (input-dependent) dimension reduction to achieve robustness against $\\ell_\\infty$-bounded perturbations. Experiments on three datasets demonstrate substantial improvement over baselines in some cases.", "questions": "- To better understand the generality of the approach: can a certified radius be derived for a composition of heterogeneous f-DP mechanisms (not necessarily all Gaussian)?\n\n- Is there an intuitive explanation for the larger gap in certified accuracy between ARS and Cohen et al. for CelebA versus ImageNet? \n\n- Are results available for a non-uniform split of the noise budget (line 223)?", "limitations": "Yes, limitations are addressed adequately in Section 5.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Originality and significance:**\nThis paper reconnects randomized smoothing and differential privacy, showing that f-DP can achieve competitive robustness certificates. By identifying this connection, the paper could seed further innovations in randomized smoothing, where the design of smoothing mechanisms has been limited due to challenges in obtaining tractable robustness certificates. This has been a problem in prior work, where the analysis of smoothing mechanisms using input-dependent additive noise (e.g., Hong et al., 2022) were later shown to be unsound.\n\n**Quality:**\nThe technical foundation is strong, which is important for work that aims to achieve provable robustness. The experiments are solid, covering a range of settings, including those where the adaptive masking approach does not achieve a significant performance advantage (ImageNet). In some cases the improvement in certified accuracy/standard accuracy over baselines is quite significant (of order 10 percentage points).\n\n**Clarity:**\nThe paper was a pleasure to read.", "weaknesses": "The proposed adaptive masking smoothing mechanism does not achieve significant improvements in certified robustness over baselines in many cases, especially for CIFAR-10 (Fig 2) and ImageNet (Fig 6). There is a more pronounced improvement for CelebA, however I wonder if this is related to the fact that the masking model is trained under supervision or whether the masking smoothing mechanism is simply a better fit for CelebA? This could perhaps be investigated by repeating the experiment without using the mouth location metadata. \n\nGiven the (at times) marginal improvement of the adaptive masking smoothing mechanism, it would be interesting to understand how it compares along other dimensions, like computational efficiency and model size. It’s noted (line 324) that the mechanism is less efficient and uses a larger model, however it would be good to quantify to better understand the trade-offs.\n\nTheorem 2.3 applies for a composition of randomized Gaussian mechanisms, which may be limiting given the range of mechanisms studied in the DP literature. I expect the theorem could be adapted for other mechanisms, but I wonder whether this would result in a tractable radius?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We start by answering the main questions in the review and then address further comments.\n\n> Q1. “[...] can a certified radius be derived for a composition of heterogeneous f-DP mechanisms [...]?”\n\nThis is a great question! As noted in the review, the theory directly applies. However, there are two key elements to compute the bounds that are not necessarily trivial to get for general mechanisms: (1) the f-DP curve of a mechanism at any attack radius value r (to compute the sup line 471); (2) the composition of such curves across mechanisms (this is really easy for Gaussian mechanisms, but more challenging for other mechanisms even without heterogeneity).\n\nFortunately, the DP community already has several tools that one could leverage to explore this design space. Notable examples that we believe are promising include:\nUsing results from deep learning training with f-DP that study efficient composition of subsampled Gaussian mechanisms (https://arxiv.org/abs/1911.11607). This would help support steps that first subsample pixels and then apply the Gaussian mechanism (though some work is needed on the subsampling front).\nUsing numerical tools for f-DP curves and composition (e.g., https://arxiv.org/abs/2106.08567, https://arxiv.org/abs/2106.02848) to support more complex mechanisms and heterogeneous composition.\n\n> Q2. “Is there an intuitive explanation for the larger gap in certified accuracy between ARS and Cohen et al. for CelebA versus ImageNet?”\n\nWe would first like to address one possible reason suggested in the review:\n\n> “There is a more pronounced improvement for CelebA, however I wonder if this is related to the fact that the masking model is trained under supervision or whether the masking smoothing mechanism is simply a better fit for CelebA?”\n\nThank you for the great suggestion. We re-ran our CelebA experiments, but without supervision for the mask, and it turns out that the supervision was not needed. The results are essentially unchanged (if anything, the variance is lower due to better masks) and visually the masks are a bit better (likely because our supervision was a coarse, approximate bounding box around the mouth, while masks without supervision are more precise). Please see Fig. 8 and 9  in the rebuttal PDF attached to the global response.\n\nAs to why the results on CelebA are much better than on other tasks, we believe that it is because the CelebA task is very well suited to gains from dimension reduction, which our approach provides. Indeed, our task on CelebA has a fairly high input resolution for certification (160x160), while the relevant part for the prediction (the mouth) is often as small as 15x15. We can see in the mask images in the attachment that the mask model accurately selects the relevant mouth area, and the final image is much clearer at that position due to noise reduction from the lower dimension. \n\nWe investigated why we did not see similar improvements on CIFAR-10 with large $k$. We found a pre-processing inconsistency between our steps that led to suboptimal masks (this only affected CIFAR-10 experiments for ARS and no other results). Fixing this led to crisper masks, and improved performance (see Figures 11a for results with $k=64$ that lead to gains similar as those seen for CelebA). On ImageNet, we do not expect such gains as the images are more complex, and relevant parts of the image are fairly large compared to the total dimensions.\n\n> Q3. “Are results available for a non-uniform split of the noise budget (line 223)?”\n\nWe did not observe much gains from early experiments learning the split or using non-uniform splits, so we do not pursue this for this paper and do not have extensive results. However, it is plausible that more extensive tuning of this parameter can yield improvements, and it would be interesting to explore this avenue in more depth.\n\n> “It’s noted (line 324) that the mechanism is less efficient and uses a larger model, however it would be good to quantify to better understand the trade-offs.”\n\nWe provide some numbers on ll. 271-273 of the submission (the time overhead for certification compared to Cohen et. al. is about 2x). We will add more details on mask model size and impact on training time and resources in that paragraph and Appendix D.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WkE3QC9opx", "reviewer": "Reviewer_Zvfp", "summary": "This work presents the first sound composition of randomized smoothing. Based on the novel theoretical results, this work presents the first sound way to compose a mask generator with the Gaussian sampling required for randomized smoothing, thereby reducing the effective dimension and improves the certification of randomized smoothing. This work opens up the possibility of more complex compositions for randomized smoothing, which is attempted before without soundness and great success. To this end, this work serves a good milestone in the field of randomized smoothing.", "questions": "See weaknesses.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "This paper presents a great theoretical contribution to randomized smoothing, namely the composition rule. I did not find evident mistakes in the proof, but others might spot issues. If the theorems presented are correct, I recommend immediate acceptance, regardless of the experimental inadequacy that I will elaborate in the weaknesses section.\n\nThe experimental section presents three different benchmarks, characterizing different aspects. The results show the advantage of the proposed method. The $L_\\infty$ robustness of randomized smoothing is improved and depend less on the data dimension.", "weaknesses": "The main inadequacy I spot is its experimental design, specifically Section 4.3. While Section 4.1 and 4.2 are interesting and validates some of the claims made, Section 4.3 presents the main benchmark in the field of randomized smoothing. However, the authors only present the results on ImageNet with $\\sigma=0.5$, while the main practice in the feild is to report results on \\{cifar-10, ImageNet\\} times \\{$\\sigma=0.25, 0.5, 1.0$\\}. I request the authors to present the full benchmark for comparison.\n\nIn addition, to compare with Cohen et al., the masking trick could also be applied to certiify $L_2$ robustness. It is not clear why the authors only report $L_\\infty$ robustness in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We address the two main requests listed under weaknesses:\n\n>  the main practice in the field is to report results on {cifar-10, ImageNet} times {𝜎=0.25,0.5,1.0}\n> “I request the authors to present the full benchmark for comparison.”\n\nThank you for the suggestion. In the rebuttal PDF we report results for CIFAR-10 (Figures 10 & 11) and ImageNet (Figure 12) at these noise levels. We will update all the CIFAR-10 and ImageNet results in the paper to these standard noise levels with evaluation across three seeds. Due to time and computational constraints during the rebuttal phase we have run a single seed for ImageNet experiments.\n\nThe CIFAR-10 results include include standard CIFAR-10 (without backgrounds, k=32) and larger background images (k=64). As expected, our approach only yields modest gains on CIFAR-10 without backgrounds, as the mask cannot provide much dimension reduction (although we still see that the masks select relevant parts of the image). With large backgrounds, the improvements are larger as shown in Figure 11 (b). These rebuttal results are an improvement after finding and fixing a pre-processing inconsistency that led to suboptimal masks (this issue only affected ARS, on CIFAR-10, and no other results).\n\n> “In addition, to compare with Cohen et al., the masking trick could also be applied to certify 𝐿2 robustness. It is not clear why the authors only report 𝐿∞ robustness in the paper.”\n\nWhile the ARS theory (f-DP based RS and composition) applies to L2, our specific instantiation using masking applies only to 𝐿∞ robustness, in the sense that it implies no gains for L2 robustness. In particular, the reduction of the noise variance in the second step (Eq 6) is valid only against 𝐿∞ adversaries, and we would not be able to reduce noise this way for an L2 adversary (this is discussed in remark 3, ll. 177-181). Intuitively, this is because in the worst case, an L2 attack could be fully applied to pixels with a mask weight of 1, and so masking does not trigger noise reductions and our approach reduces to standard RS with two steps averaging the noise. This is a core reason why we do not present L2 results.\n\nThat being said, it is plausible that using multi-step composition, one could design architectures that improve L2 robustness (a potential avenue of research for that is to leverage the f-DP analysis of the subsampled Gaussian mechanism: https://arxiv.org/abs/1911.11607). This however would require significant design and analysis work, which is not yet explored, and in this submission we leave it for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "He6ofNCgoW", "reviewer": "Reviewer_FN7A", "summary": "The paper introduces Adaptive Randomized Smoothing (ARS), an innovative theoretical extension of Randomized Smoothing (RS) based on f-Differential Privacy (f-DP) to enhance the robustness certification of machine learning models. Empirical results demonstrate that ARS surpasses both standard RS and its variants in robustness certification metrics.\n\nThe authors present a solid theoretical framework and conduct thorough experimental evaluations. Despite ARS inheriting certain inherent constraints of RS, the method represents a significant advancement, offering a fresh approach to augment RS through budget decomposition.", "questions": "1. Does the theoretical framework extend to alternative norm types, such as L1 or L2 norms?", "limitations": "See weaknesses and questions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper is well-written and easy to follow.\n2. The theoretical underpinnings are solid: The integration of RS with f-DP and the subsequent decomposition leveraging f-DP properties is a creative and compelling strategy to refine RS.\n3. The implementation of a masking mechanism is judiciously chosen to tackle the dimensionality challenges highlighted by the theoretical discourse.", "weaknesses": "1. As an enhancement of RS, ARS is subject to the same fundamental limitations, notably the requirement for a substantial sample size to attain satisfactory robustness certification. The authors acknowledge this constraint within the limitations section of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We are happy to answer the question about alternative norms.\n\n> Does the theoretical framework extend to alternative norm types, such as L1 or L2 norms?\n\nWhile the ARS theory (f-DP based RS and composition) applies to other norms such as L1 or L2, our specific instantiation using masking applies only to 𝐿∞ robustness:\n\nFor L2: masking under the Gaussian mechanism implies no gains for L2 robustness directly. In particular, the reduction in the noise variance in the second step (Eq 6) is valid only against 𝐿∞ adversaries, and we would not be able to reduce noise this way for an L2 adversary (this is discussed in remark 3, ll. 177-181). Intuitively, this is because in the worst case, an L2 attack could be fully applied to pixels with a mask weight of 1, and so masking does not trigger noise reductions and our approach reduces to standard RS with two steps averaging the noise. This is a core reason why we do not present L2 results.\nFor L1: bounding L1 with L2 (as we do between 𝐿∞ and L2 in the paper) does not involve the input dimension d. As a result, masking also doesn’t enable noise reduction by dimensionality reduction.\n\nThat being said, it is plausible that by using multi-step composition, one could design architectures that improve robustness under other norms such as L1, L2, or L0. A potential avenue of research for L2 (that may apply to other norms as well) is to leverage the f-DP analysis of the subsampled Gaussian mechanism: https://arxiv.org/abs/1911.11607. This however would require significant design and analysis work, which is not yet explored, and in this submission we leave it for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all of the reviewers for their constructive reviews. We provide answers to questions in our review-wise responses, and we have completed experiments following the suggestions and requests that we include in the pdf attached to this global response.

Specifically:

- We provide CelebA experiments without mask supervision (reviewer 7UWe), and the results are as good (if not better, as the masks are sharper) than with our coarse mask supervision. See Figures 8 & 9 (the first two figures in the rebuttal pdf).
- For CIFAR-10, we investigated the degree of improvement, as highlighted by reviewers NkYs and 7UWe, and found a pre-processing inconsistency that led to suboptimal masks (this only affected ARS, on CIFAR-10 experiments, and no other results). Fixing this improves results both quantitatively and qualitatively. For $\sigma = 0.12, 0.5, 1.5$ and $k=48$ (bottom section in Table 1, last column), ARS standard certified accuracy (at $r=0$) improves to 83.66% from 82%, 66.6% from 64.8% and 35.5% from 34% with similar standard deviations as before. We also report results (masks and certified accuracy) for no background (k=32) and large background (k=64) to emphasize the importance of higher dimensionality. As expected, ARS provides real but modest gains in terms of certified accuracy on standard CIFAR-10 images (Figure 11a): the masks select relevant pixels, but dimensionality gains are small (Figure 10a). For $k=64$, the gains are much larger (Figures 11b), as the masks successfully ignore the high dimensional distractor background (Figure 10b).
- We provide results at the common noise levels of sigma = 0.25, 0.5, 1.0 (reviewer Zvfp) on CIFAR-10 (Figure 11), including without background (Figure 11a), and ImageNet (Figure 12). We will update all the paper results to these standard noise levels with evaluation across three seeds. Due to time and computational constraints during the rebuttal phase, we have run a single seed for ImageNet experiments.

Meta-review: This paper introduces a two-step method for providing robustness certificates of smoothed classifiers using tools from differential privacy (f-DP) for multi-step composition of the guarantees. The proposed framework uses adaptive dimension reduction to improve robustness guarantees. 

Certified robustness (CR) as a field began from connections to DP, and this paper returns to those roots. Reviewers found the ideas and tools to be very interesting, and their combinations to be novel. The reviewers also highlighted that the work was likely to spark the interest of CR researchers, which could lead to a broad impact on the subfield. I recommend that the authors add their discussion of alternative norms to the paper so that readers are clear of the limitations and avenues for future work.
Decision: Accept (spotlight)