Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper suggests an extension of randomized smoothing, wherein the degree of smoothing is optimized both at training and test-time on each individual sample. At training time, the model is first "pre-trained" using a range of smoothing parameters (variance of the Gaussian perturbations), and then "fine-tuned" by selecting the variance on each sample which maximizes the verified radius. At test time, we can again select the smoothing parameter to maximize robustness.

Pros:
- Numerically, the results seem fairly strong

Cons:
- It's unclear to me whether the evaluation is fair


A few (somewhat critical) questions:

1. (Major) For the test-time procedure, this procedure selects $\sigma$ based on a computed robustness statistic. I assume that this robustness statistic uses the original image, as in other randomized smoothing approaches? (as opposed to an adversarially perturbed image). If so, this comparison seems somewhat unfair - the typical threat model is that the classifier does not get to first see the nominal image (otherwise, the classifier could cache the clean image + label, and use a nearest-neighbor lookup against its cache to handle any adversarial images.) If not, could you explain how the adversarial image is selected here?

2. What is the purpose of the balls $B$ in the section on "Predicting Procedure."? What do they add compared to computing $r^j$ directly? For what fraction of the test set is an existing $B_i$ found including the test point? (I would expect this fraction to be very small?)

3. It seems that for e.g. the SmoothAdv model trained with $\sigma = 0.25$, we should be interested in robustness with radii significantly below 0.25 (and certainly not above it). Am i misunderstanding the naming of the models?

Minor points:
- It would be interesting to see an ablation of whether the fine-tuning phase helps.
- The presentation of the algorithm could be significantly simplified (lots of notation is unnecessarily complicated, double subscripting, going into details before explaining the idea, lots of new symbols introduced throughout, etc.). The pseudocode is very helpful.

Overall:
It's clear that the authors have put significant effort into this submission, but I believe it does not currently meet the necessary bar for ICLR, though I may adjust my rating if the rebuttal satisfactorily addresses the points above. I hope some of this feedback will be useful to the authors.

EDIT: Thanks for the clarifications. Unfortunately, none of the responses are enough for me to update my rating.
One thing regarding point 1 in particular: the transductive setting seems contrived for adversarial robustness as it does not seem to correspond to a plausible threat model. It's true that in the transductive setting, the examples don't have labels, but since clean accuracy >> robust accuracy, just caching predicted labels on the clean examples is roughly as good (which can be done even if test labels are not available).

review_title: A method for adaptive smoothing parameters in randomized smoothing

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper propose a method to improve the randomized smoothing algorithm for certified robustness against adversarial attacks.
The idea is that, instead of adding the same Gaussian noise to every data points, it uses a different standard deviation for each data points. When an example is far away from the decision boundary, one can add more noise.
Pros:
- Certified robustness is an important problem in adversarial ML, and randomized smoothing is one of most promising methods.
- The proposed method is intuitive and seems to be a practical way to improve the original randomized smoothing algorithm
- Experiments show that, the certified accuracy on CIFAR-10 really increases
Cons:
- It seems to me that the proposed method is a relatively straightforward extension from the original randomized smoothing algorithm, so the technical contribution is limited.



review_title: Nice but straightforward extension of existing method

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper considers the problem of provably defense to adversarial perturbations using randomized smoothing. The authors propose sample-wise randomized smoothing -- assigning different noise levels to different samples. They also propose to first pretrain a model and then adjust the noise for higher performance based on the model’s outputs. Experiments show that proposed approach improves the performance of randomized smoothing with same noise level for small perturbations. 

Pros:
1)	The paper is well written and easy to read.
2)	The idea of sample-wise randomized smoothing is interesting, and results are reasonable.
3)	Issues with assigning arbitrary noise level to test points is well described/thought and solutions (online and batchwise) are proposed to make it compatible. 
4)	Experimental setup is comprehensive and appropriate ablation studies have been performed. 

Cons:
1)	My main concern with this work is that it is not clear to me that these ACR gains are being achieved at what cost? It appears that sample-wise randomized smoothing adds an additional computational complexity during both training and prediction/certification phases. I would like to see the train and prediction cost comparison with standard train/test, MACER, and vanilla random smooth model. This comparison will provide a better insight into the performance as on some cases, e.g., MNIST, the sample-wise RS performs pretty close to the baselines. I will argue that in the computation cost on sample-wise RS is significantly higher than the baseline robust approaches, one can simply increase the m_test in those approaches. 
2)	It will insightful to see how much gain the proposed scheme achieves with vanilla gaussian augmented models (authors only show these results with smooth adversarially trained models).
3)	Similar to adv-smooth, it will be useful to see how much gain can be achieved with: 1) pre-training, and 2) semi-supervised learning. 
4)	Results in Sec 5.2 is for online or batch setting?
5)	How does resolution of grid or \sigma_interval impact the performance (train and prediction/certification time and ACR/ACA)?

