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. W911NF2110182.


Checklist

For all authors...

Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?

Did you describe the limitations of your work?

Did you discuss any potential negative societal impacts of your work?

Have you read the ethics review guidelines and ensured that your paper conforms to them?


If you are including theoretical results...

Did you state the full set of assumptions of all theoretical results?

Did you include complete proofs of all theoretical results?


If you ran experiments...

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?
We have formal guarantees for our experimental results

Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?


If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

If your work uses existing assets, did you cite the creators?

Did you mention the license of the assets?

Did you include any new assets either in the supplemental material or as a URL?

Did you discuss whether and how consent was obtained from people whose data you're using/curating?

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?


If you used crowdsourcing or conducted research with human subjects...

Did you include the full text of instructions given to participants and screenshots, if applicable?

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable?

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?



Proof of Theorem  REF
We first define some notations that will be used in our proof. Given an input \(\mathbf {x}\) , we define the following two random variables:
\(& \mathbf {X}=\mathbf {x}+\epsilon \sim \mathcal {N}(\mathbf {x},\sigma ^{2}I), \\& \mathbf {Y}=\mathbf {x}+\delta +\epsilon \sim \mathcal {N}(\mathbf {x}+\delta ,\sigma ^{2}I),\) 

where \(\epsilon \sim \mathcal {N}(0,\sigma ^2 I)\)  and \(\delta \)  is an adversarial perturbation that has the same size with \(\mathbf {x}\) . The random variables \(\mathbf {X}\)  and \(\mathbf {Y}\)  represent random inputs obtained by adding isotropic Gaussian noise to the input \(\mathbf {x}\)  and its perturbed version \(\mathbf {x}+\delta \) , respectively.
Cohen et al. [1]} applied the standard Neyman-Pearson lemma [2]} to the above two random variables, and obtained the following two lemmas:
Lemma 1 (Neyman-Pearson lemma for Gaussian with different means) 

Let \(\mathbf {X}\sim \mathcal {N}(\mathbf {x},\sigma ^2 I)\) , \(\mathbf {Y}\sim \mathcal {N}(\mathbf {x}+\delta ,\sigma ^2 I)\) , and \(F:\mathbb {R}^d\xrightarrow{} \lbrace 0,1\rbrace \)  be a random or deterministic function. Then, we have the following:
(1) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \delta ^{T}\mathbf {w} \le \beta \rbrace \)  for some \(\beta \)  and \(\text{Pr}(F(\mathbf {X})=1)\ge \text{Pr}(\mathbf {X}\in W)\) , then \(\text{Pr}(F(\mathbf {Y})=1)\ge \text{Pr}(\mathbf {Y}\in W)\) .
(2) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \delta ^{T}\mathbf {w} \ge \beta \rbrace \)  for some \(\beta \)  and \(\text{Pr}(F(\mathbf {X})=1)\le \text{Pr}(\mathbf {X}\in W)\) , then \(\text{Pr}(F(\mathbf {Y})=1)\le \text{Pr}(\mathbf {Y}\in W)\) .

Lemma 2 
Given an input \(\mathbf {x}\) , a real number \(q\in [0,1]\) , as well as regions \(\mathcal {A}\)  and \(\mathcal {B}\)  defined as follows:
\(&\mathcal {A}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\le \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(q)\rbrace , \\&\mathcal {B}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\ge \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(1-q)\rbrace ,\) 

we have the following:
\(&\text{Pr}(\mathbf {X}\in \mathcal {A})= q, \\ &\text{Pr}(\mathbf {X}\in \mathcal {B})= q, \\&\text{Pr}(\mathbf {Y}\in \mathcal {A})=\Phi (\Phi ^{-1}(q)-\frac{\left\Vert \delta \right\Vert _2}{\sigma }), \\&\text{Pr}(\mathbf {Y}\in \mathcal {B})=\Phi (\Phi ^{-1}(q)+\frac{\left\Vert \delta \right\Vert _2}{\sigma }).\) 

