Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Summary.
The authors propose a new definition for robustness of random functions. This definition is ideal for analyzing the certified robustness under randomized smoothing techniques. They analyze and show that the Gaussian smoothing is near optimal for \ell_2 smoothing as the mean maximum error is only off by a factor of log d where d is the dimension from the optimal mean maximum energy. This is the case even under a more strict definition of robustness defined as D_\infty. Moreover, the authors show that indeed smoothing with an exponential family  is optimal under D_\infty robustness metric with radius measured in \ell_\infty.



I find the paper very interesting and the approach is novel and generic. I do not have any major criticism.

Minor comments.
1) Equation 3 "D(A(x'),A(x))" >> "D_\infty(A(x'),A(x))"
2) Page 6 third line below Theorem 16. Reference of Theorem 11 should be Corollary 11.
3) The authors should report the certified accuracy of the undefended baseline classifier over varying radius in Figures 1 and 2 and 3.
4) Running experiments on ImageNet following Cohen et al. should make the paper stronger.
4) Can the authors comment on is the certified accuracy for \sigma=0.5 at radius = 0 is better than the unsmoothned classifier a sigma 1.0. I expect that the radius of certification is larger for larger sigma.
5) The authors should explain how does the new definition of robustness relate to the common robustness definitions as the one by Cohen et al.  More discussion is necessary for this and more justification. 
6) Why is the D_MR defined as maximum over $\alpha$? It seems it is only sufficient to define it as the ratio over $\alpha$. It seems that this is only needed for Theorem 8 to hold.


------------------------------------------------------------------------

After further careful read of several relevant papers, e.g. Bun et. al 2016 and the work of Dwork "Concentrated Differential Privacy", I have several questions I would like to ask for some further clarifications.



1) Showing that a network is robust under $D_{\infty}$ robustness, implies very strong results. The type of results that are common in the literature. This is since $D_{\infty}$ robustness, implies $\epsilon$ DP networks (see Lemma 3.2 and proposition 3.3 of Bun et al.). Once $\epsilon$ DP is guaranteed identical results of Lecurer et al. can be derived immediately as this implies separation in expectation (Lecurer et al.) where one can study directly the deterministic classifier $\mathbb{E}g(\mathbf{x})$ and not the random $g$ studied in this work.

2) The authors rely on the lower bounds of Bun et al. to find the average maximum energy that preserves the $D_{\infty}$ robustness (Thm 15 and 16). Authors show that indeed exponential smoothing is optimal. This is significant but the analysis was intensively based on Bun et al.


3) The relaxation to $D_{MR}$ robustness results into improvement of the dependency on the dimension to $\sqrt{d}$ instead of $d$ for under $\ell_\infty$. This should not be surprising at all and in fact is identical to the results of Bun et al. Note that the zCDP proposed by Bun et al, is a relaxed version of DP where $\epsilon$-DP for some radius $r$ implies zCDP with radius $r^2$. See proposition 3.3. Therefore, Theorem 6 and 17 are not surprising nor are they new.


4) My major concern was with the results relating to Gaussian smoothing. I do understand that since Gaussian smoothing only implies high probability result of DP which is often referred to as ($\epsilon$,$\delta$)-DP which happens to be a equivalent to zCDP proposed by Bun et. al. Therefore, I have no issues of using $D_{MR}$ to analyzing the robustness for Gaussian smoothing since it was always analyzed in the DP community with the $\epsilon,\delta$-DP and not the stronger $\epsilon$-DP. However, the statement of the result (Theorem 12) confused me vastly. Let me clarify.


