Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper's core contribution is to extend randomized smoothing to a setting where the smoothing depends on the input data. That is, the variance of the smoothing distribution is not constant anymore but depends on the input. To ensure a proper certificate, the authors propose some memory-based technique (which essentially changes the final classifier based on the observed input data so far).
main_review: The paper tackles an important problem and aims to address one major limitation of the randomized smoothing framework: the constant variance of the (Gaussian) smoothing distribution. However, I am some concerns about the proposed approach:

1) The core idea of the approach is to optimize the sigma according to Eq. (2). However, this optimization principle assumes the constant-sigma set-up. Thus, I don't see why optimizing this equation is really principled.

Indeed, as described in Sec. 3.5, the resulting radius does NOT guarantee certification. (Side note: I find it a bit surprising to call the solution then the "radius of certification" even though it does not lead to a valid certification radius.)

The memory-based certification looks like an ad-hoc fix to this problem. This, however, leads to multiple further problems as described in the following.

2) The memory-based certification is changing the predictions of the (smooth) classifier. Thus, the final certificate is actually NOT a certificate for the original (smooth) classifier g -- but only for some adaptively changing classifier. Therefore, the original problem setting is actually never solved by the approach.

Moreover: Why should Eq. (2) make any sense for this classifier? Based on my understanding the memory-based principle could theoretically be used with any real number used as a radius. Thus, one could just randomly assign "radii of certification" to a new input sample. Put differently: The memory-based certificate is not really making any use of worst-case classifiers or alike.

Finally, since the certificate is given for this "changing classifier", I highly question the (practical) use of the certificate at all. The runtime complexity of the classifier -- and not just the certificate -- scales linearly with the number of samples seen. It is even worse than a KNN-classifier since one has to consider all test samples (and not only the training samples). Moreover, the outcome of the resulting (smooth) classifier will depend on the *order* how the test samples arrive. That is, the predictions might be different when a different order is used. Such behavior is very undesired for a classifier operating on iid data. 

3) Given that the method is actually certifying some other classifier, I am also wondering whether the experimental comparison provides any insights. At the end, different classifiers are considered.

summary_of_the_review: Overall, I highly question the use of the certificate. It is not certifying the actual smooth classifier as desired, but it certifies some other classifier (with highly undesired properties) in a non-scalable way. Thus, also the experimental comparison is questionable.

I am currently giving a score of 3. I might be open to increase it in case the authors clearly state that they are actually not certifying the smooth classifier. Put differently: The presentation has to be updated in various places since at the moment it is highly misleading and readers might get a wrong understanding of what is actually certified. Moreover, the authors should elaborate whether the experimental analysis is still useful or not.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This papers proposes to optimize the certified bound of randomized smoothing to get data dependent perturbations for different data. It also proposes a simple memory-based approach to certifying the resultant smooth classifier due to the lack of guarantee on the overlapping of the perturbation regions. The technique is incorporated into 3 randomized smoothing approaches, which shows improvement over existing methods in experiments.
main_review: The problem is important and the idea of this paper is interesting but seems quite simple, which simply optimizes the certifiable lower bound of randomized smoothing. I found it a big surprising that this has not been done before. Given the certifiable bound is already there, it seems there is not too much technical difficulties for this method, so I wonder why this has not been done before, given the randomized smoothing has been proposed for several years? Can the authors elaborate on this?

As far as I understand, the method actually seems to be only applicable to the l2 certification, given the bound is only for l2. So it seems a bit over claiming in the abstract that the method is generic. In addition to this, I believe there are bounds for the other norm certification, and I wonder if the proposed method can be applied to those cases? One example and missing reference is the paper by Li et al 2019: Certified Adversarial Robustness with Additive Noise. In that paper, they propose information theoretic analysis and get a more general bound (although the bound seems to be looser than the one by Cohen et al.), which can do L1 certification. I think a study for this would great improve the paper and should be performed empirically. In addition, Li et al also propose an enhanced training strategy called stability training, which is shown to be able to greatly improve the performance. I would suggest the authors to investigate that training strategy, in addition to the current ones using Cohen, smoothadv and macer.

