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

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

Strengths

1. The paper is well-written and easy to follow. 2. 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. 3. 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.

Questions

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

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

See weaknesses and questions.

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.

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

Questions

See weaknesses.

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

4

Limitations

The authors adequately addressed the limitations.

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.

Strengths

**Originality and significance:** This 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. **Quality:** The 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). **Clarity:** The 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. Given 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. Theorem 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?

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)? - Is there an intuitive explanation for the larger gap in certified accuracy between ARS and Cohen et al. for CelebA versus ImageNet? - Are results available for a non-uniform split of the noise budget (line 223)?

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes, limitations are addressed adequately in Section 5.

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.

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). The 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. very minor: * f-DP is not really introduced I think, the $f$ appears in prop 2.1 without any explanation, right? * unify Dong 2019 and Dong 2022 citations. I think they are the same? * " adaptivity over multi-step computation comes with no increase in certified radius" - no decrease?

Weaknesses

^

Questions

-

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

-