Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing

We thank the reviewer for taking the time to read this paper and giving constructive feedback. Please find our response below.

W1: The classification accuracy of DRS and RS. Some form of theoretical analysis is needed in order to explain that DRS is at least not a lot worse than RS.

The classification accuracy of DRS compared to that of RS is data-dependent. In the case of high-dimensional, real-world datasets, particularly those with significant information redundancy like images, the classification accuracy of DRS can be very close to that of RS. This comes from a well-known fact that images only occupy a very small subspace of the image space spanned by pixels, especially for high-resolution images. Hence, each sub-sample obtained through down-sampling retains a substantial portion of the original information. [1] claims that masking a high proportion of the input image, e.g., 75%, yields a meaningful self-supervisory task. In general, the classification accuracy of DRS will not be a lot worse than RS for those data with high information redundancy if the data is properly partitioned.

To verify that, we conducted a comparative experiment to evaluate the classification accuracy on the CIFAR-10 dataset using $f$, $f^l$,$f^r$, and $f^l+f^r$. For all classifiers, we employed a standard training strategy; we used the ResNet110 as the classification model, and SGD as the optimizer with $learningrate =0.1,~ momentum=0.9,~ and~weightdecay=5*10^{-4}$. We used the standard augmentation including random crop and flip. Each model was trained for 100 epochs with a learning rate decay implemented via $CosineAnnealingLR$. The experiment result is shown in the following table. The result reveals that DRS shows a very similar accuracy performance to RS for this image dataset.

For the improvement in the certified robustness of DRS, we primarily attribute it to its ability to guarantee the same robustness as RS using a lower noise variance. In Tables 3 and 4, we show that under consistency training, DRS under a lower noise variance achieves a higher certified accuracy and upholds a comparable level of certified robustness as RS, but encounters some accuracy drop when the noise variance increases to match that of RS.

W2: Whether a different partitioning mechanism will yield a drastically different classification result. Explain how to choose a good partitioning scheme.

Yes, a different partitioning mechanism may yield a drastically different classification result. A good partition scheme depends on the structure of the data sample. In general, for most real-world datasets, down-sampling is a good partitioning scheme because it is a good way to let each of the partitioned data contain information close to that in the original data, thereby preserving classification accuracy.

Q1: What about 3 spaces and even more partitioning.

Further partitioning the input is quite promising for enhancing the robustness upper bound. Reflecting on your discerning insight, in Appendix A.3 of the revised manuscript, we further explore the feasibility of k-partitioning based smoothing. By deriving a general architecture of the smoothed classifier $g$ using $k$-partitioning, in Equation (26), we reformulate the guarantee of certified robustness as an optimization problem. Our findings in Appendix A.3 indicate that:

