Year: 2022

Abstract:
Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. l0-norm adversarial perturbation characterizes an attack that arbitrarily modifies some features of an input such that a classifier makes an incorrect prediction for the perturbed input. l0-norm adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying robustness of top-k predictions against l0-norm adversarial perturbation is important. However, existing studies either focused on certifying l0-norm robustness of top-1 predictions or l2-norm robustness of top-k predictions. In this work, we aim to bridge the gap. Our approach is based on randomized smoothing, which builds a provably robust classifier from an arbitrary classifier via randomizing an input. Our major theoretical contribution is an almost tight l0-norm certified robustness guarantee for top-k predictions. We empirically evaluate our method on CIFAR10 and ImageNet. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.

text: Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. ℓ0-norm adversarial perturbation characterizes an attack that arbitrarily modifies some features of an input such that a classifier makes an incorrect prediction for the perturbed input. ℓ0-norm adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying robustness of top-k predictions against ℓ0-norm adversarial perturbation is important. However, existing studies either focused on certifying ℓ0-norm robustness of top-1 predictions or ℓ2-norm robustness of top-k predictions. In this work, we aim to bridge the gap. Our approach is based on randomized smoothing, which builds a provably robust classifier from an arbitrary classifier via randomizing an input. Our major theoretical contribution is an almost tight ℓ0-norm certified robustness guarantee for top-k predictions. We empirically evaluate our method on CIFAR10 and ImageNet. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.

