Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper leverages the recent anisotropic certificates for randomized smoothing for certifying multi-output classifiers. In particular, it leverages anisotropic Gaussian  and Bernoulli smoothing for better collective robustness. Experimental evaluation was conducted on semantic segmentation and node classification to demonstrate the effectiveness of the proposed method.
main_review: This paper has many merits:
- The motivation behind this work is clearly stated.
- The use of anisotropic smoothing is intuitive.
- The tasks on which the experiments are conducted are in line with the motivation.

However, there several concerns in this work that need to be addressed:
- While the major part of this work is dedicated to the theoretical analysis, it is not clear to me which parts belong to the contributions of this work and which parts are restatements from other work. For example:
1. In terms of the theoretical results in this work in sections 4, 5, and 6: what is exactly new (considered as a contribution)? For example, Proposition 1 and 4 are just a special case of the results of Eiras et.al. for when the covariance matrix is diagonal. In fact, with the formulation setup presented in section 2, a generalization of proposition 1 can be found in Appendix A of [1]. 

2. In terms of the analysis in sections 4 and 6, what is exactly new? For example, the bound derived in Equation (1) and the analysis in (3-6) are very similar to the results in Schuchardt et. al.

- In terms of experiments:
1. it is mentioned that "showcasing state-of-the-art accuracy on datasets is not part of our objective". Why? If the proposed collective anisotropic certificate is preferable, then it is necessary to show that it improves the best baselines.

2. What is the importance of certified ratio metric? Why not reporting wither certified accuracy or certified AUC in the case of segmentation. While two models could have similar certified ratios, their accuracy could significantly differ.

3. Since the analysis of this work follows the work of Schuchardt et. al., a direct comparison on the strictly local setup should be presented.

4. The experiments conducted include a single benchmark per task. The experiments should include multiple datasets to check whether the assumptions related to the use of anisotropic smoothing hold or not (e.g. homophily). 

- The writing of the paper could be significantly improved. There are several parts were the text refer to tables/figures in the appendix without mentioning the appendix. Also, please consider moving more experiments from the appendix to the main work. Moreover, in the caption of Figure 1, $\sigma_{\text{min}}$  is mentioned twice, is that a typo? It is also repeated in page 8 in the second paragraph.



[1]: Certified Defense to Image Transformations via Randomized Smoothing, NeurIPS 2020.
summary_of_the_review: While the main motivation of this work is clear, there are several parts of this work that need to be revised. In particular, it should be clearly stated which parts of the theoretical results in this work are new. Also, the experimental part of this work can be significantly improved by including stronger baselines and more datasets.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper makes three contributions in particular:
- A local version of randomized smoothing for multi-output classifiers. The authors suggest using a customized smoothing distribution for certifying each output of the multi-output classifier. The custom distributions allow them to produce tighter guarantees for each output.
- A new analysis method of variance smoothing for discrete data uses the average softmax value instead of the majority vote as the prediction rule. The authors use the first and second-order statistics (mean and variance) to provide robustness guarantees in this method.
- A collective certification strategy for multi-output classifiers using a common interface ($\ell_p$ norm ellipsoids) for base certificates for every output. The authors describe a common way of stating the base certified regions for every output. Then the multi-output certification problem can be expressed as a mixed-integer linear program to find a point inside the perturbation model that lies outside the base certified regions for the maximum number of outputs.
main_review: Strengths
- The collective certification strategy in the paper can be used with most of the existing literature on randomized smoothing, which allows it to be quite versatile and adapt to new developments in the field. The MILP relaxation and the distribution sharing ideas in the paper also highlight some critical limitations/ future research directions for randomized smoothing.
- The variance smoothing idea in the paper is quite exciting and a natural next step for getting better certificates. 
- The empirical results in Table 5 that compare the best achievable baseline performance with the performance of the proposed methods provide compelling evidence for the efficacy of the suggested approach.

