Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing

Introduction

Classifiers are vulnerable to adversarial perturbations (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017b; Jia & Gong, 2018). Specifically, given an example $\mathbf{x}$ and a classifier $f$, an attacker can carefully craft a perturbation $\delta$ such that $f$ makes predictions for $\mathbf{x}+\delta$ as the attacker desires. Various empirical defenses (e.g., Goodfellow et al. (2015); Svoboda et al. (2019); Buckman et al. (2018); Ma et al. (2018); Guo et al. (2018); Dhillon et al. (2018); Xie et al. (2018); Song et al. (2018)) have been proposed to defend against adversarial perturbations. However, these empirical defenses were often soon broken by adaptive adversaries (Carlini & Wagner, 2017a; Athalye et al., 2018). As a response, certified robustness (e.g., Wong & Kolter (2018); Raghunathan et al. (2018a); Liu et al. (2018); Lecuyer et al. (2019); Cohen et al. (2019)) against adversarial perturbations has been developed. In particular, a robust classifier verifiably predicts the same top-1 label for data points in a certain region around any example $\mathbf{x}$.

In many applications such as recommender systems, web search, and image classification cloud service (Clarifai, ; Google Cloud Vision, ), top-$k$ predictions are more relevant. In particular, given an example, a set of $k$ most likely labels are predicted for the example. However, existing certified robustness results are limited to top-1 predictions, leaving top-$k$ robustness unexplored. To bridge this gap, we study certified robustness for top-$k$ predictions in this work. Our certified top-$k$ robustness leverages randomized smoothing (Cao & Gong, 2017; Cohen et al., 2019), which turns any base classifier $f$ to be a robust classifier via adding random noise to an example. For instance, Cao & Gong (2017) is the first to propose randomized smoothing with uniform noise as an empirical defense. We consider random Gaussian noise because of its certified robustness guarantee (Cohen et al., 2019). Specifically, we denote by $p_{i}$ the probability that the base classifier $f$ predicts label $i$ for the Gaussian random variable $\mathcal{N}(\mathbf{x},\sigma^{2}I)$. The smoothed classifier $g_{k}(\mathbf{x})$ predicts the $k$ labels with the largest probabilities $p_{i}$’s for the example $\mathbf{x}$. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any base classifier.

Our contributions are summarized as follows:

Theory. We derive the first certified radius for top-$k$ predictions. Moreover, we prove our certified radius is tight for randomized smoothing with Gaussian noise.

Algorithm. We develop algorithms to estimate our certified radius in practice.

Evaluation. We empirically evaluate our method on CIFAR10 and ImageNet.

Certified Radius for Top-k𝑘k Predictions

Suppose we are given an example $\mathbf{x}$, an arbitrary base classifier $f$, $\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$, a smoothed classifier $g$, an arbitrary label $l\in\{1,2,\cdots,c\}$, and $\underline{p_{l}},\overline{p}_{1},\cdots,\overline{p}_{l-1},\overline{p}_{l+1},\cdots,\overline{p}_{c}\in$ that satisfy the following conditions:

where $\underline{p}$ and $\overline{p}$ indicate lower and upper bounds of $p$, respectively. Let $\overline{p}_{b_{k}}\geq\overline{p}_{b_{k-1}}\geq\cdots\geq\overline{p}_{b_{1}}$ be the $k$ largest ones among $\{\overline{p}_{1},\cdots,\overline{p}_{l-1},\overline{p}_{l+1},\cdots,\overline{p}_{c}\}$, where ties are broken uniformly at random. Moreover, we denote by $S_{t}=\{b_{1},b_{2},\cdots,b_{t}\}$ the set of $t$ labels with the smallest probability upper bounds in the $k$ largest ones and by $\overline{p}_{S_{t}}=\sum_{j=1}^{t}\overline{p}_{b_{j}}$ the sum of the $t$ probability upper bounds, where $t=1,2,\cdots,k$. Then, we have:

where $R_{l}$ is the unique solution to the following equation:

where $\Phi$ and $\Phi^{-1}$ are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively.

Assuming we have $\underline{p_{l}}+\sum_{j=1}^{k}\overline{p}_{b_{j}}\leq 1$ and $\underline{p_{l}}+\sum_{i=1,\cdots,l-1,l+1,\cdots,c}\overline{p}_{i}\geq 1$. Then, for any perturbation $||\delta||_{2}>R_{l}$, there exists a base classifier $f^{*}$ consistent with (1) but we have $l\notin g_{k}(\mathbf{x}+\delta)$.

We have several observations about our theorems.

Our certified radius is applicable to any base classifier $f$.

According to Equation 3, our certified radius $R_{l}$ depends on $\sigma$, $\underline{p_{l}}$, and the $k$ largest probability upper bounds $\{\overline{p}_{b_{k}},\overline{p}_{b_{k-1}},\cdots,\overline{p}_{b_{1}}\}$ excluding $\overline{p}_{l}$. When the lower bound $\underline{p_{l}}$ and the upper bounds $\{\overline{p}_{b_{k}},\overline{p}_{b_{k-1}},\cdots,\overline{p}_{b_{1}}\}$ are tighter, the certified radius $R_{l}$ is larger. When $R_{l}<0$, the label $l$ is not among the top-$k$ labels predicted by the smoothed classifier even if no perturbation is added, i.e., $l\notin g_{k}(\mathbf{x})$.

When $k=1$, we have $R_{l}=\frac{\sigma}{2}(\Phi^{-1}(\underline{p_{l}})-\Phi^{-1}(\overline{p}_{b_{1}}))$, where $\overline{p}_{b_{1}}$ is an upper bound of the largest label probability excluding $\overline{p}_{l}$. The certified radius derived by Cohen et al. (2019) for top-1 predictions (i.e., their Equation 3) is a special case of our certified radius with $k=1$, $l=A$, and $b_{1}=B$.

Prediction and Certification in practice

