Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper extends existing work on certified robustness using smoothed classifier.  
The fundamental contribution is a framework that allows for arbitrary smoothing measure, in which certificates can be obtained by convex optimization.  
A good number of technical contributions
Framework for certificate under arbitrary smoothing measure -> Theorem 1, and proof in A.4 (good use of duality)
Full calculation/result of certificates under different divergneces in Table 1.
Reasonable set of empirical evidence. 

Overall a lot of good things to be said, below are some questions/comments that could improve the paper:
*Technical*
Personally, I cannot get a lot of value out of the distinction between full-information and information-limited certification.  It’d be great if I can get some clarification on this.  
*Experiments*
Generally, more details of the experiments should be included.  
How are the convex optimization problems actually solved (e.g., what methods/tools)?  
How much more computational overhead is there?
Oddly, seems like we’re missing CIFAR10 results completely. 

Sec 5.1., 
What does each dot in Figure 3a represent?
Sec 5.2, 
Somewhat strangely, Figure 3b is results on l0 perturbation, but not l2.  What happens for l2 when we use M>1?  How does this compare to other extensions (likely the SOTA) like [1]?
Sec 5.3,
It is unclear from the writing whether the comparisons to previous works were done on the same ResNet architecutre with the same clean accuracy.  Please clarify. 
I’m not sure why we need the Librispeech results.  It’s not motivated clearly.  Also, from writing it seems the adversary zeros out a segment.  It’s unclear if this is a reasonable kind of attack to expect on speech.  If I block out a segment of the speaker, we probably don’t expect any system to do well on speaker recognition.  I suggest removing this result, or somehow make it a lot more better motivated/conducted.  Clarify if I missed reasons why simply showing your method works on speech is impressive.

Here are suggestions on writing:
Contribution --- in both the abstract and introduction, the experimental results should be stated clearer.  Be more specific, e.g., “Show SOTA certified l2 robustness on X,Y,Z, establish first certified robustness on Librispeech, and first results on certified l0, l1 robustness on A,B,C.”
More broadly in the introduction, please motivate why “adversarial attacks as measured by other smoothing measure is important”.  Past studies focus on l2-norm not just because they are do-able, but also white noise (which is naturally measured by l2-norm) is something to expect in practice.  Justify why l0, l1 would also be important.

I recommend accepting this paper, but would do so with more passion if some of the comments/questions can be addressed.

Best,

Reference:
[1] https://arxiv.org/abs/1906.04584

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: Summary: This submission proposes a unified framework for black-box adversarial certification. Based on cohen's and lee's result, it extends the \lambda_TV distance to more general f-divergence. Besides, some other techniques, e.g. reference distribution, are also included in the framework. For L_0 and L_1 perturbation, the proposed framework comes to better results than all the related methods.

Strengths:
[+] Detailed analysis and theorem.
[+] Describing the background and conclusions clearly.

Weaknesses:
[-] In the experiment section, for ImageNet, baselines use ResNet-50 but the authors use ResNet-152. I wonder whether this is fair enough.
[-] Renyi divergence is not a proper f-divergence. Therefore, maybe the title should be changed.
[-] The theorem part contains too many details and some important parts (e.g. tightness) are in appendix. It should be re-organized.

Questions:
[.] In Appendix A.7, Lagrangian strong-duality has been used to show the tightness, but I wonder whether the tightness holds for any kind f-divergence? If the authors can write down some theorem about the tightness, it will be better.

p.s. Could you give me some quick responses to my questions (e.g. ResNet-152 v.s. ResNet-50) ? Once you convince me, I would revise the score to 6. If not, I will turn down the score to 3. 
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper introduces a generalization of the randomized smoothing approach for certifying robustness of black-box classifiers, allowing the smoothing measure to be an arbitrary distribution (whereas previous work almost exclusively focused on Gaussian noise), and facilitating the certification with respect to different metrics under the same framework.

Given the wide interest in certified robustness based on randomized smoothing, the generalizations considered in this paper could have a high potential. I found the motivation, the definition of the framework and the statement of the main theoretical results, up to Section 3.2, very clear. The following sections were not as well organized, in my opinion, and need improvement. In particular, I found it not very clear how the framework can applied to recover previous results, in particular the results from Cohen et al. (2019). All the ingredients seem to be there, among Theorem 3, the result from Balle & Wang (2018), and Corollary 5, but the arguments could be presented in a better organized way.

What I also found is missing is a clear descriptions of practical algorithms for applying the framework. Again, most of the ingredients seem to be there (e.g. Table 1 in the main body, Lemma 6 as well as the discussion about sampling mechanism in the Appendix), but they are not well organized. Presumably, the same statistical methodology as in Cohen et al. is used to obtain estimates of theta_a and theta_b, but this doesn't seem to be clearly stated anywhere. How is certification practically performed for intersections of contraint sets as introduced at the end of section 2? How the full-information certification can be applied based on empirical estimates is unclear to me, too.

Finally, the description of the experiments need improvements: For instance, in Section 5.1, which smoothing measure was used? Was the ResNet classifier trained using samples from this measure? Which sets of f-divergences were used? What does Figure 3 (a) exactly show? Do the blue points correspond to the 50 data samples? The number of random samples for computing empirical estimates and the confidence bounds are missing.
In Figure 4 (a), as the l_0 norm counts the number of altered pixels I don't understand why the certified accuracy varies e.g. for epsilon *between* 0 and 1.
The experiment on the Librispeech model seems interesting, but the paper does not contain sufficient information to understand and assess the experimental set-up or the results.

In summary, while I believe that the generalizations proposed in this paper have potential, in its present form the manuscript doesn't describe clearly and accurately enough how the framework can be applied to recover previous theoretical results or perform certification in practice.

----------

I acknowledge I have read the authors' response. As it addresses my main concerns I have changed my rating from "weak reject" to "weak accept".

review_title: Official Blind Review #1

Meta-review: This submission proposes a black-box method for certifying the robustness of smoothed classifiers in the presence of adversarial perturbations. This work goes beyond previous works in certifying robustness for arbitrary smoothing measures.

Strengths:
-Sound formulation and theoretical justification to tackle an important problem.

Weaknesses
-Experimental comparison was at times not fair.
-The presentation and writing could be improved.

These two weaknesses were sufficiently addressed during the discussion. All reviewers recommend acceptance.
Decision: Accept (Poster)