MultiGuard leverages randomized smoothing [1]}, [2]}, [3]}, [4]}, [5]}. Existing randomized smoothing studies (e.g., Jia et al. [4]}) achieve sub-optimal provable robustness guarantees (i.e., certified intersection size) for multi-label classification, because they are designed for multi-class classification. For example, as our empirical evaluation results will show, MultiGuard significantly outperforms Jia et al. [4]} when extending it to multi-label classification.
Technically speaking, our work has two key differences with Jia et al.. First, the base multi-class classifier in Jia et al. only predicts a single label for an input while our base multi-label classifier predicts multiple labels for an input. Second, Jia et al. can only guarantee that a single label is provably among the \(k\)  labels predicted by a smoothed multi-class classifier, while we aim to show that multiple labels (e.g., ground truth labels of an input) are provably among the \(k\)  labels predicted by a smoothed multi-label classifier. Due to such key differences, we require new techniques to derive the certified intersection size of MultiGuard. For instance, we develop a variant of Neyman-Pearson Lemma [8]} which is applicable to multiple functions while Jia et al. uses the standard Neyman-Pearson Lemma [8]} which is only applicable to a single function. Moreover, we use the law of contraposition to derive our certified intersection size, which is not required by Jia et al..