1. for $k=2$, this optimization is proven to be convex, where the global minimum to guarantee the certified robustness is achieved by $\mathop{p'}\nolimits_A^1=\mathop{p'}\nolimits_A^2=\frac{1}{2}\tilde p$. This is in alignment with our assertion in Equation (11).
2. For $k>2$, this optimization is non-convex. Providing a numerically stable solution for the global minimum under these circumstances is challenging (the minimum might not exist). A saddle point is achieved when $\mathop{p'}\nolimits_A^j = {{\tilde p} \mathord{\left/{\vphantom {{\tilde p} k}} \right.} k} , \forall j \in \{1, \ldots, k\}$, but it does not strictly ensure the certified robustness.

We present an in-depth analysis and an illustrative visualization of this $k$-partitioning based smoothing in Appendix A.3, which may help future research endeavors.

[1] Masked autoencoders are scalable vision learners. He, Kaiming, et al., CVPR, 2022.

I want to thank the authors for their detailed response. I think I'm still not entirely sold on the idea that DRS does not sacrifice classification accuracy too much, and the explanation is a bit hand wavy. However, I do appreciate the author's additional experiments and clear illustration. I think given the current experiments and explanation I would like to raise my score to 6, since I do see value in DRS. However as a follow-up work or a journal version it is highly desirable to have some theoretical guarantee surrounding the accuracy of DRS. As for partitioning scheme, I understand down-sampling is nice, but what kind of down-sampling is critical (different modes of anti-aliasing and all that). However these details can be left to future works.

Q1: Explain the $5*{10^{ - 7}}$ in Equation (4). Is this from a pre-specified sample size in RS?

In our revised manuscript, we added an explanation that "the parameter $5 \times 10^{-7}$ is derived from a predefined error margin ($1 \times 10^{-6}$) between the estimated probability and true probability over the origin-symmetric distribution.". Indeed, this parameter maintains a relationship with the sample size.

Q2: Will DRS guarantee to generalize to the setting with different smoothing variances? Does restricting the same variance make DRS suboptimal in practice?

1. Yes, DRS guarantees generalization to the setting with difference smoothing variance. Following your insights, we analyze the generalizability of DRS with different smoothing variances in Appendix A.4 of the revised manuscript. Let $\eta$ denote the ratio of standard deviations selected for two sub-inputs, specifically $\eta={{\sigma} ^r}/{{\sigma} ^l}$. Our finding in Appendix A.4 is that the calculation of the worst-case robustness provided by DRS with different smoothing variances can be formulated into a convex optimization problem. A global minimum that guarantees the certified robustness of DRS is achieved by making the first-order derivative equal to zero, which is: $\eta *\frac{d}{{{d{\mathop{p'}\nolimits_A^l}}}}{\Phi ^{ - 1}}\left( {\mathop{p'}\nolimits_A^l + 1 - \tilde p} \right) = \frac{d}{{{d{\mathop{p'}\nolimits_A^l}}}}{\Phi ^{ - 1}}\left( \mathop{p'}\nolimits_A^l \right).$ For $\eta=1$, the solution of the above equation is $\mathop{p'}\nolimits_A^l=\mathop{p'}\nolimits_A^r=\frac{1}{2}\tilde p$, which is in alignment with our assertion in Equation (11). An illustrative visualization of this problem is presented in Figure 5. Please kindly refer to the updated manuscript for more details.
2. Yes, the reviewer is correct that restricting the uniform variance for the two sub-images is suboptimal in practice. Nonetheless, the substantial information overlap in data conveyed by the sub-images indicates that their respective optimal variance levels are close. Inspired by the input-dependent RS [2], determining the optimal variance for each image within the DRS framework is promising work.

Q3: Explain the tightness of DRS robustness bound

The tightness of the certified robustness of RS is proven in [3]. For DRS, we assume that the certified radius directly derived from RS is tight. Given that ${p_B} = 1 - {p_A}$, the inequalities presented in Equations (7), (8), (9), and (11) are transformed into equalities. This indicates the smallest of ${\left\| {{{\delta} ^l}} \right\|_2} + {\left\| {{{\delta} ^r}} \right\|_2}$ to break DRS is $\sigma \left( {{\Phi ^{ - 1}}\left( {p_A^l} \right) + {\Phi ^{ - 1}}\left( {p_A^r} \right)}\right)$. Consequently, in the worst case situation that ${\left\| {{{\delta} ^l}} \right\|_2} = {\left\| {{{\delta} ^r}} \right\|_2}$, the largest certified robustness provided by DRS is $R=\frac{\sigma }{{\sqrt 2 }}\left( {{\Phi ^{ - 1}}\left( { {p_A^l} } \right) + {\Phi ^{ - 1}}\left( {{p_A^r} } \right)} \right)$, which proves the tightness of DRS robustness bound. We added this justification in our revised manuscript in Appendix 5.

Thank you so much for taking the time to read this paper and giving constructive feedback. Please find our response below.

W1: 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.

Following your suggestion, we modified our claim in our revised version as "Prior works have not adequately tackled the challenge of the curse of dimensionality in the context of high-dimensional inputs.", and added the discussion of these two relevant works in our related work as "Sukenik et al. (2022) prove that the input-dependent RS also suffers from the curse of dimensionality and Pfrommer et al. (2023) propose a projected randomized smoothing that enhances the lower bound on the certified volume.".

Projected Randomized Smoothing (PRS) innovatively linearly projects inputs into a lower-dimensional space and improves the lower bound on the certified volume. However, PRS could be vulnerable to some specific perturbation directions. In contrast, DRS maintains efficacy across all perturbation directions. Additionally, DRS maintains its effectiveness for higher-dimensional datasets, that are profoundly impacted by the curse of dimensionality, while PRS might fail due to the large memory for holding the entire dataset. Sukenik et al. prove that input-dependent randomized smoothing suffers from the curse of dimensionality, indicating its effectiveness primarily for small to medium-sized inputs. However, this paper does not propose the solution for this curse.

W2: It is not clear whether they are using the same pre-trained model for both low-dimensional classifiers. The performance of using a model specifically trained for this DRS approach? Discuss the potential downsides of using interpolation schemes.

1. For each training strategy discussed in our paper (such as Gaussian augmentation, consistency $\ldots$), we use the same pre-trained model for both low-dimensional classifiers and fine-tune them using the same training strategy as RS for a fair comparison. We added this clarification in our revised manuscript.
2. An intriguing observation is a parallelism in performance trends between DRS and RS across diverse training strategies and models. For example, in DRS, using a stronger pre-trained model based on consistency regularization outperforms using the pre-trained model based on Gaussian augmentation. Thus we think enhancing DRS with a stronger specifically trained model is promising.
3. Employing interpolation slightly elevates the computational complexity, but it helps the alignment of the training data distributions in DRS and RS, making DRS well adapt to existing training strategies designed for RS.

W3 and 4: The first word in section 5.3 is not capitalized and more explanation on how the down-sampling is performed.

In our revised version, we corrected this typo and added an explanation of the down-sampling process: "Considering the high information redundancy of adjacent pixels in the image, we utilize two $2\times2$ pixel-index matrices as the down-sampling kernels. Each kernel selectively retains pixels along one of the two diagonals within the $2\times2$ image block, as depicted in Figure 2. The two sub-images are generated by sliding the two kernels across the original image, moving with a stride of 2.".

[1] Projected Randomized Smoothing for Certified Adversarial Robustness, Pfrommer et al., TMLR, 2023.

[2] Intriguing Properties of Input-Dependent Randomized Smoothing, Sukenik et al., ICML, 2022.

[3] Certified adversarial robustness via randomized smoothing, Cohen et al., ICML, 2019.

Thank you so much for taking the time to read this paper.

Thank you so much for taking the time to read this paper and giving constructive feedback. Please find our response below.

W1: The improvement from ${O}(1/\sqrt{d})$ to ${O}(1/\sqrt{m}+1/\sqrt{n})$ is mostly a constant change. Would $k$-partitioning based smoothing potentially enhance the robustness radius from ${O}(1/\sqrt{d})$ to something like ${O}(\sum\nolimits_{i = 1}^k {1/\sqrt{d_i}})$, where $\sum\nolimits_{i = 1}^k{1/\sqrt{d_i}}=d$.

For $m=n=\frac{d}{2}$ implemented in DRS, the improvement of the upper bound is a constant factor of $\sqrt 2$. Reflecting on your discerning insight, in Appendix A.3 of the revised manuscript, we further explore the feasibility of k-partitioning based smoothing. By deriving a general architecture of the smoothed classifier $g$ using $k$-partitioning, in Equation (26), we reformulate the guarantee of certified robustness as an optimization problem. Our findings in Appendix A.3 indicate that:

1. for $k=2$, this optimization is proven to be convex, where the global minimum to guarantee the certified robustness is achieved by $\mathop{p'}\nolimits_A^1=\mathop{p'}\nolimits_A^2=\frac{1}{2}\tilde p$. This is in alignment with our assertion in Equation (11).
2. For $k>2$, this optimization is non-convex. Providing a numerically stable solution for the global minimum under these circumstances is challenging (the minimum might not exist). A saddle point is achieved when $\mathop{p'}\nolimits_A^j = {{\tilde p} \mathord{\left/{\vphantom {{\tilde p} k}} \right.} k} , \forall j \in \{1, \ldots, k\}$, but it does not strictly ensure the certified robustness.

We present an in-depth analysis and an illustrative visualization of this $k$-partitioning based smoothing in Appendix A.3, which may help future research endeavors.

W2: Part of DRS in Section 4.2 is a bit unclear. Specifically, how is the down-sampling function implemented, and how does it make sure that every sub-sample gets enough spatial information from the original input?

In our revised paper, we added the explanation that: "Considering the high information redundancy of adjacent pixels in the image, we utilize two $2\times2$ pixel-index matrices as the down-sampling kernels. Each kernel selectively retains pixels along one of the two diagonals within the $2\times2$ image block, as depicted in Figure 2. The two sub-images are generated by sliding the two kernels across the original image, moving with a stride of 2."