Please refer to [1]}.
Next, we first generalize the Neyman-Pearson lemma to the case of multiple functions and then derive the lemmas that will be used in our proof.
Lemma 3 
Let \(\mathbf {X}\) , \(\mathbf {Y}\)  be two random variables whose probability densities are respectively \(\text{Pr}(\mathbf {X}=\mathbf {w})\)  and \(\text{Pr}(\mathbf {Y}=\mathbf {w})\) , where \(\mathbf {w}\in \mathbb {R}^{d}\) . Let \(F_{1}, F_{2}, \cdots , F_{t}:\mathbb {R}^d\xrightarrow{} \lbrace 0,1\rbrace \)  be \(t\)  random or deterministic functions. Let \(k^{\prime }\)  be an integer such that:
\(\sum _{i=1}^{t}F_{i}(1|\mathbf {w})\le k^{\prime }, \forall \mathbf {w}\in \mathbb {R}^{d},\) 

where \(F_{i}(1|\mathbf {w})\)  denotes the probability that \(F_{i}(\mathbf {w})=1\) .
Then, we have the following:
(1) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \text{Pr}(\mathbf {Y}=\mathbf {w})/\text{Pr}(\mathbf {X}=\mathbf {w}) \le \mu \rbrace \)  for some \(\mu > 0\)  and \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}\ge \text{Pr}(\mathbf {X}\in W)\) , then \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {Y})=1)}{k^{\prime }}\ge \text{Pr}(\mathbf {Y}\in W)\) .
(2) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \text{Pr}(\mathbf {Y}=\mathbf {w})/\text{Pr}(\mathbf {X}=\mathbf {w}) \ge \mu \rbrace \)  for some \(\mu > 0\)  and \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}\le \text{Pr}(\mathbf {X}\in W)\) , then \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {Y})=1)}{k^{\prime }}\le \text{Pr}(\mathbf {Y}\in W)\) .

We first prove part (1). For convenience, we denote the complement of \(W\)  as \(W^{c}\) . Then, we have the following:
\(& \frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {Y})=1)}{k^{\prime }}- \text{Pr}(\mathbf {Y}\in W) \\=&\int _{\mathbb {R}^{d}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} - \int _{W}\text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} \\=&\int _{W^{c}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} +\int _{W}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} - \int _{W}\text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} \\=&\int _{W^{c}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w}- \int _{W}(1-\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }})\cdot \text{Pr}(\mathbf {Y}=\mathbf {w})d\mathbf {w} \\\ge &\mu \cdot [\int _{W^{c}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w}- \int _{W}(1-\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }})\cdot \text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w}] \\=&\mu \cdot [\int _{W^{c}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w} +\int _{W}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w} - \int _{W}\text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w}] \\=&\mu \cdot [\int _{\mathbb {R}^{d}}\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }}\cdot \text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w} - \int _{W}\text{Pr}(\mathbf {X}=\mathbf {w})d\mathbf {w}] \\=&\mu \cdot [\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}- \text{Pr}(\mathbf {X}\in W)] \\\ge & 0.\) 

We have Equation  from REF  due to the fact that \(\text{Pr}(\mathbf {Y}=\mathbf {w})/\text{Pr}(\mathbf {X}=\mathbf {w}) \le \mu , \forall \mathbf {w}\in W\) , \(\text{Pr}(\mathbf {Y}=\mathbf {w})/\text{Pr}(\mathbf {X}=\mathbf {w}) > \mu , \forall \mathbf {w}\in W^{c}\) , and \(1-\frac{\sum _{i=1}^{t}F_{i}(1|\mathbf {w})}{k^{\prime }} \ge 0\) .
Similarly, we can prove the part (2). We omit the details for conciseness reason.

We apply the above lemma to random variables \(\mathbf {X}\)  and \(\mathbf {Y}\) , and obtain the following lemma:
Lemma 4 
Let \(\mathbf {X}\sim \mathcal {N}(\mathbf {x},\sigma ^2 I)\) , \(\mathbf {Y}\sim \mathcal {N}(\mathbf {x}+\delta ,\sigma ^2 I)\) , \(F_{1}, F_{2}, \cdots , F_{t}:\mathbb {R}^d\xrightarrow{} \lbrace 0,1\rbrace \)  be \(t\)  random or deterministic functions, and \(k^{\prime }\)  be an integer such that:
\(\sum _{i=1}^{t}F_{i}(1|\mathbf {w})\le k^{\prime }, \forall \mathbf {w}\in \mathbb {R}^{d},\) 