With probability at least $1-\alpha$ over the randomness in Predict, if Predict returns a set $T$ (i.e., does not ABSTAIN), then we have $g_{k}(\mathbf{x})=T$.

2 Certification

Given a base classifier $f$, an example $\mathbf{x}$, a label $l$, and the standard deviation $\sigma$ of the Gaussian noise, we aim to compute the certified radius $R_{l}$. According to our Equation 3, our $R_{l}$ relies on a lower bound of $p_{l}$, i.e., $\underline{p_{l}}$, and the upper bound of $p_{S_{t}}$, i.e., $\overline{p}_{S_{t}}$, which are related to $f$, $\mathbf{x}$, and $\sigma$. We first discuss two Monte Carlo methods to estimate $\underline{p_{l}}$ and $\overline{p}_{S_{t}}$ with probabilistic guarantees. However, given $\underline{p_{l}}$ and $\overline{p}_{S_{t}}$, it is still challenging to exactly solve $R_{l}$ as the Equation 3 does not have an analytical solution. To address the challenge, we design an algorithm to obtain a lower bound of $R_{l}$ via solving Equation 3 through binary search. Our lower bound can be tuned to be arbitrarily close to $R_{l}$.

Our approach has two steps. The first step is to estimate $\underline{p_{l}}$ and $\overline{p}_{i}$ for $i\neq l$. The second step is to estimate $\overline{p}_{S_{t}}$ using $\overline{p}_{i}$ for $i\neq l$.

Estimating $\underline{p_{l}}$ and $\overline{p}_{i}$ for $i\neq l$: The probabilities $p_{1},p_{2},\cdots,p_{c}$ can be viewed as a multinomial distribution over the labels $\{1,2,\cdots,c\}$. If we sample a Gaussian noise $\epsilon$ uniformly at random, then the label $f(\mathbf{x}+\epsilon)$ can be viewed as a sample from the multinomial distribution. Therefore, estimating $\underline{p_{l}}$ and $\overline{p}_{i}$ for $i\neq l$ is essentially a one-sided simultaneous confidence interval estimation problem. In particular, we aim to estimate these bounds with a confidence level at least $1-\alpha$. In statistics, Goodman (1965); Sison & Glaz (1995) are well-known methods for simultaneous confidence interval estimations. However, these methods are insufficient for our problem. Specifically, Goodman’s method is based on Chi-square test, which requires the expected count for each label to be no less than 5. We found that this is usually not satisfied, e.g., ImageNet has 1,000 labels, some of which have close-to-zero probabilities and do not have more than 5 counts even if we sample a large number of Gaussian noise. Sison & Glaz’s method guarantees a confidence level of approximately $1-\alpha$, which means that the confidence level could be (slightly) smaller than $1-\alpha$. However, we aim to achieve a confidence level of at least $1-\alpha$. To address these challenges, we discuss two confidence interval estimation methods as follows:

where $1-\alpha$ is the confidence level and $B(\alpha;u,v)$ is the $\alpha$th quantile of the Beta distribution with shape parameters $u$ and $v$. We note that the Clopper-Pearson method was also adopted by Cohen et al. (2019) to estimate label probability for their certified radius of top-1 predictions.

Estimating $\overline{p}_{S_{t}}$: One natural method is to estimate $\overline{p}_{S_{t}}=\sum_{j=1}^{t}\overline{p}_{b_{j}}$. However, this bound may be loose. For example, when using BinoCP to estimate the probability bounds, we have $\overline{p}_{S_{t}}=t\cdot(1-\underline{p_{l}})$, which may be bigger than $1$. To address the challenge, we derive another bound for $\overline{p}_{S_{t}}$ from another perspective. Specifically, we have ${p}_{S_{t}}\leq\sum_{i\neq l}p_{i}\leq 1-\underline{p_{l}}$. Therefore, we can use $1-\underline{p_{l}}$ as an upper bound of ${p}_{S_{t}}$, i.e., $\overline{p}_{S_{t}}=1-\underline{p_{l}}$. Finally, we combine the above two estimations by taking the minimal one, i.e., $\overline{p}_{S_{t}}=\min(\sum_{j=1}^{t}\overline{p}_{b_{j}},1-\underline{p_{l}})$.

It is challenging to compute the certified radius $R_{l}$ exactly because Equation 3 does not have an analytical solution. To address the challenge, we design a method to estimate a lower bound of $R_{l}$ that can be tuned to be arbitrarily close to $R_{l}$. Specifically, we first approximately solve the following equation for each $t\in\{1,2,\cdots,k\}$:

We note that it is still difficult to obtain an analytical solution to Equation 7 when $t>1$. However, we notice that the left-hand side has the following properties: 1) it decreases as $R_{l}^{t}$ increases; 2) when $R_{l}^{t}\rightarrow-\infty$, it is greater than 0; 3) when $R_{l}^{t}\rightarrow\infty$, it is smaller than 0. Therefore, there exists a unique solution $R_{l}^{t}$ to Equation 7. Moreover, we leverage binary search to find a lower bound $\underline{R_{l}}^{t}$ that can be arbitrarily close to the exact solution $R_{l}^{t}$. In particular, we run the binary search until the left-hand side of Equation 7 is non-negative and the width of the search interval is less than a parameter $\mu>0$. Formally, we have:

After obtaining $\underline{R_{l}}^{t}$, we let $\underline{R_{l}}=\max_{t=1}^{k}\underline{R_{l}}^{t}$ be our lower bound of $R_{l}$. Based on $R_{l}=\max_{t=1}^{k}R_{l}^{t}$ and Equation 8, we have the following guarantee:

2.3 Complete Certification Algorithm

Algorithm 2 shows our algorithm to estimate the certified radius for a given example $\mathbf{x}$ and a label $l$. The function SampleUnderNoise is the same as in Algorithm 1. Functions BinoCP and SimuEM return the estimated probability bound for each label. Function BinarySearch performs binary search to solve the Equation 7 and returns a solution satisfying Equation 8. Formally, our algorithm has the following guarantee:

With probability at least $1-\alpha$ over the randomness in Certify, if Certify returns a radius $\underline{R_{l}}$ (i.e., does not ABSTAIN), then we have $l\in g_{k}(\mathbf{x}+\delta)$, $\forall||\delta||_{2}<\underline{R_{l}}$.

Experiments

Datasets and models: We conduct experiments on the standard CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009) datasets to evaluate our method. We use the publicly available pre-trained models from Cohen et al. (2019). Specifically, the architectures of the base classifiers are ResNet-110 and ResNet-50 for CIFAR10 and ImageNet, respectively.

Parameter setting: We study the impact of $k$, the confidence level $1-\alpha$, the noise level $\sigma$, the number of samples $n$, and the confidence interval estimation methods on the certified radius. Unless otherwise mentioned, we use the following default parameters: $k=3$, $\alpha=0.001$, $\sigma=0.5$, $n=100,000$, and $\mu=10^{-5}$. Moreover, we use SimuEM to estimate bounds of label probabilities. When studying the impact of one parameter on the certified radius, we fix the other parameters to their default values.

Approximate certified top-$k$ accuracy: For each testing example $\mathbf{x}$ whose true label is $l$, we compute the certified radius $\underline{R_{l}}$ using the Certify algorithm. Then, we compute the certified top-$k$ accuracy at a radius $r$ as the fraction of testing examples whose certified radius are at least $r$. Note that our computed certified top-$k$ accuracy is an approximate certified top-$k$ accuracy instead of the true certified top-$k$ accuracy. However, we can obtain a lower bound of the true certified top-$k$ accuracy based on the approximate certified top-$k$ accuracy. Appendix E shows the details. Moreover, the gap between the lower bound of the true certified top-$k$ accuracy and the approximate top-$k$ accuracy is negligible when $\alpha$ is small. For convenience, we simply use the term certified top-$k$ accuracy in the paper.

2 Experimental results

Related Work

Numerous defenses have been proposed against adversarial perturbations in the past several years. These defenses either show robustness against existing attacks empirically, or prove the robustness against arbitrary bounded-perturbations (known as certified defenses).

The community has proposed many empirical defenses. The most effective empirical defense is adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017; Tramèr et al., 2018; Madry et al., 2018). However, adversarial training does not have certified robustness guarantees. Other examples of empirical defenses include defensive distillation (Papernot et al., 2016), MagNet (Meng & Chen, 2017), PixelDefend (Song et al., 2017), Feature squeezing (Xu et al., 2018), and many others (Liu et al., 2019; Svoboda et al., 2019; Schott et al., 2019; Buckman et al., 2018; Ma et al., 2018; Guo et al., 2018; Dhillon et al., 2018; Xie et al., 2018; Song et al., 2018; Samangouei et al., 2018; Na et al., 2018; Metzen et al., 2017). However, many of these defenses were soon broken by adaptive attacks (Carlini & Wagner, 2017a; Athalye et al., 2018; Uesato et al., 2018; Athalye & Carlini, 2018).

2 Certified defenses

Randomized smoothing was first proposed as an empirical defense (Cao & Gong, 2017; Liu et al., 2018) without deriving the certified robustness guarantees. For instance, Cao & Gong (2017) proposed randomized smoothing with uniform noise from a hypercube centered at an example. Lecuyer et al. (2019) was the first to prove the certified robustness guarantee of randomized smoothing for top-1 predictions. Their results leverage differential privacy. Subsequently, Li et al. (2018) further leverages information theory to improve the certified radius bound. Cohen et al. (2019) obtains a tight certified radius bound for randomized smoothing with Gaussian noise by leveraging the Neyman-Pearson Lemma. Pinot et al. (2019) theoretically demonstrated the robustness to adversarial attacks of randomized smoothing when adding noise from Exponential family distributions and devised an upper bound on the adversarial generalization gap of randomized neural networks. Lee et al. (2019) generalized randomized smoothing to discrete data. Salman et al. (2019) employed adversarial training to improve the performance of randomized smoothing. Unlike the other certified defenses, randomized smoothing is scalable to large neural networks and applicable to arbitrary classifiers. Our work derives the first certified robustness guarantee of randomized smoothing for top-$k$ predictions. Moreover, we show that our robustness guarantee is tight for randomized smoothing with Gaussian noise.

Conclusion

ACKNOWLEDGMENTS We thank the anonymous reviewers for insightful reviews. This work was supported by NSF grant No. 1937786.

References

Appendix A Proof of Theorem 1

Given an example $\mathbf{x}$, we define the following two random variables:

where $\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$. The random variables $\mathbf{X}$ and $\mathbf{Y}$ represent random samples obtained by adding isotropic Gaussian noise to the example $\mathbf{x}$ and its perturbed version $\mathbf{x}+\delta$, respectively. Cohen et al. (2019) applied the standard Neyman-Pearson Lemma (Neyman & Pearson, 1933) to the above two random variables, and obtained the following lemma:

Moreover, we have the following lemma from Cohen et al. (2019).

Given an example $\mathbf{x}$, a number $q\in$, and regions $\mathcal{A}$ and $\mathcal{B}$ defined as follows:

Based on Lemma 1 and 2, we derive the following lemma:

Suppose we have an arbitrary base classifier $f$, an example $\mathbf{x}$, a set of labels which are denoted as $S$, two probabilities $\underline{p_{S}}$ and $\overline{p}_{S}$ that satisfy $\underline{p_{S}}\leq p_{S}=\text{Pr}(f(\mathbf{X})\in S)\leq\overline{p}_{S}$, and regions $\mathcal{A}_{S}$ and $\mathcal{B}_{S}$ defined as follows:

which is the first inequality in (21). The second inequality in (21) can be obtained similarly. ∎

Next, we restate Theorem 1 and show our proof.

