Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper the authors extend the tightness guarantees of other works on randomized smoothing to the $\ell_0$ case and also tighten the guarantees given by previous works by noting the discrete nature of the predictive distribution induced by randomized ablation. In addition, they extend previous $\ell_0$ methods to certify top $k$  predictions rather than just top $1$ predictions which is typically the case for smoothing. 
main_review: There are several key pros of the paper that contribute to my favorable opinion. In particular, the authors do a good job of highlighting recent and related works and ensuring that readers understand the contribution they are making relative to those works that it builds on. Further, the advances that the authors suggest in terms of improving tightness are stated in an intuitive way which allows for greater appreciation of the relatively simple modification they make. Finally, I think the introduction of top $k$ predictions rather than top 1 prediction is an interesting contribution which extends the applicability of randomized ablation (i.e. $\ell_0$ smoothing). 

The primary cons of this paper are in its potentially incremental impact. I think the clear exposition of prior works may make this paper's contributions seem simple or incremental, but I think ultimately that these are important developments/extensions of prior work that constitutes a strong enough contribution for acceptance. 

The second primary con (and perhaps the more noteworthy one) is the applications that this method is tested on. It is rare for the $\ell_0$ metric to be tested on images in practice. However, for graph neural networks and 3D deep learning this is a primary threat model. I think it would greatly strengthen the paper if such networks were certified and would add yet another point of contribution for this paper. 



summary_of_the_review: Though one might see the contributions of this paper as incremental over other works in smoothing, I think these are valuable and important developments in the field of smoothing which can enable further applications to gain guarantees via smoothing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides both theoretical progress and experimental results on certified robustness of top-$k$ predictions. Specifically, on the theory side, the paper shows that the randomized ablation (Levin & Feizi) has $\ell_0$-norm certified radius of top-$k$ predictions. Also, the paper proves that the certified radius is tight for k = 1 and almost tight for k > 1. (The certified radius cannot be larger than “the derived radius plus 1”.) On the experiment side, the paper compares the proposed method to existing competitors and explored the impact of the related parameters.
main_review: [Strength]
1.	The writing is concise and easy to understand in general.
2.	The paper makes nontrivial theoretical progress. Also, the authors provided enough explanation about how this progress can be distinguished from other existing works, so the contribution looks to be unique.

[Weakness]
1.	I don’t see any severe weakness (to reject this paper) in this work.

[Comments]
1.	I enjoyed reading this paper, and I think that the approach is “kind of good”. For the following reasons, I’d not put a score of 8 for this paper.
A.	The suggested proof approach is not easily generalizable, so it would be hard to say that this is a major discovery in the theory of certified robustness. (If possible, some discussion on the possible uses of the proof strategy would make the paper better.)
B.	I might have missed some potential weaknesses that I should have found. For this comment, I want to discuss with other reviewers during the review process.
2.	I can understand how the authors compared their method ($\ell_0$-certified robustness) to existing counterparts (some of them are $\ell_2$-certified robustness) and I can see there are not that many possible ways to compare them. However, I’m still not convinced whether it is a fair comparison or not, and I’m not even sure whether we can directly compare those methods or not. Also, in my personal opinion, there could be better experiment questions than just showing “our method is excelling other methods”.

summary_of_the_review: I vote for accepting. First, the paper proved a nontrivial result about the certified robustness of top-$k$ predictions. Also, the paper provided enough justifications for its unique contribution to the defenses using randomized smoothing & randomized ablation type, so I believe this paper can be distinguished from other existing works. While I believe that the work itself is publishable, I’m a little bit reluctant to give a score of 8 for this paper yet due to the reasons I provided in Comments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a tighter L0 verification method for Top-K predictions of classifiers based on randomized smoothing.
main_review: I appreciate the theoretical analysis and the impressive empirical results in the paper. 
Concerns and questions:
* The "Deriving the certified radius for the smoothed classifier" sections is rather difficult to understand. I recommend the authors to reorganize this section and define the notations separately in a clearer way.
* The paper states that for $k=1$ the certified radius is tight. But this statement is only true if there is no assumption on the base classifier is made, and this is not true for a given base classifier, therefore this statement may be overclaimed.
* In Table 1&2, the comparisons of Top-1 prediction for 'Our methods' are missing.
* I recommend the author to compare with another L0 verification methods like https://openreview.net/pdf?id=HyeaSkrYPH. 
summary_of_the_review: I appreciate the theoretical analysis and the impressive empirical results in the paper but the written is not clear. I also have some questions on the experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides an almost tight l0-norm certified robustness guarantee for top-k predictions against adversarial perturbations, which extends certified radius of the top-1 prediction from Levine & Feizi (2019) to that of the top-k predictions, and the l2-norm certified radius from Jia et al. (2020) to the l0-norm certified radius. The experiments on CIFAR10 and ImageNet show that the proposed method substantially outperforms state-of-the-art for top-k predictions.
main_review: In total, this is a good work both in the theoretical perspective and the experimental perspective. The authors provide a solid proof on the l0-norm certified robustness guarantee for top-k predictions, which is different from previous works of Levine & Feizi (2019) and Jia et al. (2020). The detailed experiments show its consistent improvement in certified top-k accuracy on CIFAR-10 and ImageNet and the ablation study provides a view on how these hyperparameters affect the performance.
summary_of_the_review: The author derives an almost tight l0-norm certified robustness guarantee of top-k predictions against adversarial perturbations for randomized ablation. The corresponding theoretical analysis show both the l0-norm certified radius and the tightness. The empirical results demonstrate that the l0-norm certified robustness is substantially better than those transformed from l2-norm certified robustness.
review_title: null

Meta-review: Thank you for your submission to ICLR.  The reviewers ultimately have mixed opinions on this paper, but reading in a bit more depth I don't feel that the critical comments raised by the sole negative reviewer really raise valid points.  Specifically, the fact that this reviewer directly asks e.g. for comparisons to Levine and Feiz 2019, when the paper (before its revisions) contains an entire section devoted to exactly this comparison, strikes me as not sufficient for a thorough review.

However, while I'm thus going to recommend the paper for acceptance (it does present a notable, if somewhat minor, advance upon the state of the art in randomized smoothing), I also feel the paper is generally rather borderline for more straightforward reasons.  Specifically, given the _very_ narrow focus of the proposed improvements (improvements to the bounds of randomized smoothing, for L0 perturbations, for Top-k accuracy), I ultimately don't think the paper presents that significant an advance in the field.  The paper could go other way, thought definitely not doing so due to the issues that the sole critical reviewer takes.
Decision: Accept (Poster)