Provably Cost-Sensitive Adversarial Defense via Randomized Smoothing

1. It is essential to report the robust accuracy of both cost-sensitive and non-sensitive adversarial examples separately.

Thanks for the suggestion. We report the cost-sensitive robustness for both sensitive and non-sensitive examples under the CIFAR-10 S-Seed setting. As expected, there exists a trade-off in certified robustness performance between these two types of samples, which aligns with our training objective: a smaller margin threshold $\gamma_1$ is used for normal examples, while a larger margin threshold $\gamma_2$ is applied to sensitive examples.

2. The details of the attacks used in the experiments are not disclosed
As defined, randomized smoothing provides certified robustness against all attacks within the certified radius. For this reason, prior works on randomized smoothing—and most certification-based methods in general—do not explicitly specify a threat model or evaluate against empirical (adaptive) attacks. Following this convention, neither do we.

3. The paper does not compare its approach with the most relevant work, such as Zhang et al. (2023), nor does it include comparisons with other regular adversarial training methods.

We report the performance comparison between our method and DiffSmooth, as proposed by Zhang et al. (2023). Our Margin-CS results are presented in parentheses for direct comparison with DiffSmooth. As shown in the table, our method consistently outperforms DiffSmooth across all cost-matrix settings by a significant margin. Furthermore, our method achieves an inference time of 2.28 seconds per image, whereas DiffSmooth requires 89 seconds per image (~40 times slower), highlighting the efficiency and practicality of our approach for real-world deployment.

4. The novelty of the proposed method in comparison to Zhang et al. (2023)
Zhang et al. 2023 enhances randomized smoothing for general robustness by using a diffusion model as a denoiser before passing the noisy input to the target model. In contrast, our work improves randomized smoothing for cost-sensitive robustness (which existing approaches cannot achieve) through a novel training paradigm. As these approaches are algorithmically distinct and directionally orthogonal, we do not see a particularly strong connection between them—beyond both falling under the broader category of randomized smoothing.

5. Specifically, the overall accuracy presented in Table 1 and Table 11 is noticeably lower than that of state-of-the-art (SOTA) adversarial training methods (refer to RobustBench).

As briefly mentioned in the above response 2, there is an inevitable gap between empirical robustness (i.e., potentially effective against specific attacks, such as adversarial training) and certified robustness (i.e., provably effective against all possible attacks within a bounded perturbation, e.g., randomized smoothing). Simply speaking, the noise scale incorporated in randomized smoothing framework is much larger than that in adversarial training, since empirical attacks focus on imperceptible perturbations, whereas rigorous certification requires a reliable computation of the certified radius. This difference is then reflected in the model's clean accuracy. While a deeper investigation into the gap between these two fields would be an interesting direction, it falls outside the scope of this submission.

6. The proposed method should be compared with regular adversarial training methods, as these are designed to generalize across all adversarial scenarios.

As mentioned above, the training noise used in randomized smoothing baselines is significantly larger than that used in adversarial training methods. To illustrate this discrepancy, we evaluated the certified robustness of the top two methods on RobustBench—MeanSparse and adversarial training enhanced by diffusion models—and found that their certified performance is close to zero. This highlights the fundamental mismatch between the goals of empirical adversarial training and certification-based approaches: the former aims to improve empirical robustness under small, often imperceptible perturbations, while the latter focuses on providing formal robustness guarantees under much larger perturbation regimes.

1. The authors should report the performance variance

We conduct three independent runs of the Imagenette S-Seed setting and report the corresponding standard deviations. The experimental procedure comprises two distinct stages: the training phase and the certification (evaluation) phase. The majority of variance arises during training, while variance during certification is negligible due to extensive Monte Carlo sampling and majority voting, which together ensure stable and consistent results. As shown, running all the baselines and our method multiple times does not affect the claims nor findings. We will include performance variance details to further strengthen the manuscript.

2. Ablation study on hyper-parameters