where \(F_{i}(1|\mathbf {w})\)  denote the probability that \(F_{i}(\mathbf {w})=1\) .
Then, we have the following:
(1) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \delta ^{T}\mathbf {w} \le \beta \rbrace \)  for some \(\beta \)  and \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}\ge \text{Pr}(\mathbf {X}\in W)\) , then \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {Y})=1)}{k^{\prime }}\ge \text{Pr}(\mathbf {Y}\in W)\) .
(2) If \(W=\lbrace \mathbf {w}\in \mathbb {R}^d: \delta ^{T}\mathbf {w} \ge \beta \rbrace \)  for some \(\beta \)  and \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}\le \text{Pr}(\mathbf {X}\in W)\) , then \(\frac{\sum _{i=1}^{t}\text{Pr}(F_{i}(\mathbf {Y})=1)}{k^{\prime }}\le \text{Pr}(\mathbf {Y}\in W)\) .

By leveraging Lemma REF , Lemma REF , and Lemma REF , we derive the following lemma:
Lemma 5 
Suppose we have an arbitrary base multi-label classifier \(f\) , an integer \(k^{\prime }\) , an input \(\mathbf {x}\) , an arbitrary set denoted as \(O\) , two label probability bounds \(\underline{p_O}\)  and \(\overline{p}_{O}\)  that satisfy \(\underline{p_O} \le p_{O} =\sum _{i\in O}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {X}))\le \overline{p}_{O}\) , as well as regions \(\mathcal {A}_O\)  and \(\mathcal {B}_O\)  defined as follows:
\(&\mathcal {A}_O=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\le \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(\frac{\underline{p_{O}}}{k^{\prime }})\rbrace  \\&\mathcal {B}_O=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\ge \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(1-\frac{\overline{p}_{O}}{k^{\prime }})\rbrace \) 

Then, we have:
\(&\text{Pr}(\mathbf {X}\in \mathcal {A}_O) \le \frac{\sum _{i \in O}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {X}))}{k^{\prime }}\le \text{Pr}(\mathbf {X}\in \mathcal {B}_O) \\&\text{Pr}(\mathbf {Y}\in \mathcal {A}_O) \le \frac{\sum _{i\in O}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {Y}))}{k^{\prime }}\le \text{Pr}(\mathbf {Y}\in \mathcal {B}_O)\) 

We know \(\text{Pr}(\mathbf {X}\in \mathcal {A}_O)=\frac{\underline{p_O}}{k^{\prime }}\)  based on Lemma REF . Moreover, based on the condition \(\underline{p_O} \le \sum _{i\in O}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {X}))\) , we obtain the first inequality in Equation REF . Similarly, we can obtain the second inequality in Equation REF . We define \(F_{i}(\mathbf {w})=\mathbb {I}(i\in f_{k^{\prime }}(\mathbf {w})), \forall i \in O\) , where \(\mathbb {I}\)  is indicator function. Then, we have \(\text{Pr}(\mathbf {X}\in \mathcal {A}_O)\le \frac{\sum _{i \in O}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {X}))}{k^{\prime }}=\frac{\sum _{i \in O}\text{Pr}(F_{i}(\mathbf {X})=1)}{k^{\prime }}\) . Note that there are \(k^{\prime }\)  elements in \(f_{k^{\prime }}(\mathbf {w}),\forall \mathbf {w}\in \mathbb {R}^d\) , therefore, we have \(\sum _{i\in O}F_{i}(1|\mathbf {w}) = \sum _{i\in O}\mathbb {I}(i\in f_{k^{\prime }}(\mathbf {w})) \le k^{\prime }, \forall \mathbf {w}\in \mathbb {R}^d\) .
Then, we can apply Lemma REF  and we have the following:
\(\text{Pr}(\mathbf {Y}\in \mathcal {A}_O)\le \frac{\sum _{i\in O}\text{Pr}(F_i(\mathbf {Y})=1)}{k^{\prime }}=\frac{\sum _{i\in O }\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))}{k^{\prime }},\) 

which is the first inequality in Equation . Similarly, we can obtain the second inequality in Equation .

