Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences

Thank you for the thoughtful review. We are happy to answer the question about alternative norms.

Does the theoretical framework extend to alternative norm types, such as L1 or L2 norms?

While 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:

For 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. For 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.

That 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.

Thank you for the thoughtful review. We address the two main requests listed under weaknesses:

the main practice in the field is to report results on {cifar-10, ImageNet} times {𝜎=0.25,0.5,1.0} “I request the authors to present the full benchmark for comparison.”

Thank 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.

The 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).

“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.”

While 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.

That 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.

Thank you for the thoughtful review. We start by answering the main questions in the review and then address further comments.

Q1. “[...] can a certified radius be derived for a composition of heterogeneous f-DP mechanisms [...]?”

This 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).

Fortunately, the DP community already has several tools that one could leverage to explore this design space. Notable examples that we believe are promising include: Using 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). Using 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.

Q2. “Is there an intuitive explanation for the larger gap in certified accuracy between ARS and Cohen et al. for CelebA versus ImageNet?”

We would first like to address one possible reason suggested in the review:

“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?”

Thank 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.

As 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.

We 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.

Q3. “Are results available for a non-uniform split of the noise budget (line 223)?”

We 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.

“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.”

We 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.

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.

[...] in the standard settings the improvements are very mild, the main benefits are demonstrated on CELEBA benchmark) [...] This being said, the work (mainly the tools used) is clearly interesting enough to be accepted

In 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.