
When \(k^{\prime }=k=1\)  and \(L(\mathbf {x})\)  only contains a single label, our certified intersection size reduces to the robustness result derived by Cohen et al. [1]}, i.e., the smoothed classifier provably predicts the same label for an input when the adversarial perturbation is bounded. When \(k^{\prime }=1\) , \(k\ge 1\) , and \(L(\mathbf {x})\)  only contains a single label, our certified intersection size reduces to the robustness result derived by Jia et al. [2]}, i.e., a label is provably among the \(k\)  labels predicted by a smoothed classifier when the adversarial perturbation is bounded. In other words, the certified robustness guarantees derived by Cohen et al. [1]} and Jia et al. [2]} are special cases of our results. Note that Cohen et al. is a special case of Jia et al. Moreover, both Cohen et al. and Jia et al. focused on certifying robustness for multi-class classification instead of multi-label classification.

Our certified intersection size holds for arbitrary attacks as long as the \(\ell _2\) -norm of the adversarial perturbation is no larger than \(R\) . Moreover, our results are applicable for any base multi-label classifier.

Our certified intersection size relies on a lower bound of the label probability for each label \(i \in L(\mathbf {x})\)  and an upper bound of the label probability for each label \(j \in \lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x})\) . Moreover, when the label probability bounds are estimated more accurately, our certified intersection size may be larger.

Our theorem requires \(\underline{p_{A_u}} \le k^{\prime }\)  and \(\overline{p}_{B_{v}} \le k^{\prime }\) . We have \(\underline{p_{A_u}} \le p_{A_u} \le \sum _{i \in L(\mathbf {x})} p_{i} \le \sum _{j=1}^{c} p_j = k’\) . In Section REF , our estimated \(\overline{p}_{B_{v}}\)  will always be no larger than \(k’\) . Thus, we can apply our theorem in practice.

We note that there are respectively two terms in the left- and right-hand sides of Equation REF . The major technical challenge in our derivation stems from the second term in each side. As we will show in our experiments, those two terms significantly improve certified intersection size.