Based on Lemma REF  and Lemma REF , we derive the following lemma:
Lemma 6 
Suppose we have an arbitrary base multi-label classifier \(f\) , an integer \(k^{\prime }\) , an input \(\mathbf {x}\) , an arbitrary label which is denoted as \(l\) , two label probability bounds \(\underline{p_l}\)  and \(\overline{p}_{l}\)  that satisfy \(\underline{p_l} \le p_{l} =\text{Pr}(l \in f_{k^{\prime }}(\mathbf {X}))\le \overline{p}_{l}\) , and regions \(\mathcal {A}_l\)  and \(\mathcal {B}_l\)  defined as follows:
\(&\mathcal {A}_l=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\le \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(\underline{p_{l}})\rbrace  \\&\mathcal {B}_l=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\ge \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(1-\overline{p}_{l})\rbrace \) 

Then, we have:
\(&\text{Pr}(\mathbf {X}\in \mathcal {A}_l) \le \text{Pr}(l \in f_{k^{\prime }}(\mathbf {X}))\le \text{Pr}(\mathbf {X}\in \mathcal {B}_l) \\&\text{Pr}(\mathbf {Y}\in \mathcal {A}_l) \le \text{Pr}(l \in f_{k^{\prime }}(\mathbf {Y}))\le \text{Pr}(\mathbf {Y}\in \mathcal {B}_l)\) 

We know \(\text{Pr}(\mathbf {X}\in \mathcal {A}_l)=\underline{p_l}\)  based on Lemma REF . Moreover, based on the condition \(\underline{p_l} \le \text{Pr}(l \in f_{k^{\prime }}(\mathbf {X}))\) , we obtain the first inequality in Equation REF . Similarly, we can obtain the second inequality in Equation REF . We define \(F(\mathbf {w})=\mathbb {I}(l\in f_{k^{\prime }}(\mathbf {w}))\) . Based on the first inequality in Equation REF , we know \(\text{Pr}(\mathbf {X}\in \mathcal {A}_l) \le \text{Pr}(l \in f_{k^{\prime }}(\mathbf {X})) = \text{Pr}(F(\mathbf {X})=1)\) . Then, we apply Lemma REF  and we have the following:
\(\text{Pr}(\mathbf {Y}\in \mathcal {A}_l)\le \text{Pr}(F(\mathbf {Y})=1)=\text{Pr}(l\in f_{k^{\prime }}(\mathbf {Y})),\) 

which is the first inequality in Equation . The second inequality in Equation  can be obtained similarly.
Next, we formally show our proof for Theorem REF .

We leverage the law of contraposition to prove our theorem. Roughly speaking, if we have a statement: \(P\rightarrow Q\) , then, it's contrapositive is: \(\lnot Q\rightarrow \lnot P\) , where \(\lnot \)  denotes negation. The law of contraposition claims that a statement is true if, and only if, its contrapositive is true.
We define the predicate \(P\)  as follows:
\(& \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{a_e}})-\frac{R}{\sigma }), \max _{u=1}^{d-e+1}\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{R}{\sigma })\rbrace  \nonumber \\> & \min \lbrace \Phi (\Phi ^{-1}(\overline{p}_{b_s})+\frac{R}{\sigma }), \max _{v=1}^{k-e+1}\frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{R}{\sigma })\rbrace .\) 

We define the predicate \(Q\)  as follows:
\(\min _{\delta ,\left\Vert \delta \right\Vert _2\le R}|L(\mathbf {x}) \cap g_{k}(\mathbf {x}+\delta )|\ge e .\) 