Theorem 12 seems to be too good to be true. How is it possible that one can guarantee $D_{MR}$ robustness without any dimensionality dependence. Using Gaussian smoothing the $D_{MR}$ can depend on $\sqrt{\log{d}}$. While $\sqrt{\log{d}}$ may seem small; improving this to a constant in dimension is still a very big gap from $\sqrt{\log{d}}$. This may raise several questions whether one can actually find this optimal smoothing distribution. However, with a careful read of Theorem 12, the range of the input decreases as a function of $\sqrt{d}$. That is for a given range of input (independent from d), the energy in fact is NOT constant but scales with $\sqrt{d}$. In such a case, the Gaussian smoothing is now of order $\sqrt{d \log{d}}$. Now, the factor is still $\log{d}$, but now this is very different as indeed improving the Gaussian to $\sqrt{d}$ may not be of significant interest as the energy still depends in the optimal sense on $\sqrt{d}$ which does not allow it to scale for larger problems. Moreover, Cohen et al results show that with Gaussian smoothing the energy of the noise scales $\sqrt{d}$ since the noise energy $\|n\| = \mathcal{O}(\sqrt{d} \sigma)$ where $\sigma$ is std of Gaussian. Therefore, it seems that there is nothing surprising about such a result at all. The statement of the Theorem is very misleading and confusing.

Overall, I like this new approach of analyzing the random smoothed classifier; however, the poor presentation of the work and the mis-represented Theorems that seem to over claim are a major reason for my rating. In addition, the paper should be self-contained in which one should not need to read 2-3 other works to figure out the details in this work and the meaning of the several robustness metrics and their direct relations to DP and Lecuer et al. results. The statement of constant in dimension lower bound on the energy of the noise under $D\_{MR}$ was to me the major contribution; however, I found now that the statement is misleading and that in fact it is $\sqrt{d}$ reduces the contribution of the paper particularly after learning that such lower bounds are already derived in Bun et al.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: Summary of the paper's contributions:

This paper introduces two new notions of robustness for randomized classifiers, which are based on the notions of differential privacy (DP) of randomized mechanisms. Specifically, the D_\infty robustness and D_{MR} robustness of a random classifier are defined based on \epsilon-DP and \epsilon-zCDP, respectively.

The paper proves lower bounds on the noise level of a random classifier for which it can be certified D_\infty robust and D_{MR} robust. Further, it is shown that the lower bounds are achieved by random classifiers constructed using Gaussian noise and exponential noise for l_2 and l_\infty robustness, respectively.

Major criticisms: (1) The paper does not give sufficient motivation for studying D_\infty robustness and D_{MR} robustness. (2) The paper makes several unsubstantiated claims regarding the optimality of different noise models for adversarial robustness.

Detailed comments:

- All the claims made in the paper regarding the optimality of different noise models  are specific to D_\infty and D_{MR} robustness. However, they are written in a way to imply that the claims also hold for the standard l_2/l_\infty robustness which is studied in adversarial ML literature (especially in the abstract and intro section). The authors should make clear the relation between D_\infty and D_{MR} robustness and the standard notion of robustness of a classifier. Does one imply the other?

- Does the relaxed notion of robustness of a random classifier g (Definition 3) imply a robustness guarantee for the final output of the random classifier, i.e., \argmax_c P(g(x) = c) ?

- The experiments use the same setup as in Cohen et al, but the results are not compared with those in Cohen et al. It is not clear how to judge the significance of these results without comparison to any other method of evaluating robustness.

- "However, it is known that adding Gaussian noise often does not lead to \epsilon-DP, but rather (\epsilon; \delta)-DP (Dwork et al., 2014) which has an additional parameter \delta and thus is harder to be incorporated in our framework. To alleviate this issue, we employ Maximal Relative Renyi Divergence as the probability distance measurement to define another type of robustness, namely D_{MR} robustness." - This does not provide sufficient justification for studying D_{MR} robustness.

- A comparison is made between Theorem 10 & Corollary 11 in the paper to Theorem 1 in Cohen et al. However, it is not clear how the result in the paper is better or even equivalent to the one in Cohen et al. D_{MR} robustness seems to be an approximate notion of robustness, while the result in Cohen et al gives perfect robustness within a ball of a certain radius. The radius r in both papers scales linearly with \sigma. It is said that "a smaller c yields a larger r compared to Cohen et al." It is not clear why that is useful.

- In Theorem 12, each entry in x is restricted to be in the range [0, r/\sqrt{d}]. This means the l_2 norm of x cannot be more than r. Then, how is it meaningful to discuss the (2r, D_{MR}, l_2, \epsilon/2) robustness of an algorithm on this data, with the radius of the robust guarantee being 2r?

