Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper presents a new method for adversarial certification using non-Gaussian noise. A new framework for certification is proposed, which allows to use different distributions compared to previous work based on Gaussian noise. From this framework, a trade-off between accuracy and robustness is identified and new distributions are proposed to obtain a better trade-off than with Gaussian noise. Using these new distributions, they re-certify models obtained in previous work.

I am hesitating between a weak reject and a weak accept. The theoretical results are interesting, showing a clear trade-off between robustness and accuracy with a new lower bound and deriving better smoothing distributions. However, the experimental results are lacking, and do not support much the proposed method. Training with this new distribution would have been a natural experiment given the argument. Moreover, the results for L_inf are partial and it would be expected to have some results for ImageNet as claimed in the introduction. I would have given an accept if the previous points had been addressed and I feel that with some more work on it, it would become an excellent paper.

Main arguments:
My main concern is about the experiments: Why were Cohen et al.’s models used instead of Salman et al.’s? Salman et al.’s have achieved better certified accuracy under the L_2 norm so it would only seem natural to use their model.
About the main results: there seems to be a discrepancy between the results reported for Cohen et al. and the original paper for both CIFAR-10 and ImageNet L2 certification. Also, the reported certified accuracy for Salman et al.’s model for L_inf on CIFAR-10 reported in the original paper is 68.2 at 2/255, which is very far from the 58 in Table 3. What is the reason for these differences?

Minor comments:
In the third paragraph, it is claimed that L_inf attacks are a stronger and more relevant type of attacks than L_2 attacks. These two different objectives cannot be compared in those terms.
Defenses such as adversarial training have not been “broken” as claimed in section 2 in the sense that the claims made in the original paper still hold true. The term broken is used for defenses in which the claimed accuracy against stronger attacks were found to be much lower than what was claimed in the original paper.
It is claimed that “if ||z||_inf is too large to exceed the region of natural images, the accuracy will be obviously rather poor”; however, the common practice is to clip to the input space bounds. How would that affect the method?

Things to improve the paper that did not impact the score:
In the first paragraph, Goodfellow et al., 2015 is cited, however, papers on adversarial attacks were published earlier than that such as Szegedy et al., 2014 or Biggio et al., 2013.
Vershynin, 2018 is cited about the distribution of a gaussian in high-dimensional spaces. However, this is a very well known result and does not need any citation (or if any, Bellman, 1961).
Typo after equation 4: ||f||_{L_p}
Typo in “Black-box Certification with Randomness” paragraph: “by convovling”
Typos in Table 2.: the columns 2.0 to 3.5 are mislabeled

review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: 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.



review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: The paper introduces an improvement to the randomized smoothing analysis in Cohen et al. (2019), using Lagrangian relaxation to achieve a more general lower bound. Using this, it considers different adversarial smoothing distributions that yield some increase in certified adversarial accuracy.

Overall assessment: While the Lagrangian relaxation idea is interesting and could yield interesting follow-up work, the paper is sloppy in several respects and needs to be tightened before it can be considered for publication.

Key issues:
1. Proof of main theorem (strong duality) is incorrect. Likely the statement itself is also incorrect. Fortunately the most important direction (lower bound) is still true, so this isn't a fatal flaw to the approach.
2. The paper makes several references (in italics) to a "fundamental trade-off between accuracy and robustness". But a fundamental trade-off means that *any* method that attains good accuracy must sacrifice robustness and vice versa; this requires a "for all" statement, i.e. a lower bound. All the paper shows is that the *particular upper bound* exhibits a trade-off (and even then, the notions of "accuracy" and "robustness" are merely interpretations of quantities in the bound; it's not clear why the robustness term in particular is tied to more standard notions of robustness).
3. The justification for why the particular smoothing distributions are good ideas is sketchy.

I elaborate on 1 and 3 below. Addressing 1-3 effectively will improve my score.

#1 (main theorem is incorrect): Claim 3 in the appendix is wrong. The fact that (delta', f') outperforms (delta-bar, f-bar) with respect to lambda* does not imply that (delta', f', lambda*) is a better solution to the primal problem, because we must take max over lambda and the maximizing lambda need not be lambda*. In particular if f' doesn't satisfy the constraint we would instead take lambda to infinity.

#3 (sketchy justification): The paper justifies a smoothing distribution that concentrates more mass around the center as follows: "This phenomenon makes it problematic to use standard Gaussian distribution for adversarial certification, because one would expect that the smoothing distribution should concentrate around the center (the original image) in order to make the smoothed classifier close to the original classifier (and hence accurate)." I don't see why we should want more mass near the center---in the limit as we move all the mass towards the center and get the original classifier, our certified bound will be terrible, so it's not clear why moving in that direction should be expected to help. Indeed, the experimental gains are minimal (1 to 3 percentage points) and on methods that were not carefully tuned, so one could imagine that the baseline method could be improved by that much just with careful tuning.

I similarly didn't understand the justification for the mixed L-inf / L-2 distribution for L-infinity verification. The main justification was "The motivation is that this allows us to allocate more probability mass along the “pointy” directions with larger`∞norm, and hence decrease the maximum distance term max δ∈B`∞,rDF(λπ0‖πδ)." This is at the very least too brief for justifying the main experimental innovation in the paper (here at least the empirical improvements are bigger, although still not huge).

Minor but related: Why is the x-axis in Figure 4 so compressed? This is also in a regime where all 3 methods fail to certify so not clear it's meaningful.

Writing comment: Change some of the Theorems to Propositions. Theorems should be for key claims in paper (there shouldn't be 4 of them in one 8-page paper).
review_title: Official Blind Review #3

Meta-review: The authors extend the framework of randomized smoothing to handle non-Gaussian smoothing distribution and use this to show that they can construct smoothed models that perform well against l2 and linf adversarial attacks. They show that the resulting framework can obtain state-of-the-art certified robustness results improving upon prior work.

While the paper contains several interesting ideas, the reviewers were concerned about several technical flaws and omissions from the paper:

1) A theorem on strong duality was incorrect in the initial version of the paper, though this was fixed in the rebuttal. However, the reasoning of the authors on the "fundamental trade-off" is specific to the particular framework they consider, and is not really a fundamental trade-off.

2) The justification for the new family of distributions constructed by the author is not very clear and the experiments only show marginal improvements over prior work. Thus, the significance of this contribution is not clear.

Some of the issues were clarified during the rebuttal, but the reviewers remained unconvinced about the above points.

Thus, the paper cannot be accepted in its current form.

Decision: Reject