We will first prove the statement: \(P \rightarrow Q\) . To prove it, we consider its contrapositive, i.e., we prove the following statement: \(\lnot Q \rightarrow \lnot P\) .
Deriving necessary condition:  Suppose \(\lnot Q\)  is true, i.e., \( \min _{\delta ,\left\Vert \delta \right\Vert _2\le R}|L(\mathbf {x})\cap g_{k}(\mathbf {x}+\delta )|< e\) . On the one hand, this means there exist at least \(d-e+1\)  elements in \(L(\mathbf {x})\)  do not appear in \(g_{k}(\mathbf {x}+\delta )\) . For convenience, we use \(\mathcal {U}_{r}\subseteq L(\mathbf {x})\)  to denote those elements, a subset of \(L(\mathbf {x})\)  with \(r\)  elements where \(r = d-e+1\) . On the other hand, there exist at least \(k-e+1\)  elements in \(\lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x})\)  appear in \(g_{k}(\mathbf {x}+\delta )\) . We use \(\mathcal {V}_s \subseteq \lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x})\)  to denote them, a subset of \(\lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x})\)  with \(s=k-e+1\)  elements. Formally, we have the following:
\(&\exists \text{ }\mathcal {U}_r \subseteq L(\mathbf {x}), \mathcal {U}_r \cap g_{k}(\mathbf {x}+\delta ) = \emptyset \\&\exists \text{ } \mathcal {V}_s \subseteq \lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x}), \mathcal {V}_s \subseteq g_{k}(\mathbf {x}+\delta ),\) 

In other words, there exist sets \(\mathcal {U}_r\)  and \(\mathcal {V}_s\)  such that the adversarially perturbed label probability \(p_i^{\ast }\) 's for elements in \(\mathcal {V}_s\)  are no smaller than these for the elements in \(\mathcal {U}_r\) . Formally, we have the following necessary condition if \(|L(\mathbf {x})\cap g_{k}(\mathbf {x}+\delta )|< e\) :
\(\min _{\mathcal {U}_r} \max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \le \max _{\mathcal {V}_s} \min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\) 
Bounding \(\max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))\)  and \(\min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\)  for given \(\mathcal {U}_r\)  and \(\mathcal {V}_s\) : 
For simplicity, we assume \(\mathcal {U}_r =\lbrace w_1,w_2,\cdots ,w_r\rbrace \) . Without loss of generality, we assume \(\underline{p_{w_1}} \ge \underline{p_{w_2}}\ge \cdots \ge \underline{p_{w_r}}\) . Similarly, we assume \(\mathcal {V}_s =\lbrace z_1,z_2,\cdots ,z_s\rbrace \)  and \(\overline{p}_{z_s} \ge \cdots \ge \overline{p}_{z_2}\ge \overline{p}_{z_1}\) .
For an arbitrary element \(i\in \mathcal {U}_r\) , we define the following region:
\(\mathcal {A}_{i}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\le \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(\underline{p_i})\rbrace \) 

Then, we have the following for any \(i \in \mathcal {U}_r\) :
\(\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))\ge \text{Pr}(\mathbf {Y}\in \mathcal {A}_i)=\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

We obtain the first inequality from Lemma REF , and the second equality from Lemma REF . Similarly, for an arbitrary element \(j\in \mathcal {V}_s\) , we define the following region:
\(\mathcal {B}_{j}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\ge \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(1-\overline{p}_j)\rbrace \) 

Then, based on Lemma REF  and Lemma REF , we have the following:
\(\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y})) \le \text{Pr}(\mathbf {Y}\in \mathcal {B}_j) = \Phi (\Phi ^{-1}(\overline{p}_j)+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

Therefore, we have the following:
\(& \max _{i\in \mathcal {U}_r} \text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \\\ge & \max _{i \in \mathcal {U}_r}\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })=\max _{i \in \lbrace w_1,w_2,\cdots ,w_r\rbrace }\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })=\Phi (\Phi ^{-1}(\underline{p_{w_1}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\\& \min _{j \in \mathcal {V}_s} \text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y})) \\\le & \min _{j \in \mathcal {V}_s}\Phi (\Phi ^{-1}(\overline{p}_{j})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }) = \min _{j \in \lbrace z_1,z_2,\cdots ,z_s\rbrace }\Phi (\Phi ^{-1}(\overline{p}_{j})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })=\Phi (\Phi ^{-1}(\overline{p}_{z_1})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

Next, we consider all possible subsets of \(\mathcal {U}_r\)  and \(\mathcal {V}_s\) .
We denote \(\Gamma _{u}\subseteq \mathcal {U}_r\) , a subset of \(u\)  elements in \(\mathcal {U}_{r}\) , and denote \(\Lambda _{v} \subseteq \mathcal {V}_s\) , a subset of \(v\)  elements in \(\mathcal {V}_s\) . Then, we have the following:
\(&\max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \ge \max _{\Gamma _u \subseteq \mathcal {U}_r}\max _{i\in \Gamma _u} \text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \\&\min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y})) \le \min _{\Lambda _v \subseteq \mathcal {V}_s}\min _{j\in \Lambda _v}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\) 