Weaknesses
- No training counterpart is suggested for the proposed local smoothing strategy. The current results use a model trained with $\sigma_\min$ as the base model. It seems a bit counterintuitive to have essentially different prediction strategies during training and testing. Some of the local smoothing ideas should be reflected in training to make the objectives better aligned. 
summary_of_the_review: In summary, the paper explores a very relevant problem in certification against adversarial examples. The main ideas of the paper are pretty novel and would help future research. The paper does a great job of presenting the ideas and discussing some of the potential limitations. However, it would be better if the authors briefly discussed the mismatch between the training objectives and the test time prediction model. Taking all of this into account, I would recommend the paper be accepted.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors consider tasks mapping a single input to multiple outputs and study robustness certificate against input perturbations. To achieve the goal, the authors propose a collective certificate where each output is dependent on the entire input but assigns different levels of importance to different input regions, and then derived the collective certificate based on localized randomized smoothing. The proposed collective certificate is evaluated on both image segmentation and node classification tasks. 

main_review: Strengths: The studied problem is important and the paper is easy to follow (before evaluation) in general. The proposed method is somewhat novel. 

Weaknesses: The key difference between the proposed method and the existing works is unclear. The paper lacks comparison with the existing method. Evaluation is insufficient and some metrics are not reasonable.  



The main idea is motivated by several existing works and the key difference between the proposed method and these existing works are unclear for me. 
For instance, what’s the key difference between the proposed theoretical results (e.g., Prop 1&2) and those in Eiras et al.? Is it possible for Fischer et al. to be adapted to the considered setting? 
 

No comparison with center smoothing or/and Fischer et al., if possible. 

Figures are confused for me. For instance, what is the difference between the “dotted line” and “Naive” in Figure 2? Similar to all the other figures. 

Why using certified ratio? I do not think it meaningful to certify pixels/nodes that are wrongly classified.

The image segmentation is only evaluated on Pascal voc2012. I suggest the authors to evaluate on more datasets, e.g., Cityscape, which is used in Fischer et al. 
The authors use AUC to report the 

It is not standard to use AUC to show image segmentation results.  A commonly used metric is mIoU (mean intersection over union). 

UNet is an outdated model for semantic segmentation model. I suggest the authors to evaluate on more recent models such as deeplab v3, danet, hrnet, etc.  

What’s the computational overhead to find the optimal $\sigma_{\min}$ and $\sigma_{\max}$? 

While computation is an issue for localized RS, the way to partition an image into grid cells and certifying grid cells independently already looses semantic relationship between pixels in different cells and thus violates the purpose of semantic segmentation.  


summary_of_the_review: Collective robustness certificate is an important research problem. The proposed method is novel to some extent, but its key difference with the existing work is not unclear for me, and so as the performance comparison. My another major concern is on evaluation. For instance, the image segmentations results are not reported using reasonable metrics and the models and datasets are rather outdated on my end.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: **Summary**

The paper proposes a localized smoothing approach for certifying structured output models. The threat model of interest in this setting is the bounded input perturbation that results in the highest number of prediction flips per pixel. The paper proposes to utilize the idea that when certifying pixel predictions at location (i,j), one can smooth the input pixels (k,l) far away from (i,j) by larger noise magnitude (standard deviation) resulting in a higher certified radii as they perhaps may not play a significant role in predicting the label of (i,j). The paper formulates the problem of finding worst cases adversaries that result in misprediction to the task of finding adversaries outside the certified region with anisotropic smoothing over the input. The paper then lower bounds the binary objective with a box constraints and solve the problem using linear  programs. Experiments are conducted on image segmentation tasks along with node classification.
main_review: **Strengths**

I very much appreciate the extensive experiments in tuning in the baseline with several sigma to guarantee (1) best robust accuracy of baseline when compared to localized randomized smoothing (2) when comparing certified ratios, the accuracies are comparable. The paper's proposed methodology is very well written and the formulation is beautifully simple and intuitive.


**General Questions**

