Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors aim to improve previous works on randomized smoothing by extending the analysis to allow smoothing measures with bounded support.
main_review: The idea of this paper is to use analytic tools to enable randomized smoothing with bounded smoothing distributions, mainly uniform distribution within a symmetric Lp ball, similar to Gaussian and Laplacian distribution in previous works.

While the motivation is good, the empirical performance of the uniformly smoothed classifiers s are much worse than the Gaussian smoothed classifier. It’s worth mentioning that this should be expected as previous work has drawn conclusions that most i.i.d smoothing distributions suffer from the curse of dimensionality [1]. More importantly, in Section 5 of [1], it has been shown that uniform distributions suffer from the curse of dimensionality, in the sense that the certifiable radius is upper bounded by a factor of $(1/d^{1-1/p}$, where $d$ Is the dimensions and $p$ Is for the corresponding $L_p$ measure.

In some sense, [1] has shown that uniform distributions can be used for randomized smoothing, and the fact that it’s not a good choice.

[1] Kumar, Aounon, et al. "Curse of dimensionality on randomized smoothing for certifiable robustness." International Conference on Machine Learning. PMLR, 2020.
summary_of_the_review: While the analytic efforts in this paper are both deep and comprehensive, the problem the authors try to solve has been studied with a quite decisive and general conclusion. Considering the overlaps, I cannot recommend accepting this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a framework based on Wasserstein distance and total variance distance relaxation as well as Lagrange duality to deal with the analysis of bounded support set smoothing measures. The experimental results show the relative incapability of bounded support set smoothing measures compared with Gaussian smoothing measures.
main_review: **Strengths**

The theoretical analysis is comprehensive and sound.

**Weakness**
1. There is a huge gap between the theoretical analysis and experimental results. Around 10 Theorems proposed in the paper but I'm not sure whether all of them are necessary yet increase the reading difficulty.

2. Algorithm 1 is unnecessary since it's almost the same as existing randomized smoothing based algorithms.

3. The certified bounds in experimental parts like in Figure 2 and 3 are very trivial. I understand that the results are given by a natural trained ResNet-110, but the certified accuracy on robust trained models is also significant but missing at all in the paper. Moreover, it looks like the proposed method does support robust training but there are no experimental results shown here.

4. The paper claimed multiple times on the efficiency of the proposed compared with Dvijotham et al. (2020) but considering Dvijotham et al. (2020) has experimental results on the ImageNet dataset, it would be more convincing to add experiments on such large-scale datasets. Also, consider most conventional randomized smoothing based methods have constant computation time, so I think the author should turn down the statement "an improvement upon the state-of-the-art methods in terms of the computation time" since actually there is only one other method (Dvijotham et al. (2020)) you mentioned here.

5. No comparison experiment with conventional randomized smoothing based methods and a very related work is missing:
 Yang, Greg, et al. "Randomized smoothing of all shapes and sizes." International Conference on Machine Learning. PMLR, 2020.

summary_of_the_review: I think the current version of the paper is not well-ready to ICLR quality, there are multiple missing parts in related work and experiments sections.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors provide robustness certification results for smoothed classifiers. Specifically, the considered setting follows that of Dvijotham (2020) except the base smoothing distribution is specified to have bounded support, and the relaxation follows from an intersection of Wasserstein and TV balls. Under this setting, much of the technical machinery describes which Wasserstein and TV balls are needed to cover these bounded-support smoothing distributions.
main_review: **Strengths:** 
The paper is well organized and clearly explains the approach considered. The work is technically impressive and involves some fairly complicated derivations. The proposed approach is significantly more efficient that Dvijotham's approach. There are several results here, though sadly, many of them are negative in nature.

**Weaknesses:**
A primary downfall of this work is the motivation. It is unclear under what circumstances the designer of a robustness certificate does not have control of the smoothing distribution. The standard and accepted setting is that we desire a classifier that is robust to a specified threat model, and we are allowed to choose whichever smoothing distribution we like to achieve this goal. It is not well motivated why the opposite question should be asked: "how can one apply the full-information robust certification approach of Dvijotham when the smoothing distribution is fixed a priori?". Without such a motivation, the theorems read like a laundry list of smoothing distributions for which we can prove properties, instead of a series of hard-fought and significant contributions.

Additionally, the experiments section is unsatisfying. While it is true that no other works consider uniform distributions when smoothing, no mention is paid to the comparison of Lp-robustness certificates against competing approaches that use the same base classifier (but possibly different smoothing distributions). Is this because the uniform smoothing distribution vastly underperforms when compared to these settings?

**Other notes:**
- I've never seen "total variation distance" referred to as "total variance distance." Maybe this is valid, but it is certainly nonstandard
- The authors should probably cite Yang et al which describes optimal smoothing distributions to attain Lp robustness.

summary_of_the_review: While technically very sound, this work faces serious problems regarding motivation and provides several negative-seeming results regarding smoothing using uniform distributions. I do not recommend for acceptance, but could raise my score to borderline if a convincing argument of motivation is provided.
review_title: null

Meta-review: Authors study robustness properties of arbitrary smoothing measures with bounded support using Wasserstein distance and total variation distance. Reviewers pointed out several weaknesses about this work. In particular, they mentioned the paper is not well-organized, comparison with prior work is lacking, the conclusion of the theoretical analysis is not novel and the experiments are not comprehensive. I suggest authors to take these comments into account in improving their work.
Decision: Reject