Roughly speaking, our idea is to make the probability that the base classifier $f$ predicts $l$ when taking $\mathbf{Y}$ as input larger than the smallest one among the probabilities that $f$ predicts for a set of arbitrary $k$ labels selected from all labels except $l$. For simplicity, we let $\Gamma=\{1,2,\cdots,{c}\}\setminus\{l\}$, i.e., all labels except $l$. We denote by $\Gamma_{k}$ a set of $k$ labels in $\Gamma$. We aim to find a certified radius $R_{l}$ such that we have $\max_{\Gamma_{k}\subseteq\Gamma}\min_{i\in\Gamma_{k}}\text{Pr}(f(\mathbf{Y})=i)<\text{Pr}(f(\mathbf{Y})=l)$, which guarantees $l\in g_{k}(\mathbf{x}+\delta)$. We first upper bound the minimal probability $\min_{i\in\Gamma_{k}}\text{Pr}(f(\mathbf{Y})=i)$ for a given $\Gamma_{k}$, and then we upper bound the maximum value of the minimal probability among all possible $\Gamma_{k}\subseteq\Gamma$. Finally, we obtain the certified radius $R_{l}$ via letting the upper bound of the maximum value smaller than $\text{Pr}(f(\mathbf{Y})=l)$.

Bounding $\min_{i\in\Gamma_{k}}\text{Pr}(f(\mathbf{Y})=i)$ for a given $\Gamma_{k}$: We use $S$ to denote a non-empty subset of $\Gamma_{k}$ and use $|S|$ to denote its size. We define $\overline{p}_{S}=\sum_{i\in S}\overline{p}_{i}$, which is the sum of the upper bounds of the probabilities for the labels in $S$. Moreover, we define the following region associated with the set $S$:

We have $\text{Pr}(f(\mathbf{Y})\in S)\leq\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S})$ by applying Lemma 3 to the set $S$. In addition, we have $\sum_{i\in S}\text{Pr}(f(\mathbf{Y})=i)=\text{Pr}(f(\mathbf{Y})\in S)$. Therefore, we have:

where we have the first inequality because $S$ is a subset of $\Gamma_{k}$ and we have the second inequality because the smallest value in a set is no larger than the average value of the set. Equation 27 holds for any $S\subseteq\Gamma_{k}$. Therefore, by taking all possible sets $S$ into consideration, we have the following:

where $S_{t}$ is the set of $t$ labels in $\Gamma_{k}$ whose probability upper bounds are the smallest, where ties are broken uniformly at random. We have Equation 30 from Equation 29 because $\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S})$ decreases as $\overline{p}_{S}$ decreases.

Bounding $\max_{\Gamma_{k}\subseteq\Gamma}\min_{i\in\Gamma_{k}}\text{Pr}(f(\mathbf{Y})=i)$: Since $\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{t}})$ increases as $\overline{p}_{S_{t}}$ increases, Equation 30 reaches its maximum value when $\Gamma_{k}=\{b_{1},b_{2},\cdots,b_{k}\}$, i.e., when $\Gamma_{k}$ is the set of $k$ labels in $\Gamma$ with the largest probability upper bounds. Formally, we have:

where $S_{t}=\{b_{1},b_{2},\cdots,b_{t}\}$.

Obtaining $R_{l}$: According to Lemma 3, we have the following for $S=\{l\}$:

Recall that our goal is to make $\text{Pr}(f(\mathbf{Y})=l)>\max_{\Gamma_{k}\subseteq\Gamma}\min_{i\in\Gamma_{k}}\text{Pr}(f(\mathbf{Y})=i)$. It suffices to let:

According to Lemma 2, we have $\text{Pr}(\mathbf{Y}\in\mathcal{A}_{\{l\}})=\Phi(\Phi^{-1}(\underline{p_{l}})-\frac{||\delta||_{2}}{\sigma}))$ and $\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{t}})=\Phi(\Phi^{-1}(\overline{p}_{S_{t}})+\frac{||\delta||_{2}}{\sigma}))$. Therefore, we have the following constraint on $\delta$:

Since the left-hand side of the above inequality 1) decreases as $||\delta||_{2}$ increases, 2) is larger than 0 when $||\delta||_{2}\rightarrow-\infty$, and 3) is smaller than 0 when $||\delta||_{2}\rightarrow\infty$, we have the constraint $||\delta||_{2}<R_{l}$, where $R_{l}$ is the unique solution to the following equation:

Appendix B Proof of Theorem 2

Following the terminology we used in proving Theorem 1, we define a region $\mathcal{A}_{\{l\}}$ as follows:

According to Lemma 2, we have $\text{Pr}(\mathbf{X}\in\mathcal{A}_{\{l\}})=\underline{p_{l}}$. We first show the following lemma, which is the key to prove our Theorem 2.

where the random variables $\mathbf{X}$ and $\mathbf{Y}$ are defined in Equation 10 and 11, respectively; and $\{b_{1},b_{2},\cdots,b_{k}\}$ and $S_{t}$ are defined in Theorem 1.

Our proof is based on mathematical induction and the intermediate value theorem. For convenience, we defer the proof to Appendix B.1. ∎

Next, we restate Theorem 2 and show our proof. See 2

Based on the definition of $f^{*}$, we have the following:

Therefore, $f^{*}$ satisfies the conditions in (1). Next, we show that $l$ is not among the top-$k$ labels predicted by the smoothed classifier for any perturbed example $\mathbf{x}+\delta$ when $||\delta||_{2}>R_{l}$. Specifically, we have:

where $j=1,2,\cdots,k$. Since we have found $k$ labels whose probabilities are larger than the probability of the label $l$, we have $l\notin g_{k}(\mathbf{x}+\delta)$ when $\left\|\delta\right\|_{2}>R_{l}$. ∎

We first define some key notations and lemmas that will be used in our proof.

Given two values $q_{1}$ and $q_{2}$ that satisfy $0\leq q_{1}<q_{2}\leq 1$, we define the following region:

where the Gaussian random variable $\mathbf{X}$ is defined in Equation 10. Moreover, assuming we have pairs of $(q_{1}^{i},q_{2}^{i})$, $i=1,2,3,\cdots$, where $q_{1}^{i},q_{2}^{i}\in[q_{1},q_{2}]$, $\forall i$. We define the following region:

