Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing
Authors: Song Xia
Yi Yu
Xudong Jiang
Henghui Ding
Venue: ICLR 2024 poster (2024)
Keywords: Certified Robustness
DualRandomized Smoothing
Curse of Diemensionality.
Primary area: societal considerations including fairness, safety, privacy

Abstract: Randomized Smoothing (RS) has been proven a promising method for endowing an arbitrary image classifier with certified robustness. However, the substantial uncertainty inherent in the high-dimensional isotropic Gaussian noise imposes the curse of dimensionality on RS. Specifically, the upper bound of ${\ell_2}$ certified robustness radius provided by RS exhibits a diminishing trend with the expansion of the input dimension $d$, proportionally decreasing at a rate of $1/\sqrt{d}$. This paper explores the feasibility of providing ${\ell_2}$ certified robustness for high-dimensional input through the utilization of dual smoothing in the lower-dimensional space. The proposed Dual Randomized Smoothing (DRS) down-samples the input image into two sub-images and smooths the two sub-images in lower dimensions. Theoretically, we prove that DRS guarantees a tight ${\ell_2}$ certified robustness radius for the original input and reveal that DRS attains a superior upper bound on the ${\ell_2}$ robustness radius, which decreases proportionally at a rate of $(1/\sqrt m + 1/\sqrt n )$ with $m+n=d$. Extensive experiments demonstrate the generalizability and effectiveness of DRS, which exhibits a notable capability to integrate with established methodologies, yielding substantial improvements in both accuracy and ${\ell_2}$ certified robustness baselines of RS on the CIFAR-10 and ImageNet datasets. Code is available at https://github.com/xiasong0501/DRS.

Published as a conference paper at ICLR 2024
MITIGATING THE CURSE OF DIMENSIONALITY FOR CERTIFIED ROBUSTNESS VIA DUAL RANDOMIZED SMOOTHING
Song Xia
Yi Yu
Xudong Jiang"
Henghui Ding
Nanyang Technological University. Singapore
(xias0002, yuyi0010 exdjiang))ntuu.c edu. sg, henghui. dinggggmiiinnnnnn.. com
ABSTRACT
Randomized Smoothing (RS) has been proven promising method for endowing an arbitrary image classifier with certified robustness. However, the substantial uncertainty inherent in the high-dimensional isotropic Gaussian noise imposes the curse of dimensionality on RS. Specifically, the upper bound of le certified ro- bustness radius provided by RS exhibits diminishing trend with the expansion of the input dimension d, proportionally decreasing rate of 1/vd. This paper explores the fcasibility of providing & certified robustness for high- dige-diiensional input through the utilization of dual smoothing in the lower-dimensional space. The proposed Dual Randomized Smoothing (DRS) down-samples the input im- age into two sub-images and smooths the two sub-images in lower dimensions. Theoretically, we prove that DRS guarantees tight & certified robustness radius for the original input and reveal that DRS attains a superior upper bound on the l robustness radius, which decreases proportionally at a rate of (1//m+1/vD) with m + n d. Extensive experiments demonstrate the generalizability and effectiveness of DRS, which exhibits notable capability to integrate with es- tablished methodologies, yielding substantial improvements both accuracy and l certified robustness baselines of RS on the CIFAR-10 and ImageNet datasets. Code is available at hhttps:/githubb.com httpa//.....omiiaooooo0/////
INTRODUCTION
Deep neural networks have shown great potential for an ever-increasing range of complex applica-
tions
Yu et al. 2023 Wu et al.) 2024 Ding al. 2023b a Ju al. 2023 Luo al. 2023 Kong
ct al.
2022
While those models achieve commendable performance and manifest a capacity for
generalization within the distribution they trained on, they concurrently exhibit pronounced
vulnerability to adversarial examples (Biggio et al. 2013 Szegedy et al.) 2014]] Tramer et al. 2020) eu al. 2022). By adding small and human imperceptible perturbation to the image, the adver- sarial examples could mislead the well-trained deep neural network at a high success rate.
In response to these adversarial vulnerabilities, researchers have explored variety of methods to enhance the robustness of deep neural networks. The empirical defense method, e.g., adversarial training (Madry et al.) 2018 Ding al., 2019 Shafahi al. 2019 Sriramanan et al. [021 Cheng et al. 2023). bolsters model robustness through iterative training with adversarially generated ex- amples. However, this kind of empirical defense is not fully trustworthy. Many empirical defense approaches are later broken by more intricately crafted adversarial attacks (Carlini & Wagner 2017] Yuan et al. (00T Heeddrycks et al. 2202 Duan et al. 2021 [i al. 2023). This inspires researchers to develop methodologies capable of providing certified robustness, e.g., guaranteeing the classifier
to return a constant prediction result within a certain range (Raghunathan et al., 2018 Wong &
Kolter 2018 Hao et al. 2022 Kakizaki et al. 2023).
Randomized Smoothing (RS) has been proven a promising method to provide certified robustness for any kind of classifiers. Initially introduced by Lecuyer et al. (2019). RS is guaranteed with loose robustness boundary, and later Cohen et al. (009)) theoretically ly proves tight robustness boundary
Research lead and supervisor X Corresponding author (henghui.ding ding gmail.com)

---