There are two stages in the hyperparameter tuning process. In the first stage, $\lambda_1$ and $\lambda_2$ control the overall trade-off between certified accuracy and cost-sensitive robustness. As expected, increasing $\lambda_1$ and $\lambda_2$ leads to a decrease in overall accuracy but an improvement in cost-sensitive robustness. We set $\lambda_1 = \lambda_2 = 3$ to achieve a favorable balance between the two objectives.

In the second stage, we fix $\lambda_1$ and $\lambda_2$ and tune $\gamma_1$ and $\gamma_2$. Here, $\gamma_1$ determines the margin threshold for selecting normal samples, while $\gamma_2$ controls the threshold for sensitive samples. We observe that increasing $\gamma_2$ enhances cost-sensitive performance, whereas increasing $\gamma_1$ improves overall accuracy, but will decrease cost-sensitive performance. A grid search reveals that the combination $(\gamma_1, \gamma_2) = (4, 16)$ yields satisfactory results.

We will include these details in the revised manuscript's Appendix.

1. Theorem 4.4 (Certified robustness estimate is statistically valid). The logic appears correct, but empirical verification (e.g., checking Monte Carlo estimates converge) would strengthen confidence.

We conduct the certification process using varying numbers of Monte Carlo samples, where N denotes the number of samples and r represents the certified radius returned by Algorithm 1. The results for the S-Seed setting are shown in the table below. We observe that as N increases, the certified radius gradually converges. Specifically, once N exceeds 50,000, the certified radius stabilizes and exhibits minimal fluctuation.

2. No Adaptive Attack Evaluation: The method is only tested under L2 norm perturbations.

As defined, randomized smoothing provides certified robustness against all attacks—including adaptive ones—within the certified radius. For this reason, prior works on randomized smoothing (and most certification-based methods in general) do not evaluate against adaptive attacks. While we agree that exploring the gap between certified robustness and empirical robustness (i.e., performance under actual attacks) is an interesting direction, it falls outside the scope of this submission.

Although randomized smoothing is formally defined for L2 norm perturbations, prior work has shown that it can be effectively extended to other norms [1,2]. As this generalization is well-established and independent of our main contributions, we do not focus on it here, but we are happy to provide relevant results upon request.

[1] Yang, Greg, et al., "Randomized Smoothing of All Shapes and Sizes", ICML 2020 [2] Vorácek, V., & Hein, M., "Improving L1-Certified Robustness via Randomized Smoothing by Leveraging Box Constraints", ICML 2023

3. Limited Discussion on Real-World Deployment: Practical constraints (e.g., computational cost, real-time processing) are not discussed.

As suggested, we report the training and inference time evaluated on a single A100 GPU (40 GB Memory). During training, we employ a margin-based loss to optimize the cost-sensitive certified radius, which necessitates a substantial amount of Gaussian sampling (e.g. 16) for accurate radius estimation, as well as sufficient epochs to ensure convergence. This results in a slight increase in the training time. During inference, they all share the same certification procedure, so their certification time is nearly identical.

4. What is the computational overhead of certification? How does Monte Carlo certification time scale with input dimensions and the number of classes? Can the method be extended to other robustness frameworks?

The overall certification cost is $O(N\times T_{fwd})+O(C)$, where $N$ is the Gaussian sampling number and $T_{fwd}$ is the cost per forward pass (depends on model size and input dim), $C$ is the number of classes. $O(C)$ is due to post-processing steps after the Monte Carlo sampling. This includes operations like finding the top classes, computing confidence bounds, and estimating per-class certified radii. While this cost is small compared to the sampling phase, it scales linearly with the number of classes $C$. Our certification algorithm is compatible with any robustness framework. It is independent of the training procedure and can also be integrated into diffusion-based certification methods (as shown in the reponse to Reviewer KFXn), The values in parentheses correspond to our method.

5. Ablation Study & Sensitivity Analysis: Adding a hyperparameter sensitivity analysis would improve the practical usability of the method.

Please refer to our Response 2 to Reviewer AS48 for the hyperparameter sensitivity analysis. The experimental results show that the parameter $\lambda$, $\gamma$ controls the trade-off between overall accuracy and cost-sensitive performance. We will include more details on the ablation study and sensitivity analysis in the Appendix of the revised manuscript.