$\mathcal{C}^{\prime}(q_{1},q_{2})$ is the remaining region of $\mathcal{C}(q_{1},q_{2})$ excluding $\mathcal{C}(q_{1}^{1},q_{2}^{1}),\mathcal{C}(q_{1}^{2},q_{2}^{2}),\cdots$. Given two values $q_{1}^{\lambda}$ and $q_{2}^{\lambda}$ that satisfy $q_{1}\leq q_{1}^{\lambda}\leq q_{2}^{\lambda}\leq q_{2}$, we also define the following two functions:

where the random variables $\mathbf{X}$ and $\mathbf{Y}$ are defined in Equation 10 and 11, respectively.

Next, we show a key property of our defined functions $r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$ and $r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})$.

If $r_{x}(q_{1}^{\kappa},q_{2}^{\kappa})\leq r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$ and $q_{2}^{\kappa}\geq q_{2}^{\lambda}$ (or $q_{1}^{\kappa}\geq q_{1}^{\lambda})$, then we have $r_{y}(q_{1}^{\kappa},q_{2}^{\kappa})\leq r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})$.

Scenario I: $q_{2}^{\kappa}\geq q_{1}^{\kappa}\geq q_{2}^{\lambda}\geq q_{1}^{\lambda}$. We denote $h_{x}$ and $h_{y}$ as the probability densities for the random variables $\mathbf{X}$ and $\mathbf{Y}$, respectively. Then, we have $h_{x}(\mathbf{z})=(\frac{1}{\sqrt{2\pi}\sigma})^{d}\exp(-\frac{\sum_{i=1}^{d}(z_{i}-x_{i})^{2}}{2\sigma^{2}})$ and $h_{y}(\mathbf{z})=(\frac{1}{\sqrt{2\pi}\sigma})^{d}\exp(-\frac{\sum_{i=1}^{d}(z_{i}-x_{i}-\delta_{i})^{2}}{2\sigma^{2}})$. Therefore, the ratio of the probability density of $\mathbf{Y}$ and the probability density of $\mathbf{X}$ at a given point $\mathbf{z}$ is as follows:

Next, we compare the ratio for the points in different regions and have the following:

The Equation 57 from 56 is based on Equation 55 and the fact that $\delta^{T}(\mathbf{z}-\mathbf{x})\leq\sigma\left\|\delta\right\|_{2}\Phi^{-1}(1-q_{1}^{\kappa})$ for any point $\mathbf{z}$ in the region $\mathcal{C}^{\prime}(q_{1}^{\kappa},q_{2}^{\kappa})$ from Definition 1. Similarly, we can obtain Equation 59 from 58. We note that the Equation 58 from 57 is because $q_{2}^{\lambda}\leq q_{1}^{\kappa}$. Based on Equation 57 and 58, we know that there exists a real number $u$ such that:

Combining the Equation 56, 57, and 60, we have the following:

Taking an integral on both sides of the Equation 61 in the region $\mathcal{C}^{\prime}(q_{1}^{\kappa},q_{2}^{\kappa})$ and recalling the definition of $r_{x}(q_{1}^{\kappa},q_{2}^{\kappa})$ and $r_{y}(q_{1}^{\kappa},q_{2}^{\kappa})$, we have the following:

Based on Equation 62, 63, and the condition that $r_{x}(q_{1}^{\kappa},q_{2}^{\kappa})\leq r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$, we have the following:

Scenario II: $q_{2}^{\kappa}\geq q_{2}^{\lambda}\geq q_{1}^{\kappa}\geq q_{1}^{\lambda}$. We have:

Therefore, we have the following equation:

Similar to Scenario I, we know that there exists $u$ such that:

Similar to Scenario I, we have the following based on Equation 66:

Scenario III: $q_{2}^{\kappa}\geq q_{2}^{\lambda}\geq q_{1}^{\lambda}\geq q_{1}^{\kappa}$. As $r_{x}(q_{1}^{\kappa},q_{2}^{\kappa})\leq r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$, we have $r_{x}(q_{1}^{\kappa},q_{2}^{\kappa})=r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$. Therefore, we have $r_{y}(q_{1}^{\kappa},q_{2}^{\kappa})=r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})$. ∎

Next, we list the well-known Intermediate Value Theorem and show several other properties of our defined functions $r_{x}(q_{1}^{\lambda},q_{2}^{\lambda})$ and $r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})$.

If a function $F$ is continuous at every point in the interval $[a,b]$ and $(F(a)-v)\cdot(F(b)-v)\leq 0$, then there exists $x$ such that $F(x)=v$.

Roughly speaking, the Intermediate Value Theorem tells us that if a continuous function has values no larger and no smaller (or no smaller and no larger) than $v$ at the two end points of an interval, respectively, then the function takes value $v$ at some point in the interval.

Given two probabilities $q_{x},q_{y}$, if we have:

Then, there exists $q_{1}^{\prime},q_{2}^{\prime}\in[q_{1},q_{2}]$ such that:

then there exists $q_{1}^{\prime\prime},q_{2}^{\prime\prime}\in[q_{1},q_{2}]$ such that:

We define function $F(x)=r_{x}(q_{1},x)$. Then, we have $(F(q_{1})-q_{x})\cdot(F(q_{2})-q_{x})\leq 0$ since $F(q_{1})=0\leq q_{x}$ and $F(q_{2})=r_{x}(q_{1},q_{2})>q_{x}$ based on Equation 70. Therefore, according to Lemma 6, there exists $q_{1}^{\prime}\in[q_{1},q_{2}]$ such that:

Similarly, we can prove that there exists $q_{2}^{\prime}\in[q_{1},q_{2}]$ such that $r_{x}(q_{1}^{\prime},q_{2})=q_{x}$.