heading: 1 INTRODUCTION
text: Adversarial example is a well-known severe security vulnerability of classifiers. Specifically, given a classifier f and a testing input x, an attacker can carefully craft a human-imperceptible perturbation δ such that f(x) ̸= f(x+ δ). The perturbation δ is called adversarial perturbation, while the input x+ δ is called an adversarial example. Many empirical defenses (Goodfellow et al., 2015; Na et al., 2018; Metzen et al., 2017; 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 developed to defend against adversarial examples in the past several years. However, these empirical defenses were often soon broken by strong adaptive adversaries (Carlini & Wagner, 2017; Athalye et al., 2018; Uesato et al., 2018; Athalye & Carlini, 2018). To end this cat-and-mouse game, many certified defenses (Scheibler et al., 2015; Carlini et al., 2017; Ehlers, 2017; Katz et al., 2017; Cheng et al., 2017; Lomuscio & Maganti, 2017; Fischetti & Jo, 2018; Bunel et al., 2018; Wong & Kolter, 2018; Wong et al., 2018; Raghunathan et al., 2018a;b; Dvijotham et al., 2018a;b; Gehr et al., 2018; Mirman et al., 2018; Singh et al., 2018; Weng et al., 2018; Zhang et al., 2018; Gowal et al., 2018; Wang et al., 2018; Lecuyer et al., 2019; Li et al., 2019; Cohen et al., 2019; Lee et al., 2019; Salman et al., 2019; Wang et al., 2020; Jia et al., 2020; Zhai et al., 2020) have been proposed. In particular, a classifier f is said to be certifiably robust for an input x if it provably predicts the same top-1 label (i.e.,f(x) = f(x+ δ)) when the adversarial perturbation δ is bounded, e.g., the ℓp-norm of δ is smaller than a threshold. The threshold is also called certified radius. In this work, we focus on ℓ0-norm adversarial perturbation, which arbitrarily manipulates some features of a testing input and can be implemented in the physical world.
However, most existing certified defenses focus on top-1 predictions. In many applications, top-k predictions that return the k most likely labels are more relevant. For instance, when a classifier is deployed as a cloud service (also called machine learning as a service) (Google Cloud Vision; Microsoft; Amazon AWS; Clarifai), top-k labels for a testing input are often returned to a customer for more informed decisions; in recommender systems and web searches, top-k items/webpages are recommended to a user. Despite the importance and relevance of top-k predictions, their certified robustness against adversarial perturbations is largely unexplored. One exception is the recent work from Jia et al. (2020), which derived a tight ℓ2-norm certified robustness for top-k predictions. Such ℓ2-norm certified robustness can be transformed to ℓ0-norm certified robustness via employing the inequality between ℓ0-norm and ℓ2-norm. However, the ℓ0-norm certified robustness derived from such transformations is suboptimal.
Our work: We aim to develop ℓ0-norm certified robustness of top-k predictions. Our approach is based on randomized smoothing (Cao & Gong, 2017; Liu et al., 2018; Lecuyer et al., 2019; Li et al., 2019; Cohen et al., 2019; Lee et al., 2019; Jia et al., 2020; Levine & Feizi, 2019), which can build a certifiably robust classifier from any base classifier via randomizing the input. We adopt randomized smoothing because it is applicable to any classifier and scalable to large neural networks. In particular, we use a randomized smoothing method called randomized ablation (Levine & Feizi, 2019), which achieves state-of-the-art ℓ0-norm certified robustness for top-1 predictions. Unlike other randomized smoothing methods (Cao & Gong, 2017; Lecuyer et al., 2019; Li et al., 2019; Cohen et al., 2019) that randomize an input via adding additive noise (e.g., Gaussian, Laplacian, or discrete noise) to it, randomized ablation randomizes an input via subsampling its features. Specifically, given an arbitrary classifier (called base classifier) and a testing input x, randomized ablation creates an ablated input via retaining some randomly selected features in x and setting the remaining features to a special value, e.g., median of the feature value, mean of the feature value, or a special symbol. When the testing input is an image, the features are the image’s pixels. Then, we feed the ablated input to the base classifier. Since the ablated input is random, the output of the base classifier is also random. Specifically, we denote by pj the probability that the base classifier outputs a label j for the random ablated input. The original randomized ablation method builds a smoothed classifier that outputs the label with the largest label probability pj for a testing input x. In our work, the smoothed classifier returns the k labels with the largest label probabilities for x.
Our major theoretical contribution is an almost tight ℓ0-norm certified robustness guarantee of top-k predictions for the smoothed classifier constructed by randomized ablation. Specifically, we first derive an ℓ0-norm certified robustness guarantee of top-k predictions for the smoothed classifier. Our results show that a label l is provably among the top-k labels predicted by the smoothed classifier for a testing input x when the attacker arbitrarily perturbs at most rl features of x, where rl is the ℓ0-norm certified radius. Moreover, we prove that our certified radius is tight when k = 1 and is almost tight when k > 1. In particular, if no assumptions on the base classifier are made, it is impossible to derive a certified radius that is larger than rl + I(k ̸= 1). In other words, when an attacker manipulates at least rl + 1 + I(k ̸= 1) features of a testing input, there exists a base classifier from which the smoothed classifier’s top-k predicted labels do not include l or there exist ties.
Our work has several technical differences with Levine & Feizi (2019). First, we derive the ℓ0-norm certified radius of top-k predictions for randomized ablation, while Levine & Feizi (2019) only derived the certified radius of top-1 predictions. Second, our certified radius is the same as or larger than that in Levine & Feizi (2019) for top-1 predictions, because we leverage the discrete property of the label probabilities to derive our certified radius. Third, we prove the (almost) tightness of the certified radius, while Levine & Feizi (2019) didn’t. Our work also has several technical differences with Jia et al. (2020), which derived a tight ℓ2-norm certified radius of top-k predictions for randomized smoothing with Gaussian additive noise. Since they add additive Gaussian noise to a testing input, the space of randomized inputs is continuous. However, our space of ablated inputs is discrete, as we randomize a testing input via subsampling its features. As a result, Jia et al. and our work use substantially different techniques to derive the ℓ2/ℓ0-norm certified radiuses and prove their (almost) tightness. In particular, when deriving the ℓ2/ℓ0-norm certified radiuses, our work needs to construct different regions in the discrete space of ablated inputs such that the Neyman-Pearson Lemma (Neyman & Pearson, 1933) can be applied. When proving the (almost) tightness, we use a completely different approach from Jia et al.. First, Jia et al. relies on the Intermediate Value Theorem, which is not applicable to our discrete data. Second, since Gaussian noise is not uniform, Jia et al. need to prove the results via Mathematical Induction. However, Mathematical Induction is
unnecessary in our case because the ablated inputs that can be derived from an input are uniformly distributed in the space of ablated inputs.
We evaluate our method on CIFAR10 and ImageNet. Our results show that our method substantially outperforms state-of-the-art for top-k predictions. For instance, our method achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker arbitrarily perturbs 5 pixels of a testing image. Under the same setting, Jia et al. (2020) achieves a certified top-3 accuracy of only 9.0%, when transforming their ℓ2-norm certified robustness to ℓ0-norm certified robustness.
Our contributions can be summarized as follows:
• We derive an ℓ0-norm certified radius of top-k predictions for randomized ablation. • We prove that our certified radius is tight when k = 1 and almost tight when k > 1. • We empirically evaluate our method on CIFAR10 and ImageNet.

heading: 2 THEORETICAL RESULTS
text: In this section, we show our core theoretical contributions.

heading: 2.1 BUILDING A SMOOTHED CLASSIFIER VIA RANDOMIZED ABLATION
text: Suppose we have a base classifier f , which classifies a testing input x to one of c classes {1, 2, · · · , c} deterministically. For simplicity, we assume x is an image with d pixels. Given an input x, randomized ablation (Levine & Feizi, 2019) creates an ablated input as follows: we first randomly subsample e pixels from x without replacement and keep their values. Then, we set the remaining pixel values in the ablated input to a special value, e.g., median of the pixel value, mean of the pixel value, or a special symbol. When the image is a color image, we set the values of the three channels of each pixel separately. Note that an ablated input has the same size with x. We use h(x, e) to denote the randomly ablated input for simplicity. Given h(x, e) as input, the output of the base classifier f is also random. We use pj to denote the probability that the base classifier f predicts class j when taking h(x, e) as input, i.e., pj = Pr(f(h(x, e)) = j). Note that pj is an integer multiple of 1(de) , which we will leverage to derive a tighter certified robustness guarantee. We build a smoothed classifier g that outputs the k labels with the largest label probabilities pj’s for x. Moreover, we denote by gk(x) the set of k labels predicted for x.

heading: 2.2 DERIVING THE CERTIFIED RADIUS FOR THE SMOOTHED CLASSIFIER
text: Defining two random variables: Suppose an attacker adds a perturbation δ to an input x, where ∥δ∥0 is the number of pixels perturbed by the attacker. We define the following two random variables:
U = h(x, e), V = h(x+ δ, e), (1)
where the random variables U and V denote the ablated inputs derived from x and its perturbed version x+ δ, respectively. We use S to denote the joint space of U and V , i.e., S is the set of ablated inputs that can be derived from x or x + δ. Given the definition of U and V , Pr(f(U) = j) and Pr(f(V ) = j) respectively represent the label probabilities of the input x and its perturbed version x+ δ predicted by the smoothed classifier.
Derivation goal: Intuitively, an ablated input h(x, e) is very likely to not include any perturbed pixel if ∥δ∥0 is bounded and e is relatively small, and thus the predicted labels of the smoothed classifier are not influenced by the perturbation. Formally, our goal is to show that a label l ∈ {1, 2, · · · , c} is provably in the top-k labels predicted by the smoothed classifier for an input x when the number of perturbed pixels is no larger than a threshold. In other words, we aim to show that l ∈ gk(x+ δ) when ∥δ∥0 ≤ rl, where rl is the certified radius. Our key idea to derive the certified radius is to guarantee that, when taking V as input, the label probability for label l is larger than the smallest one among the label probabilities of any k labels from all labels except l. We let Γ = {1, 2, · · · , c} \ {l}, i.e., Γ denotes the set of all labels except l. We use Γk to denote a set of k labels in Γ. Then, we aim to find a maximum certified radius rl such that:
Pr(f(V ) = l) > max Γk⊂Γ min j∈Γk Pr(f(V ) = j). (2)
Roughly speaking, the above equation means that: to ensure l exists in the set of top-k labels, Pr(f(V ) = l) should be larger than the minimum probability observed by taking any set of k labels Γk excluding l. To reach the goal, we derive a lower bound of Pr(f(V ) = l) and an upper bound of maxΓk⊂Γ minj∈Γk Pr(f(V ) = j). In particular, we derive a lower bound and an upper bound using the probabilities that V is in certain regions of the discrete space S, and such probabilities can be efficiently computed for ∀ ∥δ∥0 = r. Then, we can leverage binary search to find the maximum r such that the lower bound is larger than the upper bound and treat the maximum r as the certified radius rl. Next, we respectively introduce how to derive lower and upper bounds and use them to compute certified radius.
Deriving a lower bound of Pr(f(V ) = l) and an upper bound of maxΓk⊂Γ minj∈Γk Pr(f(V ) = j): We show our intuition to derive the upper and lower bounds. Our formal analysis is shown in the proof of Theorem 1. Our idea to derive the bounds is to divide the discrete space S in an innovative way such that we can leverage the Neyman-Pearson Lemma (Neyman & Pearson, 1933). Suppose for the random variable U , we have a lower bound of the label probability for l and an upper bound of the label probability for every other label. Formally, we have pl, p1 · · · pl−1, pl, · · · , pc that satisfy the following:
pl ≤ Pr(f(U) = l), pj ≥ Pr(f(U) = j),∀j ̸= l, (3) where p and p denote the lower and upper bounds of p, respectively. Multiplying each term in Equation (3) by ( d e ) , we have pl· ( d e ) ≤ Pr(f(U) = l)· ( d e ) , pj · ( d e ) ≥ Pr(f(U) = j)· ( d e ) ,∀j ̸= l. Since pl and pj(∀j ̸= l) are integer multiples of 1(de) , we have ⌈pl · ( d e ) ⌉ ≤ Pr(f(U) = l) · ( d e ) , ⌊pj · ( d e ) ⌋ ≥
Pr(f(U) = j) · ( d e ) ,∀j ̸= l. Therefore, we have the following:
p′l ≜ ⌈pl ·
( d e ) ⌉(
d e ) ≤ Pr(f(U) = l), p′j ≜ ⌊pj · (de)⌋(d e
) ≥ Pr(f(U) = j),∀j ̸= l. (4) Let pak ≥ pak−1 · · · ≥ pa1 be the k largest ones among {p1, · · · , pl−1, pl+1, · · · , pc}, where ties are broken uniformly at random. We denote Υt = {a1, a2, · · · , at} as the set of t labels with the smallest label probability upper bounds in the k largest ones and denote by p′Υt = ∑ j∈Υt p ′ j the sum of the t label probability bounds, where t = 1, 2, · · · , k. We define regions A, B, and C in S as the sets of ablated inputs that can be derived only from x, only from x + δ, and from both x and x + δ, respectively. In particular, the region A is a set of ablated inputs that can only be obtained via sampling e features (pixels) from x. The region B is a set of ablated inputs that can only be obtained via sampling e features from the perturbed x+ δ, and the region C is a set of ablated inputs that can be obtained via sampling e features from both x and x + δ. Then, we can find a region A′ ⊆ C such that Pr(U ∈ A′ ∪ A) = p′l. Note that we assume we can find such a region A′ since we aim to find sufficient condition. Similarly, we can find HΥt ∈ C such that we have Pr(U ∈ HΥt) = p′Υt . Then, we can apply the Neyman-Pearson Lemma (Neyman & Pearson, 1933) to derive a lower bound of Pr(f(V ) = l) and an upper bound of maxΓk⊂Γ minj∈Γk Pr(f(V ) = j) by leveraging the probabilities of V in regions A′ ∪ A and HΥt ∪ B. Formally, we have the following:
Pr(f(V ) = l) ≥ Pr(V ∈ A′ ∪ A), max Γk⊂Γ min j∈Γk
Pr(f(V ) = j) ≤ k
min t=1 Pr(V ∈ HΥt ∪ B) t . (5)
Computing certified radius: Given the lower and upper bounds, we can find the maximum r = ∥δ∥0 such that the lower bound Pr(V ∈ A′ ∪A) is larger than the upper bound minkt=1 Pr(V ∈HΥt∪B) t . The maximum r is the certified radius. Formally, we have the following theorem: Theorem 1 (ℓ0-norm Certified Radius for Top-k Predictions). Suppose we have an input x with d features, a deterministic base classifier f , an integer e, a smoothed classifier g where gk(x) is a set of k labels predicted for x, an arbitrary label l ∈ {1, 2, · · · , c}, pl, p1, · · · , pl−1, pl+1, · · · , pc that satisfy Equation (3), and p′l, p ′ j(∀j ̸= l) that are defined in Equation (4). If the following optimization problem has a solution rl:
rl = argmax r≥0
r s.t. p′l − (1− ( d−r e )( d e ) ) > kmin t=1 p′Υt + (1− (d−re ) (de) ) t . (6)
Then, we have the following:
l ∈ gk(x+ δ),∀ ∥δ∥0 ≤ rl. (7)
Proof. Please refer to Appendix A.
Next, we show that our derived certified radius is (almost) tight. In particular, when using randomized ablation and no further assumptions are made on the base classifier, it is impossible to certify an ℓ0-norm radius that is larger than rl + I(k ̸= 1) for top-k predictions. Theorem 2 (Almost Tightness of our Certified Radius). Assuming we have ( d−rl−2 e−1 ) ≥ 1, p′l +∑
j∈Υk p ′ j ≤ 1, and p′l + ∑ j ̸=l p ′ j ≥ 1. If no assumption on the base classifier is made, then, for any perturbation ∥δ∥0 > rl + I(k ̸= 1), there exists a base classifier f∗ consistent with Equation (3) but we have l /∈ gk(x+ δ) or there exist ties.
Proof. Please refer to Appendix B.
Comparing with Levine & Feizi (2019) when k = 1: Our certified radius reduces to the maximum r that satisfies p′l − p′a1 > 2 · (1 − (d−re ) (de) ) when k = 1. In contrast, the certified radius in Levine & Feizi (2019) is the maximum r that satisfies pl − pa1 > 2 · (1 − (d−re ) (de)
). Since p′l ≥ pl and p′ak ≤ pak , our certified radius is the same as or larger than that in Levine & Feizi (2019). Note that the method by Levine & Feizi (2019) cannot be extended in a straightforward way to derive the certified robustness for top-k predictions. The reason is that they consider each label independently in their derivation. In particular, they use the probability that the base classifier predicts label i for an ablated clean input (i.e., Pr(f(U) = i)) to bound the probability that the base classifier predicts label i for an ablated adversarial input (i.e., Pr(f(V ) = i)). However, to derive the certified robustness for top-k predictions, we need to jointly derive the bounds for multiple label probabilities (i.e., Equation (5)). Moreover, because of the difference in deriving label-probability bounds, our techniques are significantly different. In particular, Levine & Feizi only need the law of total probability while we leverage Neyman-Pearson Lemma. Moreover, Levine & Feizi (2019) did not analyze the tightness of the certified radius for top-1 predictions.
Comparing with Jia et al. (2020): Jia et al. (2020) proved the exact tightness of their ℓ2-norm certified radius for randomized smoothing with Gaussian noise. We highlight that our techniques to prove our almost tightness are substantially different from those in Jia et al.. First, they proved the existence of a region via the Intermediate Value Theorem, which relies on the continuity of Gaussian noise. However, our space of ablated inputs is discrete. Therefore, given a probability upper/lower bound, it is challenging to find a region whose probability measure exactly equals to the given value, since the Intermediate Value Theorem is not applicable. As a result, we cannot prove the exact tightness of the ℓ0-norm certified radius when k > 1. To address the challenge, we find a region whose probability measure is slightly smaller than the given upper bound, which enables us to prove the almost tightness of our certified radius. Second, since Gaussian noise is not uniform, they need to iteratively construct regions via leveraging Mathematical Induction. However, Mathematical Induction is unnecessary in our case because the ablated inputs that can be derived from an input are uniformly distributed in the space of ablated inputs.
Computing rl in practice: When applying our Theorem 1 to calculate the certified radius rl in practice, we need the probability bounds p′l and p ′ Υt
and solve the optimization problem in Equation (6). We can leverage a Monte Carlo method developed by Jia et al. (2020) to estimate the probability bounds (pl and pj ,∀j ̸= l) with probabilistic guarantees. Then, we can use them to estimate p′l and p ′ Υt . Moreover, given the probability bounds p′l and p ′ Υt
, we can use binary search to solve Equation (6) to find the certified radius rl.
Specifically, the probabilities p1, p2, · · · , pc can be viewed as a multinomial distribution over the label set {1, 2, · · · , c}. Given h(x, e) as input, f(h(x, e)) can be viewed as a sample from the multinomial distribution. Therefore, estimating pl and pi for i ̸= l is essentially a one-sided simultaneous confidence interval estimation problem. In particular, we leverage the simultaneous
confidence interval estimation method called SimuEM (Jia et al., 2020) to estimate these bounds with a confidence level at least 1− α. Specifically, given an input x and parameter e, we randomly create n ablated inputs, i.e., ϵ1, ϵ2, · · · , ϵn. We denote by nj the frequency of the label j predicted by the base classifier for the n ablated inputs. Formally, we have nj = ∑n i=1 I(f(ϵi) = j), where j ∈ {1, 2, · · · , c} and I is the indicator function. According to Jia et al. (2020), we have the following probability bounds with a confidence level at least 1− α:
pl = B (α c ;nl, n− nl + 1 ) , pj = B(1− α c ;nj + 1, n− nj), ∀j ̸= l, (8)
where B(q; ξ, ζ) is the qth quantile of a beta distribution with shape parameters ξ and ζ. Then, we can compute p′l and p ′ j ,∀j ̸= l based on Equation (4). Finally, we estimate p′Υt as p ′ Υt =
min( ∑
j∈Υt p ′ j , 1− p′l).

heading: 3 EVALUATION

heading: 3.1 EXPERIMENTAL SETUP
text: Datasets and models: We use CIFAR10 (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) for evaluation. We normalize pixel values to be in the range [0,1]. We use the publicly available implementation1 of randomized ablation to train our models. In particular, we use ResNet-110 and RestNet-50 as the base classifiers for CIFAR10 and ImageNet, respectively. Moreover, as in Lee et al. (2019), we use 500 testing examples for both CIFAR10 and ImageNet.
Parameter setting: Unless otherwise mentioned, we adopt the following default parameters. We set e = 50 and e = 1, 000 for CIFAR10 and ImageNet, respectively. We set k = 3, n = 100, 000, and α = 0.001. We will study the impact of each parameter while fixing the remaining ones to their default values.
Evaluation metric: We use the certified top-k accuracy as an evaluation metric. Specifically, given a number of perturbed pixels, certified top-k accuracy is the fraction of testing images, whose true labels have ℓ0-norm certified radiuses for top-k predictions that are no smaller than the given number of perturbed pixels. Note that our ℓ0-norm certified radius corresponds to the maximum number of pixels that can be perturbed by an attacker.
Compared methods: We compare six randomized smoothing based methods. The first four are only applicable for top-1 predictions, while the latter two are applicable for top-k predictions.
• Cohen et al. (2019). This method adds Gaussian noise to a testing image and derives a tight ℓ2-norm certified radius for top-1 predictions. In particular, considering the three color channels and each pixel value is normalized to be in the range [0,1], an ℓ0-norm certified number of perturbed pixels rl can be obtained from an ℓ2-norm certified radius √ 3rl.
• Lee et al. (2019). This method derives an ℓ0-norm certified radius for top-1 predictions. This method is applicable to discrete features. Like Lee et al. (2019), we treat the pixel values as discrete in the domain {0, 1/256, 2/256, · · · , 255/256}. Since their ℓ0-norm certified radius is for pixel channels (each pixel has 3 color channels), a certified number of perturbed pixels rl can be obtained from their ℓ0-norm certified radius 3rl.
• Levine & Feizi (2019). This method derives an ℓ0-norm certified number of perturbed pixels for top-1 predictions in randomized ablation. This method requires a lower bound of the largest label probability and an upper bound of the second largest label probability to calculate the certified number of perturbed pixels. They estimated the lower bound using the Monte Carlo method in Cohen et al. (2019) and the upper bound as 1 - the lower bound. Note that our certified radius is theoretically no smaller than that in Levine & Feizi (2019) when k = 1. Therefore, we use our derived certified radius when evaluating this method. We also found that the top-1 certified accuracies based on our derived certified radius and their derived certified radius have negligible differences on CIFAR10 and ImageNet, and thus we do not show the differences for simplicity.
1https://github.com/alevine0/randomizedAblation/
Note that we compare with Cohen et al. (2019) and Jia et al. (2020) because we aim to show that it is suboptimal to derive ℓ0-norm certified robustness for top-k predictions by leveraging the relationship between ℓ2-norm and ℓ0-norm.

heading: 3.2 EXPERIMENTAL RESULTS
text: Comparison results: Table 1 and 2 respectively show the certified top-k accuracies of the compared methods on CIFAR10 and ImageNet when an attacker perturbs a certain number of pixels. The Gaussian noise in Cohen et al. (2019) and Jia et al. (2020) has mean 0 and standard deviation σ. We obtain the certified top-k accuracies for different σ, i.e., we explored σ = 0.1, 0.12, 0.25, 0.5, 1.0. Lee et al. (2019) has a noise parameter β. We obtain the certified top-1 accuracies for different β. In particular, we explored β = 0.1, 0.2, 0.3, 0.4, 0.5, which were also used by Lee et al. (2019). Then, we report the largest certified top-k accuracies of Cohen et al. (2019), Lee et al. (2019), and Jia et al. (2020) for each given number of perturbed pixels. We use the default values of e for Levine & Feizi (2019) and our method.
We have two observations from Table 1 and 2. First, our method substantially outperforms Jia et al. (2020) for top-k predictions, while Levine & Feizi (2019) substantially outperforms Cohen et al. (2019) and Lee et al. (2019) for top-1 predictions. Since our method and Levine & Feizi (2019) use randomized ablation, while the remaining methods use additive noise (Gaussian or discrete noise) to randomize a testing input, our results indicate that randomized ablation is superior to additive noise at certifying ℓ0-norm robustness. Second, Levine & Feizi (2019) + SimuEM (Jia et al., 2020)
outperforms Levine & Feizi (2019). This is because SimuEM can more accurately estimate the label probability bounds via simultaneous confidence interval estimations.
Impact of k, e, n, and α: Figure 1, 2, 3 and 4 show the certified top-k accuracy of our method vs. number of perturbed pixels for different k, e, n, and α, respectively. Naturally, the certified top-k accuracy increases as k increases. For instance, when 5 pixels are perturbed, the certified top-1 and top-3 accuracies are 63.6% and 78.0% on CIFAR10, respectively. We observe that e provides a tradeoff between accuracy under no attacks and robustness. Specifically, when e is larger, the accuracy under no attacks (i.e., certified accuracy with 0 perturbed pixels) is higher, while the certified accuracy decreases to 0 more quickly as the number of perturbed pixels increases. As n becomes larger, the curve of the certified accuracy may become higher. The reason is that a larger n makes the estimated label probability bounds pl and pΥt tighter and thus the ℓ0-norm certified radius may be larger, which result in a larger certified accuracy. Theoretically, as the confidence level 1− α decreases, the curve of the certified accuracy may become higher. This is because a smaller confidence level leads to tighter estimated label probability bounds pl and pΥt , and thus the certified accuracy may be larger. However, we observe the differences between different confidence levels are negligible when the confidence levels are high enough (i.e., α is small enough).

heading: 4 RELATED WORK
text: Many certified defenses have been proposed to defend against adversarial perturbations. These defenses leverage various techniques including satisfiability modulo theories (Scheibler et al., 2015; Carlini et al., 2017; Ehlers, 2017; Katz et al., 2017), interval analysis (Wang et al., 2018), linear programming (Cheng et al., 2017; Lomuscio & Maganti, 2017; Fischetti & Jo, 2018; Bunel et al., 2018; Wong & Kolter, 2018; Wong et al., 2018), semidefinite programming (Raghunathan et al., 2018a;b), dual optimization (Dvijotham et al., 2018a;b), abstract interpretation (Gehr et al., 2018; Mirman et al., 2018; Singh et al., 2018), and layer-wise relaxation (Weng et al., 2018; Zhang et al., 2018; Gowal et al., 2018; Chiang et al., 2020). However, these defenses suffer from one or two limitations: 1) they are not scalable to large neural networks and/or 2) they are only applicable to specific neural network architectures. Randomized smoothing addresses the two limitations. Next, we review randomized smoothing based methods for certifying non-ℓ0-norm and ℓ0-norm robustness. Randomized smoothing for non-ℓ0-norm robustness: Randomized smoothing was first proposed as an empirical defense (Cao & Gong, 2017; Liu et al., 2018). In particular, Cao & Gong (2017) proposed to use uniform random noise from a hypercube centered at a testing example to smooth its predicted label. Lee et al. (2019) derived certified robustness for such uniform random noise. Lecuyer et al. (2019) was the first to derive formal ℓ2 and ℓ∞-norm robustness guarantee of randomized smoothing with Gaussian or Laplacian noise via differential privacy techniques. Subsequently, Li et al. (2019) leveraged information theory to derive a tighter ℓ2-norm robustness guarantee. Cohen et al. (2019) leveraged the Neyman-Pearson Lemma (Neyman & Pearson, 1933) to obtain a tight ℓ2-norm certified robustness guarantee for randomized smoothing with Gaussian noise. Other studies include Pinot et al. (2019); Carmon et al. (2019); Salman et al. (2019); Zhai et al. (2020); Dvijotham et al. (2019); Blum et al. (2020); Levine & Feizi (2020); Kumar et al. (2020); Yang et al. (2020); Zhang et al. (2020); Salman et al. (2020); Zheng et al. (2020). All these studies focused on top-1 predictions. Jia et al. (2020) derived the first ℓ2-norm certified robustness of top-k predictions against adversarial perturbations for randomized smoothing with Gaussian noise and proved its tightness. Randomized smoothing for ℓ0-norm robustness: All the above randomized smoothing based provable defenses were not (specifically) designed to certify ℓ0-norm robustness. They can be transformed to ℓ0-norm robustness via leveraging the relationship between ℓp norms. However, such transformations lead to suboptimal ℓ0-norm certified robustness. In response, multiple studies (Lee et al., 2019; Levine & Feizi, 2019; Dvijotham et al., 2019; Bojchevski et al., 2020; Jia et al., 2020; Zhang et al., 2021; Wang et al., 2021; Liu et al., 2021) proposed new randomized smoothing schemes to certify ℓ0-norm robustness. For instance, Lee et al. (2019) derived an ℓ0-norm certified robustness for classifiers with discrete features using randomized smoothing. In particular, for each feature, they keep its value with a certain probability and change it to a random value in the feature domain with an equal probability. Levine & Feizi (2019) proposed randomized ablation, which achieves state-of-the-art ℓ0-norm certified robustness. However, their work focused on top-1 predictions and they did not analyze the tightness of the certified robustness guarantee for top-1 predictions. We derive an almost tight ℓ0-norm certified robustness guarantee of top-k predictions for randomized ablation.

