Provably Robust Cost-Sensitive Learning via Randomized Smoothing

The contributions of this paper are somewhat weak since some conclusions claimed in the main paper could be directly realized by Cohen et al. (2019). Furthermore, in Alg.1, where the $R_1$ comes from? In Cohen's paper, they also considered this in a binary classification case.

Another non-neglected limitation of this paper is that it can only process the binary cost-matrix problem. This is also a possible reason why the Cohen-R algorithm cannot perform well.

Also, the motivation of Sec.4.2 needs to be further added.

• Why can Eq.(4) work well? Why must we do the optimization like this?
• I noticed that $I_2$ also includes the cost-sensitive sample. But why the cost-sensitive samples included in $I_2$ is processed differently from I_3?
• Moreover, the certified radii R_{c-s} would be greater than $0$ since the set $[m]$ includes $\Omega_y$. Thus, why does $I_3$ exist $-\gamma_2$？
• Generally speaking, we usually do not obtain the exact value of g due to the expectation. Thus, in Eq.(4), how do you back-propagate $g(x)$?

Finally, the experiment part is somewhat unconvincing. The authors should consider more of the latest randomizing smooth methods, such as [1,2].

Ref:

• [1] Consistency regularization for certified robustness of smoothed classifiers, NeurIPS, 2020.
• [2] Provably robust deep learning via adversarially trained smoothed classifiers, NeurIPS, 2019.

1. Binary Cost Matrix: A 0/1 cost matrix may not be sufficient to capture real-world cost-sensitive ML tasks. The cost of misclassification would rarely be zero. Take the example mentioned in the second paragraph of the introduction. While misclassifying a benign tumor as malignant is less detrimental than the reverse, the cost of such a misclassification will not be zero. If so, one could simply label all tumors as malignant and achieve an overall classification cost of zero. However, such a classifier would not provide us with any valuable information.

   It would be more impactful to design robustness certificates for a general cost matrix where the entries need not be 0/1. It might be possible to certify the expected misclassification cost by using the distribution of the cost under the smoothing noise. The following work on certifying the expected confidence of a neural network could be adapted for a general cost matrix:

   Certifying Confidence via Randomized Smoothing, Kumar et al., NeurIPS 2020.

2. Novelty: The robustness certificate designed in this work is a straightforward adaptation of Cohen et al.'s certificate [1]. The certificate in [1] takes the difference between two terms where the second term depends on p_b, the probability of the second most likely class. This paper redefines p_b as the probability of the most likely class in the set of class labels with cost 1.


   [1] Certified Adversarial Robustness via Randomized Smoothing, Cohen et al., ICML 2019.

3. Sample Complexity: The number of samples required for computing the proposed certificate is higher than that of the baseline certificate from [1]. It depends on the number of classes with cost 1. While this might be manageable for the small number of classes considered in the experiments (<= 10), scaling to a large number of classes, such as in ImageNet (1000 classes), would be difficult.

1. The paper appears to be a straightforward adaptation of Cohen et al. [1] to a cost-sensitive context, limiting its novelty. Algorithm 1 seems to selectively ignore classes based on the cost matrix, and the training approach in Section 4.2 appears to be a variation of MACER. If my assessment is incorrect, I'd appreciate clarification in the rebuttal about the unique challenges faced when integrating randomized smoothing [1] and MACER into the cost-sensitive framework.

2. The paper lacks comparisons with several key baselines [2,3,4]. It's essential to address these well-established methods, especially since SmoothMix reportedly outperforms MACER in [4].

[1] Cohen et al., Certified Adversarial Robustness via Randomized Smoothing, ICML 2019
[2] Salman et al., Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers, NeurIPS 2019
[3] Jeong et al., Consistency Regularization for Certified Robustness of Smoothed Classifiers, NeurIPS 2020
[4] Jeong et al., SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness, NeurIPS 2021

1. Although providing theorem 3.2 for computing robust radius, the proof of this theorem is a straightforward generalization of Theorem 1 in [Cohen et al 2019], hence raising a novelty concern. Note that this limited novelty doesn't affect the reviewer's rating on this work.
2. This method is designed to handle the cost-sensitive setting, for example, medical classification as the paper claimed. However, the improvement in medical setting is not as noticeable as in synthetic setting (Cifar10 and imagenette).