Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper integrates model ensembles with randomized smoothing to improve the certified accuracy. The methodology is motivated theoretically by showing the effect of model ensemble on reducing the variance of smooth classifiers. Moreover, it proposes an adaptive sampling algorithm to reduce the computation required for certifying with randomized smoothing. Extensive experiments were conducted on CIFAR10 and ImageNet datasets.
main_review: This paper has several strengths.

- The problem that this work is tackling is both of interest and importance.
- The theoretical analysis presented in section 5 along with figure 2 potentially motivates the use of model ensemble.
- The Adaptive Sampling proposed in section 6 algorithm is practical.
- The experiments conducted in this work are extensive. They cover several frameworks for training smooth classifiers and several datasets. In most of the setups, model ensemble resulted in improvements in the certified accuracy.

However, there are several concerns that need to be addressed:

- The main claim about the time reduction that CertifyADP provides is based on an unfair comparison with Certify. The amount of information that both algorithms provide is not the same. CertifyADP tells whether an instance is certified with a pre-chosen radius $r$ or not, however it gives no hint about the actual radius that the instance is certified with, which is the output of Certify. I am not trying to lower the importance of CertifyADP since in many practical situations, it is useful to know whether an instance is certified with a given radius or not, but the comparison against Certify needs to be fair.

- The writing of the paper can be significantly improved (especially section 5). 


Here are few comments/suggestions:

- typo: In page 4 third paragraph, "$y_p$ to be zero-mean".

-  While the analysis in section 5 are interesting, consider shrinking it to include more experiments in the main paper such as Table 15. It is interesting to see that the ensemble of models trained by different frameworks outperforms individual models. 

- Consider switching the locations of figures 5 and 6 since figure 6 is mentioned in the text before figure 5.

- The definitions of SampleRF, TimeRF, and KCR are in the last page in the paper. However, they are important to understand table 3 and the "Computational Overhead Reduction" paragraph.

- Figures 2 and 3 need more elaborative discussion.
summary_of_the_review: This work has several merits as pointed out in the main review. The key concern is the unfair comparison between Certify and CertifyADP presented in this work. Moreover, the writing of this paper can be vastly enhanced for better exposure.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors propose using the aggregation of an ensemble of similar models as the base classifier in the randomized smoothing (RS). They show that the use of ensembles helps reduce the variance of the base classifier under noisy inputs, thus, improving the performance of RS. Both theoretical arguments and numerical experiments are included to support their idea. Further, the authors provide practical algorithms that significantly reduce the computational costs of their method.

main_review: Strengths:
1. From both theoretical and experimental perspectives, the authors demonstrate the effectiveness of combining randomized smoothing with ensembles in building certified robust classifiers.
2. Though the theoretical arguments include many assumptions, the authors carried out experiments to validate them.
3. They proposed Adaptive Sampling and K-consensus algorithms to reduce the computational cost, making their method more practical.

Weaknesses/Concerns:

While the empirical evidence are sufficient to support the effectiveness of using ensemble to boost the performance of RS, I have some concerns about the assumptions in the theoretical arguments. 

It assumes that the "correlation between the logits of different classifiers has a similar structure but smaller magnitude than the correlation between logits of one classifier". Since different classifiers only differ in random seed for training, they should share behaviors in common. However, it is quite possible that such commonness is captured by $\mathbb{E}_l[f^l(x)]$, reflecting the underlying task, network architecture, dependence on $x$, etc., while the deviations of different models $\delta^i$ and $\delta^j$ are uncorrelated.

In fact, as shown in Figure 11(a) in the appendix, the off-diagonal blocks in the Delta subfigure are almost identical to the ones in the True covariance subfigure. It would be possible to reconstruct an argument about the variance reduction solely based on the assumption that $Cov(y^i_c, y^j_c)$ are near zero.
summary_of_the_review: The underlying topic of constructing a certified robust classifier is important. The main idea of the paper is sound and is supported by extensive experiment investigations. Further, the authors proposed algorithms to reduce the computational cost, making their method not only workable but also practical. There also includes empirical studies to validate (to some extent) the assumptions in their theoretical arguments. Hence, I would like to support the publication of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper aims to boost randomized smoothing (RS). Specifically, the paper demonstrates that an ensemble of diverse base models can enhance RS both theoretically and empirically. The key insight is that reducing variance of ensembles over the introduced perturbations can lead to more consistent classifications for inputs. The paper also introduce two simple  yet effective techniques to speed up the certification. Extensive experiments are conducted to thoroughly evaluate the proposed boosted RS.

main_review: Strengths

+Important research problem

+Well written and well-organized

+Interesting analysis on why ensemble works

+Extensive evaluation

Weaknesses

-Evaluation only on the L2 certification

-Missing related work
summary_of_the_review: Certifying an ensemble of models is faster than certifying an individual model through the proposed two strategies. However, training an ensemble of models requires far more computational resources and time than training an individual model. Although the authors mainly leverage the pretrained models, but in practical applications this may be infeasible. I would suggest the authors discuss the issues of training an ensemble of models.   

The authors say that “…substantially increased certifiable radii for samples close to the decision boundary..” in abstract, but no results to validate this claim. I would like to see the results for those samples having a small margin.  

The authors assume that y_c is the clean part and y_p is the perturbation/noisy part. How to define y_p and y_c when evaluating the real image datasets? Or y_p and y_c are just for analysis? 

What’s the impact of $\alpha$ and $\beta$? 

In table 1, why ensemble is less effective than MACER when radius r is small? 

“Even when using only K = 2, we already obtain 81% and 70% of the ACR improvement obtainable by always evaluating the full ensembles (k = 10 and k = 50) “ => How do you calculate the numbers 81% and 70%? 

 In Table 3, what do SampleRF, KRC, and TimeRF mean or short for? 

My another concern is that the experimental results are only for certifying L2 perturbation.  There are several papers that design RS to certify $L_0$, $L_1$, $L_\infty$ perturbation.  For example, 

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

$L_1$: Lee et al., “Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers”, NeurIPS 2019

$L_\infty$: Yang et al., Randomized Smoothing of All Shapes and Sizes

I am also really interested in whether the proposed ensemble is also effective for certifying $L_0$, $L_1$, or/and $L_\infty$ perturbation. 

The following papers also derive certified robustness based on 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”
review_title: null

Meta-review: This paper integrates model ensembles with randomized smoothing to improve the certified accuracy. The methodology is motivated theoretically by showing the effect of model ensemble on reducing the variance of smooth classifiers. Moreover, it proposes an adaptive sampling algorithm to reduce the computation required for certifying with randomized smoothing. Extensive experiments were conducted on CIFAR10 and ImageNet datasets.

The strengths of the paper are as follows:
+ In terms of significance of the topic, the problem tackled in the paper is significant and highly relevant. 
+ The motivation of using model ensemble is clearly illustrated via a figure and well justified with theoretical analysis. 
+ Algorithmically, the paper proposes Adaptive Sampling and K-consensus algorithms to reduce the computational cost, making the method more practical.
+ Experimentally, the paper exhibits competitive results against several frameworks for training smooth classifiers and on several datasets.
Decision: Accept (Spotlight)