heading: 5 CONCLUSION
text: In this work, we derive an almost tight ℓ0-norm certified robustness guarantee of top-k predictions against adversarial perturbations for randomized ablation. We show that a label l is provably among the top-k labels predicted by a classifier smoothed by randomized ablation for a testing input when an attacker arbitrarily modifies a bounded number of features of the testing input. Moreover, we prove our derived bound is almost tight. Our empirical results show that our ℓ0-norm certified robustness is substantially better than those transformed from ℓ2-norm certified robustness. Interesting future works include exploring other noise to certify ℓ0-norm robustness for top-k predictions and incorporating the information of the base classifier to derive larger certified radiuses.

heading: ACKNOWLEDGMENTS
text: We thank the anonymous reviewers for insightful reviews. This work was supported by the National Science Foundation under Grants No. 1937786 and 2125977, as well as the Army Research Office under Grant No. W911NF2110182.

heading: A PROOF OF THEOREM 1
text: We define the following two random variables:
U = h(x, e), V = h(x+ δ, e). (9)
where U and V denote the ablated inputs derived from x and its perturbed version x + δ with parameter e, respectively. We use S to denote the domain space of U and V . Our proof is based on the Neyman-Pearson Lemma (Neyman & Pearson, 1933), and we present it as follows:
Lemma 1 (Neyman-Pearson Lemma). Suppose U and V are two random variables in the space S with probability distributions ρu and ρv, respectively. Let F : S −→ {0, 1} be a random or deterministic function. Then, we have the following:
• If Z1 = {s ∈ S : ρu(s) > µ · ρv(s)} and Z2 = {s ∈ S : ρu(s) = µ · ρv(s)} for some µ > 0. Let Z = Z1 ∪ Z3, where Z3 ⊆ Z2. If we have Pr(F (U) = 1) ≥ Pr(U ∈ Z), then Pr(F (V ) = 1) ≥ Pr(V ∈ Z).
• If Z1 = {s ∈ S : ρu(s) < µ · ρv(s)} and Z2 = {s ∈ S : ρu(s) = µ · ρv(s)} for some µ > 0. Let Z = Z1 ∪ Z3, where Z3 ⊆ Z2. If we have Pr(F (U) = 1) ≤ Pr(U ∈ Z), then Pr(F (V ) = 1) ≤ Pr(V ∈ Z).
Proof. We show the proof of the first part, and the second part can be proved similarly. For simplicity, we use F (1|s) and F (0|s) to denote the conditional probabilities that F (s) = 0 and F (s) = 1, respectively. We use Zc to denote the complement of Z, i.e., Zc = S \ Z. We have the following:
Pr(F (V ) = 1)− Pr(V ∈ Z) (10) = ∑ s∈S F (1|s) · ρv(s)− ∑ s∈Z ρv(s) (11)
= ∑ s∈Zc F (1|s) · ρv(s) + ∑ s∈Z F (1|s) · ρv(s)− ∑ s∈Z F (1|s) · ρv(s)− ∑ s∈Z F (0|s) · ρv(s) (12)
= ∑ s∈Zc F (1|s) · ρv(s)− ∑ s∈Z F (0|s) · ρv(s) (13)
≥ 1 µ · ( ∑ s∈Zc F (1|s) · ρu(s)− ∑ s∈Z F (0|s) · ρu(s)) (14)
= 1
µ · ( ∑ s∈Zc F (1|s) · ρu(s) + ∑ s∈Z F (1|s) · ρu(s)− ∑ s∈Z F (1|s) · ρu(s)− ∑ s∈Z F (0|s) · ρu(s)) (15)
= 1 µ · ( ∑ s∈S F (1|s) · ρu(s)− ∑ s∈Z ρu(s)) (16)
= 1
µ · (Pr(F (U) = 1)− Pr(U ∈ Z)) (17)
≥0. (18)
We obtain (14) from (13) because ρu(s) ≥ µ · ρv(s),∀s ∈ Z and ρu(s) ≤ µ · ρv(s),∀s ∈ Zc. We have the last inequality because Pr(F (U) = 1) ≥ Pr(U ∈ Z).
Next, we will derive our certified robustness guarantee. For simplicity, we denote Γ = {1, 2, · · · , c}\ {l}, i.e., Γ denotes the set of all labels except l. We use Γk to denote a set of k labels in Γ. Calibrating the lower and upper bounds: Recall that pl and pj ,∀j ̸= l are integer multiple of 1(de) . Then, given the probability lower and upper bounds in Equation (3), we have the following:
p′l ≜ ⌈pl ·
( d e ) ⌉(
d e ) ≤ Pr(f(U) = l), p′j ≜ ⌊pj · (de)⌋(d e ) ≥ Pr(f(U) = j),∀j ̸= l, (19)
Deriving a lower bound of Pr(f(V ) = l): We will derive a lower bound of the probability Pr(f(V ) = l). For simplicity, we define the following regions:
A = {s ∈ S|s ⪯ x, s ̸⪯ x+ δ},B = {s ∈ S|s ̸⪯ x, s ⪯ x+ δ}, C = {s ∈ S|s ⪯ x, s ⪯ x+ δ}, (20)
where we say s ⪯ x if Pr(h(x, e) = s) > 0, and we say s ̸⪯ x if Pr(h(x, e) = s) = 0. Intuitively, the notations ⪯ and ̸⪯ mean that an ablated input can or cannot be derived from an input, respectively. For instance, region A contains ablated inputs that can be derived from x but cannot be derived from x+ δ, region B contains ablated inputs that can be derived from x+ δ but cannot be derived from x, and region C contains ablated inputs that can be derived from both x and x+ δ. Suppose we have r = ||δ||0. Then, the size of C would be ( d−r e ) since d − r features are the same for x and x + δ.
Similarly, we know the size of A and B would be ( d e ) − ( d−r e ) . Since we keep e features randomly sampled from x or x+ δ without replacement and set the remaining features to a special value, we have the following probability mass functions:
Pr(U = s) =
{ 1
(de) , if s ∈ A ∪ C
0, otherwise. (21)
Pr(V = s) =
{ 1
(de) , if s ∈ B ∪ C
0, otherwise. (22)
Since we know the size of A, B, and C, as well as the probability mass functions of the random variables U and V in these regions, we have the following probabilities:
Pr(U ∈ C) = ( d−r e )( d e ) ,Pr(U ∈ A) = 1− (d−re )( d e
) ,Pr(U ∈ B) = 0, (23) Pr(V ∈ C) = ( d−r e
)( d e ) ,Pr(V ∈ B) = 1− (d−re )( d e
) ,Pr(V ∈ A) = 0. (24) We consider the case of p′l ≥ 1−
(d−re ) (de) . Note that we can do this because we aim to find a sufficient
condition. We let A′ ⊆ C such that it satisfies the following:
Pr(U ∈ A′) = p′l − Pr(U ∈ A). (25)
Given region A′, we construct the following region:
E = A′ ∪ A. (26)
Then, we have the following probability based on Equation (25):
Pr(U ∈ E) = Pr(U ∈ A) + Pr(U ∈ A′) = p′l. (27)
We define a binary function F (s) = I(f(s) = l). Then, we have the following:
Pr(F (U) = 1) = Pr(f(U) = l) ≥ p′l = Pr(U ∈ E). (28)
The middle inequality is based on Equation (19) and the right-hand equality is from Equation (27). Furthermore, we have Pr(U = s) > 1·Pr(V = s) if and only if s ∈ A, and Pr(U = s) = 1·Pr(V = s) if s ∈ A′. Therefore, we can apply Lemma 1 and we have the following:
Pr(F (V ) = 1) = Pr(f(V ) = l) ≥ Pr(V ∈ E). (29)
Therefore, we have the following lower bound for Pr(f(V ) = l):
Pr(V ∈ E) (30) =Pr(V ∈ A′) + Pr(V ∈ A) (31) =Pr(V ∈ A′) (32) =Pr(U ∈ A′) (33)
=p′l − (1− ( d−r e )( d e
) ). (34) Note that we have Equation (34) from (33) based on Equation (25).
Deriving an upper bound of maxΓk⊂Γ minj∈Γk Pr(f(V ) = j): We use Λ to denote an arbitrary subset of Γk, i.e., Λ ⊆ Γk. We denote p′Λ = ∑ j∈Λ p ′ j , which is the sum of the upper bound of the probability for the labels in Λ. We assume p′Λ ≤ Pr(U ∈ C). We can make this assumption because we aim to find a sufficient condition. Given p′Λ, we can find a region HΛ ⊆ C such that we have the following:
p′Λ = Pr(U ∈ HΛ). (35)
Given the region HΛ, we construct the following region:
IΛ = HΛ ∪ B. (36)
Then, we have the following probability:
Pr(U ∈ IΛ) = Pr(U ∈ HΛ) + Pr(U ∈ B) = p′Λ. (37)
Furthermore, for any given Λ, we define a binary function G(s) = I(f(s) ∈ Λ). Then, we have the following:
Pr(G(U) = 1) = Pr(f(U) ∈ Λ) = ∑ j∈Λ Pr(f(U) = j) ≤ p′Λ = Pr(U ∈ IΛ). (38)
We have ∑
j∈Λ Pr(f(U) = j) ≤ p ′ Λ based on Equation (19) and we have rightmost equality from
Equation (37). Then, we can apply Lemma 1 and we have the following:
Pr(G(V ) = 1) ≤ Pr(V ∈ IΛ). (39)
The value of Pr(V ∈ IΛ) can be computed as follows:
Pr(V ∈ IΛ) (40) =Pr(V ∈ HΛ) + Pr(V ∈ B) (41)
=Pr(U ∈ HΛ) + (1− ( d−r e )( d e
) ) (42) =p′Λ + (1− ( d−r e
)( d e
) ), (43) where the last equality is from Equation (35). Therefore, we have the following:∑
j∈Λ Pr(f(V ) = j) (44)
=Pr(f(V ) ∈ Λ) (45) =Pr(G(V ) = 1) (46) ≤Pr(V ∈ IΛ) (47)
=pΛ + (1− ( d−r e )( d e
) ). (48) Moreover, we have the following:
min j∈Γk Pr(f(V ) = j) ≤ min j∈Λ
Pr(f(V ) = j) ≤ ∑ j∈Λ Pr(f(V ) = j)
|Λ| = Pr(f(V ) ∈ Λ) |Λ| . (49)
We have the leftmost inequality because Λ ⊆ Γk, and we have the middle inequality because the smallest value in a set is no larger than the average value of the set. Taking all possible Λ into consideration and we have the following:
min j∈Γk Pr(f(V ) = j) (50)
≤ min Λ⊆Γk Pr(f(V ) ∈ Λ) |Λ|
(51)
= k
min t=1 min Λ⊆Γk,|Λ|=t Pr(f(V ) ∈ Λ) |Λ|
(52)
= k
min t=1 Pr(f(V ) ∈ Υt) t
(53)
≤ k
min t=1
p′Υt + (1− (d−re ) (de) )
t , (54)
where Υt is the set of t labels in Γk whose probability upper bounds are the smallest, where ties are broken uniformly at random. The upper bound of Pr(f(V ) ∈ Υt) is increasing as p′Υt increases. Therefore, the upper bound of Pr(f(V )∈Υt)t reaches the maximum value when Γk = {a1, a2, · · · , ak}, i.e., Γk is the set of labels in Γ with the largest probability upper bounds. In other words, we have the following:
max Γk⊂Γ min j∈Γk
Pr(f(V ) = j) ≤ k
min t=1
p′Υt + (1− (d−re ) (de) )
t , (55)
where Υt = {a1, a2, · · · , at}.
Deriving the certified radius: Our goal is to make Pr(f(V ) = l) > maxΓk⊂Γ minj∈Γk Pr(f(V ) = j). Therefore, it is sufficient to satisfy the following:
p′l − (1− ( d−r e )( d e ) ) > kmin t=1 p′Υt + (1− (d−re ) (de) ) t , (56)
where Υt = {a1, a2, · · · , at}. Therefore, we can find the maximum r that satisfies the above condition. Formally, we can solve the following optimization problem to find rl:
rl = argmax r r (57)
s.t. p′l − (1− ( d−r e )( d e ) ) > min t p′Υt + (1− (d−re ) (de) ) t , (58)
where Υt = {a1, a2, · · · , at}. Note that we make two assumptions in our derivation, i.e., p′l ≥ (1− (d−re ) (de) ) and p′Υt ≤ (d−re ) (de) . In particular, when Equation (58) is satisfied, we must have p′l ≥ (1− (d−re ) (de) ) since the left-hand side of Equation (58) is non-negative. In addition, we have p′l + p ′ Υt ≤ 1 in
practice. Therefore, we have p′Υt ≤ 1− p ′ l ≤ (d−re ) (de) .
Technical differences with Jia et al. (2020): Our technical contribution in proving the theorem is the construction of new discrete regions such that the Neyman-Pearson Lemma can be used. Our proof of Theorem 1 has the following differences with Jia et al. First, the construct of the regions A/B/C (Eq 18) are different from Jia et al. due to the discrete space. Second, deriving the lower bound of Pr(f(V ) = l) faces two new challenges in our case. The first challenge is that we need to find two regions A and A′ while Jia et al. just need to find one region. The second challenge is how to find these regions. To address the challenge, we first take into consideration of whether A′ exists or not. If A′ exists, we need to shrink region A′ because our space is discrete. These two challenges do not exist in the continuous case considered by Jia et al. Third, similar to deriving the lower bound of Pr(f(V ) = l), our work is also different from Jia et al. at deriving the upper bound of maxΓk∈Γ minj∈Γk Pr(f(V ) = j).

heading: B PROOF OF THEOREM 2
text: We consider two scenarios: k = 1 and k ̸= 1. In particular, we first consider the scenario where k = 1. We have Γ1 = {a1} when k = 1. We consider two cases.
Case I: In this case, we consider p′l < (1− (d−rl−1e )
(de) ). We let Al ⊆ A be the region that satisfies the
following:
p′l = Pr(U ∈ Al). (59)
We can find such region because p′l is an integer multiple of 1 (de) . We let Dl = Al and we have the following:
p′l = Pr(U ∈ Dl),Pr(V ∈ Dl) = 0. (60)
Then, we can divide the remaining region (A ∪ C) \ Dl into c− 1 disjoint regions such that we have the following:
∀j ∈ {1, 2, · · · , c} \ {l},Pr(U ∈ Dj) ≤ p′j . (61) We can find these regions because we have p′l + ∑ s̸=l p ′ s ≥ 1. Moreover, we have the following:
∀j ∈ {1, 2, · · · , c} \ {l},Pr(V ∈ Dj) ≥ 0. (62)
Given these regions, we construct the following base classifier:
f∗(z) = j, if z ∈ Dj . (63)
Note that f∗ is well defined and is consistent with Equation (3). It is easy to see that label l is not the predicted label by the corresponding smoothed classifier g∗ when ∥δ∥0 > rl.
Case II: In this case, we consider p′l ≥ (1− (d−rl−1e )
(de) ). Since rl is the maximum value that satisfies
Equation (6), we have the following condition when ∥δ∥0 = rl + 1: p′l − (1− ( d−rl−1 e )( d e ) ) ≤ p′a1 + (1− ( d−rl−1 e )( d e
) ). (64) We let Al = A and we can find Cl ∈ C such that the following equation holds:
Pr(U ∈ Cl) = p′l − (1− ( d−rl−1 e )( d e
) ). (65) Then, we let Dl = Cl ∪ Al and we have the following:
Pr(U ∈ Dl) = p′l. (66)
Furthermore, we have the following:
Pr(V ∈ Dl) (67) =Pr(V ∈ Cl) + Pr(V ∈ Al) (68) =Pr(U ∈ Cl) + 0 (69)
=p′l − (1− ( d−rl−1 e )( d e
) ), (70) where the last equality is from Equation (65). Since we have p′l + p ′ a1 ≤ 1, we can find region Ca1 ∈ C \ Cl such that we have the following:
Pr(U ∈ Ca1) = p′a1 . (71)
We define Da1 = Ca1 ∪ B. Then, we have Pr(U ∈ Da1) = Pr(U ∈ Ca1) = p′a1 . Similarly, we have the following:
Pr(V ∈ Da1) (72) =Pr(V ∈ Ca1) + Pr(V ∈ B) (73)
=p′a1 + (1− ( d−rl−1 e )( d e ) ). (74)
Finally, we can divide the remaining region A ∪ C \ (Dl ∪ Ca1) into c− 2 disjoint regions such that we have the following:
∀j ∈ {1, 2, · · · , c} \ ({l} ∪ {a1}),Pr(U ∈ Dj) ≤ p′j . (75) We can find these region because p′l + ∑ s̸=l p ′ s ≥ 1. Given these regions, we construct the following base classifier:
f∗(z) = j, if z ∈ Dj . (76) Note that f∗ is well defined and is consistent with Equation (3). Next, we show that label l is not in the top-1 predicted labels by the smoothed classifier or there exist ties when the ℓ0 perturbation is larger than rl. In particular, we have the following:
Pr(f∗(V ) = a1| ∥δ∥0 > rl) (77) =Pr(V ∈ Da1 | ∥δ∥0 > rl) (78)
=p′a1 + (1− ( d−rl−1 e )( d e
) ) (79) ≥p′l − (1− ( d−r−1 e
)( d e
) ) (80) =Pr(V ∈ Dl| ∥δ∥0 > rl) (81) =Pr(f∗(V ) = l| ∥δ∥0 > rl). (82)
We have Equation (80) from (79) based on Equation (64). Therefore, the label l is not predicted by the corresponding smoothed classifier g∗ or there exist ties. Combining the two cases, we reach the conclusion.
Next, we will show our bound is almost tight when k ̸= 1. In particular, we will show we can construct a classifier f∗ such that the label l is not among the top-k predicted labels or there exist ties when the adversarial perturbation is larger than rl + 1. Similarly, we consider two cases.
Case I: In this case, we consider p′l < (1− (d−rl−2e )
(de) ). We let Al ⊆ A be the region that satisfies the
following:
p′l = Pr(U ∈ Al). (83)
We can find such region because p′l is an integer multiply of ν = 1 (de) . We let Dl = Al and we have the following:
p′l = Pr(U ∈ Dl),Pr(V ∈ Dl) = 0. (84)
Then, we can divide the remaining region (A ∪ C) \ Dl into c− 1 disjoint regions such that we have the following:
∀j ∈ {1, 2, · · · , c} \ {l},Pr(U ∈ Dj) ≤ p′j . (85) We can find these regions because we have p′l + ∑ s̸=l p ′ s ≥ 1. Moreover, we have the following:
∀j ∈ {1, 2, · · · , c} \ {l},Pr(V ∈ Dj) ≥ 0. (86) Given these regions, we construct the following base classifier:
f∗(z) = j, if z ∈ Dj . (87) Note that f∗ is well defined and is consistent with Equation (3). It is easy to see that label l is not among the top-k predicted labels or there exist ties when ∥δ∥0 > rl + 1.
Case II: In this case, we consider p′l ≥ (1 − (d−rl−2e )
(de) ). For simplicity, we denote the following
quantity:
ν = 1( d e ) . (88)
Since rl is the maximum value that satisfies Equation (6), we have the following condition:
p′l − (1− ( d−rl−1 e )( d e ) ) ≤ min t p′Υt + (1− (d−rl−1e ) (de) ) t . (89)
In other words, the left-hand side of Equation (6) is no larger than its right-hand side when r = rl+1. Based on the recurrence relation of the binomial coefficient, we have the following:(
d− rl − 1 e
) = ( d− rl − 2
e
) + ( d− rl − 2
e− 1
) . (90)
Combining with the condition ( d−rl−2 e−1 ) ≥ 1, we have the following:
p′l − (1− ( d−rl−1 e )( d e
) ) (91) =p′l − (1− ( d−rl−2 e
)( d e ) − (d−rl−2e−1 )( d e
) ) (92) =p′l + ( d−rl−2 e−1 )( d e ) − (1− (d−rl−2e )( d e
) ) (93) ≥p′l + ν − (1− ( d−rl−2 e
)( d e
) ). (94) Similarly, we have the following:
min t
p′Υt + (1− (d−rl−1e )
(de) )
t (95)
=min t
p′Υt − (d−rl−2e−1 ) (de) + (1− ( d−rl−2 e ) (de) )
t (96)
≤min t
p′Υt − ν + (1− (d−rl−2e )
(de) )
t . (97)
Then, based on Equation (89), we have the following:
p′l + ν − (1− ( d−rl−2 e )( d e ) ) ≤ min t p′Υt − ν + (1− (d−rl−2e ) (de) ) t (98)
⇐⇒p′l − (1− ( d−rl−2 e )( d e ) ) ≤ min t p′Υt − ν − t · ν + (1− (d−rl−2e ) (de) ) t (99)
=⇒p′l − (1− ( d−rl−2 e )( d e ) ) < min t p′Υt − t · ν + (1− (d−rl−2e ) (de) ) t . (100)
For simplicity, we denote the following:
w = k
argmin t=1
pΥt − t · ν + (1− (d−rl−2e )
(de) )
t , (101)
where ties are broken uniformly at random. Then, based on Equation (100), we have the following:
p′l − (1− ( d−rl−2 e )( d e ) ) < p′Υw − w · ν + (1− ( d−rl−2 e ) (de) ) w . (102)
Given Equation (101), we have the following if w < k:
p′Υw+1 − (w + 1) · ν + (1− (d−rl−2e )
(de) )
w + 1 ≥
p′Υw − w · ν + (1− (d−rl−2e )
(de) )
w (103)
⇐⇒ p′Υw+1 + (1−
(d−rl−2e ) (de) )
w + 1 ≥
p′Υw + (1− (d−rl−2e )
(de) )
w (104)
⇐⇒p′Υw+1 + (1− ( d−rl−2 e )( d e ) ) ≥ (w + 1) · p′Υw + (1− ( d−rl−2 e ) (de) ) w (105)
⇐⇒p′Υw+1 − p ′ Υw ≥
p′Υw + (1− (d−rl−2e )
(de) )
w (106)
⇐⇒p′aw+1 ≥ p′Υw + (1−
(d−rl−2e ) (de) )
w , (107)
where Υw = {a1, a2, · · · , aw}. Similarly, we have the following if w > 1:
p′Υw−1 − (w − 1) · ν + (1− (d−rl−2e )
(de) )
w − 1 ≥
p′Υw − wν + (1− (d−rl−2e )
(de) )
w (108)
⇐⇒ p′Υw−1 + (1−
(d−rl−2e ) (de) )
w − 1 ≥
p′Υw + (1− (d−rl−2e )
(de) )
w (109)
⇐⇒p′Υw−1 + (1− ( d−rl−2 e )( d e ) ) ≥ (w − 1) · p′Υw + (1− ( d−rl−2 e ) (de) ) w (110)
⇐⇒p′aw ≤ p′Υw + (1−
(d−rl−2e ) (de) )
w . (111)
Note that the Equation (111) also holds when w = 1. Next, we will show we can build a base classifier f∗ such that the label l is not in the top-k predicted labels or there exist ties when the adversarial perturbation is larger than rl + 1. Our proof relies on constructing disjoint regions for label l, Υk, and {1, 2, · · · , c} \ ({l} ∪Υk), respectively. We let Al = A and we can find Cl ∈ C such that the following equation holds:
Pr(U ∈ Cl) = p′l − (1− ( d−rl−2 e )( d e
) ). (112) Then, we let Dl = Cl ∪ Al and we have the following:
Pr(U ∈ Dl) = p′l. (113)
Furthermore, we have the following:
Pr(V ∈ Dl) (114) =Pr(V ∈ Cl) + Pr(V ∈ Al) (115) =Pr(U ∈ Cl) + 0 (116)
=p′l − (1− ( d−rl−2 e )( d e
) ), (117) where the last equality is from Equation (112). For simplicity, we denote the following value:
τ = p′Υw + (1−
(d−rl−2e ) (de) )
w . (118)
Next, we will construct the region for ∀j ∈ Υw. Based on Equation (112), we have the following:
Pr(U ∈ C \ Cl) (119) =Pr(U ∈ C)− Pr(U ∈ Cl) (120)
=(1− ( d−rl−2 e )( d e ) )− (p′l − (1− (d−rl−2e )(d e
) )) (121) =1− p′l. (122)
For ∀j ∈ Υw, we can find disjoint region Cj ⊆ C \ Cl such that we have the following:
Pr(U ∈ Cj) = p′j . (123)
We can find these regions because the summation of the probability of U in these regions is less than the probability of U in C \ Cl, i.e., we have the following:∑
j∈Υw
p′j = p ′ Υw ≤ 1− p ′ l = Pr(U ∈ C \ Cl), (124)
where the middle inequality is from the condition p′l + ∑ s∈Υk p ′ s ≤ 1, and the right equality is based on Equation (119) - (122). Given these regions, we have the following:
∀j ∈ Υw,Pr(V ∈ Cj) = p′j . (125)
Based on Equation (111), definition of τ in Equation (118), and ∀j ∈ Υw, p′j ≤ p′aw , we have the following:
∀j ∈ Υw, p′j ≤ p′aw ≤ τ. (126)
Then, for ∀j ∈ Υw, we can find disjoint region Bj ∈ B such that we have the following:
τ − ν − p′j ≤ Pr(V ∈ Bj) ≤ τ − p′j . (127)
We can construct these regions for three reasons: 1) the value of τ − p′j is no smaller than 0 based on Equation (126), 2) ∀j ∈ Υw, there exists a number in the range [τ − ν − p′j , τ − p′j ] that is an integer multiple of 1
(de) , and 3) the summation of the probability of V in these regions is no larger than the
probability of V in B, i.e., we have the following:∑ j∈Υw Pr(V ∈ Bj) (128)
≤ ∑ j∈Υw (τ − p′j) (129)
=p′Υw + (1− ( d−rl−2 e )( d e
) )− p′Υw (130) ≤(1− ( d−rl−2 e
)( d e
) ) (131) =Pr(V ∈ B). (132)
For ∀j ∈ Υw, we let Dj = Cj ∪ Bj . Then, we have the following:
Pr(V ∈ Dj) (133) =Pr(V ∈ Cj) + Pr(V ∈ Bj) (134) ≥p′j + τ − ν − p′j (135) =τ − ν, (136)
where the Equation (135) from (134) is based on Equation (123) and (127). Next, we will construct the regions for the labels in Υk \ Υw. In particular, for ∀j ∈ {aw+1, aw+2, · · · , ak}, we can find disjoint region Dj ∈ C \ (Cl ∪ (∪s∈ΥwCs)) such that we have the following:
Pr(U ∈ Dj) = p′j . (137)
Note that we can find these regions because p′l + ∑ s∈Υk p ′ s ≤ 1. Similarly, we have the following for ∀j ∈ Υk \Υw:
Pr(V ∈ Dj) = p′j ≥ τ. (138)
We have the left inequality because ∀j ∈ Υk \Υw, p′j ≥ τ based on Equation (107). Finally, we can divide the remaining region Dj ⊆ C ∪ A \ (Dl ∪ (∪s∈ΥkCs)) into c− k − 1 disjoint regions such that we have the following:
∀j ∈ {1, 2, · · · , c} \ ({l} ∪Υk),Pr(U ∈ Dj) ≤ p′j . (139) We can find these region because p′l + ∑ s̸=l p ′ s ≥ 1. Given these regions, we construct the following base classifier:
f∗(z) = j, if z ∈ Dj . (140)
Note that f∗ is well defined and is consistent with Equation (3). Next, we show that label l is not in the top-k predicted labels by the smoothed classifier when the ℓ0 perturbation is larger than rl + 1. In particular, for ∀j ∈ Υk, we have the following:
Pr(f∗(V ) = j| ∥δ∥0 > rl + 1) (141) =Pr(V ∈ Dj | ∥δ∥0 > rl + 1) (142) ≥τ − ν (143)
= p′Υw − w · ν + (1−
(d−rl−2e ) (de) )
w (144) >p′l − (1− ( d−r−2 e )( d e
) ) (145) ≥Pr(V ∈ Dl| ∥δ∥0 > rl + 1) (146) =Pr(f∗(V ) = l| ∥δ∥0 > rl + 1). (147)
We have Equation (145) from (144) based on Equation (102). Therefore, the label l is not among the top-k predicted labels by the corresponding smoothed classifier g∗. Combining the two cases, we reach the conclusion.
Takeaway: The key challenge in proving the tightness of certified robustness guarantee is that we are not able to find regions in the discrete space that satisfy certain conditions. The reason is that we cannot arbitrarily divide the discrete space into different regions. To address the challenge, we propose to relax the conditions in finding the regions to prove that the certified robustness guarantee is almost tight. The idea in our proof is very general and we hope our proof can inspire future research in proving the (almost) tightness for ℓ0-norm certified robustness guarantee.