For any $q_{2}^{e}\in[q_{2}^{\prime},q_{2}]$, we define $H(x)=r_{x}(x,q_{2}^{e})$. Then, we know $H(q_{1})=r_{x}(q_{1},q_{2}^{e})\geq r_{x}(q_{1},q_{2}^{\prime})=q_{x}$ since $q_{2}^{e}\geq q_{2}^{\prime}$. Moreover, we have $H(q_{2}^{e})=0\leq q_{x}$. Therefore, we have $(H(q_{1})-q_{x})\cdot(H(q_{2}^{e})-q_{x})\leq 0$. According to Lemma 6,we know there exists $q_{1}^{e}\in[q_{1},q_{2}^{e}]$ such that $r_{x}(q_{1}^{e},q_{2}^{e})=q_{x}$ for arbitrary $q_{2}^{e}\in[q_{2}^{\prime},q_{2}]$. We define $G(x)=r_{y}(q_{1}^{e},x)$ where $x\in[q_{2}^{\prime},q_{2}]$, and $q_{1}^{e}$ are a value such that $r_{x}(q_{1}^{e},x)=q_{x}$ for a given $x$. When $x=q_{2}^{\prime}$, we can let $q_{1}^{e}=q_{1}$ since $r_{x}(q_{1},q_{2}^{\prime})=q_{x}$, and when $x=q_{1}$, we can let $q_{1}^{e}=q_{2}^{\prime}$ since $r_{x}(q_{2}^{\prime},q_{2})=q_{x}$. Based on Equation 73 and Lemma 6, we know that there exists $x\in[q_{2}^{\prime},q_{2}]$ such that $G(x)=q_{y}$. Therefore, there exists $q_{1}^{\prime\prime}$ and $q_{2}^{\prime\prime}$ such that:

Assuming we have $q_{1}^{\lambda}=0$, $q_{2}^{\lambda}=\overline{p}_{S_{t}}$. If $q_{2}^{\lambda}=\overline{p}_{S_{t}}\leq\min_{i}q_{1}^{i}$, then we have the following:

If $q_{2}^{\lambda}\leq\min_{i}q_{1}^{i}$, then we have $\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{\lambda},q_{2}^{\lambda})=\mathcal{C}(q_{1}^{\lambda},q_{2}^{\lambda})$ since no region is excluded. Therefore, we have $r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})=\text{Pr}(\mathbf{Y}\in\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{\lambda},q_{2}^{\lambda}))=\text{Pr}(\mathbf{Y}\in\mathcal{C}(q_{1}^{\lambda},q_{2}^{\lambda}))=q_{2}^{\lambda}-q_{1}^{\lambda}=\overline{p}_{S_{t}}$ based on Equation 51. We note that $\mathcal{C}(q_{1}^{\lambda},q_{2}^{\lambda})=\mathcal{B}_{S_{t}}$ when $q_{1}^{\lambda}=0$ and $q_{2}^{\lambda}=\overline{p}_{S_{t}}$. Therefore, we can obtain Equation 80 based on the definition of $r_{y}(q_{1}^{\lambda},q_{2}^{\lambda})$ from Definition 1. ∎

If we have $q_{1}\leq q_{2}^{o}\leq q_{2}$, then we have the following:

We further generalize Lemma 5 to two regions. Specifically, we have the following lemma:

Assuming we have a region $\mathcal{C}_{w}\subseteq\mathcal{C}(q_{1}^{w},q_{2}^{w})$ and we have $\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{w},q_{2}^{w})=\emptyset$. If $q_{1}\geq q_{1}^{w}$, $q_{2}\geq q_{2}^{w}$ and $r_{x}(q_{1}^{\prime},q_{2}^{\prime})\leq\text{Pr}(\mathbf{X}\in\mathcal{C}_{w})$, then we have:

We let $q_{1}=\max(q_{1},q_{2}^{w})$. As $\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{w},q_{2}^{w})=\emptyset$ and $q_{1}\geq q_{1}^{w}$, we can obtain the conclusion by applying Lemma 5 on $\mathcal{C}^{\prime}(q_{1},q_{2})\cup\mathcal{C}_{w}$. ∎

Next, we restate Lemma 4 and show our proof. See 4

Our proof leverages Mathematical Induction, which contains two steps. In the first step, we show that the statement holds initially. In the second step, we show that if the statement is true for the $m$th iteration, then it also holds for the $(m+1)$th iteration. Without loss of generality, we assume $\tau=\operatornamewithlimits{argmin}_{t=1}^{k}\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{t}})}{t}$. Therefore, we have the following:

Recall the definition of $\mathcal{B}_{S_{\tau}}$ and we have the following:

where $\overline{p}_{S_{\tau}}=\sum_{j\in S_{\tau}}\overline{p}_{j}$. We can split $\mathcal{B}_{S_{k}}$ into two parts: $\mathcal{B}_{S_{\tau}}$ and $\mathcal{B}_{S_{k}}\setminus\mathcal{B}_{S_{\tau}}$. We will show that $\forall j\in[1,\tau]$, we can find disjoint $\mathcal{C}_{b_{j}}\subseteq\mathcal{B}_{S_{\tau}}$ whose union is $\mathcal{B}_{S_{\tau}}$ such that:

For the other part, we will show that $\forall j\in[\tau+1,k]$, we can find disjoint $\mathcal{C}_{b_{j}}\subseteq\mathcal{B}_{S_{k}}\setminus\mathcal{B}_{S_{\tau}}$ whose union is $\mathcal{B}_{S_{k}}\setminus\mathcal{B}_{S_{\tau}}$ such that:

We first show that $\forall j\in[1,\tau]$, we can find $\mathcal{C}_{b_{j}}\subseteq\mathcal{B}_{S_{\tau}}$ that satisfy Equation 85 and 86. Since our proof leverages Mathematical Induction, we iteratively construct each $\mathcal{C}_{b_{j}},\forall j\in[1,\tau]$. Specifically, we first show that we can find $\mathcal{C}_{b_{\tau}}\subseteq\mathcal{B}_{S_{\tau}}$ that satisfies the requirements. Then, assuming we can find $\mathcal{C}_{b_{\tau}},\cdots,\mathcal{C}_{b_{\tau-m+1}}$, we show that we can find $\mathcal{C}_{b_{\tau-m}}\subseteq\mathcal{B}_{S_{\tau}}\setminus(\cup_{j=\tau-m+1}^{\tau}\mathcal{C}_{b_{j}})$. We will leverage Lemma 7 to prove the existence for each $\mathcal{C}_{b_{j}}$. Next, we show the two steps.