- In Theorem 12, the lower bound on the expected l_\infty norm of the random noise is shown to be independent of d, while the expected l_\infty norm for Gaussian noise scales with \sqrt{\log d}. I don't think it is correct to claim that Gaussian noise is "near" optimal from this analysis.

-  In Definition 23, it is not clear what Loss(Y||Y') is.

Suggestions for improvement:

- The authors should make it clear in the abstract that the optimality of the noise models is with regards to the newly defined notions of robustness.

- It would be worthwhile to discuss how D_\infty and D_{MR} robustness differ from standard notions of minimax robustness.

- One possible way to motivate the relaxed robustness introduced in Definition 3 is to link it to the robustness of the randomized classifier in Definition 1.

- Please consider using \left( \right) instead of ( ).

- For experiments, it would help to compare D_\infty and D_{MR} robustness alongside the standard l_2 robustness. In addition to training the network on Gaussian augmented dataset, it might be worthwhile to compare it to other baseline approaches as done in Cohen et al.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This work examines the recently proposed randomized smoothing method for certifying the robustness of neural networks. The authors explain a theoretical framework for analyzing randomized smoothing as a certification method, propose two alternative definitions of robustness (D_MR and D_inf), and prove that using Gaussian noise for smoothing is near “optimal” for L2 robustness, while using exponential noise for smoothing is optimal for L_inf robustness (the authors do this by establishing a lower bound on the noise necessary for smoothing to work). This also leads the authors to the interesting conclusion that randomized smoothing may not be scalable to high dimensional data for L_inf robustness.

In its current state, I would vote to weakly reject this paper for one key reason. The notions of robustness defined by the authors (Definitions 3/7/8) is not the same as standard adversarial robustness (Definition 2), and the authors do not explain clearly how to translate their results back to adversarial robustness. Proving results about their own version of robustness is interesting, but it must be related back to the standard notion of adversarial robustness so that the broader machine learning community can understand how the authors’ contributions fit in the literature. It may in fact be quite straightforward to relate the two notions, but I think the authors should explain how to do so clearly. I am happy to reconsider if the authors can address this (and other comments below) in a satisfactory manner.

I did not check the authors’ theoretical proofs, but I find the statements of the theorems interesting, especially the results about the maximum certifiable radius for L_inf robustness. This provides significant new insight about the fact that L_inf robustness may not be easy to certify using randomized smoothing methods. However, it is not clear to me how best to translate the authors’ results to a result for the standard notion of adversarial robustness, which I believe would be interesting to present clearly.

I would encourage the authors’ to clarify (and tone down) their statement about the “optimality” of Gaussian noise for L2 robustness. Theorem 12 provides a lower bound on the L_inf norm of the noise added, and they show that Gaussian noise is close to “optimal” in terms of expected L_inf norm. I am a bit confused as to why are we providing bounds on the L_inf norm of the added noise (especially since we are verifying L2 robustness) - in what other ways is Gaussian noise (near) optimal? Does it also have the expected lowest L2 norm? Also, why do we want the noise to have low norm? I feel that “optimal” should mean being able to prove the largest possible robust radius, and if that is not what you are proving, I would encourage you to try to avoid overclaiming.

Finally, the experimental results should also not just be in terms of D_MR robustness. Otherwise, it is hard to compare with prior work like Cohen et. al.

Some additional feedback:

- “the Lp-normed robustness” can be replaced with “Lp-norm robustness” everywhere
- Page 1, say “the Gaussian mechanism” instead of “Gaussian mechanism” (toward the end of the first paragraph)
- Table 1’s formatting can be improved (maybe have a box around the whole table)
- Theorem 12 - use “In other words” instead of “In another word”
review_title: Official Blind Review #1

Meta-review: After the rebuttal, the reviewers agree that this paper would benefit from further revisions to clarify issues regarding the motivation of the DP-based security definition,  any relationship it may have to standard definitions of privacy, and the role of dimensionality in the theoretical guarantees.
Decision: Reject