Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper provides a random smoothing technique for L1 perturbation and proves the tightness results for binary classification case. Overall, there are some new results in this paper -- establishing a new certificate bounds for L1 perturbation model. However, I have several concerns about whether this contribution is significant enough: 

Random smoothing has been studied extensively recently and the proof technique in this paper is not so different from previous papers (Cohen et al, Li et al). Also, there were L0 perturbation bounds proposed by (Leet et al). Therefore, although I agree that a tighter certified bound compared to (Lecuyer et al) is new, the paper seems to be a bit incremental. It will be more interesting to see if the proposed technique/theorem can be used for a wider range of norms. 

Also, it may be more interesting to add some discussions about why L1 perturbation is important for image classification (is it more human-imperceptible?)

=======

I have checked the rebuttal and other reviewers' comments. Although there are interesting components in this paper, I do agree that the paper is incremental given that many random smoothing methods have been proposed recently for L2, L_infty norms. Therefore I think this is a borderline case and will be ok with rejection. 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: Summary.

The authors propose a new certified classifier in \ell_1 norm that is tight. That is to say, upon smoothing a given classifier f with Laplacian noise, a smoothed version of that classifier (probabilistic maximum majority vote) is certified with a radius measured in \ell_1 norm. The authors show that this bound is tight for binary classifiers. These results are complementary to Cohen et al. results.

Major comments.

1) The major contribution of this paper is the tightness under the \ell_1 norm for a binary classifier. I do not find this particularly significant. The question is of what value is such a result other than a mathematical exercise. For instance a good justification that the paper is lacking could be one where authors show that their radius is indeed tighter than all other works. The paper still lacks this (I will elaborate on this later), although, their bounds are indeed tighter than Lecure's et al. Since it is not clear whether or not the new certified smoothed classifier has indeed the largest radius among all other works, then at least a justification for why would one prefer a Laplacian noise of a Gaussian noise. Why is Gaussian smoothing sufficient for this purpose given that we do not know for sure that the radius is larger?  What value/advantages does this add? The authors motivate their work by saying deriving the tightest \ell_1 is difficult due to the "asymmetry"  of the norm. While I do agree on this; however, this is not enough motivation as we we are doing doing abstract maths here.

The new derived radius is not really comparable to the Gaussian radius with \ell_2 radius and this is my major concern. By norm equivalence, we have that \ell_2 \leq \ell_1 \leq \sqrt{n} \ell_2 where n is the dimension. That is to say that the radius computed with \ell_1 is larger than the \ell_2 in some cases by a square root of dimension. The authors can correct me on this if I'm wrong, but for a fair comparison in worst case sense the radius of Cohen et al. should be scaled by \sqrt{n}. In such a scenario, it is really difficult to understand when does it make sense to tackle such a smoothing technique as opposed to Gaussian smoothing.

I would not have asked the authors about such a question if the authors derived generic radius under \ell_p smoothing (which is difficult of course). To this end, I believe since the motivation is not clear nor the results are generic enough, I find the work incremental specifically after noting that the radius can be deduced from the work of Li et al. where the main contribution here is the tightness of the radius for a binary classifier.


Moreover, I believe the paper still requires some polishing in terms of writing and presentation.

Some more comments.

I believe the paper can benefit from some rewriting. Here is a list of things the authors can do to improve the paper.

1) Define what M is, page 3 "and it is easy to see that M is a mixed random variable". I believe the authors meant T(x).
2) The figures are hardly readable. For instance, authors can perhaps increase the legend's font size in figures 4. Also the chosen colors are suboptimal (perhaps the line width of the plots) should be increased. 
3) The section below Theorem 3 should be moved up to before Theorem 3 as this discusses the proof of Theorem 2. Once a Theorem is presented, the proof sketch should follow.
4) Experiments on the undefended classifier has to be in Figures 6  7 and 8.
5) Lastly, why are comparison between Cohen et. al. and Lecuyer et. al. in Figure 6 inconsistent with Figure 5 of Cohen et al.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: In this paper, the author derived a tight ell_1, which is not the symmetric norm, robustness certificates under isotropic Laplace distributions. Experimentally, the authors showed that the deep networks smoothed 
by Laplace distributions yield the state-of-the-art certified robustness in ell_1 norm on the CIFAR-10 
and ImageNet. To find the ell_1 certificate, the authors first identified the tight robustness certificate, for attacking the model in one particular direction, say the first direction. To show that any other perturbation directions cannot lead to a worse result, the authors convert the d dimensional likelihood function into a one-dimensional function, and the authors used relaxation for different perturbations and show that the worst-case result is bounded by the previously identified direction.  However, I have the following concerns about this work:

1. Theoretically, the authors only showed the certificate is tight for binary classification. I would suggest
the author change their claim in the abstract.

2. What is M on page 3 which is used without definition after definition 1?

3. Can you give a concrete continuous probability distribution that leads to the scenario in Fig.~3?

4. Can you extend the analysis to a multi-class classification scenario?

5. Besides randomized smoothing on the input images, recently Wang et al showed that randomize the deep nets can
also improve the deep nets and they gave it a nice theoretical interpretation. Here is the reference: Bao Wang, Binjie Yuan, Zuoqiang Shi, Stanley J. Osher. ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies, arXiv:1811.10745, NeurIPS, 2019

Overall, since this work is a straightforward integration of some existing work, I think this
paper lack novelty. Please address the above questions in rebuttal.
review_title: Official Blind Review #1

Meta-review: After reading the author's response, all the reviewers agree that this paper is an incremental work. The presentation need to be polished before publish.
Decision: Reject