1. Why is Equation 1 not an equality? Is not the set H for every pixel output is exactly tight? Or is the assumption here that H can be an over-approximation to the true certified region? 

2. In the case where H is given by the localized smoothing using Propositions 1 or 2, will this result in an exact equality for (1)?

3. Can the authors comment of the compleixty for solving (5) with the proposed splits in the inputs? How does the method compare against the Naive approach. I believe it should be much more expensive as it requires the computation of the lower bound to the probability of success and then followed by solving the high dimensional linear program.

4. There are no comparisons against Fischer et al on certifying semantic segmentation.

5. It is not clear to how does the Naive classifier in Fgiure 2 work. Is it simply to perform RS certification for every pixel independently and counting the number of certifiable functions with a shared sigma over all inputs? If so, it is not clear to me why does the dashed line perform worse than this Naive approach?

6. It is also not clear to me why does solving the linear program reformulation work better than direct RS with anisotropic certificates (dashed line vs solid orange). Since the linear program lower bounds the original objective should not it be providing a pessimistic certified accuracy compared to the dash orange? That is to say, it tends to produce more adversaries that flip predictions under the lower bound but does not necessarily flip prediction of the original binary objective?

7. This is related to (6). What is the key motivation/intuition behind believing that solving (3) is better than directly certifying the anisotropic certificates. This link is very much un clear to me.

8. One of the key weaknesses that I see so far is the small certification experiments. For example, on the segmentation task, the certified accuracy is reported only on 50 images of the validation dataset. Perhaps a different dataset experiments (Cityscapes) following Fischer et al would make the submission stronger.

9. It is not clear to me if showing state-of-the-art certification results is not the objective of the paper, what is the key objective/insight of this reformulation? Showing that localized RS has a better trade-off between accuracy and robustness is not sufficiently novel for several reasons. (1) The per pixel sigma certification was derived in prior art which the paper faithfully state. (2) The proposed method of nonshared sigma over all method (without linear relaxation) is expected to be better intuitively as it overparameterizes the smoothing distribution holding the global shared sigma RS as a special case. So, I do not follow: what are the key *new* insights that I am missing here (please correct me if I am wrong here). (3) The certification time is not reported which is expected to be much larger.

10. I generally enjoyed reading the variance smoothing part (section B.2 in the appendix). The authors' are to be commended on it. Can the authors comment on how much of improved radius can the incorporation of the variance bring compared to classical RS certification. Does it actually tighten the radius for other certificates beyond gaussian? If so, this should be highlighted more in the paper as I believe this is significant. If not, then why doing variance smoothing and not directly with the expectation fixed and lower bounding over functions with a fixed expected prediction with Bernoulli distribution? So in short, why variance smoothing? 



**Minor comments**
1. Page 3, line 9: "be the probability of g y" >> "of predicting y under g".
2. Caption of Figure 2. Sigma_min is given two values, I believe the second should be Sigma_max.
3. Page 8, line 11: sigma_min assigned twice.
3. Page 8, line 16: "Figure Fig. 2".
4. Proposition 4 in page 17. The radius shown by Eiras et al is without inverse CDF. It is only the difference in predictions between the top and runner up class.
5. Figure 1. I generally advise to have 4x6 grid in the figure aligning with the text. This is particularly the case as when Figure 1 was referenced in the experiments, it was after describing the 4x6 splits of the input.
summary_of_the_review: See above.
review_title: null

Meta-review: The authors develop a framework for improving robustness certificates obtained by randomly smoothed classifiers in settings with multiple outputs (segmentation or node classification), by combining local robustness certificates obtained for individual classifiers. They validate their results empirically and demonstrate gains from their approach.

The reviewers were mostly in agreement that the authors make a novel and interesting contribution. However, there were a lot of technical concerns raised by reviewers that, while addressed during the discussion phase, would require a substantial revision of the paper to address adequately. Overall, I feel the paper is borderline but recommend rejection and encourage the authors to incorporate feedback from the reviewers and submit to a future venue.
Decision: Reject