Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a smoothing technique to perform adversarial training, such that the trained model is robust to small $l_2$ perturbations in the input. The major contribution is that the proposed method is applicable to a wide range of distance metrics. The idea of computing the minimum enclosing ball is also a very interesting idea, and I believe similar idea can be used to smoothing based optimization. 
main_review: Pros: 
1. This paper provides not only a theoretical justification of the proposed method but also an algorithm that can be implemented and used in practice. 

Cons: 
1. There is no description on the distribution of the input perturbation $x-x'$. It only says $||x-x'||_2 \le \epsilon_1$. Is the noise uniformly distributed into all the pixels or concentrated in a local region. Since the Guassian smoothing is used, it is natural to assume that the proposed method only works when the input image is perturbed by a white noise, unless additional experiments show that the proposed method also works for concentrated perturbations. In recent years, there are new adversarial attack methods, e.g., square attack,  that generate concentrated perturbations to fool an image classifier. Thus, it is important to understand what kind of perturbations the proposed method can handle. 

2. In the examples using pre-trained models, they authors trained the base models on data with added noises to make them more robust to input perturbations. My understanding is that this is not part of the proposed smoothing technique. For those examples, it is not clear which part (noise injection or smoothing) plays a more important role in making a robust model. An ablation study on this would be helpful. 

3. It's not clear how to choose the value $h$ in $\epsilon_1 = h \sigma$ on Line 241. The authors claim, in Line 246, that the increasing of $h$ improves the quality of the certificates. Does it mean that I should use a very large $h$? In practice, we usually assume we know $\epsilon_1$ and question is how to find an appropriate $\sigma$ so that we can get the best certificates (smallest $\epsilon_2$). I don't know whether this is the setting considered in this paper. 

4. There is a little abuse of notation that cause some confusion. For example, is $\sigma$ in Line 237 the same as $\sigma$ in Line 241? Is the constant $h$ in Line 241 the same as the $h$ in Line 96? I think they are all different. If so, it would be better to use different notations. 

In summary, even though the authors proposed a promising idea, there is a lack of ablation study to demonstrate the effectiveness of the method. I would be happy to increase my rating if the above concerns are addressed. 




limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to extend certifiable robustness methods based on randomized smoothing into the situation when the output space is a general metric space. The basic idea is to output the center of the smallest ball in the output space that can enclose half the probability mass of the output distribution with Gaussian input.
main_review: Originality: The paper is based on randomized smoothing methods but focuses on a new setting where the output space is a general metric space. 

Quality: The proposed method is interesting and suitable for many situations. It will be better if the authors can explain why the proposed method will work without requiring the output of the base classifier to be bounded, because most of the previous randomized smoothing approaches usually rely on the assumption that the output is bounded (in [0, 1]). 

Clarity: This paper is well written.

Significance: The setting considered in this paper is potential, however, the experiments results in the paper is limited. The reviewer would like to encourage the authors to add more examples (maybe as future work) to showcase the usage of certifying in a metric space.

---
Update after rebuttal:
The rebuttal provides more detailed explanations of the paper which the reviewer suggests should be added to the paper. And I'll keep my score as weak accept.
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors extends randomized smoothing, originally developed for classifiers, to functions which map inputs to a general metric space. The extension seems intuitive but is technically challenging. The authors develop tractable, statistical methods both for finding the smooth prediction as well as computing the certificates. Various experiments are conducted to highlight its flexibility in different metrics and scenarios, such as Jaccard distance w.r.t. face detection, total variation distance w.r.t. dimension reduction, and angular distance for image reconstruction. 
main_review: 1. Well-executed statistical methods for deriving and computing the certificates of robustness. It is not clear how tight the certificate is, though. 

2. It is not clear to me how to choose $\Delta$. How exactly to select $\Delta_1$ appropriately so the process succeeds easily (as written in line 161)? Can the user optimize $\Delta$ to improve the certificate (given the same smoothed model)?

3. I think line 107 and the first part of Section 3.2 can be written in a much more clear way by writing the "classifier" down explicitly. For example, you can write it as something like $P(\mathbb{I}(f(x + \delta) \in B))$ and it will be clear that $\mathbb{I}(f(x + \delta) \in B)$ is a classifier so you can apply the result from (Cohen et al. 2019). 

4. Theorem 1 is very clean, highlighting how the certificate is derived in a high-level, ideal scenario, but since it is very similar to Theorem 2 and Theorem 1 is not really used, I wonder whether it is possible to simplify this part. 

5. The derivation of the certificate is not very clean, with some details missing / hiding in the Appendix. In the Appendix, since there is no page limitation, I suggest the authors to write every step in detail so as to make this paper self-contained. For example, first writing Hoeffding's inequality and DKW inequality down and then showing how the inequalities are applied can help the readers understand the proof. 

6. The problem is not strongly motivated. It is not clear how severe current systems would fail and what the consequences would be in the context considered in this paper. For example, how non-robust can a model without smoothing behaves for dimension reduction? Even if it is indeed not very robust, what would be the real world consequence? Based on the writing, the authors only indicate the existence of adversarial examples and motivate robustness for face recognition, but it is not really clear how bad existing methods are. 

In contrast, it is very clear how bad and imperceptible adversarial example can be in image classifiers, and the consequence is trivial since many mission-critical problem (e.g., face identification) are formulated as classification problems. The contribution of this paper is currently very limited to its technical discovery due to this reason. 