Published as a conference paper at ICLR 2024
Avaraginng Pioel-wise addition
of certified radius
No ise
RS
DR5:m-n
Clessification
DR5:m=2n
Inpull x--Re
Partition
RS dimension to
Class
RS al dimension
Dimension
(a)
(h)
Figure 1: (a) The smoothing process of DRS. (b) The upper bound & certified radius (calculated
by Equation and Equation 15) of RS and DRS with a = 1/vd and smoothed probability = 0.999.
via the Neyman-Pearson lemma (Nyyman & Pearson 1933p. In Cohen al. (2019), ) by cornupting the original image with the isotropic Gaussian noise at the same dimension, RS turns any base clas- sifier into the smoothed one by predicting with the "majority vote" among the noised samples. The smoothed classifier is thereby assured to exhibit certified robustness to inputs characterized by con- fident classifications. Specifically, it has been substantiated that the smoothed classifier consistently produces unchanging classification outcome within predetermined range, typically & or foo ball centered around the original input. Meanwhile, RS does not necessitate any a prior assumptions regarding the parameters architectural configurations of classifiers, making it feasible provide certified robustness for most deep neural network models.
However, the high uncertainty caused by Gaussian noise not only decays the classification accuracy but also imposes the curse of dimensionality (Kumar et al. 2020 Wu et al. 2021), which makes the upper bound of &g certified radius provided by RS progressively diminishes at a rate of 1/vd. The predominant emphasis in existing research focuses on refining RS by training classifiers with enhanced capability of predicting corrupcd images, such as training the classifier with the Gaussian noise augmented images (Cohen et al. 22099), utilizing adversarial training (Salman al., 2019), adding an extra deep learning denoiser (Salman et al. 2020 Carlini et al., 2023)), and using model ensemble (Horváth et al. 2022).
While the aforementioned methods demonstrate notable performance gain by either fortifying the classifier or introducing extra denoising modules, they have not effectively addressed the inherent challenge of the curse of dimensionality arising from nigh-dimensional Gaussian noise. Conse- quently, the certified robustness provided by RS still continues to diminish fast with the increase of dimension d. To mitigate this, introduce novel smoothing mechanism termed Dual Ran- domized Smoothing (DRS). As illustrated in Figure T by partitioning the original d-dimensional input into two sub-inputs with lower dimensionality of m and n. DRS offers certified robustness for the original input through dual smoothing within the lower-dimensional space, and shows a more promising upper bound of & certified radius. To minimize the information loss caused by the par- tition of the input for the classification, this paper harnesses the spatial redundancy inherent in the image and partitions the input through image down- wwwn-sampinn with two predefined indexes. The key contributions of this paper can be summarized as follows:
We introduce a novel smoothing mechanism called Dual Randomized Smoothing (DRS). Theoretically, we prove capacity providing tight & certified robustness for the high- dimensional input via dual smoothing in the lower-dimensional space.
We demonstrate that DRS effectively mitigates the curse of dimensionality. DRS yields superior upper bound for fg robustness, characterized by slower rate of diminishment.
We develop the first implementation of DRS by partitioning the input based on the spatial redundancy of the image. Extensive experiments validate the generalizability and effec- tiveness of DRS. DRS can adeptly integrate with various existing methods, resulting in substantial enhancements to both the accuracy and the certified robustness baseline of RS.
RELATED WORK
Certified defense. Certified defense aims to guarantee that no adversarial example exists within a neighborhood of the input, often & or loo ball. Those methods typically either exact ('com- plete") or conservative ("sound but incomplete"). Exact methods will report whether there exists or not adversary near the data point to mislead the classifier, usually by mixed integer linear pro-
2

---

Published as a conference paper at ICLR 2024
gramming Lomuscio & Maganti 2017 Tjeng al. 2018) satisfiability modulo theories (Katz et al. 2017). J. However, those methods take a large number of computational resources thus being hard to transfer to large-scale neural networks (Tjeng et al. 2018). Conservative methods also certify there is an adversary existing, but they might decline to make a certification when the data resides in safe neighborhood. The advantage of such methods lies in the enhanced flexibility and reduced computational resource requirements (Wong & Kolter 2018 Wang et al., 2018). However, these methods either require specific network architecture (e.g., ReLu activation or layered feed-forward structure) or extensive customization for new architectures. Furthermore, none of them are shown to be feasible to provide defense for modern machine learning tasks such as ImageNet.
Randomized smoothing. Randomized Smoothing (RS) shows attractive proprieties in providing certified robustness for any classifier via noise smoothing. RS is first proposed by [ecuyer et al. (2019), which utilizes inequalities from the differential privacy literature to provide a loose fz or 2 robustness guarantee for the smoothed classifier. Later, [Cohen et al.) (2019) proves the tight robustness boundary for f2 norm adversary via the Jeyman-PPerson lemma, which guarantees much stronger certified robustness. However, the presence of high-dimensional Gaussian noise inevitably erodes the performance of the model. This phenomenon termed the curse of dimensionality was initially noted by Yang et al. (2020) and Kumar et al. (2020). which highlight that the upper bound of the certified radius of randomized smoothing will diminish as the input dimension increases. Wu let al. (2021) extends this observation to encompass a broader range of smoothing distributions, revealing that the lg certified radius of RS diminishes at a rate proportional to 1/vd.
The predominant focus of existing research lies in enhancing the perdition of the classifier under Gaussian noise corruption. Cohen et al. (2019) trains the classifier with input images augmented by Gaussian noise, and Salman et al. (2019) further enhances this by adversarial training. Zhai et al. (2019) proposes a loss function aiming to maximize the certified radius, and Jeong & Shin (2020) adds a consistency regularization facilitate the base classifier in producing more consistent predic- tions under Gaussian distribution. Alternatively, (Salman et al. (2020) utilizes a deep learning- denoiser to purify the corrupted image before classification, and Horváth et al. (2022) utilizes the model ensemble to reduce the overall prediction variance. Most recently, Carlinii et al. (2023) in-
troduces a potent denoiser founded on the diffusion model, representing a substantial advancement in noise mitigation that greatly enhances overall robustness. However, prior works have not ad- equately tackled the challenge of the curse of dimensionality in the context of high- high-dimensional inputs. (Sūkeník al. (2022) proves that the input-dependent RS also suffers from the curse of dimensionality and Pirommer et al.] (2023) proposes a projected randomized smoothing that en- hances the lower bound on the certified volume. Different from previous works, this paper first demonstrates the feasibility of providing l certified robustness for high-dimensional input via dual smoothing in the lower-dimensional space, thus effectively mitigating the disaster caused by dimen- sion expansion. Meanwhile, we theoretically prove DRS can provide tight &g certified robustness radius for the original digh-dimensional input via the lower dimensional smoothing. Additionally, we show that DRS achieves a more promising l2 robustness upper bound that decreases at rate of (1/vm=+ + 1//n) with m + n d.
3 PRELIMINARY
3.1 RANDOMIZED SMOOTHING
Consider a l classes classification problem with the input æ E Rd and the label y y {cI...., }. RS first corrupts each input x by adding the isotropic Gaussian noise (e; 0, I) Then it turns an arbitrary base classifier f into a smoothed version F that possesses &g certified robustness guarantees. The smoothed classifier F returns whichever the class the base classifier f is most likely to return among the distribution N + E; x. I)), which is defined as:
F(x)= arg max (f + c).
(1)
cEY
Theorem 1. (From (Cohen el al. ). let f: Rd + y be any deterministic or random function, and F be the smoothed version defined in Equation 7 Let ca and en be the most probable and runner-up classes returned by F with smoothed probability P and Pa respectively. Then F(x: +
8) = CA establishes for all adversarial perturbations ö, satisfying that 16 l2 I R', where
R'= f (p o (p()))
(2)
3

---

Published as a conference paper at ICLR 2024
In Equation c denotes the Gaussian Cumulative Distribution Function (CDF) and + signifies its inverse function. Theorem indicates that the &2 certified robustness provided by RS is closely linked to the base classifier's 's performance the Gaussian distribution: a more consistent prediction within a given Gaussian distribution will return a stronger certified robustness. The proof of Theo- rem can be found in the Appendix [A.]] It is not clear not how calculate PA and pa exactly if is a deep neural network. Thus Monte Carlo sampling is used to estimate the smoothed probability. This theorem also establishes when we assign PA with lower bound estimation PA and assign pB
with a upper bound estimation with pB 1 PA- Then the radius R' equals:
R' = 0 ( (pA))
(3)
Equation 3 establishes based on - (1 PA Φ (PA). The smoothed classifier F is guar- anteed to return the constant prediction сд around within the Eg ball of radius R'.
3.2 CURSE OF THE DIMENSIONALITY
While Randomized smoothing shows the intriguing property of providing certified robustness for arbitrary classifiers, it suffers from the curse of dimensionality due to high-dimensional noise cor- ruption (Kumar et al., 2020). This paper delves into the curse of dimensionality of the l certified robustness proposed by Wu et al./ (2021).
Proposition 1. (From (Wu et al. (. an arbitrary continuous and origin- wrigin-symmetric distribu- tion q, i.e., Vz, q(2) q(-2), ufilized in smoothing, the certified &g radius provided by randomized smoothing of an arbitrary d-dimensional input a is bounded by:
max P Pera (5(m c)
r(x)=
(4)
Vd
1-5-10
where ((r:4) = -1 J1 (z)dz dz is the probability mass of distribution g inside a la ball with
radius r and the parameter 5 10-7 is derived from a predefined error margin between the estimated probability and true probability over the symmmerey distribution. Proposition| indicates that the & certified radius provided by RS is limited by an upper bound with a constant multiplier of
1/vd and diminishes with the expansion of d. The detailed proof can be found in Wu et al. 2021)
4 CERTIFIED ROBUSTNESS VIA DUAL RANDOMIZED SMOOTHING
To mitigate the curse of dimensionality that makes the upper bound of certified robustness dimin- ish for high-dimensional input, we propose a new smoothing mechanism called Dual Randomized Smoothing (DRS). As shown in Figure I DRS provides certified robustness for arbitrary input æ by dual smoothing in the lower dimensional space. Consider an input E Rd, which can be partitioned into two spatially non-overlapping sub-inputs, denoted as x' E Rm and x' E R", where m + nn = d. Our DRS transforms any base classifier f into smoothed version g defined as:
g (x)
arg max (Ip +e') c) + (P (x" + +=") =)), nEy
(5)
where el and are the isotropic Gaussian noises with the mean 0 and the standard deviation that share the same dimension as æ! and x". g(xx) returns whichever the class f and fr are most likely to return by considering the expectation of the probabilities derived from the distributions N( + e'; of
and N(x" + ,"";"",o"")
Theorem 2. Let fr Ih + y and fr 12"" + y be arbitrary deterministic or random functions, and g be the smoothed version defined in Equation S Denote ca and eg as the most probable and
runner-up classes returned by g. Then g(æz + 5) = CA establishes for all adversarial perturbations
8 satisfying that |0112 < R, where:
R =
④ 3--1p0 (p') - (P') 24 V2
(9)) where p E'
(6)
In Equation 6 p¹ and p" are the smoothed probabilities returned by base classifier f and f and d-1 is the inverse of the Gaussian CDF. Theorem 2 indicates that the & certified robustness provided by DRS for the input is closely linked to the performance of base classifiers f and f sub-inputs x' and x"; the higher the consistency in predictions of f and f" within some specific Gaussian distributions, the greater the level of certified robustness the smoothed classifier g yields.
4

---

Published as a conference paper at ICLR 2024
Proof of Theorem 2 In Equation 5 the smoothed classifier bases its decision the average of smoothed classification probabilities for x' and x". Let p' represent the smoothed probability under the adversarial attack. To mislead the smoothed classifier g successfully, p' must fulfiil the condi- tion: p'a + P'B 2 p"aa + p'A- Let us consider the worst-case scenario for the classifiers under the adversarial attack, where the adversarial attack maximizes the increment in the smoothed probabil- ity of the runner-up class, equalizing it with the reduction in the smoothed probability of the most probable class. This leads to the following equations: p'A - -p'A = Ap', P'B F' -Ap', and
P'A P'A Ap", PB F' = Ap", where Ap represents the probability change.
Given that PB PA establishes for all scenarios, we can get that:
(PA) Φ (p^ Ap) < . (pn + Ap) x (pn).
(7)
Thus, according to Theorem 1 and Equation 7 to successfully mislead the smoothed classifier g. the adversarial perturbation 8' and 8 added in x' and x" must fulfill that:
||8|| 1| 2 ( (P'x) + - (p%) 4 (1's) - (P')))
(8)
Equation establishes based on using RS to calculate the certified radius in each sub-image. Addi- tional details regarding the derivation of Equation ( and Equation 8 can be found in Appendix A..
Assume the critical condition of misleading g is achieved, where p B + +p' p'A +p get:
We can
pdA + p
i 1.
(9)
Utilizing Equation 9 we can demonstrate that the final two terms in Equation fulfill that:
+ (v' - (1")) +-
x
v'a)
(10)
and the maximum of Equation
10 is achieved when p"A = -p" = 2 due to S 1. So we get:
6 111 + ||0'| 1l2 2 (4 ( (P'A) + (vx) - 24 { =
(11)
where s is a constant if we get the exact value of the smoothed probability of the most probable and runner-up classes from f' and f". Since x' and x" are spatially non-overlapping, the overall adversarial perturbation 8 added in the original input æ must satisfying the condition:
|b||2 = / 18'1 11
(12)
The proof is concluded we take the lower bound of Equation 12 as the lg certified robustness provided by DRS.
Theorem also establishes when give the lower bound estimation p'a and p'a along with the upper
bound estimation p/g - Pla and PBB = 1 - p'A- Then the lg certified radius R of DRS is:
(-11 p/ R= v2
$ 1-1 D'A )AA
(13)
The following of this paper mainly considers the radius defined in Equation 13 as the bg certified radius provided by DRS for the fair comparison with RS.
4.1 ANALYSIS OF THE UPPER BOUND LIMITATION
Assume both RS and DRS take the lower bound estimation for PA and the upper bound estimation for Pg. pg. We
get the relationship of &g certified robustness of input w between DRS and RS as follows::
R₂
/2 (R' + RR )r)
(14)
Thus the &g certified radius provided by DRS of an arbitrary d-dimensional input æ is bounded by: (f (o"))))))
max Pel CEN
+ 5 max Per wn (f" (a""+=))=))
(w)) < where + d. This signifies that compared with RS, the DRS, which employs smoothing within the liver-dimensional space, exhibits a significantly more favorable upper bound for l certified radius, which is proportional reduction in the rate by (1/vm- 1/vn).
5
CEN
("), (15)
2m
1-5+10-
22n
5--10-
5

---

Published as a conference paper at ICLR 2024
SampleUnneeroosee
Noise
o0,
LowerConfBound
Down sample
Sampling
Inputx
Classiter
Estimate lower bound probability
Interpolation
Interpalation
Classiter
Estimate lower bound probability
2x2 pixe!
..iinde.....
Sampling
Noise e" ~ NO
Figure 2: The implementation of Dual Randomized Smoothing (DRS). The image is down-sampled into two conerllaapping sub-images by utilizing two predefined 2x2 pixel indexes.
Algorithm Prediction and l2 certified robustness radius of DRS
1: Input: base classifiers {f', f noise standard deviation image æ, index idx, sampling times ni and n, confidence level
2: x', x² Downsample(x; idx)
3: count0', "rundd"'cound00" coond0" <- SungleeUnderrooisstt . a', x", n ČA,CB + top two index in (countO' count0r)
5: count", ,count" <- nnder (', "", ,'',,''"e" ut,aa x², .1;
6: P'AP'A LowerCon [Bound(counde [2x], countt" [Ra], m, a)
if p/ + 2 return prediction é and radius V2 --1
else return ABSTAIN
4.2 IMPLEMENTATION OF DUAL RANDOMIZED SMOOTHING USING SPATIAL REDUNDANCY
We implement our dual randomized smoothing as shown in Figure 2 Considering the high infor- mation redundancy of adjacent pixels in the image, we utilize two 2 2 pixel-index matrices as the down-sampling kernels. The two sub-images are generated by sliding the two kernels across the original image, as depicted
Figure 2 Each kernel selectively retains pixels along one of the two diagonals within the 2 x 2 image block, moving with stride of 2. This down-sample approach ensures that the sub-images uphold a significant portion information from æ for classification.
After partition, we first corrupt each sub-image by adding the isotropic Gaussian noise with zero mean and standard deviation of a. To facilitate fast adaptation for models that are pre-trained on the original images, we employ interpolation to resize the noise-corrupted sub-images to the same spatial resolution as the original image x. Then we utilize Algorithm to estimate the lower bound probability and calculate the certified robustness. The function SampleU Comnppeeenerrrra oise samples set of n perturre images and counts the number of samples assigned to each respective class. The function LowerCon on Bound provides binomial estimate of the lower bound probability, relying on the number of correctly classified samples counl(č.) out of a total of n samples, with confidence of a. More details about the sampling and estimation function can be found in Appendix A.66)
5 EXPERIMENT RESULT
5.1 EXPERIMENT SETUP
Evaluation details. Consistent with the prior work, we evaluate the proposed DRS on the CIFAR- 10 (Krizhessky & Hinton 2009) and ImageNet (Deng et al. 2009) datasets. We report the certified accuracy at each predetermined radius r, meaning the percentage of samples that are correctly clas- sified and guaranteed with certified radius larger than r. Moreover, we report the Average Certified Radius (ACR), calculated by averaging the certified radius among all correctly classified samples. We compare the performance of our DRS with RS under different training strategies delicately designed for RS. including Gaussian augmentation (Cohen et al.] (019). consistency regulariza- tion (Jeong & Shin 2020), and diffusion-denoising (Carlini et al. 2023). We also consider the
performance of using SmoothAdv (Salman et al. 2019) and Boosting (Horváth et al., (022) for a more comprehensive comparison.

---

Published as a conference paper at ICLR 2024
Table 1: The comparison results of RS and DRS on CIFAR-IO. The best performance under each training strategy is bold. We evaluate RS and DRS under two noise levels and report the best result.
Certified accuracy at predetermined & radius r (%)
Dataset
Training strategy
Smoothing
0.00
0.25
0.50
0.75
1.00
1.25
1.50
2.00
RS
(..25,0.50)
76.2
60.5
42.4
33.0
22.2
14.9
9.9
Gaussian
DRS
00.18,
83,4
65.8
50.2
34.5
24.7
15.8
10.5
DRS
(0.25,0.50)
78.1
62.5
48.7
35.8
24.5
17.9
12.9
4.6
RS
{0.25, 0.50)
75.5
67.1
57.2
47.7
36.3
29.7
25.0
CIFAR-IO
Consistency
DRS
{0.18, 0.366
77.8
70.2
59.2
47.8
37.2
31.8
26.7
DRS
(0.25, 0.50)
72.5
64.7
56.6
47.1
38.6
29.2
24.1
17.4
RS
(.52)
83.3
72.1
57.8
44.3
31.8
24.6
18.9
Diffusion-
DRS
{0.18, 0.36)
86.7
77.6
63.1
50.6
42.4
33.7
24.8
denoising
DRS
{0.25, 0.50
85.6
77.5
67.9
56.7
42.1
35.8
29.8
21.1
Table 2: The comparison results of RS and DRS on ImageNet. The best performance under each training strategy is bold. We evaluate RS and DRS under two noise levels and report the best result.
Certified accuracy predetermined & radius r (%)
Dataset
Training strategy
Smoothing
0.00
0.25
0.50
0.75
1.00
1.25
1,50
2.00
RS
{0.25, 0.50
67.0
58.6
48.4
42.6
38.0
32.4
28.4
Gaussian
DRS
{0.18, 0.36)
70.6
61.0
52.0
42.8
38.4
32.6
25.4
DRS
{0.25, 0.50
67.6
58.2
49.6
42.8
35.6
33.2
29.8
21.0
RS
{0.25, 0.50
64.8
58.9
54.0
48.8 8
42.2
36.7
35.0
ImageNet
Consistency
{0.18, 0.36
69.2
61.6
58.4
49.0
44.1
38.4
35.2
{0.25, 0.50
64.8
57.3
44.6
41.3
39.6
37.9
36.6
29.0
RS
{0.25, 0.50
66.8
56.4
46.2
38.0
31.2
27.6
24.4
Diffusion-
DRS
{0.18, 0.36)
68.2
59.6
53.4
49.0
38.0
33.4
32.0
denoising
DRS
{0.25, 0.50
65.4
58.2
52.0
45.8
41.0
33.6
28.8
24.4
Implementation details. Following (Cohen et al.)
2019
Shin 2020) Horváth al.) [022).
we utilize the ResNet 110 (He et al., (016) and ResNet 50 as base classifiers for CIFAR- and ImageNet under all utilized training strategies. For the diffusion-denoisiie 2023), use the same model provided by (Nichol & Dhariwal] 202I): a 50M-parameter model on CIFAR-10 and 352M-paraeeter class unconditional diffusion model on ImageNet. We re-ensemble the noise-corrupted sub-images for more effective denoising, based on that the adversarial perturba- tion designed for the classifier has a minor influence on the noise prediction of the diffusion model. For RS, we consider the model trained under Gaussian noise with a E {0.25, 0.50) to get the highest certified accuracy at each predetermined radius For DRS that gets /2 improvement in certified dius when A P'A = PA, we test its performance under the Gaussian noise with a E {0.18, 0.36} J. We report the best performance separately for more comprehensive and fair comparison. Due to the high computational cost of estimating the smoothed probability, we get our results by evaluating every 5th image on CIFAR- 10 and every 100 image on ImageNet. We set the number of samples no 100, = 100, 000, and the estimation confidence parameter 0.001, meaning that we sample 100, 000 times from the Gaussian distribution to estimate the expectation of the probability and derive the lower bound with the confidence 1
method (Carlini et al.
and {0.25, 0.50).
comparby
Training details. For each training strategy, we use the same pre-train model for both low- dimensional classifiers and fine-tune them using the same training strategy as RS. For consistency training, we set the hyperparameter À that controls the weight of consistency loss equal to 10 for both DRS and RS. On CIFAR-10, we fine-tuned all models for total of 40 epochs using the Adam (Kingma & Ba 2014) optimizer with an initial learning rate at le and decaying 0.1 at epochs 25 and 35. On ImageNet, fine-tuned the model for total of 15 epochs using the Adam optimizer with an initial learning rate at 1e-5 and decaying 0.1 at epochs 5 and 10.
5.2 THE CERTIFIED ACCURACY AT PREDETERMINED RADIUS
We present the comparison results between DRS and RS under the training strategies namely Gaussian augmentation (Cohen et al. 2019) consistency regularization (Jeong & Shin 2020). and

---

Published as a conference paper at ICLR 2024
Table The performance of an identical model using Gaussian augmentation and consistency train- ing strategies on the CIFAR-I0 1- dataset.
(a) Gaussian
(b) Consistency
Smoothing
Accuracy (%)
ACR
Smoothing
Accuracy (%)
ACR
RS
0.25
76.2
0.43
RS
0.25
75.5
0,55
DRS
0.18
83.4
0.50
DRS
0.18
77.8
0.57
DRS
0.25
78.1
0.56
DRS
0.25
72.5
0.67
RS
0.50
66.4
0.54
RS
0.50
64.3
0.74
DRS
0.36
70.8
0.58
DRS
0.36
64.8
0.77
DRS
0,50
64.4
0.60
DRS
0,50
55.3
0.81
80
Accuracy
80
Accuracy
75
75
70
RS-Gaussian
RS-consistency
DRS-Gaussian
65
DRS-consistency
65
0.3
0.4
0.5
0.6
0.3
0.4
0.5
0.6
0.7
0.8
ACR
ACR
(a) Gaussian
(b) Consistency
Figure 3: The accuracy and robustness trade-off curve of RS and DRS on CIFAR-10 dataset. The data collected by training multiple models using noise with a E [0.07, 0.7]. We this curve by second-order polynomial function.
duffusion-denoising (Carlini et al. 2023) on the CIFAR-10 and ImageNet in Table and Table The results consistently demonstrate that DRS significantly outperforms RS in terms of certified accuracy across all radius r. Specifically, on the CIFAR-10 10 dataset, DRS achieves the most substan- tial gain in certified accuracy at r 0.50, resulting improvements of approximately 7.8%, 2.0%. and 10.1 % when integrated with the three aforementioned methods. On the ImageNet dataset, DRS using the three strategies exhibits the most substantial certified accuracy gain at 0.5, leading to enhancements of accuracy by approximately 3.6%, 4.4%, and 7.2%.
Furthermore, our investigation reveals that DRS, employing noise levels of {0.18, 0.36), attains the best improvement in certified accuracy across all certified radius r. This is attributed to that our DRS guarantees higher bound of the certified radius using the same level a, allowing the classifier to maintain its robustness with reduced level of noise corruption. While increasing the noise level to (0.25, 0.50) causes a slight drop in the certified accuracy due to the inherent trade-off between accuracy and robustness, it guarantees much better certified accuracy for large Eg radius, e.g., r = 2.00, Ieading to an overall higher average certified robustness.
5.3 ANALYSIS OF THE ACCURACY AND ROBUSTNESS TRADE-OFF OFF BETWEEN RS AND DRS
Whether a fundamental trade-off between accuracy and robustness exists in deep learning models is an active open question. This subsection discusses this trade-off between RS and DRS by reporting the Average Certified Radius (ACR) and the certified accuracy at r the measure of overall ro- bustness and classification accuracy. We investigate this trade-off in both RS and DRS by examining the performance of an identical model across various noise levels.
We show the classification accuracy and ACR of models trained with Gaussian and consistency reg- ularization on both the CIFAR- 10 and ImageNet datasets in Table and that, in comparison to RS, our DRS consistently increases the classification accuracy significantly while simultaneously improving or preserving the ACR under noise with o = 0.18 or 0.36. When increasing the noise's standard deviation to 0.25 or 0.50, the DRS significantly improves the ACR but experiences an accuracy drop at o = 0.50. We attribute this phenomenon to the high level of noise compromising the utility of the information and subsequently hindering the effective feature
and Table 4 The results reveal
8

---

Published as a conference paper at ICLR 2024
Table The performance of an identical model using Gaussian augmentation and consistency train- ing strategies on the ImageNet dataset.
(a) Gaussian
(b) Consistency
Smoothing
Accuracy (%)
ACR
Smoothing
Accuracy (%)
ACR
RS
0.25
67.0
0.48
RS
0.25
64.8
0,52
DRS
0.18
70.6
0.51
DRS
0.18
69.2
0.53
DRS
0.25
67.6
0.62
DRS
0.25
64.8
0.64
RS
0.50
57.2
0.73
RS
0.50
56.0
0.79
DRS
0.36
61.6
0.73
DRS
0.36
59.2
0.80
DRS
0,50
54.0
0.84
DRS
0,50
54.0
0.84
Table 5: The performance of boosting DRS by model ensemble on the CIFAR-10 dataset.
Certified accuracy predetermined & radius (%)
σ
Training strategy
model ensemble
0.00
0.25
0.50
0.75
83.4
65.8
50.2
34.5
0.50
Gaussian
84.7
68.8
54.6
38.6
0.53
0.18
77.8
70.2
59.2
47.8
0.57
consistency
2
78.0
70.5
61.9
51.3
0.60
75.5
69.1
56.8
45.3
0.55
smoothadv
2
76.1
70.0
59.4
47.5
0.57
learning of the base classifier. To give more straightforward and comprehensive comparison of the accuracy-robustness trade-off inherent in DRS and RS, we trained multiple models on the CIFAR- 10 dataset using noise levels with [0.07, 0.7]. Figure presents the curve that depicts the trend of accuracy and ACR across models under DRS and RS using various noise levels. Our results il- lustrate that the proposed DRS consistently enhances certified accuracy and the robustness baseline provided by RS, ultimately achieving a superior robuustess trade-off.
5.4 BooST DRS BY MODEL ENSEMBLE
Horváth et al. (2022) has demonstrated that the performance of Randomized Smoothing (RS) can be enhanced through model ensemble techniques, which mitigate prediction variance by aggregating decisions from a larger ensemble of models. we apply this boosting approach to DRS by creating en- sembles of two models, employing noise with 0.18 on the CIFAR-10 dataset. Table []ble(3show,, shows the performance of the boosted DRS using training strategies of Gaussian, consistency, and Smoothadv, indicating that this boosting method can seamlessly integrate with our DRS, and effectively enhance the certified accuracy and average certified robustness.
CONCLUSION
The curse of dimensionality leads the diminishing in the & certified robustness provided by Randomized Smoothing (RS) rate of 1/vd, with d representing the dimension of the input image. To mitigate it, this paper explores the feasibility of providing l certified robustness for high-dimensional inputs via dual smoothing in the lower-dimensional space. Then novel smooth- ing mechanism called Dual Randomized Smoothing (DRS) is proposed, which provides a tight & certified robustness and yields superior upper bound for l robustness. By initially down-sampling the input image into two sub-images, DRS preserves the majority of the input image's 's information within the low-dimensional data thanks to the information redundancy of the neighboring pixels in most images. Theoretically, we prove a tight l certified robustness radius for the proposed DRS and demonstrate that DRS achieves a more promising robustness upper bound that decreases at the rate of (1/ + 1/ 1/)r),, where
d. Experimentally. we find that DRS effectively integrate with existing methods designed for RS and consistently outperforms RS in terms both the accuracy and & certified robustness the CIFAR-10 10 and ImageNet datasets.

---

Published as a conference paper at ICLR 2024
REFERENCES
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smnić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. Joint European conference on machine learning and knowledge discovery in databases, 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE symposium on security and privacy, 2017.
Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslic Rice, Mingjie Sun, and Zico Kolter. (certified!!) adversarial robustness for free! In Proc. Int'l Conf. Learning Repre- sentations, 2023.
Zhiyuan Cheng, James Chenhao Liang. Guanhong Tao, Dongfang Liu, and Xiangyu Zhang. Adver- sarial training of self-supervised monocular depth estimation against physical-word world attacks. In Proc. Int'l Conf. Learning Representations, 2023.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Proc. Int'l Conf. Machine Learning, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, 2009.
Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma training: Direct input space margin maximization through adversarial training. In Proc. Int'l Conf. Learning Representations, 2019.
Henghui Ding, Chang Liu, Shuting He, Xudong Jiang, and Chen Change Loy. MeViS: A large-scale benchmark for video segmentation with motion expressions. In Proc. IEEE Int'l Conf. Computer Vision, 2023a.
Henghui Ding, Chang Liu, Shuting He, Xudong Jiang, Philip HS Torr, and Song Bai. MOSE: A new dataset for video object segmentation in complex scenes. In Proc. IEEE Int'l Conf. Computer Vision, 2023b.
Henghui Ding, Chang Liu, Suchen Wang, and Xudong Jiang. VLT: Vision-language transformer and query generation for referring segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2023c.
Ranjie Duan, Yuefeng Chen, Dantong Niu. Yun Yang, A Kai Qin, and Yuan He. Advdrop: Ad- versarial attack to dnns by dropping information. In Proc. IEEE Int'l Conf. Computer Vision, 2021.
Zhongkai Hao, Chengyang Ying, Yinpeng Dong, Hang Su, Jian Song, and Jun Zhu. Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing. In Proc. Int'l Conf. Machine Learning, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. IEEE Int' I Conf. Computer Vision and Pattern Recognition, 2016.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, 2021.
Miklós Horváth, Mark Niklas Mueller, Mare Fischer, and Martin Vechev. Boosting randomized
smoothing with variance reduced classifiers. In Proc. Int'l Conf. Learning Representations, 2022.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. In Proc. Annual Conf. Neural Information Processing Systems, 2020.
Yakun Ju, Boxin Shi, Yang Chen, Huiyu Zhou, Junyu Dong, and Kin-Man Lam. Gr-psn: Learning to estimate surface normal and reconstruct photometric stereo images. IEEE Trans. on Visualization and Computer Graphics, 2023.
10

---

Published as a conference paper at ICLR 2024
Kazuya Kakizaki, Kazuto Fukuchi, and Jun Sakuma. Certified defense for content based image retrieval. In Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, pp. 4561-4570, 2023.
Guy Katz, Clark Barrett David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International conference on computer aided verification, 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1eXiv:1412.6980 2014.
Chenqi Kong, Baoliang Chen, Haoliang Li, Shiqi Wang, Anderson Rocha, and Sam Kwong. Detect and locate: Exposing face manipulation by semantic-and noise-level telltales. IEEE Trans. on Information Forensics and Security, 2022.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Mas- ter's s thesis, University of Tront, 2009.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In Proc. Int'l Conf. Machine Learning. 2020.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, 2019.
Qizhang Li, Yiwen Guo, Wangmeng Zuo, and Hao Chen. Making substitute models more bayesian can enhance transferability of adversarial examples. In Proc. Int'l Conf. Learning Representa- lions, 2023.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arXiv:1706.07351 2017.
Anwei Luo, Chenqi Kong, Jiwu Huang, Yongjian Hu, Xiangui Kang, and Alex C Kot. Beyond the prior forgery knowledge: Mining critical clues for general face forgery detection. IEEE Trans. on Information Forensics and Security, 2023.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In Proc. Int'l Conf. Learning Rep- resentations, 2018
Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 1933.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In Proc. Int'l Conf. Machine Learning, 2021.
Samuel Pfrommer, Brendon G. Anderson, and Somayeh Sojoudi. Projected randomized smoothing for certified adversarial robustness. Transactions on Machine Learning Research, 2023.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In Proc. Int'l I Conf. Learning Representations, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Proc. Annual Conf. Neural Information Processing Systems, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. Proc. Annual Conf. Neural Information Processing Systems, 2020.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Proc. Annual Conf. Neural Information Processing Systems, 2019.

---

Published as a conference paper at ICLR 2024
Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj, et al. Towards efficient and effective adver- sarial training. In Proc. Anmual Conf. Neural Information Processing Systems, 2021.
Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input- dependent randomized smoothing. In Proc. Int'l Conf. Machine Learning, 2022.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In Proc. Int'l Conf. Learning Representations, 2014.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In Proc. Int'l Conf. Learning Representations, 2018.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Proc. Annual Conf. Neural Information Processing Systems, 2020.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Proc. Annual Conf. Neurul Information Processing Systems, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proc. Int'l Conf. Machine Learning. 2018.
Jianzong Wu, Xiangtai Li, Shilin Xu, Haobo Yuan, Henghui Ding, Yibo Yang, Xia Li, Jiangning Zhang, Yunhai Tong, Xudong Jiang, Bernard Ghanem, and Dacheng Tao. Towards open vocabu- lary learning: A survey. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2024.
Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions. In International Conference on Artificial Intelligence and Statistics, 2021.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. In Proc. Int'l Conf. Learning Representations, 2020.
Yi Yu, Wenhan Yang, Yap-Peng Tan, and Alex C Kot. Towards robust rain removal against adversar- ial attacks: comprehensive benchmark analysis and beyond. In Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, pp. 6013-6022 2022.
Yi Yu, Yufei Wang. Wenhan Yang, Shijian Lu, Yap-Peng Tan, and Alex C Kot. Backdoor attacks against deep image compression via adaptive frequency trigger. In Proc. IEEE Int'l Conf. Com- puter Vision and Pattern Recognition, pp. 12250-12259, 2023.
Zheng Yuan, Jie Zhang, Yunpei Jia, Chuanqi Tan, Tao Xue, and Shiguang Shan. Meta gradient adversarial attack. In Proc. IEEE Inl'l I Conf. Computer Vision, 2021.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-fres free and scalable robust training via maximizing certified radius. In Proc. Int" I Conf. Learning Representations, 2019.
12

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1 PROOF OF THEOREM 1
In this subsection, we give the proof of Theorem version f as:
Assume f 12d + [0, 1] and define the smoothed
f(x)
E c~N(0.1)
[f( + +)] (2mjerz Ja f (x + E) exp (-11l=11² de.
(16)
Lemma 1. (Derived from Salman et al.
2019)). for any function f Rd - [0, 1}, subject to the constraint that f(x)e = P, then μ Vf(x). I V2n ( ) any unit direction p..
Lemma points out that the upper bound of the gradient of the smoothed classifier f is limited by ( (p))
(p)))) Let and cg be the most probable and the rumner-up classes with probabilities PA and pg. So, for any & nosm-based adversarial perturbation ô that successfully establish:
mislead the smoothed classifier f, resulting in f (xc 5) 2 fA(w + 8),
|| 2 2
1
exp(
( (1-)
dp+ 1
exp( _
( (8-1())))) dp
2m
pn 2
1 PA
1
exp(
- 1
-2
1 (p))
dp
2 2
2T
2
PB
1
(p)
2
( 1 (Px) $ (p-)),
2
(17)
which concludes the proof of Theorem
1
The detailed proof of lemma I can be found in Salman
al. 2019)
A.2
PROOF OF THE EQUATION 7 AND EQUATION
For Equation 7 as we have क (p) - (1 p). we get:
(pB + Ap) -1 (pB) = 1 (1 pB) -1 (1 PB Ap)
(18)
Because PB 2 PA and we have /b (p) is convex function for porp- E [0, 1]. assume function
fulfills that:
h (p) Φ- (p) - क (p Ap), where Ap E [0, we have the first-order derivative / (p) > 0 establishes for all scenarios. Thus we get:
(19)
Φ Φ (1 pB) Φb (1 PB Ap) + (pA) - --1 1 ( Ap),
(20)
which concludes the proof of Equation 7 For Equation g to make the smoothed probability
increases to f'y after adding adversarial perturbation 6, using Lemma we have:
|0||2 -- (1/) - (FB) > Φ (PA) (ya)-
(21)
Consider the worst case where Pn a. the adversarial perturbations added in each sub-image fulfill that:
1 1100 = क - サ-'("")) - -- (p'z) ক (p-1(pb)
(22)
= - - + क (PT) - (p"(a") - Φ (1D'a)
which conclude the proof of Equation
13

---

Published as a conference paper at ICLR 2024
Visualized target function 6-1.50
Visualized target function for k=
0.000
2.0
p 1.00
0.075
- 0.95
I 0.90
15
Fundion Welee
Function Value
10
1.0
Saddle point w5 50, p
0.000
-0.5
-1.0
Minima 48-45
Minima p0
0.0
Minima -0.50
02 04 05 06 07
-0.075
0.0
0.4
1.0
-0100
(a)
(b)
Figure 4: (a) The visualized landscape of objective function for h 2 across various p. (b)The visualized landscape of objective function for hs = 3 with P = 1.50.
A.3 ANALYSIS OF K- P-PARIITIONING BASED SMOOTHING
Section 4.1 illustrates that dual smoothing in the lower-dimensional space effectively mitigates the curse of dimensionality. This section explores the feasibility of further enlarging the certified ro- bustness upper bound by k-partitioning based smoothing.
Consider input x Rdd which be partitioned into l spatially non-overlapping sub-inputs,
denoted as x E R4, where Σ dg d. The k-partitioning based smoothing transforms any f=1
classifier f into a smoothed version y defined as:
g(x)
arg max cE
( + =),
(23)
where e is the isotropic Gaussian noises with the mean 0 and the standard deviation that share the same dimension as æ!. Denote and eg as the most probable and runner-up classes returned by g. Assuming p' is the smoothed probability returned by the base classifier f and 8 is the adversarial perturbation adding in sub-input x², To mislead the smoothed classifier successfully, according to Equation 17 the adversarial perturbation 8 added each sub-input x must fulfill:
[81|/2 2 a
(PA)) Φ (p%))) Vj fl....,k, k.
(24)
Thus the sum of the 8 fulfills:
Σ 1 2
(P') - Φ- -D-((")))
(25)
where pd represents the smoothed probability under the adversarial attack and satisfies that P' In Equation 25 P is a constant value that can estimated
z
p and Σ p - - ( -
by n sampling. Thus calculating the certified robusiness of smoothed classifier can be turned into solving the optimization problem defined as:
min 2
Σ
Φ
(D%)
j=1
k Σ
k
(26)
2 Σ
(p)) + P2),
s.t.
j=1
j=1
p
Vje [1....,kk k}.
14

---

Published as a conference paper at ICLR 2024
However, due to being non-convex, the above problem is not typical convex optimization.
For k denote:
p p= - Ph
1,
(27)
where ý represents the sum of the average probability between the most probable class CA and the runner-up class CB. According to the first constraint in Equation 26 we can
derive that p²A = p') Meanwhile, Φ-1 (p'a
1 (1 (1-v'a) establishes for
plA [0, 1]. Thus, the above objective function can be transformed into:
min
T
( (1'a+1 7)
+
(28)
This The objective function Equation 28 is a convex function with global minimum achieved by p²AA - 1/2 P.
For l: > 2, denote:
k
pB)
The objective function is non-convex. Providing a numerically stable solution for the global minimum under these circumstances is challenging (the minimum might exist). A saddle point achieved by:
D'A p/k, Vj (k.
(30)
The landscape of objective function for k and k 3 is visualized in Figure 4 for more straightforward comparison and illustration.
15

---

Published as a conference paper at ICLR 2024
Visualized target function for n=0.5
Visualized target function for n=
1.00
#=0000
0 0.90
1.
0 0.50
0.50
Function Value
Function Volee
3
0.5
NNrrima P1.70
0.0
00.0.8
_Mnnmma]]--.1
Minima 00.06
-1.0
Minima 00
Minima =0.01
0.
0.2
0.4
0.6
0.8
10
0.0
0.2
0.4
0.6
0.3
1.0
P1
(a)
(b)
Figure 5: The visualized landscape of objective function and for smoothing with different variances.
For symmetric cases where 17 2 and r 0.5, the sum of the optimal p" A is p.
A.4 ANALYSIS OF SMOOTHING WITH DIFFERENT VARIANCE
This subsection discusses the feasibility of using Gaussian noise with different variances to smooth the sub-images in DRS. Consider an input æ R4, which can be partitioned into two spatially non- overlapping sub-inputs, denoted as x' R and x" R". Define the smoothed classifier g same as in Equation 5 while s' and s" are the isotropic Gaussian noises with the mean 0 and the standard deviation o' and o". According Equation 24 and 25 to mislead g successfully, the adversarial perturbation 5 must fulfill:
88 1 2 d ( (2)) (D'a) + o" (2 ( 10----160 - (p')))
x-
(31)
where p', A represents the smoothed probability under the adversarial attack and satisfies that PA 2 a and p" + P'A (P'A BBB + + + p'g)- Assume 17 = o" o"/o', Equation 31 can be rewritten as:
18 + 18" 1|
2 o' c (P'a) 1/ (PA)) ol x (1')) + t (r)))
(32)
Thus according to Equation 26 and Equation 28, calculating the certified robustness of smoothed classifier can be turned into solving the optimization problem defined as:
min 84
n
(p'A
+1 - -- -- (D'A).
(33)
s.t.
DE (0.
17 7> 0.
Denote p 1 (ph + p/ + p3 + p The first-order derivative of the above objective function is:
7 d 4 -1
1r +1 - 5) d d
(p*)
d
A
2
+1 -
p A
2T
nexp
exp
2
(34)
2
--1 pm
-1 1/
+1 D)
-1
1
-V2mnexp
exp
2
2
Owing the inherent positivity of the exponential function, the sign of the first derivative hinges on the comparison of the value of --1 p
+1 +1- - -- (1²A with the critical value of
16

---

Published as a conference paper at ICLR 2024
Visualization of (p') + -3² for Various 1 --
1-p=0.0
1-p= 0.1
1-p=
1-3-0.5
Function Value
1-p=0.7
1-
-10
0.2
0.4
0.6
0.8
1.0
p'
+1-) ---1 (p-1('a))
Figure 6: The visualized landscape of 4
+1 1
2 In 77' Moreover, the expression क 6-'(p'/ (1'x -- --
exhibits monotonic increasing trend from negative infinity to positive infinity within the interval ÿ E (0,1) I) (a horizontal line if p = L.). The visualization of this function shown in Figure for illustration. Therefore, it can be asserted that the objective function initially demonstrates monotonically decreasing behavior, which subsequently transitions into an increasing trend. Thus, the minimum is achieved when the first-order derivative equals zero, which is:
Φ (1'x"a-1--))
x --" 21n
(35)
When á is set to 1, the objective function assumes a monotonic property (specifically, a decreasing trend for 7) and conversely, increasing trend for 7/ < 1), with the minimum being attained
the boundary the domain of p' Thus according Equation I1 and 12. we can derive certified robustness boundary for DRS under different variances smoothing. The landscape of the objective
function is visualized in Figure f a more straightforward illustration.
A.S JUSTIFICATION OF TIGHTNESS OF DRS ROBUSTNESS BOUND
The tightness of the certified robustness of RS is proven by Cohen et al. 2019). Assume the certified radius directly deduced from RS tight. Given that pB
PA the inequalities presented in and 11 are transformed into equalities. This indicates the smallest of | ||
Equations 7 8 9
(P's) the adversarial perturbation à is:
break DRS
-- (p%)). Denote ||8'|12 + ||0" according to Equation 12
|81|2 v |18'1 118-12
(36)
Consequently, in the worst case situation that ||0'||2 ||0" the largest certified robutsness pro- vided by DRS is v ( bound.
(P'a) + क-1 (p%)), which justify the tightness of DRS robustness
A.6 DETAILS ABOUT THE DRS CERTIFIED ALGORITIM
This section illustrates the details of the certified algorithm of DRS.
Downsample(zz idæ) down-sample the original image æ into two spatially non-overlapping sub- images based on the index vector ida and returns the sub-images at dimension and n.
17

---

Published as a conference paper at ICLR 2024
x", n) initially performs times sampling from the distribution of SompleUnder.Noiste fr, x²,"",
N(x' + =';x', I) and N(x" + ""="",021 Then it counts the frequency of predicted classes by f and f on those samples and returns two corresponding k dimensional arrays that contain these frequency counts.
LowerCon Bound [Ca), count" [ea, n, n, a) calculates the lower bound probability with confidence at least a using binomial estimation. Where p is an unknown probability fulfilling that count (CA) (nn, p), where is the binomial distribution with probability p and sampling times nt.
18


Reviews:
[{"review_id": "BhO39tICBJ", "reviewer": "Reviewer_acuW", "summary": "This paper investigates the certified robustness offered by randomized smoothing. Specifically, it addresses the curse of dimensionality associated with standard randomized smoothing algorithms. The authors introduce the concept of dual randomized smoothing, which partitions the input into two subsamples with dimensions $m$ and $n$ such that $m+n=d$. Each subsample is processed by a randomized smoothing classifier. The final decision of the algorithm is based on the most probable class from both classifiers. As a consequence, the dual randomized smoothing enhances the dimension dependence of $\\ell_2$ robustness radius from $O(1/\\sqrt{d})$ to $O(1/\\sqrt{m} + 1/\\sqrt{n})$.", "questions": "(Based on first point in weakness) Have you considered further partitioning the input, for instance, into $k$ subsamples, and then leveraging $k$ randomized smoothing classifiers for the final decision? Would such an approach potentially enhance the dimension dependence even more, perhaps improving the robustness radius from $O(1/\\sqrt{d})$ to something like $O(\\sum_{i=1}^k 1/\\sqrt{d_k})$, where $\\sum_{i=1}^k d_k = d$?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper addresses the curse of dimensionality of DS and improves dimension dependence from $O(1/\\\\sqrt{d})$ to $O(1/\\\\sqrt{m}+1/\\\\sqrt{n})$. The idea of partitioning input into subsamples into subsamples is very interesting.\n\n- The proposed algorithm is easy and efficient to implement. Also, experiments show DRS have improved empirical performance over standard DS.", "weaknesses": "- The improvement from $O(1/\\\\sqrt{d})$ to $O(1/\\\\sqrt{m}+1/\\\\sqrt{n})$ is mostly a constant change.\n\n- Part of DRS in Section 4.2 a bit unclear. Specifically, how is the downsampling function implemented, and how does it make sure that every subsample gets enough spatial info from the original input?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y79eEiOS7U", "reviewer": "Reviewer_h68g", "summary": "-", "questions": "-", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O89JN1ZCTz", "reviewer": "Reviewer_iAVM", "summary": "This paper proposes \"dual randomized smoothing\" as a method to alleviate the curse of dimensionality faced by standard randomized smoothing. The proposed method splits inputs into two lower-dimensional components, then performs smoothing in the low-dimensional spaces before bringing the components together to form a final prediction. A certified radius of robustness is theoretically proven, and experiments on benchmark image datasets are given to showcase the enhanced robustness of the method.", "questions": "1. Where does the $5*10^{-7}$ come from in (4)? Is this from a pre-specified sample size in RS? It would be nice to briefly mention this in Section 3.2.\n2. Why restrict the two low-dimensional smoothing procedures to share the same variance? How restrictive/suboptimal is this in practice? Will your guarantees generalize to the setting with different smoothing variances?\n3. The authors claim that their bound is tight. Perhaps I missed this, but where is this claim proven/justified?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction is thorough yet concise, and very nicely recapitulates the curse of dimensionality for randomized smoothing and clearly states the paper's contributions towards alleviating these issues.\n2. The related works section is thorough and well situates the proposed method within the vast amounts of works focused on enhancing randomized smoothing.\n3. The main theoretical result (robust radius for the DRS method) appears sound and provides novel insight into the dimensionality aspects at hand.\n4. The experiments are extensive and show nice improvements over standard RS.\n5. Overall, the paper is well-written and is very easy to read.", "weaknesses": "1. The authors claim that prior works fail to mitigate the curse of dimensionality for randomized smoothing approaches. However, they have missed the relevant works [1],[2], which should be discussed.\n2. The authors propose to use interpolation in Section 4.2 to utilize pre-trained models defined on the original input space, to act as the lower-dimensional classifiers. It is not clear whether they are using the same pre-trained model for both low-dimensional classifiers, or two different ones. Further, the potential downsides to using such interpolation schemes is not discussed. How much performance loss is there in taking this approach when compared to using two models $f^l$ and $f^r$ specifically trained for this dual RS approach? Of course, this would require additional pre-training, which may be costly for certain applications, but it would be good to know how much better the corresponding robustness certificates would be.\n3. First word in Section 5.3 is missing capitalized first letter.\n4. I think a bit more explanation would be useful on how the down-sampling is performed to break each input into its two parts. Specifically, it is sort of glossed over in text and left to the reader to interpret the procedure based on Figure 2. A simple one to two sentence explanation in the main body of the paper would suffice, preferably with an explicit pointer to the graphic of Figure 2, where the authors may want to state that the index set corresponds to a two-part partition of the images pixel indices, and $x^l$ is the vector composed of $x$'s pixel values $x_i$ with $i\\in\\text{idx}$, and $x^r$ is the vector composed of $x$'s pixel values $x_i$ with $i\\notin\\text{idx}$.\n\n[1] Projected Randomized Smoothing for Certified Adversarial Robustness, Pfrommer et al., TMLR, 2023\n[2] Intriguing Properties of Input-Dependent Randomized Smoothing, Sukenik et al., ICML, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ida6yItNAm", "reviewer": "Reviewer_Vvvf", "summary": "The authors introduced the dual random smoothing technique in order to mitigate the curse of dimensionality in the certified robustness bound in the realm of RS techniques.", "questions": "If partitioning into 2 spaces is good for mitigating curse of dimensionality, what about 3 spaces and even more? theoretically speaking they should mitigate the problem better, but why choose 2?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. By partitioning the input into two orthogonal spaces, and apply RS to each of them, the authors mitigated the curse of dimensionality.\n2. The technique proposed can be used in conjunction with a number of other methods, outside of plain RS.\n3. Theorem 2 showcases that this kind of technique is agnostic of the exact partition scheme, which make the application of this technique more ubiquitous.", "weaknesses": "1. This paper does not convince me that DRS will be better at RS in in terms of classification accuracy. Although experiments can partially validate this idea, but I think some form of theoretical analysis is needed in order to explain that DRS is at least not a lot worse than RS, because experiments can be easily tuned to show better results.\n\n2. The authors did not explain the partitioning mechanism in too much detail, so I'm curious whether a different partitioning mechanism will yield drastically different classification results (in terms of dimensionality scaling it should be fine due to Theorem 2), because this is very possible. Also the authors should explain how to choose a good partitioning scheme as this is conceivably very important to DRS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)