Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper extends the traditional randomized smoothing, which only supports single-label classifiers, to support multi-label classifiers. The extension is based on a generalization of Neyman-Pearson lemma: the Neyman-Pearson lemma still holds for a normalized sum of functions as long as the normalized sum is within [0, 1] universally. The proposed method is evaluated on a few classical multi-class datasets including VOC 2007, MS-COCO, and NUS-WIDE, and achieves superior performance compared to a naive extension from top-k certification in terms of multi-class precision, recall, and F1 score.
strengths_and_weaknesses: Strengths:
- Non-trivial technical contributions: a generalization version of Neyman-Pearson lemma and the resulting certification protocol based on the extended randomized smoothing for multi-class certification.
- Handles an important problem: multi-class certification is a common learning task formulation, e.g., in computer vision.
- Significant experimental results: consistently beating an adapted baseline (from top-k randomized smoothing certification).
- Writing quality is good.

Weaknesses:
- Some mathematical illustrations may not be rigor enough. See "Questions" for more details.
- The underlying technical idea is a bit straightforward, or not explained clearly enough in terms of challenges. See "Limitations" for more detail.

Note: I am not familiar with multi-label classification literature. Therefore, I didn't evaluate the corresponding experimental protocols, e.g., the selection of evaluation datasets. I will take other reviewers' comments into account for this part.
questions: - In Eqn. (8), where do we constrain the validness of input to $\Phi^{-1}$? In other words, $\dfrac{\underline{p_{A_u}}}{k'}$ or $\dfrac{\overline{p}_{B_v}}{k'}$ seems to be possible to grow larger than 1, is it the case? If so, we may need to fix Eqn. (8) and the corresponding proofs, especially in Eqns. (72) and (78).
limitations: - After reading the submission, I feel the main technical idea is to use (e+1)-th ground-truth label's lower probability bound to compare with the (e+1)-th adversarial label's upper probability bound to derive the certification. This idea seems to be a bit straightforward. On the other hand, the technique of bagging multiple labels together for certification (second terms in Eqn. (8) constraints) sounds interesting to me. I am wondering whether this bagging technical contributes much to the final certification tightness, or is just incremental. Maybe an ablation study can be conducted to quality this. If the technique contributes much, I would recommend the authors squeeze some space in Section 3.3 (seems most sampling techniques are already in the literature) and expand the discussion of this technique more to highlight the novelty and technical contributions.

- Following the above comments, the experimental section seems to mainly convey "the proposed method is superior than the baseline" but lacks the discussion on **why** it surpasses the baseline. The discussion between Line 360 and 362 looks a bit thin to me.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes MultiGuard, where multi-label classification with provable guarantees against adversarial perstubations is studied. The method is based on randomized-smoothing, where randomization with Gaussian noise is utilized to provide a smoothed classifier with provable guarantees, and this work generalizes that to multi-label classification, with adjusted claims to suit multi-label classification.
strengths_and_weaknesses: This work uses simple yet intuitive tools and techniques, namely a variant of Neyman-Pearson lemma as well as law of contraposition to extend the provable guarantees of randomized-smoothing multi-class classification to that of mutli-label. Eventhough technical novelty is somewhat limited, the problem is of interest and together with the provable performance, the community would benefit from the publication of the work.

Furthermore, the paper is written well and is easy to follow and has good structure. Numerical results are well presented and parameter sensitivity is studied, however in terms of comparison with other methods are somewhat limited, since the method is only compared with Jia et al, and thus could benefit from more extensive comparisons.

questions: In order to make the paper self-contained, I’d recommend to add a section on the training procedure of the proposed method. Even though references to ASL for training the base multi-label classification training is given, the paper is not self contained as no further information, i.e. the definition of the loss and training procedure and/or hyper parameters, is given, which makes the work not self-contained. 
limitations: The bounds drop quickly as the multi-label parameter k drops for 1 to higher values (2 or 3), which poses the question of whether these bounds are non-trivial or useful in practice.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper discusses the adversarial robustness of multi-label classification task, extend provably robust defense methods to multi-label case, and derive a way to estimate the certified intersection size, which is the least number of true labels in the set of labels predicted by the certified classifier. Specifically, the author extends works of randomized smoothing to multi-label task by leveraging the law of contraposition and a variant of Neyman-Pearson lemma to derive the conditions of robust certification and using MC algorithm to help estimate the certified intersection size.