Another comment is about the setting of the parameter n in Algorithm 1. It seems the authors only consider setting n = 1, which I think is highly inaccurate with high variance. Although the authors provide some results in the appendix with n=8, I think the study is not deep enough. More detailed studies on this parameter and the effect on the accuracy as well as the balance between training time and accurate need to be investigated.

A minor comment: the visualization in Figure 6 does not seem the provide much information. A better visualization I am looking for actually is similar to the illustration in Figure 1, but on a real case. I am expecting the decision boundary can be drawn and the optimized radiuses of different data samples can be shown as well.
summary_of_the_review: The idea of this paper is interesting and the paper itself is a solid work to improve model robustness by optimizing the certified bounds w.r.t. the noise variance. However, there are missing comparisons with existing techniques/methods, which I hope to be solved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on training robust deep neural networks. The author(s) developed a data-dependent randomized smoothing method to certify the DNN classifier. Their proposed methods are evaluated on benchmark datasets and are shown to outperform other baseline approaches. 
main_review: The paper is not in my area but I find it easy to read and follow. I agree that the making the variance of the Gaussian noise to be data-dependent has the potential to largely improve the performance of the randomized smoothing classifier. However, it is not clear to me that why maximizing the radius $R$ would be beneficial to the resulting smooth classifier. It would be better if the author(s) could provide more motivation and justification on their proposed objective function. 
summary_of_the_review: The author(s) might want to discuss in detail why it is desirable to maximize the radius $R$ in their proposed objective function.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new randomized smoothing technique to improve the robustness of models. Specifically, in the original randomized smoothing approach, we use a fixed variance parameter $\sigma$ for the Gaussian smoothing. The authors claim that this is in general suboptimal as some data samples far away from the decision boundary can be further smoothed. Motivated by this, the authors propose to optimize the smoothing parameter $\sigma$ for every data sample, by solving an optimization problem using Monte Carlo approximation and SGD. The paper also provides a simple procedure for the certification of the data dependent smooth classifier. Through extensive experiments, the paper shows the effectiveness of the proposed approach.
main_review: The paper is well written and the experiments are well developed. 

The main contribution of the paper is to adapt the smoothing parameter $\sigma$ to every input data point by maximizing the certification radius $R$. This is a natural way to improve the randomized smoothing technique. Some questions are given below.

1. If one data $x$ is close to the boundary and classified incorrectly (e.g., suppose $x_3$ in Fig.1 is classified incorrectly), then in this case optimizing the radius would actually reduce the value of $\sigma$. So will this approach apply to models that have low classification accuracy?

2. Regarding the runtime/scalability. If we apply this data-dependent randomized smoothing to perform adversarial training, it seems that we need to generate a specialized gaussian noise for every single sample at each time. In the SmoothAdv algorithm, there they can reuse the gaussian noises to corrupt a batch of samples (because $\sigma$ is fixed). Can the authors comment on the scalability of your approach?

3. The paper discusses $\ell_2^r$ certification, can the proposed approach extends to more general types of certifications?
summary_of_the_review: See the comments.
review_title: null

Meta-review: The idea to adapt the noise variance in the certification of a base classifier sounds natural and interesting, but unfortunately fundamentally flawed, as correctly pointed out by Reviewer viFi (also acknowledged in the authors' response): the author's main algorithm does not lead to any theoretical certification while the empirical fix (based on memory), however successful in one's experiment, does not rule out the possibility of failure when future test samples flood in. Incidentally, I believe this fallacy may have also answered Reviewer Xsdx's question (why this has not been done before). I agree with Reviewer viFi that the writing of this work is a bit deceptive and will require significant change. In particular, one cannot wave hands at claims on certification: you need to formally prove the memory-based empirical fix will provably certify a region for what classifier and under what assumption. Therefore, the current draft cannot be accepted. Please consider rethinking about the idea and rewriting the paper according to the reviewers' comments.
Decision: Reject