Randomized smoothing, which was recently proved to be a certified defensive technique, has received considerable attention due to its scalability to large datasets and neural networks. However, several important questions still remain unanswered in the existing frameworks, such as (i) whether Gaussian mechanism is an optimal choice for certifying 2 -normed robustness, and (ii) whether randomized smoothing can certify ∞ -normed robustness (on high-dimensional datasets like ImageNet). To answer these questions, we introduce a unified and selfcontained framework to study randomized smoothing-based certified defenses, where we mainly focus on the two most popular norms in adversarial machine learning, i.e., 2 and ∞ norm. We answer the above two questions by first demonstrating that Gaussian mechanism and Exponential mechanism are the (near) optimal options to certify the 2 and ∞ -normed robustness. We further show that the largest ∞ radius certified by randomized smoothing is upper bounded by
where d is the dimensionality of the data. This theoretical finding suggests that certifying ∞ -normed robustness by randomized smoothing may not be scalable to high-dimensional data. The veracity of our framework and analysis is verified by extensive evaluations on CIFAR10 and ImageNet.
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.