Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes localized randomized smoothing to improve collective certificate.
It formulates the problem as a solution to a linear program after smoothing different parts of a given input image differently.
Experiments were carried on two standard segmentation benchmarks and one node classification dataset showing the effectiveness of the proposed approach.
strength_and_weaknesses: Strengths:

- The problem that this paper studies is important.

- The experiments presented in this work provide improvements over previous approaches supporting the main claims.

Weaknesses:

- The scale of the experiments in this work is rather small. Certifying only 50 images from Pascal and CityScapes might be not enough to draw conclusions on. I would suggest extending the results on larger amount of samples. Also, some fine-grained experimental analysis on instances containing different number of categories could also be insightful.

- The second contribution of this work claims an efficient anisotropic randomized smoothing certificate. However, this problem was previously explored in the literature, as dictated in the related work, by Eiras et.al. Efficiency analysis between different approaches would strengthen this contribution. Further and since the experiments are done on few number of samples, how does the proposed method compare to ANCER from Eiras et.al when combined with other baselines?

- The writing of the paper along with the presented notation need improvements in some parts of this work. For example, small paragraphs discussing both Theorem 4.2 and 5.1 would ease the reading of this work.
Further, in theorem 4.2, the prediction is referred to as $y_n$ while in the third paragraph of section 4 it is $\mathbf y$.

clarity,_quality,_novelty_and_reproducibility: This work is clear in some aspects such as the motivation to the problem and the proposed method. However, and as dictated in the weaknesses, there are several parts of this paper that need improvements. 
summary_of_the_review: This work has several merits of this work including the motivation, theoretical analysis, and supporting experiments. However, there are few concerns that I hope to be addressed in the discussion period. This includes the claim about the second contribution (efficient anisotropic certification), limited experimental analysis, and the writing of this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel certification mechanism for certification in the multiple-output setting (e.g., image segmentation) based on randomized smoothing (RS), referred to as a collective certificate.
RS typically is used to create a robust-by-construction classifier in the (single-output) classification setting, by evaluating a base model multiple times and reporting the majority output.

The key idea of this work is to utilize perturbation distributions for RS that match the locality patterns of the model outputs (e.g., use anisotropic distributions that capture locality). Prior works have either ignored this locality aspect or only treated strict locality imposed by the receptive field of convolutions.
This, in turn, requires determining the appropriate anisotropic smoothing distirbutions for all local regions, which the authors propose to solve a mixed-interger linear program (MILP). To avoid the high cost of the MILP, discretizations, and simplfications (larger regions) as well as a relation to linear programming are considered.

The approach is thoroughly evaluated on image segmentation and node classification. The results are good if the locallity assumptions truly hold (and deteriored as expected if not).
strength_and_weaknesses: **Strengths**:
- The paper is well-written and easy to follow. Arguments in the main paper are thorughly backed-up by derivation and explanation in the appendix.
- Algorithmically interesting approach for a relevant problem.
- Mathematical justifications are thorough and appear to be correct seem correct.

**Weaknesses**:
- Some aspects of inference are unclear (see below).


clarity,_quality,_novelty_and_reproducibility: 
As stated above the paper is quite well written and presents a theoretically novel algorithm (with strong empirical evaluation).
However, one aspect that I did not find to be discussed in the paper is the inference procedure:

At inference time (when we are just interested in the result, not the certificate) RS requires to determine the top class (for each output) under the smoothing distribution.
Can you comment on the inference procedure in your case? In particular, whether we can solve for the same smoothing distribution when at inference time given a (potentially perturbed) as used during certification time and then use this to determine the output class?

In terms of reproducibility I believe that access to the code will be instrumental. While the authors promise to release the code on OpenReview in Section 9, I can not see it at the time I am writing this review. As I assume the cause of this is either an OpenReview setting or miscommunication by the review guidelines, I am giving the Authors the benefit of the doubt.






A minor formatting issue: Table 1 (Page 30) is too wide for the page.



summary_of_the_review: This is a well-written paper proposing a new smoothing approach for multi-output settings.
My main concern is how inference would be handled soundly.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a framework, Localized Smoothing, to solve the problem of collective certification. The proposed method does not rely on any assumption for the validity, but it is formulated to be able to exploit any homophily/soft locality property in the multiple labeling task. The paper's main idea is to use region-specific smoothing distribution that puts more noise on less relevant pixels and less on relevant pixels. The paper also provides experimental evidence showing the algorithm's superior performance on image segmentation and node classification tasks.
strength_and_weaknesses: Strengths
- The proposed method extends the idea of using a strict locality condition to produce certificates to exploiting soft locality to produce a general certification method. 
- The authors propose a general framework to efficiently combine local certificates as long as they satisfy the correct interface.
- The Variance-constrained certification approach provides a scalable way to do anisotropic $\ell_0$ certification, which could be independent interest.
- The experiments provided in the paper are detailed and give a comprehensive view of the benefits of the proposed algorithm.
clarity,_quality,_novelty_and_reproducibility: The paper provides a novel approach to solving the collective certification problem, and the proposed solution achieves much better results than the current state-of-the-art. The paper is also very well-written and easy to follow, and the authors also provide extensive, detailed, reproducible experiments.
summary_of_the_review: The proposed method, Localized Smoothing, provides a general framework for collective robustness certification. The theorems proved in the paper show the theoretical benefit of using the proposed method over the existing state-of-the-art, which is also reflected in the experiments. Moreover, the Variance-constrained certification approach defined in the paper could be of independent interest. In general, I think the ideas in the paper, as well as the final algorithm, would be of interest to the ML community.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors extend the randomized smoothing approach to anisotripic distributions, showing how this extension enables computation of stronger robustness certificates for tasks beyond classification like image segmentation

Strengths:
1. The method proposed is sound and exploits a natural idea of anisotropic noise to obtain tighter certificates.
2. The experiments convincingly demonstrate the effectiveness of the technique.

Weaknesses:
1. No major weaknesses, minor ones were clearly addressed during the rebuttal phase.

Hence, I recommend acceptance.

justification_for_why_not_higher_score: The paper could be accepted as an oral potentially. My hesitations are that 1) the initial versions of the paper lacked some writing clarity, and while the revisions addressed some concerns, it can be improved further, 2) The certification requires solving a MILP, which may present scalability issues.
justification_for_why_not_lower_score: The authors present a sound and novel technique that improves randomized smoothing certificates, and is justified both theoretically and empirically.
Decision: Accept: notable-top-25%