Experiments on three datasets (VOC 2007, MS-COCO, NUS-WIDE) show that the proposed method performs better than directly extending randomized smoothing (Jia et al.) to multi-label classification. They also do experiments to study the effects of important hyper-parameters.

strengths_and_weaknesses: Strengths:

- The work is novel as it is the first one to extend provably robust defense to multi-label classification and the extension is not trivial as multi-label classification is different from multi-class classification. Besides, experiments show that directly extending the method proposed for multi-class classification to multi-label does not work well. The authors also show that randomized smoothing methods proposed for multi-class classification can be viewed as special cases of their framework.

- The paper is clearly written and easy to follow. The method is straightforward and not hard to implement. The proposed method works well on three benchmark datasets.

Weakness:

- Though pseudo code and some implementation details are provided, actual code is not provided,  It is better if the actual code can be provided for reproducing the results.

questions: NA
limitations: Though the method performs better than directly extending randomized smoothing on multi-class classification to multi-label case, the performance is far from perfect. There's still room for improvement. The author points out some improvement direction at the end of the work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, a multi-label variant of the random smoothing technique is designed by extending the Neyman-Pearson Lemma from the single-output model to the multi-output model. The theoretical study shows that the proposed multi-label random smoothing method can be considered as a more general framework of provably robust learning. It takes the single-label random smoothing work published in [12] as a special variant. Furthermore, considering only one of the multiple labels as the protected target by the injected random smoothing noise, the proposed method can be also reduced to [22]. 
strengths_and_weaknesses: Strong points: 

1. How to design the random smoothing noise for multi-output classification algorithms is important and remains open to address. It is good to see research efforts devoted to this topic. Extending the Neyman-Pearson Lemma is a decent idea along this track. 

2. The theoretical study is solid and points out clearly the relation between the proposed method and the previous random-smoothing techniques. 

Weak points: 

The core idea of mult-label classification is to make use of the correlation between multiple labels, to boost the learning performance. Highly correlated labels are likely to have similar classification accuracy levels (they tend to be correctly classified / misclassified at the same time). It is unclear how the proposed method considers the label correlation in the design of the random smoothing noise. For example, the provably robustness radius / bound should be similar for highly correlated labels, as the same smoothing perturbation tends to bring similar effects to the correlated label pairs.  Therefore considering untargeted multi-label attacks, the design of the random smoothing noise should be able to benefit from the label correlation:  we can minimise the variance of the random smoothing noise, while providing the provably defense to as many as possible correlated labels.  


questions: The major question is it is unclear whether the proposed theoretical study based on the extended Neyman-Pearson Lemma considers the label correlation explicitly in protecting multi-label systems against adversarial attacks. Furthermore, an injected random smoothing noise may protect some labels, while harm the classification performance of the other labels severely. Could the proposed theoretical analysis provide some insights on how to control the unexpected classification performance drops in multi-label systems ?  This is also the unique problem in robustifying multi-label learning tasks, in contrast to the single-label tasks.  

######

We are satisfied with the clarification provided by the author. We think this concern has been well addressed. 
limitations: Please find our concerns in the listed weak points.
review_title: null

Meta-review: metareview: This paper studies adversarial examples for varieties of randomized smoothing, namely, ways to improve the robustness of a classifier by adding noise and averaging over inputs. The main contribution is MultiGuard, which is a provably robust defense for multi-label classification. Moreover, the method works for a variety of classifiers, and the authors also provide theoretical and empirical results to back up their method.

The reviewers generally find the technical contribution to be significant (although perhaps elementary) as well as finding the problem domain to be important and interesting. The reviewers also found the mathematical tools to be intuitive and appropriate (e.g., a variant of Neyman-Pearson lemma as well as a law of contraposition to extend the provable guarantees of randomized-smoothing multi-class classification to that of mutli-label). In addition to acknowledging the theoretical results, the reviewers also felt that the empirical studies were sufficient to verify the authors’ main findings.

On the negative side, there are some concerns about clarity and rigor of the results. I would encourage the authors to improve the exposition and the preliminaries to increase the readability of the work. Similarly, there are some questions about comparison to prior work and similar ideas that should be addressed.

Overall, I recommend acceptance. The positives outweigh the negatives, and the author-review discussion seemed to address many of the main questions. 
confidence: Certain
Decision: Accept