Step I: We show that we can find $\mathcal{C}_{b_{\tau}}\subseteq\mathcal{B}_{S_{\tau}}$ that satisfies Equation 85 and 86. We let $q_{1}=0$ and $q_{2}=\overline{p}_{S_{\tau}}$, and we define the following region:

which can be directly obtained as $\mathcal{C}^{\prime}(q_{1},q_{2})=\mathcal{B}_{S_{\tau}}$. As we have $\overline{p}_{b_{\tau}}\leq r_{x}(q_{1},q_{2})=\overline{p}_{S_{\tau}}=\sum_{j=1}^{\tau}\overline{p}_{b_{j}}$, there exist $q_{1}^{\prime}=\overline{p}_{S_{\tau}}-\overline{p}_{b_{\tau}},q_{2}^{\prime}=\overline{p}_{b_{\tau}}$ such that:

The equality in the middle is from Lemma 8, the left inequality is because $q_{2}^{\prime}=\overline{p}_{b_{\tau}}\geq\overline{p}_{b_{1}}$, and the right inequality is from Equation 83. Furthermore, we have the following:

We obtain Equation 100 from Equation 99 based on Lemma 8, and Equation 101 from Equation 100 based on Equation 83. Therefore, we have the following:

Thus, there exists $(q_{1}^{\tau},q_{2}^{\tau})$ such that $r_{x}(q_{1}^{\tau},q_{2}^{\tau})=\overline{p}_{b_{\tau}},r_{y}(q_{1}^{\tau},q_{2}^{\tau})=\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$ based on Lemma 7. Then, we have the following based on the definition of $r_{x},r_{y}$:

Finally, we let $\mathcal{C}_{b_{\tau}}=\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{\tau},q_{2}^{\tau})$, which meets our goal.

Step II: Assuming we can find $\{(q_{1}^{\tau},q_{2}^{\tau}),(q_{1}^{\tau-1},q_{2}^{\tau-1}),\cdots,(q_{1}^{\tau-m+1},q_{2}^{\tau-m+1})\}$ ($\forall j\in[\tau-m+1,\tau],q_{1}\leq q_{1}^{j}\leq q_{2}^{j}\leq q_{2}$) where $1\leq m\leq\tau-1$ such that $\forall j\in[\tau-m+1,\tau]$, we have:

We denote $e=\tau-m$. We show we can find $\mathcal{C}_{b_{e}}$ such that we have:

We let $q_{1}=0,q_{2}=\overline{p}_{S_{\tau}}$ and denote

The Equation 116 from 115 is based on the Equation 108, and the Equation 117 from 116 is based the Equation 51 and 106. Furthermore, we have the following:

The Equation 123 from 122 is because $\mathcal{C}(q_{1},q_{2})=\mathcal{B}_{S_{\tau}}$ and the Equation 107. We have $\overline{p}_{b_{e}}\leq r_{x}(q_{1},q_{2})$. Therefore, based on Lemma 7, there exist $q_{1}^{\prime},q_{2}^{\prime}$ such that:

Equation 128 from 127 is based on Lemma 9, Equation 129 from 128 is based on Equation 90 and 125, and Equation 130 from 129 is obtained from Equation 91 and the fact that $\lceil(\sum_{j=1}^{e}\overline{p}_{b_{j}})/\overline{p}_{b_{e}}\rceil\geq\tau$. Next, we show:

In particular, we consider two scenarios.

Scenario 1). $q_{1}^{\prime}\geq\min_{j=\tau-m+1}^{\tau}q_{1}^{j}$. We denote $t=\operatornamewithlimits{argmin}_{j=\tau-m+1}^{\tau}q_{1}^{j}$. We let $\mathcal{C}_{w}=\mathcal{C}_{b_{t}}\subseteq\mathcal{C}(q_{1}^{t},q_{2}^{t})$. As $q_{1}^{\prime}\geq q_{1}^{t},q_{2}\geq q_{2}^{t}$ and $r_{x}(q_{1}^{\prime},q_{2})=\overline{p}_{b_{e}}\leq\text{Pr}(\mathbf{X}\in\mathcal{C}_{w})=\overline{p}_{b_{t}}$, we have the following based on Lemma 10:

Scenario 2). $q_{1}^{\prime}<\min_{j=\tau-m+1}^{\tau}q_{1}^{j}$. We have the following:

Moreover, we have $r_{x}(q_{1},q_{1}^{\prime})=q_{1}^{\prime}-q_{1}$ from Lemma 8. The above two should be equal. Thus, we have $q_{1}^{\prime}=\sum_{j=1}^{e-1}\overline{p}_{b_{j}}=\overline{p}_{S_{\tau-m-1}}$ since $e=\tau-m$. we have:

We obtain Equation 140 from Equation 139 based on Lemma 8.

Therefore, we have the following in both scenarios:

Based on Lemma 7, there exist $q_{1}^{e},q_{2}^{e}$ such that $r_{x}(q_{1}^{e},q_{2}^{e})=\overline{p}_{b_{\tau}},r_{y}(q_{1}^{e},q_{2}^{e})=\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$. Then, we have the following based on the definition of $r_{x},r_{y}$:

We let $\mathcal{C}_{e}=\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{e},q_{2}^{e})$. From the definition of $\mathcal{C}^{\prime}(q_{1},q_{2})$, we have $\forall j\in[e+1,\tau],\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}_{b_{j}}=\emptyset$. Thus, we have $\forall j\in[e+1,\tau],\mathcal{C}_{b_{e}}\cap\mathcal{C}_{b_{j}}=\emptyset$ since $\mathcal{C}_{b_{e}}\subseteq\mathcal{C}^{\prime}(q_{1},q_{2})$.