Minor:
1)	There seems to be typo in Sec 5.1: [0, 12, 0.25].

review_title: Interesting work but requires more clarifications

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes an improved sample-wise randomized smoothing technique, where the noise level is tuned for different samples, for certification of robustness. Further, it also proposes a pretrain-to-finetune methodology for training networks which are then certified via sample-wise randomized smoothing. The authors show in experiments on CIFAR and MNIST that combining their training methodology and certification methodology can sometimes improve the average certified when compared to state-of-the-art randomized smoothing techniques Smooth-Adv (Salman et. al, 2019).

I recommend a rejection because the key takeaways of the paper should be clarified and the pretrain-to-finetune framework and the allocation of regions must be explained and justified better.

The key idea of using different noise levels for different samples is intuitive and explained well in the motivation section (4.1). Furthermore, the authors show that their methodology does indeed lead to minor improvements in average certified l2-radius on Smooth-Adv for the CIFAR dataset, which is a more interesting dataset than MNIST, where the proposed technique performs similarly or slightly worse than Smooth-Adv.

However, the paper does have shortcomings in its clarity and organization. First, I think the sample-wise certification is a clear and well-motivated idea, and should be discussed as the major contribution, rather than the pretrain-to-finetune framework. Furthermore, I was confused about the allocation of regions in the prediction step of the sample-wise certification; explaining why it is necessary, and why it is better than allocating a region for every single test datapoint (which is what I thought the motivation section in 4.1 explained) would improve the paper significantly. Finally, the amount of notation in the paper should be simplified significantly, and the notation often makes the paper more confusing (and sometimes, I could not understand due to either incorrect or unclear notation). For example, the pseudocode in Algorithm 1 would have been better if the notation was simplified, and in Algorithm 2, I did not know what B_{i_j} referred to at all.

Specifically regarding the allocation of regions, I did not understand why it was necessary or led to improvements over choosing a new region for each test datapoint. Explaining it clearly, and showing an ablation study that compares using region-allocation and not using region-allocation would provide good motivation for its use.

Specifically regarding the pretrain-to-finetune framework, I have the following questions:
I saw that in Appendix C that the pretrain-to-finetune framework is necessary for the sample-wise randomized smoothing to show an improvement. Are there explanations for why sample-wise randomized smoothing does not well work by itself?

Why does it make sense to do this 2 step procedure? Why does the pre-training have to involve varying noise levels if the fine-tuning procedure already finds the optimal noise level for each sample to train with? Could the pre-training just be the same as Smooth-Adv?

How much does it matter which noise levels we choose during the pre-training phase? I noticed that the authors usually chose noise from 0.12 up to the amount that they compare to with SmoothAdv, but the reasons for this are not discussed.


Overall, I feel that the paper has a well-motivated idea (sample-wise randomized smoothing) and shows some minor improvements in terms of results, but that clarity for all other parts of the paper must be improved significantly.


Post Rebuttal Update:

I appreciate the author response, but I will maintain my score after reading the rebuttal and discussion with other reviewers. It still appears to me that the motivation and clarity can be improved, and so I would recommend focusing on those aspects in future revisions. Additionally, baselines such as "allocating a region for every single test point" should be compared to in a clear way (as opposed to being in the appendix), as such baselines seem natural to compare to.
review_title: Motivation and explanations of methodology could be improved

Meta-review: The paper considers an extension of randomized smoothing where the smoothing noise may differ for different points. The resulting method shows good performance experimentally. However, the reviewers raised a number of problems which, at the moment, precludes the acceptance of the paper, such as the following:

- The paper analyzes the transductive setting, where all the test points are available to fine-tune the smoothing parameters of the predictor. It is not clear how this setting corresponds to a real adversarial threat model, and whether the final tuning needs to use the perturbed or unperturbed points. In the first case, the resulting certified radius is different from what is normally used in the literature, while in the latter it is not clear how the method would be useful to mitigate any real adversarial attack.
- A related comment is that the paper should explain (and state) properly how the results of Cohen et al.  (2019) are applicable to compute the certified radius, which would also provide a proper explanation why partitioning is used.
- The training cost of the procedure seems very high, and this is not discussed.
- The clarity of the presentation should be improved.




Decision: Reject