We define the following quantities:
\(\underline{p_{\Gamma _u}}=\sum _{i\in \Gamma _u}\underline{p_i}\text{ and } \overline{p}_{\Lambda _v}=\sum _{j\in \Lambda _v}\overline{p}_j\) 

Given these quantities, we define the following region based on Equation REF :
\(& \mathcal {A}_{\Gamma _u}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\le \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})\rbrace  \\& \mathcal {B}_{\Lambda _v}=\lbrace \mathbf {w}: \delta ^{T}(\mathbf {w}-\mathbf {x})\ge \sigma \left\Vert \delta \right\Vert _2\Phi ^{-1}(1-\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})\rbrace \) 

Then, we have the following:
\(&\frac{\sum _{i\in \Gamma _u}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {Y}))}{k^{\prime }} \\\ge &\text{Pr}(\mathbf {Y}\in \mathcal {A}_{\Gamma _u}) \\=& \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

We have Equation  from REF  based on Lemma REF , and we have Equation  from  based on Lemma REF . Therefore, we have the following:
\(& \max _{i\in \Gamma _u} \text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \\\ge & \frac{\sum _{i\in \Gamma _u}\text{Pr}(i \in f_{k^{\prime }}(\mathbf {Y}))}{u} \\=&\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

We have Equation  from REF  because the maximum value is no smaller than the average value. Similarly, we have the following:
\(\min _{j\in \Lambda _v}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\le \frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

Recall that we have \(\overline{p}_{w_1} \ge \overline{p}_{w_2}\ge \cdots \ge \overline{p}_{w_r}\)  for \(\mathcal {U}_r\) . By taking all possible \(\Gamma _u\)  with \(u\)  elements into consideration, we have the following:
\(\max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))\ge \max _{\Gamma _u \subseteq \mathcal {U}_r}\max _{i\in \Gamma _u} \text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))\ge \max _{\Gamma _u=\lbrace w_1,\cdots ,w_u\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\) 

In other words, we only need to consider \(\Gamma _u=\lbrace w_1,\cdots ,w_u\rbrace \) , i.e., a subset of \(u\)  elements in \(\mathcal {U}_r\)  whose label probability upper bounds are the largest, where ties are broken uniformly at random. The reason is that \(\Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\)  increases as \(\underline{p_{\Gamma _u}}\)  increases. Combining with Equations REF , we have the following:
\(\max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \ge \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{w_1}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{\Gamma _u=\lbrace w_1,\cdots ,w_u\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace \) 
Similarly, we have the following:
\(\min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\le \min \lbrace \Phi (\Phi ^{-1}(\overline{p}_{z_1})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\min _{\Lambda _v=\lbrace z_1,\cdots ,z_v\rbrace }\frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace \) 
Bounding \(\min _{\mathcal {U}_r} \max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y}))\)  and \(\max _{\mathcal {V}_s} \min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\) :  We have the following:
\(& \min _{\mathcal {U}_r} \max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \\\ge & \min _{\mathcal {U}_r} \max \lbrace \max _{i \in \lbrace w_1,w_2,\cdots ,w_r\rbrace }\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{\Gamma _u=\lbrace w_1,\cdots ,w_u\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace  \\\ge & \max \lbrace \max _{i \in \lbrace a_e,a_{e+1},\cdots ,a_k\rbrace }\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{\Gamma _u=\lbrace a_e,\cdots ,a_{e+u-1}\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace  \\= & \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{a_e}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{\Gamma _u=\lbrace a_e,\cdots ,a_{e+u-1}\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace  \\= & \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{a_e}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{u=1}^{d-e+1}\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace  ,\) 

where \(\Gamma _u=\lbrace a_e,\cdots ,a_{e+u-1}\rbrace \) . We have Equation  from  because \(\max \lbrace \max _{i \in \lbrace w_1,w_2,\cdots ,w_r\rbrace }\Phi (\Phi ^{-1}(\underline{p_i})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\max _{\Gamma _u=\lbrace w_1,\cdots ,w_u\rbrace }\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace \)  reaches the minimal value when \(\mathcal {U}_r\)  contains \(r\)  elements with smallest label probability lower bounds, i.e., \(\mathcal {U}_r=\lbrace a_e,a_{e+1},\cdots ,a_{d}\rbrace \) , where \(r=d-e+1\) . Similarly, we have the following:
\(\max _{\mathcal {V}_s} \min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y}))\le \min \lbrace \Phi (\Phi ^{-1}(\underline{p_{b_s}})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }),\min _{v=1}^{s}\frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }) \rbrace  ,\) 

