Our main theoretical contribution is to show that, given a set of labels (e.g., the ground truth labels) for an input, at least \(e\)  of them are provably in the set of \(k\)  labels predicted by MultiGuard for the input, when the \(\ell _2\) -norm of the adversarial perturbation added to the input is no larger than a threshold. We call \(e\)  certified intersection size. We aim to derive the certified intersection size for MultiGuard. However, existing randomized smoothing studies [1]}, [2]}, [3]} achieves sub-optimal provable robustness guarantees when generalized to derive our certified intersection size. The key reason is they were designed for multi-class classification instead of multi-label classification. Specifically, they can guarantee that a smoothed multi-class classifier provably predicts the same single label for an input [1]}, [2]} or a certain label is provably among the top-\(k\)  labels predicted by the smoothed multi-class classifier [3]}. In contrast, our certified intersection size characterizes the intersection between the set of ground truth labels of an input and the set of labels predicted by a smoothed multi-label classifier. In fact, previous provable robustness results [2]}, [3]} are special cases of ours, e.g., our results reduce to Cohen et al. [2]} when \(k^{\prime }=k=1\)  and Jia et al. [3]} when \(k^{\prime }=1\) .