heading: C OTHER APPLICATIONS
text: In this paper, we focus on image classification. However, our method is also applicable for other applications such as graph neural networks and 3D deep learning. For example, we conduct experiments for 3D deep learning. In particular, we evaluate our methods on the ModelNet40 (Wu et al., 2015) benchmark dataset and use PointNet (Qi et al., 2017) as the base classifier. We set e = 16, n = 10, 000, and α = 0.001. When the number of modified points is 10, 20, 30, 40, and 50, the certified accuracies for top-1 prediction are 0.779, 0.743, 0.700, 0.649, and 0.570; and the certified accuracies for top-3 prediction are 0.901, 0.867, 0.829, 0.803, and 0.775.

heading: D COMPARING WITH CHIANG ET AL. (2020)
text: We also compare with our method with Chiang et al. (2020). We note that the method in Chiang et al. is only applicable for top-1 prediction. We compare with the method on the CIFAR10 dataset for top-1 predictions using the publicly available code. The results are as follows. When the number of perturbed pixels is 1, 2, 3, 4, and 5, the certified accuracies for our method are respectively 0.746,
0.718, 0.690, 0.660, and 0.636. In contrast, the certified accuracies of Chiang et al. are 0.400, 0.369, 0.342, 0.312, 0.308. As the results show, our method is better than Chiang et al. (2020). We note that our certified robustness guarantee is probabilistic while Chiang et al. (2020) can give a deterministic certified robustness guarantee.

Review summaries:
This paper provides an almost tight l0-norm certified robustness guarantee for top-k predictions against adversarial perturbations, which extends certified radius of the top-1 prediction from Levine & Feizi (2019) to that of the top-k predictions, and the l2-norm certified radius from Jia et al. (2020) to the l0-norm certified radius. The experiments on CIFAR10 and ImageNet show that the proposed method substantially outperforms state-of-the-art for top-k predictions.

The paper provides both theoretical progress and experimental results on certified robustness of top-$k$ predictions. Specifically, on the theory side, the paper shows that the randomized ablation (Levin & Feizi) has $\ell_0$-norm certified radius of top-$k$ predictions. Also, the paper proves that the certified radius is tight for k = 1 and almost tight for k > 1. (The certified radius cannot be larger than “the derived radius plus 1”.) On the experiment side, the paper compares the proposed method to existing competitors and explored the impact of the related parameters.