MultiGuard: Provably Robust Multi-label Classification against Adversarial Examples
Authors: Jinyuan Jia
Wenjie Qu
Neil Zhenqiang Gong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Adversarial examples
multi-label classification
certified defense

Abstract: Multi-label classification, which predicts a set of labels for an input, has many applications.  However, multiple recent studies showed that multi-label classification is vulnerable to adversarial examples. In particular, an attacker can manipulate the labels predicted by a multi-label classifier for an input via adding carefully crafted, human-imperceptible perturbation to it. Existing provable defenses for multi-class classification achieve sub-optimal provable robustness guarantees when generalized to multi-label classification. In this work, we propose MultiGuard, the first provably robust defense against adversarial examples to multi-label classification. Our MultiGuard leverages randomized smoothing, which is the state-of-the-art technique to build provably robust classifiers. Specifically, given an arbitrary multi-label classifier, our MultiGuard builds a smoothed multi-label classifier via adding random noise to the input. We consider isotropic Gaussian noise in this work. Our major theoretical contribution is that we show a certain number of ground truth labels of an input are provably in the set of labels predicted by our MultiGuard when the $\ell_2$-norm of the adversarial perturbation added to the input is bounded. Moreover, we design an algorithm to compute our provable robustness guarantees. Empirically, we evaluate our MultiGuard on VOC 2007, MS-COCO, and NUS-WIDE benchmark datasets. Our code is available at: https://github.com/quwenjie/MultiGuard

MultiGuard: Provably Robust Multi-label Classification against Adversarial Examples
Jinyuan Jia"
Wenjie Qu"
University of Illinois Urbana-Chane Chaaaa-Champaign Ainyaa@111inois..om
Huazhong University of Science and Technology ven_jie_qquQutlook. com
Neil Zhengiang Gong
Duke University
neil. gonl.gongd edu
Abstract
Multi-label classification, which predicts a set of labels for an input, has many ap- plications. However, multiple recent studies showed that multi-label classification is vulnerable to adversarial examples. In particular, an attacker can manipulate the labels predicted by multi-label classifier for input via adding carefully crafted, human-imperceptible perturbation to it. Existing provable defenses for multi-class classification achieve sub-optimal provable robustness guarantees when general- ized to multi-label classification. this work, we propose MultiGuard, the first provably robust defense against adversarial examples to multi-labe classification. Our MultiGuard leverages randomized smoothing. which is the state-of-the-art technique build provably robust classifiers. Specifically, given arbitrary multi-label classifier, our MultiGuard builds a smoothed multi-label classifier via adding random noise to the input. We consider isotropic Gaussian noise this work. Our major theoretical contribution is that we show a certain num- ber of ground truth labels of an input are provably in the set of labels predicted by our MultiGuard when the fz-norm of the adversarial perturbation added to the input is bounded. Moreover, we design an algorithm to compute our prov- able robustness guarantees. Empirically, we evaluate our MultiGuard on VOC 2007, MS-COCO, and NUS-WIDE benchmark datasets. Our code is available at: https: http//gttttu...../ cww httpm//wwwni/////eeeeeee M/u/tuutttt Guard
Introduction
Multi-class classification assumes each input only has one ground truth label and thus often predicts
a single label for an input. In contrast, in multi-label classification 42 35] (3), each input has
multiple ground truth labels and thus multi-label classifier predicts set of labels for an input. For instance, an image could have multiple objects, attributes, or scenes. Multi-label classification has many applications such as diseases detection [16), object recognition recognition [18], document classification
retail checkout
34 etc..
However, similar to multi-class classification, multiple recent studies |6
showed that multi-label classification is also vulnerable to adversarial examples. In particular, an attacker can manipulate the set of labels predicted a multi-label classifier for input via adding carefully crafted perturbation to it. Adversarial examples pose severe security threats to the applications of multi-label classification in security-critical domains. To mitigate adversarial examples multi-label
53
30
Equal contribution. Wenjie Qu performed this research when he remote intern in Gong's group
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

