Robustness is an important property to guarantee the security of machine learning models. It has recently been demonstrated that strong robustness certificates can be obtained on ensemble classifiers generated by input randomization. However, tight robustness certificates are only known for symmetric norms including 0 and 2 , while for asymmetric norms like 1 , the existing techniques do not apply. By converting the likelihood ratio into a one dimensional mixed random variable, we derive the first tight 1 robustness certificate under isotropic Laplace distributions in binary case. Empirically, the deep networks smoothed by Laplace distributions yield the state-of-the-art certified robustness in 1 norm on CIFAR-10 and ImageNet.
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.