7. In addition, there is no empirical comparison to existing models. Even though this work might be the first work for certified robustness w.r.t. metric space outputs, the authors can still compare it with vanilla models without smoothing, and show that the vanilla model would fail (i.e. finding an adversarial example) under the certified region given by the smoothed model. Clearly the authors can run simple gradient methods to find adversarial examples for total variation distance and angular distance. 

8. Lots of space are wasted for large figures in experiment sections and simple concepts (e.g., how cosine is computed). I suggest the authors to shrink figure sizes and replace trivial concepts with technical details in the proofs to make the method more understandable. 

9. Nevertheless, the paper still seems technically solid (if the proof are indeed correct), and the problem seems new and interesting (although the significance is questionable), I will recommend this paper for marginally above the acceptance threshold. 

Minor:
In line 103 and 104, I think it should be $h(x + \delta)$ and $h(x' + \delta)$. 

Disclaimer:
I did not read all the proofs in the Appendix. 
limitations_and_societal_impact: There seems no immediate negative societal impacts. The authors could also discuss potential methods that would improve the tightness of their method.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes an extension to randomized smoothing to certify robustness of functions over more general metric spaces by finding the center of the smallest ball which contains at least half of the output of a set of points. They approximate this center by finding the point with the smallest median distance to the other points.
main_review: I think this paper feels a bit like a solution in search of a problem.

I've seen a lot of work take randomized smoothing and do some small change to apply it to a slightly different setting, without presenting much work that seems truly novel. These sorts of works are worth sharing, but I don't personally feel they're worth publishing individually at a top conference. I don't believe that smoothing over general metric spaces is useless, and of course I know that the authors had to do some work to bridge the gap from A to B---hence I feel the contribution does have merit. But ultimately this paper presents a very minor development necessary to apply randomized smoothing to [slightly new setting X that no one has yet staked a claim on].

The presentation is decent. The experiments are decent. The math is trivial, but fine. This is the only meaningful summary I feel I can give on this work: it is technically correct, but not insightful and the math is trivial. So I guess the question is, what is the expectation for an accepted publication? This is a subjective question. I think it should be more than just a stamp of approval that the math is technically correct, so while I don't think this work is bad, I would not recommend publication.

Additional notes:

* Line 39 is not correct, randomized smoothing was not first studied by Cohen et al. The idea of injecting noise a la differential privacy is due to [1], and the formulation in its current form was first suggested in [2].

* Are the authors aware that smoothing a bounded function with Gaussian noise already naturally induces certified robustness in the form of Lipschitzness? This is known as the Weierstrass transform, see Appendix A of [3]. I'm not 100% sure but I think this could serve as a (much faster, simple) baseline to compare when evaluating bounded functions such as IOU?

[1] Certified Robustness to Adversarial Examples with Differential Privacy. Lecuyer et al. 2018

[2] Certified Adversarial Robustness with Additive Noise. Li et al. 2019 (this paper was originally called "Second-Order Adversarial Attack and Certifiable Robustness" and was first posted to arXiv in 2018).

[3] Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. Salman et al. 2019


---------------------
**Update post rebuttal**

The authors and I had some fruitful discussion. However, my feeling that the novelty and significance of the submission are below the bar for publication remains. I think this is an ok idea, but the work itself just isn't a paper's worth of material. I encourage the authors to further explore this idea; fleshed out with additional experiments, more finetuned theoretical analyses, or other improvements I expect this could be a reasonable publication.
limitations_and_societal_impact: Sure
review_title: null

Meta-review: Thank you for your submission to NeurIPS.  The reviewers and I are all in agreement that the proposed work presents a nice (if incremental, at least from a technical perspective), extension to randomize smoothing, to apply to more general output spaces than previous approaches.  The results are technically sound, even if by no means represent a foundational breakthrough, and the experiments illustrate the potential usefulness of the approach.  And the authors did a great job during the response period discussing the issues raised by the reviewers and offering further potential benefits of the approach.

The majority of the discussion centered around the question of whether such a result is substantial enough (from a philosophical standpoint) to warrant publication at NeurIPS.  And in this setting, I want to make two points.  First, I think it's entirely appropriate for the reviewer to bring up the point in this manner.  Paper selection for NeurIPS _is_ ultimately about making subjective (rather than just factual) evaluations of papers, and it's entirely appropriate for the reviewer to highlight their concerns about the fundamental novelty and perceived impact of the work.  Indeed, it's far preferable to bring it up in an honest and frank manner (and engage fully with the reviewers afterward in discussion), than to try to couch this fundamental concern in the veil of minor technical issues with the paper (which is too often the standard in reviews).  If there are questions about a paper's significance, it can and should be brought up in the manner.  And second, I must say that I agree to some extent with what this reviewer is saying: there _is_ an extent to which the paper seems to be extending randomized smoothing to "one more domain".  And the other three reviewers, while being positive, are only minorly so, and weren't substantially swayed by the author response.

Despite this, however, I am going to recommend the paper be accepted.  While I'm sympathetic to the points that the negative reviewer makes, ultimately I think that rejecting an otherwise-universally-recommended-to-be-accepted paper on the grounds of perceived significance be an incorrect decision, given that it's such a subjective quality.  My own reading of the paper is that it presents a practically-valuable extension to randomized smoothing for problems beyond classification, using technically sound approaches.  Although the methodology may not be the most fundamentally groundbreaking, it covers a topic of likely interest to a wide variety of practitioners who may be considering using randomized smoothing, and hence has a notable value for the field.  Given all this, I believe the paper does meet the bar for NeurIPS despite the ultimate persisting disagreement between reviewers.
Decision: Accept (Poster)