It is well-known that  classifiers are vulnerable to adversarial perturbations. To defend against adversarial perturbations, various certified robustness results have been derived. However, existing certified robustnesses are limited to top-1 predictions. In many real-world applications, top-$k$ predictions are more relevant. In this work, we aim to derive certified robustness for top-$k$ predictions. In particular, our certified robustness is based on randomized smoothing, which turns any classifier to a new classifier via adding noise to an input example. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any classifier. We derive a tight robustness in $\ell_2$ norm for top-$k$ predictions  when using randomized smoothing with Gaussian noise. We find that generalizing the certified robustness  from top-1 to top-$k$ predictions faces significant technical challenges. We also empirically evaluate our method on CIFAR10 and ImageNet. For example, our method can obtain an ImageNet classifier with a certified top-5 accuracy of 62.8\% when the $\ell_2$-norms of the adversarial perturbations are less than 0.5 (=127/255). Our code is publicly available at: \url{https://github.com/jjy1994/Certify_Topk}. Classifiers are vulnerable to adversarial perturbations (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017b; Jia & Gong, 2018) . Specifically, given an example x and a classifier f , an attacker can carefully craft a perturbation δ such that f makes predictions for x + δ 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; . 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 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 N (x, σ 2 I). The smoothed classifier g k (x) predicts the k labels with the largest probabilities p i 's for the example x. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any base classifier. Our major theoretical result is a tight certified robustness bound for top-k predictions when using randomized smoothing with Gaussian noise. Specifically, given an example x, a label l is verifiably among the top-k labels predicted by the smoothed classifier g k (x + δ) when the 2 -norm of the adversarial perturbation δ is less than a threshold (called certified radius). The certified radius for top-1 predictions derived by Cohen et al. (2019) is a special case of our certified radius when k = 1. As our results and proofs show, generalizing certified robustness from top-1 to top-k predictions faces significant new challenges and requires new techniques. Our certified radius is the unique solution to an equation, which depends on σ, p l , and the k largest probabilities p i 's (excluding p l ). However, computing our certified radius in practice faces two challenges: 1) it is hard to exactly compute the probability p l and the k largest probabilities p i 's, and 2) the equation about the certified radius does not have an analytical solution. To address the first challenge, we estimate simultaneous confidence intervals of the label probabilities via the Clopper-Pearson method and Bonferroni correction in statistics. To address the second challenge, we propose an algorithm to solve the equation to obtain a lower bound of the certified radius, where the lower bound can be tuned to be arbitrarily close to the true certified radius. We evaluate our method on CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009) datasets. For instance, on ImageNet, our method respectively achieves approximate certified top-1, top-3, and top-5 accuracies as 46.6%, 57.8%, and 62.8% when the 2 -norms of the adversarial perturbations are less than 0.5 (127/255) and σ = 0.5. 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. Adversarial perturbation poses a fundamental security threat to classifiers. Existing certified defenses focus on top-1 predictions, leaving top-k predictions untouched. In this work, we derive the first certified radius under 2 -norm for top-k predictions. Our results are based on randomized smoothing. Moreover, we prove that our certified radius is tight for randomized smoothing with Gaussian noise. In order to compute the certified radius in practice, we further propose simultaneous confidence interval estimation methods as well as design an algorithm to estimate a lower bound of the certified radius. Interesting directions for future work include 1) deriving a tight certified radius under other norms such as 1 and ∞ , 2) studying which noise gives the tightest certified radius for randomized smoothing, and 3) studying certified robustness for top-k ranking. A PROOF OF THEOREM 1 Given an example x, we define the following two random variables: where ∼ N (0, σ 2 I). The random variables X and Y represent random samples obtained by adding isotropic Gaussian noise to the example x and its perturbed version x + δ, respectively. Moreover, we have the following lemma from Cohen et al. (2019) . Lemma 2. Given an example x, a number q ∈ [0, 1], and regions A and B defined as follows: ) Then, we have the following equations: Proof. Please refer to Cohen et al. (2019) . Based on Lemma 1 and 2, we derive the following lemma: Lemma 3. Suppose we have an arbitrary base classifier f , an example x, a set of labels which are denoted as S, two probabilities p S and p S that satisfy p S ≤ p S = Pr(f (X) ∈ S) ≤ p S , and regions A S and B S defined as follows: Proof. We know that Pr(X ∈ A S ) = p S based on Lemma 2. Combined with the condition that p S ≤ Pr(f (X) ∈ S), we obtain the first inequality in (20) . Similarly, we can obtain the second inequality in (20). We define M (z) = I(f (z) ∈ S). Based on the first inequality in (20) and Lemma 1, we have the following: 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. Theorem 1 (Certified Radius for Top-k Predictions). Suppose we are given an example x, an arbitrary base classifier f , ∼ N (0, σ 2 I), a smoothed classifier g, an arbitrary label l ∈ {1, 2, · · · , c}, and p l , p 1 , · · · , p l−1 , p l+1 , · · · , p c ∈ [0, 1] that satisfy the following conditions: where p and p indicate lower and upper bounds of p, respectively. Let where ties are broken uniformly at random. Moreover, we denote by S t = {b 1 , b 2 , · · · , b t } the set of t labels with the smallest probability upper bounds in the k largest ones and by p St = t j=1 p bj the sum of the t probability upper bounds, where t = 1, 2, · · · , k. Then, we have: where R l is the unique solution to the following equation: where Φ and Φ −1 are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively. Proof. Roughly speaking, our idea is to make the probability that the base classifier f predicts l when taking 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 Γ = {1, 2, · · · , c} \ {l}, i.e., all labels except l. We denote by Γ k a set of k labels in Γ. We aim to find a certified radius R l such that we have max Γ k ⊆Γ min i∈Γ k Pr(f (Y) = i) < Pr(f (Y) = l), which guarantees l ∈ g k (x + δ). We first upper bound the minimal probability min i∈Γ k Pr(f (Y) = i) for a given Γ k , and then we upper bound the maximum value of the minimal probability among all possible Γ k ⊆ Γ. Finally, we obtain the certified radius R l via letting the upper bound of the maximum value smaller than Pr(f (Y) = l). Bounding min i∈Γ k Pr(f (Y) = i) for a given Γ k : We use S to denote a non-empty subset of Γ k and use |S| to denote its size. We define p S = i∈S 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 Pr(f (Y) ∈ S) ≤ Pr(Y ∈ B S ) by applying Lemma 3 to the set S. In addition, we have . Therefore, we have: Moreover, we have: where we have the first inequality because S is a subset of Γ 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 ⊆ Γ k . Therefore, by taking all possible sets S into consideration, we have the following: where S t is the set of t labels in Γ k whose probability upper bounds are the smallest, where ties are broken uniformly at random. We have Equation 30 from Equation 29 because Pr(Y ∈ B S ) decreases as p S decreases. Since Pr(Y ∈ B St ) increases as p St increases, Equation 30 reaches its maximum value when Γ k = {b 1 , b 2 , · · · , b k }, i.e., when Γ k is the set of k labels in Γ with the largest probability upper bounds. Formally, we have: where Obtaining R l : According to Lemma 3, we have the following for S = {l}: Recall that our goal is to make Pr(f (Y) = l) > max Γ k ⊆Γ min i∈Γ k Pr(f (Y) = i). It suffices to let: According to Lemma 2, we have Pr( . Therefore, we have the following constraint on δ: Since the left-hand side of the above inequality 1) decreases as ||δ|| 2 increases, 2) is larger than 0 when ||δ|| 2 → −∞, and 3) is smaller than 0 when ||δ|| 2 → ∞, we have the constraint ||δ|| 2 < R l , where R l is the unique solution to the following equation: B PROOF OF THEOREM 2 Following the terminology we used in proving Theorem 1, we define a region A {l} as follows: According to Lemma 2, we have Pr(X ∈ A {l} ) = p l . We first show the following lemma, which is the key to prove our Theorem 2. Lemma 4. Assuming we have p l + k j=1 p bj ≤ 1. For any perturbation δ 2 > R l , there exists k disjoint regions C bj ⊆ R d \ A {l} , j ∈ {1, 2, · · · , k} that satisfy the following: where the random variables X and Y are defined in Equation 10 and 11, respectively; and {b 1 , b 2 , · · · , b k } and S t are defined in Theorem 1. Proof. 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. Theorem 2 (Tightness of the Certified Radius). Assuming we have p l + k j=1 p bj ≤ 1 and p l + i=1,··· ,l−1,l+1,··· ,c p i ≥ 1. Then, for any perturbation ||δ|| 2 > R l , there exists a base classifier f * consistent with (1) but we have l / ∈ g k (x + δ). Proof. Our idea is to construct a base classifier such that l is not among the top-k labels predicted by the smoothed classifier for any perturbed example x + δ when ||δ|| 2 > R l . First, according to Lemma 4, we know there exists k disjoint regions C bj ⊆ R d \ A {l} , j ∈ {1, 2, · · · , k} that satisfy Equation 37 and 38. Moreover, we divide the remaining region R d \ (A {l} ∪ k j=1 C bj ) into c−k −1 regions, which we denote as C b k+1 , C b k+2 , · · · , C bc−1 and satisfy Pr(X ∈ C bj ) ≤ p bj for j ∈ {k + 1, k + 2, · · · , c − 1}. Note that b 1 , b 2 , · · · , b c−1 is some permutation of {1, 2, · · · , c} \ {l}. We can divide the remaining region into such c−k −1 regions because p l + i=1,··· ,l−1,l+1,··· ,c p i ≥ 1. Then, based on these regions, we construct the following base classifier: Based on the definition of f * , we have the following: Pr(f 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 x + δ when ||δ|| 2 > R l . Specifically, we have: where j = 1, 2, · · · , k. Since we have found k labels whose probabilities are larger than the probability of the label l, we have l / ∈ g k (x + δ) when δ 2 > R l .
We study the certified robustness for top-k predictions via randomized smoothing under Gaussian noise and derive a tight robustness bound in L_2 norm. This paper extends work on deducing a certified radius using randomized smoothing, and shows the radius at which a smoothed classifier under Gaussian perturbations is certified for the top k predictions. This paper builds upon the random smoothing technique for top-1 prediction, and aims to provide certification on top-k predictions.