Randomized classifiers have been shown to provide a promising approach for achieving certified robustness against adversarial attacks in deep learning. However, most existing methods only leverage Gaussian smoothing noise and only work for 2 perturbation. We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks, from a unified variational optimization perspective. Our new framework allows us to identify a key trade-off between accuracy and robustness via designing smoothing distributions, helping to design two new families of non-Gaussian smoothing distributions that work more efficiently for 2 and ∞ attacks, respectively. Our proposed methods achieve better results than previous works and provide a new perspective on randomized smoothing certification.
Summary:
This paper investigates the choice of noise distributions for smoothing an arbitrary classifier for defending against adversarial attacks.  The paper focuses on the two major adversaries: \ell_2 adversaries and \ell_\infty adversaries. Theorem 1 quantifies the tradeoff between the choice of smoothing distribution which (1) has clean accuracy close to the original classifier and (2) promotes the smoothness of smoothed classifier (and hence adversarial accuracy).  For the \ell_2 adversary, the paper argues that Gaussian distribution is not the right choice, because the distribution is concentrated on the spherical shell around the x. Instead, the authors propose using a new family of distributions, with the norm square  (p_{|z|_2^2}) following the scaled \chi^2 distribution with degree d-k (Eq. 8). This allows an extra degree of freedom, and setting k=0 recovers the Gaussian distribution. For \ell_\infty perturbations, the paper suggests another family of distributions combining the \ell_2 and \ell_\infty norm (Eq. 9), and argues that it outperforms the natural choice of \ell_\infty norm-based distributions (Eq. 10).
I think the paper should be rejected because (1) For \ell_2 perturbations, there is no major difference between this new family of distributions (d-k \chi^2) and a Gaussian with different variance. (2) For \ell_\infty distributions, the motivation of mixed norm distributions (Eq. 9) over \ell_\infty based distributions (Eq. 10) is not very clear. (3) The experimental evidence is also weak (see below).
Main arguments:
1. The distribution of the norm \|z\|_2 in Eq. (8) would be concentrated on a thin spherical shell of radius about \sqrt{d-k}\sigma. As the Gaussian distribution with standard deviation \sigma' is supported on a shell of radius about \sqrt{d} \sigma', for each (k,\sigma) in the family of Eq. 8, there is an equivalent Gaussian with appropriate \sigma' (Theorem 3 now just compares the radius of the spherical shell). Therefore, I don't see the benefit of this extra degree of freedom of k: the noise distribution is again a "soap bubble" of a different radius. Thus, a grid search over \sigma' for a Gaussian should be the same as a grid search over (k,\sigma) in Eq. 8.
Even the experimental experiments are a marginal improvement over Cohen et al.  I don't see why the value of (k,\sigma) was not provided in Table 1 and only \sigma was provided. Also, the table of Cohen et al. was only calculated for specific values of \sigma for Gaussian distributions (0.12, 0.25, 0.5, 1.00). For a fair comparison, comparable values of \sigma's must be calculated, and then the best choice should be selected. 
2. In the light of previous arguments, I don't think the choice of Eq. (9) or Eq. (10) is well motivated. 
Why not smooth it with a cube of appropriate radius? Also, not enough experimental details are provided for Table 3.  Salman et al. (2019) reports the accuracy of 68.2% for \ell_infty perturbations (Table 3, Salman et al. (2019)), whereas the value reported in your Table 3 for at the same radius is 58%. Is it a typo? In any case, the values reported for the proposed model in Table 3 are only a marginal improvement over Figure 1 (left) in Salman et al. (2019), just going by the trivial \ell_2 to \ell_\infty certificate.
Other areas for improvement:
1. The paper contains numerous grammatical errors, confusing statements, and nonstandard phrases.  For example: (i) more less robust, (ii) black start, (iii) pointy points, etc.  I suggest that the authors spend more time clarifying their manuscript.
2. The paragraph starting with "Trade-off between Accuracy and Robustness": I think this paragraph should be reworded for clarification.  It is not robustness but rather the lack thereof -- say, sensitivity.
3. On p.5, why was the toy classifier sphere-based? The toughest classifier for Gaussian smoothing (the one achieving the lower bound for Gaussian smoothing) is actually a linear classifier.