where \(\Lambda _v=\lbrace b_{s-v+1},\cdots ,b_{s}\rbrace \)  and \(s=k-e+1\) .
Applying the law of contraposition: 
Based on necessary condition in Equation REF , if we have \(|T\cap g_{k}(\mathbf {x}+\delta )|<e\) , then, we must have the following:
\(& \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{a_e}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }), \max _{u=1}^{d-e+1}\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace  \\\le & \min _{\mathcal {U}_r} \max _{i\in \mathcal {U}_r}\text{Pr}(i\in f_{k^{\prime }}(\mathbf {Y})) \\\le & \max _{\mathcal {V}_s} \min _{j\in \mathcal {V}_s}\text{Pr}(j\in f_{k^{\prime }}(\mathbf {Y})) \\\le & \min \lbrace \Phi (\Phi ^{-1}(\overline{p}_{b_e})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }), \min _{v=1}^{k-e+1}\frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace ,\) 

We apply the law of contraposition and we obtain the statement: if we have the following:
\(& \max \lbrace \Phi (\Phi ^{-1}(\underline{p_{a_e}})-\frac{\left\Vert \delta \right\Vert _2}{\sigma }), \max _{u=1}^{d-e+1}\frac{k^{\prime }}{u}\cdot \Phi (\Phi ^{-1}(\frac{\underline{p_{\Gamma _u}}}{k^{\prime }})-\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace  \nonumber \\> & \min \lbrace \Phi (\Phi ^{-1}(\overline{p}_{b_s})+\frac{\left\Vert \delta \right\Vert _2}{\sigma }), \max _{v=1}^{k-e+1}\frac{k^{\prime }}{v}\cdot \Phi (\Phi ^{-1}(\frac{\overline{p}_{\Lambda _v}}{k^{\prime }})+\frac{\left\Vert \delta \right\Vert _2}{\sigma })\rbrace ,\) 

Then, we must have \(|L(\mathbf {x})\cap g_{k}(\mathbf {x}+\delta )|\ge e\) .
From Equation REF , we know that Equation REF  is satisfied for \(\forall \left\Vert \delta \right\Vert _2 \le R\) . Therefore, we reach our conclusion.
[tb]
Computing the Certified Intersection Size


Input: \(f\) , \(\mathbf {x}\) , \(L(\mathbf {x})\) , \(R\) , \(k^{\prime }\) , \(k\) , \(n\) , \(\sigma \) , and \(\alpha \) .
Output: Certified intersection size.
\(\mathbf {x}^1, \mathbf {x}^2,\cdots ,\mathbf {x}^n \leftarrow \textsc {RandomSample}(\mathbf {x}, \sigma )\)
counts\([i] \leftarrow \sum _{t=1}^{n}\mathbb {I}(i \in f(\mathbf {x}^t)), i = 1,2,\cdots ,c. \)
\(\underline{p_{{i}}}, \overline{p}_{{j}} \leftarrow \textsc {ProbBoundEstimation}(\text{counts},\alpha ), i \in L(\mathbf {x}), j \in \lbrace 1,2,\cdots ,c\rbrace \setminus L(\mathbf {x})\)
\(e \leftarrow \)  BinarySearch(\(\sigma ,k^{\prime },k,R,\lbrace \underline{p_i}|i\in L(\mathbf {x})\rbrace ,\lbrace \overline{p}_j | j \in \lbrace 1,2,\cdots ,c\rbrace  \setminus L(\mathbf {x}) \rbrace \) )
return \(e\)
<FIGURE><FIGURE><FIGURE><FIGURE><FIGURE>