classification, several empirical defenses 49 30] have been proposed. For instance, Melacci et al. [30] proposed to use the domain knowledge on the relationships among the classes improve the robustness of multi-label classification. However, these defenses have no provable robustness guarantees, and thus they are often broken by more advanced attacks. For instance, Melacci et al. [30] showed that their proposed defense can be broken by an adaptive attack that exploits the domain
knowledge used in the defense. Moreover, existing provably robust defenses [T0 8 17 46 [2 [2]
are all for multi-class classification, which achieve sub-optimal provable robustness guarantee when extended to multi-label classification as shown by our experimental results.
Our work: We propose MultiGuard, the first provably robust defense against adversarial examples for multi-label classification. MultiGuard leverages randomized smoothing [5] 29 24 26 12), which is the state-of-the ofrttheart technique to build provably robust classifiers. In particular, compared to other provably robust techniques, randomized smoothing has two advantages: 1) scalable to large-scale neural networks, and 2) applicable to any classifiers. Suppose we have an arbitrary multi-label classifier (we call it base multi-label classifier), which predicts k'' labels for an input. We build smoothed multi-label classifier via randomizing an input. Specifically, given an input, we first create randomized impul via adding random noise to it. We consider the random noise be isotropic Gaussian in this work. Then, we use the base multi-label classifier to predict labels for the randomized input. Due to the randomness in the randomized input, the k labels predicted by the base multi-label classifier are also random. We use to denote the probability that the label i is among the set of k labels predicted by the base multi-label classifier for the randomized input, where i E 21.2.... ... c]. We call p: label probability. Our smoothed multi-laber classifier predicts the & labels with the largest label probabilities for the input. We note that ke' and is are two different parameters.
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 f--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 (24 12 22 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 [24] 12 or certain label is provably among the top-k labels predicted by the smoothed multi-class classifier (22. 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 lulti-label classifier. In fact, previous provable robustness results 12 22 are special cases of ours, e.g., our results reduce to Cohen et al. [12 when k k = 1 and Jia et al. 22 when k' = 1.
In particular, there are two challenges in deriving the certified intersection size. The first challenge is that the base multi-label classifier predicts multiple labels for an input. The second challenge is that an input has multiple ground truth labels. To solve the first challenge, we propose variant of Neyman-Pearse
Lemma (33] that is applicable to multiple functions, which correspond to multiple labels predicted by the base multi-label classifier. In contrast, existing randomized smoothing studies (24] 26 12 22 for multi-class classification use the standard Deyyaan-Pearson Lemma [33 that is only applicable for single function, since their base multi-class classifier predicts a single label for an input. To address the second challenge, we propose to use the law of contraposition to simultaneously consider multiple ground truth labels of an input when deriving the certified intersection size.
Our derived certified intersection size the optimal solution to an optimization problem, which involves the label probabilities. However, it is very challenging to compute the exact label probabilities due the continuity of the isotropic Gaussian noise and the complexity of the base lubti-label classifiers (e.g., complex deep neural networks). In response, we design Monte Carlo algorithm to estimate the lower or upper bounds of label probabilities with probabilistic guarantees. More specifically, we can view the estimation of lower or upper bounds of label probabilities as binomial proportion confidence interval estimation problem in statistics. Therefore, we use the Clopper- Pearson [] method from the statistics community to obtain the label probability bounds. Given the estimated lower or upper bounds of label probabilities, we design an efficient algorithm to solve the optimization problem to obtain the certified intersection size.

---

and NUS-WIDE benchmark datasets. We use the certified top-k precision @ R, certified top-k recall @ R. and certified top-k fl-score@ R to evaluate our MultiGuard. Roughly speaking, certified top-k precision @ R is the least fraction of the k predicted labels that are ground truth labels of an input when the fn-norm of the adversarial perturbation is at most R: certified top-k recall @ R is the least fraction of ground truth labels of an input that are in the set of k labels predicted by our MultiGuard; and certified top-k fl @ R is the harmonic mean of certified top-k precision @ R and certified top-k recall @ R. Our experimental results show that our MultiGuard outperforms the state-of-the-art certified defense [22] when extending it to multi-label classification. For instance, and our MultiGuard respectively achieve 24.3% and 31.3% 3% certified top-k precision @ R. 51.6% and 66.4% certified top-k recall @ R. as well as 33.0% and 42.6% certified top-k fl-score @ R when k' = 1, h = 3, and R = 0.5.
Empirically, we evaluate our MultiGuard on VOC 2007,
VOC 2007 dataset, Jia et al. [2]
Our major contributions can be summarized as follows:
We propose MultiGuard, the first provably robust defense against adversarial examples for multi- label classification.
We design a Monte Carlo algorithm to compute the certified intersection size.
We evaluate our MultiGuard on VOC 2007, MS-COCO, and NUS- LUS-WIDE benchmark datasets.
2 Background and Related Work
Multi-label classification: In multi-label classification, a multi-label classifier predicts multiple 21
labels for an input. Many deep learning classifiers [27 52 43 45| 57 32
54
48 [3] have
been proposed for multi-label classification. For instance, a naive method for multi- classification to train independent binary classifiers for each label and use ranking or thresholding to derive the final predicted labels. This method, however, ignores the topology structure among labels and thus cannot capture the label co-occurrence dependency (e.g., mouse and keyboard usually appear together). In response, several methods 45] 7 have been proposed to improve the performance of multi-label classification via exploiting the label dependencies in an imput. Despite their effectiveness, these methods rely on complicated architecture modifications. To mitigate the issue, some recent studies [48] 2 proposed to design new loss functions. For instance, Baruch et al. [2] introduced an asymmetric loss (ASL). Roughly speaking, their method is based on the observation that, in multi- label classification, most inputs contain only a small fraction of the possible candidate labels, which leads to
gradients from positive labels during training. Their experimental results indicate that their method achieves state-of-the-ar performance on multiple benchmark datasets.
Ad Adversarial examples to multi-label classification: Several recent studies 440 56
53
30 (0
showed that multi-label classification is vulnerable to adversarial examples. An attacker can manip- ulate the set of labels predicted by a multi-label classifier for an input via adding carefully crafted perturbation to it. For instance, Song et al. (40 proposed white-box, targeted attacks to multi-label classification. In particular, they first formulate their attacks as optimization problems and then use gradient descent to solve them. Their experimental results indicate that they can make a multi-label classifier produce an arbitrary set of labels for input via adding adversarial perturbation to it. Yang et al. 53 explored the worst-case ciis-caassfiiation risk of a multi-label classifier. In particular, they bi-level set function optimization problem and leverage random greedy
formulate the problem search to find an approximate solution. Zhou et al. (56) proposed to generate &g -norm adversarial perturbations to fool multi-label classifier. In particular, they transform the optimization problem of finding adversarial perturbations into a linear programming problem which can be solved efficiently.
Existing empirically robust defenses: Some studies [49 1 30 developed empirical defenses to mitigate adversarial examples in multi-label classification. For instance, Wu et al. (49 applied adversarial training. method developed to train robust multi-class classifiers, to improve the robustness of multi-label classifiers. Melacci et al. [30] showed that domain knowledge, which measures the relationships among classes, can be used to detect adversarial examples and improve the robustness of multi- classifiers. However, all these defenses lack provable robustness guarantees and thus, they often broken by advanced adaptive attacks. For instance, Melacci et al. (30] showed that their defenses can be broken by adaptive attacks that also consider the domain knowledge.
Existing provably robust defenses: All existing provably robust defenses [3 10
6
19 8 17 46
4 22 12 26 36 23
47
(3)
31
38 55 50 were designed for multi-class classification instead
of multi-label classification. In particular, they guarantee that robust multi-class classifier
3

---

predicts the same single label for an input or a label (e.g.. the single ground truth label of the input) is among the top-k labels predicted by a robust multi-class classifier. These defenses are sub-optimal for multi-label classification. Specifically, in multi-label classification, we aim to guarantee that at least some ground truth labels of an input are in the set of labels predicted by robust multi-label classifier.
MultiGuard leverages randomized smoothing 224 26 12 22 51. Existing randomized smoothing studies (e.g., Jia et al. [22]] achieve sub-optimal provable robustness guarantees (i.e., certified intersection size) for multi-labed classification, because they are designed for multi-class classification. For example, as our empirical evaluation results will show, MultiGuard significantly outperforms multi-label classification. Technically speaking, our work has two key differences with Jia et al.. First, the base multi- 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 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 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 33 which is applicable to multiple functions while Jia et al. uses the standard Neyman- Peannon Lemma [3 which is only applicable to single function. Moreover, we use the law of contraposition to derive certified intersection size, which is not required by Jia et al..
Jia et al. [22] when extending
3
Our MultiGuard
3.1 Building our MultiGuard
Label probability: Suppose we have a multi-label classifter f which we call base multi-label classifier. Given an input x, the base multi-label classifier If predicts k'' labels for it. For simplicity, we use for (x) to denote the set of k labels predicted by f for x. We use E to denote an isotropic Gaussian noise, i.e., (0, o². I), where a is the standard deviation and I is an identity matrix. Given x + as input, the output of f would be random due to the randomness of e, i.e. Jw (x + e) is random set of k' labels. We define label probability pt as the probability that the label i is among the set of top-k' labels predicted by f when adding isotropic Gaussian noise to an input x, where i {1,2, ... cc. Formally, we have P. Pr(i E fw (x + c)).
Our smoothed multi-label classifier: Given the label probability p, 's for an input x, our smoothed multi-label classifier g predicts the k labels with the largest label probabilities for x. For simplicity, we use (x) to denote the set of k labels predicted by our smoothed multi-label classifier for an input x.
Certified intersection size: An attacker adds a perturbation 5 to an input x. 9a (x + 6) is the set of l labels predicted by our smoothed multi-label classifier for the perturbed input x + ô. Given set of labels [xx) (e.g., the ground truth labels of x), our goal is to show that at least of them are in the set of & labels predicted by our smoothed multi-label classifier for the perturbed input, when the fz-norm of the adversarial perturbation is at most R. Formally, we aim to show the following:
min [(x) n gx + 8)1 2 c. S
where we call e certified intersection size. Note that different inputs may have different certified intersection sizes.
3.2 Deriving the Certified Intersection Size
Defining two random variables: Given an input x, we define two random variables X = x Y = x 5 +e, where is an adversarial perturbation and is isotropic Gaussian noise. Roughly speaking, the random variables X and Y respectively denote the inputs derived by adding isotropic Gaussian noise to the input x and its adversarially perturbed version x + 8. Based on the definition of the label probability, we have p;
Pr(i E fir (X)). We define adversarial label probability pf as P. = Pr(i E fie (Y)), i E (1, 2, ................................ .c. Intuitively, adversarial label probability Pi is the probability that the label is in the set of ke' labels predicted by the base multi-label classifier ʃ for Y. Given an adversarially perturbed input x + ō, our smoothed multi-label classifier predicts the & labels with the largest adversarial label probabilities p. for it.

---

Derivation sketch; We leverage the law of contraposition in our derivation. Roughly speaking. if we have a statement: P - Q. then its contrapositive is: -Q - -P, where is the logical negation symbol. The law of contraposition claims that a statement is true if and only if its contrapositive is true. particular, we define the following predicate:
: min [L(x) n 94 (x 6xx
&116
Intuitively, Q is true if at least e labels in L(x) can be found in 9*(x + d) for an arbitrary adversarial perturbation whose fy-norm is no larger than R. Then, we have -Q mins,, [x(x
gx(x+ + 6)1 e. Moreover, we derive a necessary condition (denoted as -P) for -Q be true, i... -Q P. Roughly speaking, -P compares upper bounds of the adversarial label probabilities of the labels in {1, .......... .c}
[xx) with lower bounds of those in L(x). More specifically, -P represents that the lower bound of the eth largest adversarial label probability of labels in L(x) is no larger than the upper bound of the (k- + 1 1)th largest adversarial label probability of the labels in 21.2. .c \ L(x). Finally, based on the law of contraposition, we have P - Q, i.e. Q is true if is true (i.e.. -P is false).
The major challenges we face when deriving the necessary condition -P are as follows: (1) the adversarial perturbation 8 can be arbitrary as long as its fg-norm is no larger than R. which has infinitely many values, and (2) the complexity of the classifier (c.g.. complex deep neural network) and the continuity of the random variable Y make it hard to compute the adversarial label probabilities. We propose an innovative method to solve the challenges based on two key observations: (1) the random variable Y reduces X under no attacks (i.e., = 0) and (2) the adversarial perturbation is bounded, i.e., ||ō]|, I R. Our core idea is to bound the adversarial label probabilities using the label probabilities. Suppose we have the following bounds for the label probabilities (we propose an algorithm to estimate such bounds in Section 3.3
p: 2 Ps. Vi L(x),
(3)
P5 S,, Vj E (1,2, .c) L(x).
(4)
Given the bounds for label probabilities, we derive lower bound of the adversarial label probability for each label E L(x) and an upper bound of the adversarial label probability for each label
j E {1, ... .c} \ Lxx). To derive these bounds, we propose variant of the Seyman-PParson Lemma 33 which enables us to consider multiple functions. In contrast, the standard Neyman-
Pearson Lemma 33 is insufficient as it is only applicable to single function while the base multi-label classifier outputs multiple labels.
We give an overview of our derivation of the bounds of the adversarial label probabilities and show the details in the proof of the Theorem T in supplementary material. Our idea construct some regions in the domain space of X and Y via our variant of the Neyman- Pearson Lemma. Specifically, given the constructed regions, we can obtain the lower/upper bounds of the adversarial label probabilities using the probabilities that the random variable Y is in these regions. Note that the probabilities that the random variables X and Y are in these regions can be casily computed as we know their probability density functions.
Next, derive lower bound of the adversarial label probability p (i E I(x)) as example to illustrate our main idea. Our derivation of the upper bound of the adversarial label probability for label in {1, ...,.... \ L(x) follows similar procedure. Given label i L(x). we can find region A, via our variant of Neyman-Pearson Lemma (33 such that Pr(X E A:) = p;. Then, we
can derive a lower bound of p via computing the probability of the random variable Y in the region Ar, i.e., we have:
(5) The above lower bound can be further improved via jointly considering multiple labels in Lxx). Suppose we use I.. L(x) denote an arbitrary set of u labels. We can craft a region Ar. via
p 2 Pr(Y E A.).
variant of Neyman- Peansonn Lemma such that we have Pr(X Ar.)) Eier, Pt Then, can derive the following lower bound:
k' Pr(Y E Ar.). N
max REr u
P
(6)
The eth largest lower bounds of adversarial label probabilities of labels in T.(x) can be derived by combing the lower bounds in Equation and Formally, we have the following theorem:
5

---

Theorem 1 (Certified Intersection Size). Suppose we are given an input x, a base multi-label classifier f. our smoothed classifier g. and a set of d ground truth labels L(x) {aj a2. ..a for x. Moreover, we have lower bound Pt of pr for each i E T.(x satisfying Equation 3 and an upper bound? Pj of Pj for each j E {1,2, ... ,c] ,00,,,,,,,), for convenience. Let Pbi 2 Pbz
L(x) satisfying Equation 4 We assume Pai 2 2.. 2 Pas Pbe-a be the e d label probability upper bounds for the labels in 21,2, c} L(x). where ties are broken uniformly random. Given perturbation size R. we have the following guarantee:
min &.IAA||25R
[[(x) n gx + 8)1 2
where is the optimal solution to the following optimization problem or 0 if it does not have solution;
argmax e1=1,2,0 min(d,e)
s.t. m (Po
R
max
k'
(
PA_ -11
k
R
PB R
> min (Po,)
o ),
(8)
where and 4 respectively are the cumulative distribution function and its inverse of the standard Gaussian distribution, 1) = dd-e++1, PA...
Eize" 4u-1
Pay. $ = k k e' c''+1, and PB. -i==s-41 Pop
Proof. Please refer to Appendix A in supplementary material.
We have the following remarks for our theorem:
When k' = k = and L(x) only contains a single label, our certified intersection size reduces to the robustness result derived by Cohen et al. [12), i.e., the smoothed classifier provably predicts the same label for an input when the adversarial perturbation is bounded. When k' = 1, k 2 1, and [(x) only contains a single label, our certified intersection size reduces the robustness result derived by Jia et al. [22). i.e., label is provably among the k labels predicted by a smoothed classifier when the adversarial perturbation is bounded. other words, the certified robustness guarantees derived by Cohen et al. [12] and Jia et al. [22] are special cases of our results. Note that Cohen et al. a special case of Jia 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 fy-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 E [(x) and upper bound of the label probability for each label j E {1,2, ..,,,,.... ,c} \ L(x). Moreover, when the label probability bounds are estimated more accurately, our certified intersection size may be larger.
Our theorem requires PA. S k and PB. S W. We have PA, PA, S Eiel(x) Pi S Ej=1 k'. In Section 3.3 our estimated PB, will always be no larger than k.. Thus, can apply our theorem in practice.
We note that there are respectively two terms the left- and right-hand sides of Equation 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.
3.3 Computing the Certified Intersection Size
In order to compute the certified intersection size for an input we need to solve the optimization problem in Equation [ The key challenge of solving the optimization problem to estimate lower bounds P; of label probabilities for i E L(x) and upper bounds P, of label probabilities for E 21,2, , c) L(x). To address the challenge, we design a Monte Carlo algorithm to estimate these label probability bounds with probabilistic guarantees. Then, given the estimated label probability bounds, we solve the optimization problem to obtain the certified intersection size.

---

Estimating label probability bounds: We randomly sample n Gaussian noise from and add them to the input x. We use x²_ x² ,.... ,x to denote the n noisy inputs for convenience. Given these noisy inputs, we use the base multi-label classifier I to predict k' labels for each of them. Moreover, we define the label frequency n. of label as the number of noisy inputs whose predicted k' labels include i. Formally, we have n; = >" I[i E fxx(x))), E f1.2,....,a c). where is an indicator function. Based on the definition of label probability Ps. we know that n, follows a binomial distribution with parameters n and pi. where is the number of noisy inputs and p; is the label probability of label i. Our goal is to estimate a lower or upper bound of pi based on n, and n, which is a binomial proportion confidence interval estimation problem. Therefore, we can use the Clopper-Pearson [T] method from the statistics community to estimate these label probability bounds. Formally, we have the following label probability bounds:
p Beta( = Th, n nu + 1), E L(x),
(9)
F, Beta(1 c n,, n, + 1), Vj E (1,2.-.., ,c] L(x),
(10)
where 1- - is the confidence level and (eta(p; s, 1)) is the pth quantile of the Beta distribution with
shape parameters and e. Based on Bonferroni correction 314, the overall confidence level for the label probability upper or lower bounds is a. To solve the optimization problem in Equation g
we also need to estimate PA. and PB.. In particular, we can estimate PA. = Σ
'' +u-1
Po and
PB. Li=s-u+1% However, this bound may be loose for PB.. We can further improve the bound via considering the constraint that PB. + EiEL(x) Pi I K. In other words, we have PB. S k' -iE Pt. Given this constraint, we can estimate PB. = min(Ci= Pb, K' - EiEL(x) P.). Note that the above constraint is not applicable for PA... since it is a lower bound.
Solving the optimization problem in Equation 8 Given the estimated label probability lower or upper bounds, we solve the optimization problem in Equation 8 via binary search.
Algorithm 1 in supplementary materials shows our complete algorithm to compute the certified intersection size for an input x. The function RANDOMS AMPLE returns n noisy inputs via first sampling noise from the isotropic Gaussian distribution and then adding them the input x. Given the label frequency for each label and the overall confidence a as input, the function PRON aims to estimate the label probability bounds based on Equation and Io] The function BINARYSEARCH returns the certified intersection size via solving the optimization problem in Equation 8 using binary search.
Complete algorithm:
4 Evaluation
4.1 Experimental Setup
Datasets: We adopt the following multi-label classification benchmark datasets:
VOC 2007 [15]: Pascal Visual Object Classes Challenge (VOC 2007) dataset [15] contains 9,963 images from 20 objects (i.c., classes). On average, each image has 2.5 objects. Following previous work 44 split the dataset into 5,011 training images and 4,952 testing images.
MS-COCO [28]: Cierosoft-COCOO (MS-COCO) 28) dataset contains 82,081 training images, 40,504 validation images, and 40,775 testing images from 80 objects. Each image has 2.9 objects on average. The images in the testing dataset do not have ground truth labels. Therefore, following previous work (7]. we evaluate our method on the validation dataset.
NUS-WIDE 9 : NUS-WIDE dataset 9 originally contains 269,648 images from Flickr. The images are manually annotated into 81 visual concepts, with 2.4 visual concepts per image on average. Since the URLs of certain images are not accessible, we adopt the version released by (2). which contains 154,000 training images and 66,000 testing images.
certified defenses for multi-class classification, we randomly sample 500 images from the testing (or validation) dataset of each dataset to evaluate our MultiGuard.
Similar to previous work 12 25
We adopt ASL (2 to train the base multi-label classifiers on the three benchmark datasets. In particular, ASL leverages an asymmetric loss to solve the positive-negative imbalance issue (an image has a few positive labels while has many negative labels average) in multi-label classification, and achieves state-of-the-arr performance on the three benchmark datasets. Suppose qj is the probability that base multi-label classifier predicts label j (j 1,2,. ,c) for
Base multi-label classifiers:
7

---

training imput. Moreover, we let y, be 1 (or 0) if the label j is (or is not) ground truth label of the training input. The loss of ASL [2] is as follows: L AST. Σj= ツル (1 yj y where Lj+ (1 1 7+ log(4;) and ش = (max(q) m, 0)) log (1 - max(q; mn, 0)). Note that
0, 7- 4. 7+. 7-, and m are hyperparameters. Following 22. we set training hyperameters -3- and batch size and m = 0.05. We train the classifier using Adam optimizer, using learning rate 10
32. We adopt the public implementation of ASI in our experiments. Similar to previous work [22 on randomized smoothing based multi- claas classification, we add isotropic Gaussian noise to the training data when we train our base multi-label classifiers. In particular, given a batch of training images, we add isotropic Gaussian noise to each of them, and then we use the noisy training images to update the base multi-label classifier. Our experimental results indicate that such training method can substantially improve the robustness of our MultiGuard (please refer to Figurefojn supplementary material).
Evaluation metrics: We use certified top-k precision R. certified top-k recall@ R, and certi- fied top-k fl-score as evaluation metrics. We first define them for single testing input and then for multiple testing inputs. In particular, given the certified intersection size for test- ing input x under perturbation size R. we define them as follows: certified top-k precision&/R = e/k, certified top-k r ex)] certified top-k fl-score@R R 2 e + k)), where L(x) is the set of ground truth labels of x and the symbol| in a set. Roughly speaking, certified top-k precision @ R is the least fraction of the & predicted labels for an input that are ground truth labels, when the f2-norm of the adversarial perturbation is at most R; certified top-k recall @ R is the least fraction of the ground truth labels in I.(x) that are in the labels predicted by MultiGuard; and certified top-k fl-score@ @ R measures a trade-off between certified top-k precision @ R and certified top-k recall @ R. Note that the above definition is for a single testing input. Given a /eating/validationn dataset with multiple testing inputs, the overall certified top-k precision @ R. certified top-k recall @ R. and certified top-k fl-score@ R are computed as the averages over the testing inputs.
measures the number of elements
Compared methods: We compare with the state-of-the-an certified defense, namely Jia et al. [2] by extending it to multi- classification. To the best of our knowledge, Jia et al. is the only certified defense that considers top-k predictions against & no-mo adversarial perturbations. Given an arbitrary label, Jia et al. derived a certified radius such that the label is among the top-k labels predicted by the smoothed classifier (Theorem certified radius. Given perturbation size R. the certified intersection size e can be computed as the number of labels in Lxx) whose certified radii are larger than R.
Jia et al.). For each label in L(x). we compute a
Parameter setting: Our MultiGuard has the following parameters: k (the number of labels predicted by the base multi-label classifier for an input), & (the number of labels predicted by our smoothed multi-label classifier for an input), standard deviation a, number of noisy inputs and confidence level a. Unless otherwise mentioned, we adopt the following default parameters: a = 0.001, 1. 000, a = 0.5, k = and k 3 for VOC 2007 dataset, and k'' = 3 and A 10 for MS-COCO and NUS-WIDE datasets, where we use larger ke' and i for MS-COCS and NUS- WIDE because they have more classes.
4.2 Experimental Results
The first row in Figure [ shows the comparison results on VOC 2007 dataset in default setting. We find that MultiGuard achieves higher certified top-k precision @ R. certified top-k recall@ @ R, and certified top-k fl-score @ R. than Jia et al.. MultiGuard is better than Jia et al. because MultiGuard jointly considers all ground truth labels, while Jia et al. can only consider each ground truth label independently. For instance, suppose we have two ground truth labels; it is very likely that both of them are not in the top-k predicted labels when considered independently, but at least one of them is among the top-k predicted labels when considered jointly. The intuition is that it easier for an attacker to find an adversarial perturbation such that certain label is not in the top-k predicted labels, but it is more challenging for an attacker to find an adversarial perturbation such that both of the two labels are not in the top-k predicted labels. Our observations on the other two datasets are similar, which can be found in Figure 2 in supplementary material.
Comparison results:
8

---

mt. MubiGuord
coriiled tep-i wwp--t/f--rorree fo-rree
MuhiGuard
Muhiiuarr
cerdricd took
carttic
94
00
2.0
90
20
='=1
carrival seplccooll
===1
cotiffed (op--t---eeeee
K'
K'-3
K'
k=1
contifod topsk (1-40r0
x=1
k=3
==
k=
0.25
centitel popek mrail
curtiffed toppl E1-sare
0.5
0-
0.5
0-1
0-1
n 100
nartiful mreal
n= 100
centifee topk fl-om
1=100
1,000
D 10, 000
10, 000
- 0,000
certifee topel meil
comiiee toppk (1-00re
0.001
- 0.001
0.001
(a) Certified top-k precision @ R
(b) Certified top-k recall R
(c) Certified top-k fl-score@) R
Figure 1: Comparing with Jia et al. [22] (first row). Impact of k' (second row), k (third row), a (fourth row), n (fifth row), and a (sixth row) on certified top-k precision R, certified top-k recall@ R, and certified top-k fl-score@ R. The dataset is VOC 2007. The results the other two datasets are shown in supplementary material.

---

Impact of k': The second row in Figure shows the impact of k' on VOC 2007 dataset. In particular, we find that larger k' achieves a larger certified top-k precision R (or certified top-k recall @ R or certified top-k f1-score @ R) without attacks (i.e., R 0), but the curves drop more quickly as R increases (i.e., a larger k' is less robust against adversarial examples as increases). The reason is that larger k'' gives an attacker larger attack space. Note that this is also reflected in our optimization problem in Equation [
In particular, the left-hand (or right-hand) side in Equation decreases (or increases) as k' increases, which leads to smaller certified intersection size K increases, We have similar observations on MS-COCO and NUS-WIDE datasets. Please refer to Figure in supplementary material.
Impact of k: The third row in Figure [ shows the impact of & on VOC 2007 dataset. We have the following observations from experimental results. First, A achieves a tradeoff between the certified top-k precision @ R without attacks and robustness. In particular, a larger k gives us a smaller certified top-k precision @ I without attacks, but the curve drops more slowly as R increases (i.e..& a larger & is more robust against adversarial examples as R increases). Second, we find that certified top-k recall @ R increases as k increases. The reason is that more labels predicted by our MultiGuard as & increases. Third, similar to certified top-k precision @ R. l also achieves a tradeoff between the certified top-k fl-score@)) R without attacks and robustness. We also have those observations on the other two datasets. Please refer to Figure in supplementary material for details.
Impact of a: The fourth in Figure shows the impact of VOC 2007 dataset. The experimental results indicate that a achieves a tradeoff between the certified top-k precision @ R (or certified top-k recall @ R or certified top-k fl-score@) Rt) without attacks (i.e., R = 0) and robustness. Specifically, a larger a leads to a smaller certified top-k precision@ R (or certified top-k recall @ It or certified top-k fl-score@ @ I2) without attacks, but is more robust against adversarial examples as R increases. The observations on the other two datasets are similar. Please refer to Figure S in supplementary material.
Impact of n and a: The fifth and sixth rows in Figure Saaree[ressse respectivel show the impact of n and on VOC 2007 dataset. In particular, we find that certified top-k precision @ R (or certified top-k recall@ @ R or certified top-k fl fl-score@ I2) increases as n or a increases. The reason is that a larger n or a gives us tighter lower or upper bounds of the label probabilities. which leads larger certified intersection sizes. However, we find that the certified top-k precision @ R (or certified top-k recall @ R or certified top-k fl-score@ R) insensitive to a once is small enough and insensitive to n once is large enough.
Effectiveness of the second terms in Equation 8 We perform experiments under our default setting to validate the effectiveness of our second terms in the left- and right-hand sides of Equation 8 Our results are as follows: with and without the second terms, MultiGuard respectively achieves 31.3% and 23.6% certified top-k precision @ R. 66.4% and 48.8% certified top-k recall @ R. as well as 42.6% and 31 8% certified top-k f1-score@: @ R. where the perturbation size R = 0.5 and the dataset is VOC 2007. As the result shows, our second terms can significantly improve certified intersection size.
5 Conclusion
In this paper, we propose MultiGuard, the first provably robust defense against adversarial examples for multi-label classification. In particular, we show that a certain number of ground truth labels of an input are provably predicted by our MultiGuard when the -orm of the adversarial perturbation added to the input is bounded. Moreover, we design an algorithm to compute the certified robustness guarantees. Empirically, we conduct experiments on VOC 2007, MS-COCO, and NUS-WIDD benchmark datasets to validate our MultiGuard. Interesting future work to improve MultiGuard includes: 1) incorporating the knowledge of the base multi-label classifier, and 2) designing new methods to train more accurate base multi-label classifiers.
Acknowledgements:
We thank the anonymous reviewers for constructive comments. This work was supported by NSF under Grant No. 1937786 and 2125977 and the Army Research Office under Grant No. 191
10

---

References
[1] Rohit Babbar and Bernhard Schölkopf. Adversarial extreme multi-label classification. arXiv preprint arXiv:1803.0153 2018.
[2] Emanuel Ben-Baruch, Tal Ridnik, Nadav Zamir, Asaf Noy, Itamar Friedman, Matan Protter, and Lihi Zelnik-Manor Asymmetric loss for multi-label classification, 2020.
[3] Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del Istituto Superiore di Scienze Economiche Commericiali di Firenze, 8:3-62, 1936.
[4] Rudy R Buncl, llker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view piecewise linear neural network verification. In NeurlPS, 2018.
[5] Xiaoyu Cao and Neil Zhenqiang Gong, Mitigating evasion attacks to deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, pages 278-287, 2017.
[6] Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. Provably minimally- adversarial examples. arXiv, 2017.
[7] Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo. Multi-label image recognition with graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5177-5186, 2019.
[8] Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 251-268 Springer, 2017.
[9] Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yantao Zheng. Nus- wide: real-world web image database from national university of singapore. In Proceedings of the ACM International Conference on Image and Video Retrieval, CIVR '09, New York, NY, USA, 2009. Association for Computing Machinery.
[10] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pages 854-863. PMLR, 2017.
[11] Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-411 1934.
[12] Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.0021.9 2019.
[13] Son D Dao, Ethan Zhao, Dinh Phung. and Jianfci Cai. Multi-label image classification with contrastive learning, arXiv preprint arXiv:2107.11626 2021.
[14] Olive Jean Dunn. Multiple comparisons among means. Journal of the American statistical association, 56(293):52 64, 1961.
[15] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results. http://www.paseal. network
html.
[16] Zongyuan Ge, Dwarikanath Mahapatra, Suman Sedai, Rahil Garnavi, and Rajib Chakra- vorty. Chest x-rays classification: multi-label and fine-grained problem. arXiv preprint 1MXi::1807.07244 2018.
[17] Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2018.
[18] Marian George and Christian Floerkemeier. Recognizing products: A per-exemplar multi-label image classification approach. European Conference on Computer Vision, pages 440-455. Springer, 2014.

---

[19] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin. Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 18 18.00.2211 12715, 2018.
[20] Shu Hu, Lipeng Ke, Xin Wang, and Siwei Lyu. Tkml-ap: Adversarial attacks to top-k multi- label learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7649-7657, 2021.
[21] Dat Huynh and Ehsan Elhamifar. Interactive multi-label cnn learning with partial labels. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 9423-9433 9432, 2020.
[22] Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In International Conference on Learning Representations, 2020.
[23] Jinyuan Jia, Binghui Wang, Xiaoyu Cao. Hongbin Liu, and Neil Zhenqiang Gong, Almost tight 10-norm certified robustness of top-k predictions against adversarial perturbations. In International Conference on Learning Representations, 2022.
[24] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE Symposium Security and Privacy (SP), pages 656-672. IEEE, 2019.
[25] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, pages 49 4910-4921, 2019.
[26] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, pages 9464-94499 2019.
[27] Xin Li, Feipeng Zhao, and Yuhong Guo. Multi-label image classification with a probabilistic label enhancement model. In UAI, volume 1, pages 1-10, 2014.
[28) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollar, and Larry Zitnick. Microsoft coco: Common objects in context. In ECCV. European Conference on Computer Vision, September 2014.
[29] Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pages 369-385, 2018
[30] Stefano Melacci, Gabriele Ciravegna, Angelo Sotgiu, Ambra Demontis, Battista Biggio, Marco Gori, and Fabio Roli. Can domain knowledge alleviate adversarial attacks in multi-label classifiers? arXiv preprint (rXXi:2000603833, 2020.
[31] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pages 3578-3586, 2018
[32] Jinseok Nam, Eneldo Loza Mencía, Hyunwoo Kim, and Johannes Fürnkranz. Maximizing subset accuracy with recurrent neural networks in multi-label classification. In Proceedings of the 3t International Conference on Neural Information Processing Systems, pages $419-5429 5429, 2017.
[33] Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London., 269( 706):289-333 -37, 1933.
[34] Joannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artieres, George Paliouras, Eric Gaussier, Ion Androutsopoulos, Massih-Rezz Amini, and Patrick Galinari. Lshte: benchmark for large-scale text classification. arXiv preprint arXiv: 08581, 2015.
12

---

[35] Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for multi- label classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 259-269. Springer, 2009.
[36] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pages 11292-11303 2019.
[37] Karsten Scheibler, Leonore Winterer, Ralf Wimmer, and Bernd Becker. Towards verification of artificial neural networks. In MBMV, 2015.
[38] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. NeurlPS, 1(4):6, 2018.
[39] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):1- 30, 2019.
[40] Qingquan Song, Haifeng Jin, Xiao Huang, and Xia Hu. Multi-label adversarial perturbations. In 2018 IEEE International Conference on Data Mining (ICDM), pages 1242-1247. IEEE, 2018.
[41] Konstantinos Trohidis, Grigorios Tsoumakas, George Kalliris, and Ioannis P Vlahavas. Multi- label classification of music into emotions. In ISMIR, volume 8, pages 325-330, 2008.
[42] Grigorios Tsoumakas and loannis Katakis. Multi-label classification: An overview. Interna- tional Journal of Data Warehousing and Mining (IJDWM), 2007.
[43] Jinng Wang. Yi Yang, Junhua Mao, Zhiheng Huang, Chang Huang, and Wei Xu. Cnn-rnn: A unified framework for multi-label image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2285-2294, 2016.
[44] Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang. and Suman Jana. Efficient formal safety analysis of neural networks. arXiv preprint arXiv: 1809 2018.
[45] Zhouxia Wang, Tianshui Chen, Guanbin Li, Ruijia Xu, and Liang Lin. Multi-label image recog- nition by recurrently discovering attentional regions. In Proceedings of the IEEE international conference on computer vision, pages 464 472, 2017.
[46] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295 PMLR, 2018
[47] Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. arXiv preprint 1xxiv:8805 /2514, 2018.
[48] Tong Wu, Qingqiu Huang, Ziwei Liu, Yu Wang, and Dahua Lin. Distribution-balancee loss for multi-label classification in long-tailed datasets. In European Conference on Computer Vision, pages 162-178. Springer, 2020.
[49] Yi Wu, David Bamman, and Stuart Russell. Adversarial training for relation extraction. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1778-1783. 2017.
[50] Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Train- ing for faster adversarial robustness verification via inducing relu stability. arXiv preprint 1rXiv:1809.03000 2018.
[51] Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, 2020.
[52] Hao Yang. Joey Tianyi Zhou, Yu Zhang, Bin-Bin Gao, Jianxin Wu, and Jianfei Cai. Exploit bounding box annotations for mubti-label object recognition. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 280-288, 2016.
13

---

[53] Zhuo Yang, Yufei Han, and Xiangliang Zhang. Characterizing the evasion attackability of multi-label classifiers. In AAAI, 2021.
[54] Renchun You, Zhiyao Guo, Lei Cui, Xiang Long, Yingze Bao, and Shilei Wen. Cross-modality attention with semantic graph embedding for multi-label classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 12709-12716, 2020.
[55] Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv:1906.066 19366663666666....11111 2019.
[56] Nan Zhou, Wenjian Luo, Xin Lin, Peilan Xu, and Zhenya Zhang. Generating multi-label adversarial examples by linear programming. In 2020 International Joint Conference Neural Networks (IJCNN) pages 1-8. IEEE, 2020.
[57] Feng Zhu, Hongsheng Li, Wanli Ouyang, Nenghai Yu, and Xiaogang Wang. Learning spatial regularization with image-level supervisions for multi-label image classification. In Proceedings of the IEEE Conference Computer Vision and Patern Recognition, pages 5513-5522 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [N/A] We have formal guarantees for our experimental results
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL.? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "TqhDKd5_5ik", "reviewer": "Reviewer_RjyH", "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]. ", "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.  \n\n######\n\nWe 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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points: \n\n1. 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. \n\n2. The theoretical study is solid and points out clearly the relation between the proposed method and the previous random-smoothing techniques. \n\nWeak points: \n\nThe 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.  \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Q5T60HS986g", "reviewer": "Reviewer_9w49", "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.\n\nExperiments 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.\n", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- 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.\n\n- 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.\n\nWeakness:\n\n- 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E0g0EV0g6so", "reviewer": "Reviewer_7aeN", "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.", "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.\n\n- 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.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.\n- Handles an important problem: multi-class certification is a common learning task formulation, e.g., in computer vision.\n- Significant experimental results: consistently beating an adapted baseline (from top-k randomized smoothing certification).\n- Writing quality is good.\n\nWeaknesses:\n- Some mathematical illustrations may not be rigor enough. See \"Questions\" for more details.\n- The underlying technical idea is a bit straightforward, or not explained clearly enough in terms of challenges. See \"Limitations\" for more detail.\n\nNote: 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0dDa639s_KP", "reviewer": "Reviewer_95yU", "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.", "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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nFurthermore, 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept