Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a loss function for training the base classifier for randomized smoothed classifiers. Specifically, the loss distinguishes between training examples with high prediction confidence and those with low confidence. Several empirical tricks are applied to design the loss function to optimize the performance. Experiments on MNIST and CIFAR-10 show that the proposed training method is superior to existing state-of-the-art randomized smoothed classifiers, especially when the radius r is large.
main_review: While the provided experimental results look promising, the designed loss function (especially for the low-confidence loss) seems to be very complicated in my perspective and the explanation in Section 3 are not clear enough to support such design. In particular, I have the following questions for authors to provide more clarifications:

1. The proposed CAT-RS loss relies on the prediction confidence of a classifier f for selecting examples. Is such f trained in advance or iteratively updated over the training process? How do you obtain the final certified smoothed classifier?

2. I do not understand the design of Equation (7) for the low confidence examples. Discussions in Section 3.1 do not give a clear picture on such specific design choice. Can you provide a clarification on this? 

3. Follow the previous question, the cold start problem mentioned in Section 3.1 is also confusing to me. Why Equation (6) leads to a cold start problem? Why Equation (7) resolves this issue? The authors use many terms like “the easiest noise” and “harder ones” in the paragraph above Equation (7), which are vague and hard to parse.

4. Figure 1 and Figure 2 are not well-explained. What do you mean by p_f=0.9 in Figure 1? Is it computed for a single example or computed as an averaged score for the whole dataset? What does areas with different colors represent in Figure 2? I do not understand the colored cross mark in Figure 2 as well.

Other comments:

1. The whole procedure for obtaining the final randomized smoothed classifier should be described in addition to the training loss.

2. It would be better to provide experiments on larger dataset such as Image-Net.


summary_of_the_review: In summary, the empirical results of the paper show advantages of the proposed training objective in producing better certified smoothed classifiers. However, given the current low clarity of the paper, especially when introducing the design of the proposed loss function, I suggest a weak reject for this work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed new loss functions during the training of classifiers for certified robustness via randomized smoothing. The new loss function treat samples with different confidence level differently. The main idea is to prioritize samples with high confidence because it provides more additional certified radius when its confidence grows.
main_review: Major comments:
- The paper proposes a pretty novel method to boost the training for certified robustness. The experiments look descent to me although the hyperparameter selection seems random to me. I wonder if a cross-validation is performed.
- The intuition behind the loss of high-confidence samples is that the noise samples provided is limited, which cannot guarantee the real $p_f(x,y)$ to be close enough to 1. This is especially important especially for ACR as increasing $p_f(x,y)$ can increase the certified radius more when $p_f(x,y)$ is closer to 1. However, the method used by the authors seems a little arbitrary to me. They find the worst noises within the $\ell_2$-ball of sampled noise by PGD, and somehow normalize the worst noise. Unlike SmoothAdv or simply increasing the number of samples, there is no clear reason why this should work. 
- The intuition behind low-confidence part is also natural, basically giving ways to high-confidence part. I think the authors have done that part pretty well.

Minor comments:
- $K$ is used as the number of classes and the binomial random variable.
- Sec 3.1, para 2, $p$ is not known here, so I think the $p$ in binomial distribution should be the empirical estimation $\hat p$.
- Sec 3.2, define $\delta^*$ and how it is normalized.
- Why is the binomial distribution necessary? You can probably just set $K$ to be the $pM$. 
- In Table 3, row (b), do you include the masking condition to $L^{high}$? If not, what is the performance if the condition is applied?
summary_of_the_review: My current assessment of this paper is slightly below the threshold because I am not very satisfied with the high-confidence part. I would like to hear from the authors about the mathematical intuition behind the current loss.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies certified robustness via randomized smoothing (RS). RS has a fundamental accuracy and robustness tradeoff. The authors aim to enhance such tradeoff through a sample-wise control of robustness over the training samples. In particular, the authors investigate the correspondence between robustness and prediction confidence of smoothed classifiers and design a new loss function. The proposed method is evaluated on MNIST and CIFAR10.  
main_review: Strengths:
+The studied problem is important
+Paper is easy to follow 

Weaknesses
-Novelty is limited 
-Insufficient evaluation 
-Missing important references

How do you make predictions during the training process, e.g., how do you obtain $\hat{p}_f $ in line 2 in Algorithm 1? Going forward, what’s the computational complexity of the proposed method? 

The loss $L^{(high)}$ is only evaluated when  $\mathbb{1}[(\hat{p}_f=1)]$?  How many training samples with the associated generated noises make $(\hat{p}_f=1$. I thinks this is a very strong constrain on my end. 

Why $p_0$ is limited to the range (0,1], instead of $(1, \infty)$? 

The proposed method obtains comparable performance with the existing methods. How about the running time?

There is no result on the ImageNet.  

The following paper also considers model’s confidence. Please discuss with it.  

Kumar et al., “Certifying Confidence via Randomized Smoothing” 


The following papers also derive certified robustness based on randomized smoothing 

Wang et al. “Certified robustness of graph neural networks against adversarial structural perturbation via Randomized Smoothing”

Jia et al., “Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing” 

Zhang et al., “Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework”

Mohapatra et al., “Higher-Order Certification for Randomized Smoothing”

Kumar et al., “Certifying Confidence via Randomized Smoothing”

Kumar et al., “Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness ”

Fischer  et al., “Certified Defense to Image Transformations via Randomized Smoothing”

Lee et al., “Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers”

summary_of_the_review: The studied problem is important and paper is easy to follow. However, the novelty is limited and the evaluation is insufficient.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes CAT-RS which combines two novel losses for training base classifiers for randomized smoothing. The two novel losses aim at preserving clean accuracy for hard samples and improving the certified radius for easy samples. In term of ACR (average certified radius), the method achieves state-of-the-art on MNIST and CIFAR-10.
main_review: This paper focuses on improving the certified robustness via training a better base classifier for randomized smoothing. The empirical analysis of "hard" and "easy" training samples is novel and innovative, which backs up the proposed losses. However, the experimental results do not provide strong empirical evidence on the effectiveness of the proposed method, and some important evaluation data, like results on ImageNet, running time statistics, etc, are not reported.

Strengths:
- The analysis, including the separation of "hard" and "easy" training samples and different treatments for them, is novel and interesting.
- The paper is very well written. The narration is coherent. The proposed method is clearly backed up by explanations.

Weaknesses:
- Based on the existing experimental results, the effectiveness of the proposed method is not apparent.

I appreciate that major baselines in this field are included in the experimental evaluation.

In terms of ACR, the proposed approach achieves state-of-the-art. However, the margin is not large enough, only except CIFAR-10 sigma=1.00 case. The authors claim that the method may be more significant on dataset with high complexity. Then IMHO, ImageNet results are inevitable to support this.

In terms of certified test accuracy, the proposed approach cannot achieve good benign accuracy or high certified accuracy under small radius though this is one of its primary goals (a better trade-off between robustness and accuracy). On CIFAR-10, the empirical performance seems to be better. However, the proposed method still cannot improve the accuracy under all radii compared with Gaussian (Cohen et al), and under most radii, the performance improvements are within 1.5%.
 
- Lack of ImageNet results.

All the compared baselines are evaluated on ImageNet. The high certified robustness on the standard ImageNet dataset is one of the unique strengths of randomized smoothing, and evaluation on ImageNet provides a more complete landscape on the method's performance on complex and large-scale datasets. Without ImageNet, it is hard to fairly evaluate the approach.

- Lack of training time statistics.

The M=4 intuitively would make the training process take > 4 times longer than Gaussian (Cohen et al), > 2 times longer than Consistency (Jeong et al), and about the same time as SmoothAdv (with m=4). Is it true? Then we may need to consider whether it is valuable to take a much longer time to obtain a small improvement.

Questions:
- On what set are the models evaluated?
Is the evaluation conducted on a uniformly picked subset of the full test set as other baselines? If so, is the set size 1000?
- Can you report the upper contour results across different sigma's for a clearer comparison?
- If the experiment results on ImageNet are provided, based on those results, I will re-evaluate this work.

Suggestion on the method:
- Maybe you can also try to assign different weights to the training samples. For example, if $p_f(x,y)$ is already high, we may sample more (e.g., set M=8/16 for each sample) to have a more precise estimation of $p_f(x,y)$, then assign higher weights to the sample with larger $p_f(x,y)$, since improvement on that sample would contribute more to ACR.
- In $L^{\mathtt{high}}$ loss, you first find $\delta^*$ then normalize them. Maybe you can incorporate the normalization inside - applying PGD on $\mathrm{normalized}(\delta^*)$.
summary_of_the_review: I appreciate the analysis and the novelty of the proposed training method. However, the current loss design seems to be not effective enough, and there are a few important details missing in the experimental evaluation. Therefore, I do not lean towards acceptance. The authors may try to follow the proposed principle to improve the detail design of the current training approach.
review_title: null

Meta-review: This authors seek to improve upon previous work on randomized smoothing for certifiably robust models. They develop loss functions inspired by the notion of distinguishing hard and easy samples while training the base classifier that is randomly smoothed and conduct experiments evaluating their proposed losses on benchmark datasets.

While the reviewers agree that the paper contains interesting ideas, the paper in its current form is unacceptable for publication because:
1) Missing large scale experiments: All prior work on randomized smoothing report results on ImageNet, and this was seen as one of the main advantages of randomized smoothing. Since the authors do not report this, it brings into question the robustness and scalability of improvements obtained.
2) Computational complexity and improvements: The authors' approach has significant computational complexity and the final improvements obtained are marginal. This makes it difficult to justify the use of a more expensive method.
Decision: Reject