Therefore, we reach our goal by Mathematical Induction, i.e., for $\forall j\in[1,\tau]$, we have:

We can also verify that $\cup_{j=1}^{\tau}\mathcal{C}_{b_{j}}=\mathcal{B}_{S_{\tau}}$.

Next, we show our proof based on Mathematical Induction for the other part, i.e., $\mathcal{B}_{S_{k}}\setminus\mathcal{B}_{S_{\tau}}$. Our construction process is similar to the above first part but has subtle differences.

Step I: Let $q_{1}=\sum_{j=1}^{\tau}\overline{p}_{b_{j}}$ and $q_{2}=\sum_{j=1}^{k}\overline{p}_{b_{j}}$. We define:

The Equation 150 is based on the fact that $\mathcal{C}^{\prime}(q_{1},q_{2})=\mathcal{C}(q_{1},q_{2})$ and Definition 1, and we obtain Equation 154 from 155 based on Equation 83. We have $\overline{p}_{b_{k}}\leq r_{x}(q_{1},q_{2})$. Therefore, based on Lemma 7, we know that there exists $q_{1}^{\prime}=q_{2}-\overline{p}_{b_{k}},q_{2}^{\prime}=q_{1}+\overline{p}_{b_{k}}$ such that:

Scenario 1). In this scenario, we consider $r_{y}(q_{1}^{\prime},q_{2})>\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$. We let $q_{1}^{k}=q_{1}^{\prime},q_{2}^{k}=q_{2}$, i.e., we have $\mathcal{C}_{b_{k}}=\mathcal{C}(q_{1}^{\prime},q_{2})\cap\mathcal{C}^{\prime}(q_{1},q_{2})$. Then, we have:

Scenario 2). In this scenario, we consider $r_{y}(q_{1}^{\prime},q_{2})\leq\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$. We have the following:

We obtain Equation 167 from 166 via Lemma 9, and we obtain Equation 168 from 167 based on Equation 150 to 156 and the fact $r_{x}(q_{1},q_{2})/r_{x}(q_{1},q_{2}^{\prime})=\frac{\sum_{j=\tau+1}^{k}\overline{p}_{b_{j}}}{\overline{p}_{b_{\tau+1}}}\geq k-\tau$. We have $(r_{y}(q_{1}^{\prime},q_{2})-\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau})\cdot(r_{y}(q_{1},q_{2}^{\prime})-\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau})\leq 0$. Therefore, from Lemma 7, we know that there exist $(q_{1}^{k},q_{2}^{k})$ such that:

Similarly, we let $\mathcal{C}_{b_{k}}=\mathcal{C}^{\prime}(q_{1},q_{2})\cap\mathcal{C}(q_{1}^{k},q_{2}^{k})$.

Based on the conditions of our constructions in the two scenarios, we know that if $\text{Pr}(\mathbf{Y}\in\mathcal{B}_{b_{k}})>\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$, then we have $q_{2}^{k}=q_{2}$.

Step II: We show that if we can find $(q_{1}^{k},q_{2}^{k}),\cdots,(q_{1}^{k-m+1},q_{2}^{k-m+1})$ where $m\in[1,k-\tau-1]$ and $\mathcal{C}_{b_{j}},\forall j\in[k,k-m+1]$ such that:

Then, we can find $(q_{1}^{k-m},q_{2}^{k-m})$ such that:

For simplicity, we denote $e=k-m$, we let $q_{1}=\sum_{j=1}^{\tau}\overline{p}_{b_{j}}$ and $q_{2}=\sum_{j=1}^{k}\overline{p}_{b_{j}}$, and we define:

We have $\overline{p}_{b_{e}}\leq r_{x}(q_{1},q_{2})$. Therefore, based on Lemma 7, we know that there exists $q_{1}^{\prime},q_{2}^{\prime}$ such that:

Scenario 1). In this scenario, we consider that the following holds:

We let $q_{1}^{e}=q_{1}^{\prime},q_{2}^{e}=q_{2}$, i.e., $\mathcal{C}_{b_{e}}=\mathcal{C}(q_{1}^{\prime},q_{2})\cap\mathcal{C}^{\prime}(q_{1},q_{2})$. Then, we have:

We note that we have $q_{1}^{\prime}\leq\min_{j=e+1}^{k}q_{1}^{i}$ in this scenario. Otherwise, Equation 186 will not hold based on Lemma 10. We give a short proof.

Assuming $q_{1}^{\prime}>\min_{j=k-m+1}^{k}q_{1}^{j}$. We denote $w=\operatornamewithlimits{argmin}_{j=k-m+1}^{k}q_{1}^{j}$. We let $\mathcal{C}_{w}=\mathcal{C}_{b_{w}}\subseteq\mathcal{C}(q_{1}^{w},q_{2}^{w})$. Note that in this case, we have $q_{2}^{w}<q_{2}$ because $q_{2}^{w}=q_{2}$ and $q_{1}^{\prime}>q_{1}^{w}$ cannot hold at the same time as long as $r_{y}(q_{1}^{\prime},q_{2})>0$. Thus, we have $\text{Pr}(\mathbf{Y}\in\mathcal{C}_{w})=\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$ because if $\text{Pr}(\mathbf{Y}\in\mathcal{C}_{w})>\frac{\text{Pr}(\mathbf{Y}\in\mathcal{B}_{S_{\tau}})}{\tau}$, we have $q_{2}^{w}=q_{2}$. As we have $q_{1}^{\prime}>q_{1}^{w},q_{2}>q_{2}^{w}$ and $r_{x}(q_{1}^{\prime},q_{2})=\overline{p}_{b_{e}}\leq\text{Pr}(\mathbf{X}\in\mathcal{C}_{w})=\overline{p}_{b_{w}}$. We have the following based on Lemma 10: