Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations
Authors: Jinyuan Jia
Binghui Wang
Xiaoyu Cao
Hongbin Liu
Neil Zhenqiang Gong
Venue: ICLR 2022 Poster (2022)

Abstract: Top-$k$ predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. $\ell_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. $\ell_0$-norm adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying  robustness of top-$k$ predictions against $\ell_0$-norm adversarial perturbation is important. However, existing studies either focused on certifying $\ell_0$-norm robustness of top-$1$ predictions or  $\ell_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 $\ell_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. 

Published as a conference paper at ICLR 2022
ALMOST TIGHT LO-NORM CERTIFIED ROBUSTNESS OF TOP-k PREDICTIONS AGAINST ADVERSARIAL PERTUR-
BATIONS
Jinyuan Jia
Binghui Wang
Xiaoyu Cao
Duke University jinyuan. ji duke. eduu
Illinois Institute of Technology bwang700 iitteett...
Duke University
xiaoyu. wiaaoyu.co@@duke.ce. waweecce.eddeeeeeeooo
Hongbin Liu
Neil Zhenqiang Gong
Duke University
Duke University
hongbin. Liudduke.e edu
neil. gongeduke.edu
ABSTRACT
Top-k predictions are used in many real-world applications such as machine learn- ing service, recommender systems, and web searches. f--norm adversarial perturbation characterizes an attack that arbitrarily modifies some features of an input such that a classifier makes incorrect prediction for the perturbed input. fo-norm ad adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying robustness of top-k predictions against f--norm ad adversarial perturbation is important. However, existing studies either focused on certifying fn-norm robustness of top-1 predictions or &n-norm robust- ness 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 L-- form certified robustness guarantee for top-k predictions. We empirically evaluate our method CIFARIO 10 and ImageNet. For instance, method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when attacker arbitrarily perturb 5 pixels of testing image.
INTRODUCTION
Adversarial example is a well-known severe security vulnerability of classifiers. Specifically, given classifier / and testing input x, an attacker can carefully craft a numan-imperceptible perturbation 5 such that [xx) * f(x 5). The perturbation is called adversarial perturbation, while the input
x x++ 8 called an adversarial example. Many empirical defenses (Goodfello et al. 2015: Na et al.)
2018 Metzen al. 2017 Svoboda et al. 2019 Buckman et al. 2018, 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. 2013] Carlini et al.) 2017: Ehlers, 2017 Katz et al. 2017; 2017:[Cheng et al., 2017 2017| Lomuscio &
Maganti| 2017 2 Fischetii & Jo [018]] Bunel al. [2018] Wong Kolter [0188] [olter[2018
Wong al. 20188)
Raghunathan et al. 2018 bj Dvijotham et [l. 8a Balballlaa Gehr et [0. et al. 2018 Singh
2018: Weng al. | 2018| Zhang et al. 2018 Gowal et al. 2018 Wang al. [018]] 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.) (0200) have been proposed. In particular, a classifier is said to be
certifiably robust for an input if it provably predicts the same top-1 label ((x)..((z) f(z 6)) when the adversarial perturbation ó is bounded, e.g., the fo-norm of 6 is smaller than threshold. The threshold is also called certified radius. In this work, we focus Lu norm adversarial perturbation, which arbitrarily manipulates some features of a testing input and can be implemented in the physical world.

---

Published as a conference paper at ICLR 2022
However, most existing certified defenses focus top-1 predictions. In many applications, top-k predictions that return the most likely labels are more relevant. For instance, when a classifier service) (Google Cloud Vision
is deployed as cloud service (also called machine learning 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 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 tight éz-norm certified robustness for top-k predictions. Such fn-norm certified robustness can be transformed to fn-norm certified robustness via employing the inequality between nn-norm and fo-ormm However, the fo-norm certified robustness derived from such transformations is suboptimal.
Our work: We aim to develop fo-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 let al. 2019 Cohen et al.] 2019 Lee et al. [019 Jia et al. [020]] 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-theear fg-norm certified robustness for top-1 predictions. Unlike other
randomized smoothing methods (Cao & Gong 2017 Lecuyer et al.) 2019: Li et al. 2019; Cohen
al. 2019) that randomize an input via adding additive noise (c.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 testing input x, randomized ablation creates an ablated inpul 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 image, the features are the image's '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 for the random ablated input. The original randomized ablation method builds a smoothed classifier that outputs the label with the largest label probability Py for a testing input In work, the smoothed classifier returns the k labels with the largest label probabilities for x.
Our major theoretical contribution is almost tight fo-norm certified robustness guarantee of top-k predictions for the smoothed classifier constructed by randomized ablation. Specifically, we first derive an t 6o-norm certified robustness guarantee of top-k predictions for the smoothed classifier. Our results show that a label is provably among the top-k labels predicted by the smoothed classifier for a testing input x when the attacker arbitrarily perturbs at most ry features of x, where ri is the Eg no-norm certified radius. Moreover, we prove that our certified radius is tight when k = 1 and is almost tight when & > 1. In particular, if no assumptions on the base classifier are made, it is impossible to derive a certified radius that is larger than ri + [[k f 1). In other words, when an attacker manipulates at least rt- + 1 + I[(k f 1) features of a testing input, there exists a base classifier from which the smoothed classifier's top-k predicted labels do not include I there exist ties.
Our work has several technical differences with Levine & Feizi (211)). First, we derive the Eo fo-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 fg-norm certified radius of top-k predictions for randomized smoothing with Gaussian additive noise. Since they add additive Gaussian noise to a testing imput, 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 al. and our work use substantially different techniques to derive the Ez/Eo-norm certified radiuses and prove their (almost) tightness. In particular, when deriving the f2/6o-norm certified radiuses, our work needs to construct different regions in the discrete space of ablated inputs such that the Beyman-Pearson Lemma (Neyman& & Pearson
1933) can be applied. When proving the (almost) tightness, we use 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
2

---

Published as a conference paper at ICLR 2022
unnecessary in case because the ablated inputs that can be derived from an imput uniformly distributed in the space of ablated inputs.
We evaluate method CIFARIO and ImageNet. Our results show that our method substantially outperforms state-of-the-are for top-k predictions. For instance, our method achieves a certified top-3 accuracy of 69.2% ImageNet when attacker arbitrarily perturbs 5 pixels of testing image. Under the same setting, Dia et al. (020)) achieves a certified top-3 accuracy of only 9.0%, when transforming their 2--norm certified robustness to fn-norm certified robustness.
Our contributions can be summarized as follows:
We derive 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 CIFARIO and ImageNet.
THEORETICAL RESULTS
In this section, we show core theoretical contributions.
2.1 BUILDING A SMOOTHED CLASSIFIER VIA RANDOMIZED ABLATION
Suppose we have base classifier f. which classifies a testing input to one of c classees {1, .c} deterministically. For simplicity, we assume x is an image with pixels. Given an input x, randomized ablation (Levine & Feizi 2019) creates an ablated imput as follows: we first randomly subsample pixels from x without replacement and keep their values. Then, we set the remaining pixel values in the ablated input to special value, e.g., median of the pixel value, mean of the pixel value, or special symbol. When the image 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 l((x, e) to denote the randomly ablated input for simplicity. Given h(x, e) as imput, the output of the base classifier f is also random. We use pj denote the probability that the base classifier f predicts class when taking h(x,e e) as input, i.e., Pj (r(f(h(x, e)) j). Note that Pj is integer multiple of (:) which we
will leverage to derive tighter certified robustness guarantee. We build smoothed classifier g that outputs the k labels with the largest label probabilities p, 's for x. Moreover, we denote by gl gx(x) the set of k labels predicted for x.
2.2 DERIVING THE CERTIFIED RADIUS FOR THE SMOOTHED CLASSIFIER
Defining two random variables: Suppose an attacker adds a perturbation ó to an input x, where [|ōl| the number of pixels perturbed by the attacker. We define the following two random variables:
h(xx e), V h(x + 5,e).
(1)
where the random variables U and V denote the ablated inputs derived from x and its perturbed version + 8, 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 + 8. Given the definition of and V, Pr(J(U) = j) and PV(f(V)= = respectively represent the label probabilities of the input and its perturbed version x ++0 predicted by the smoothed classifier.
Derivation goal: Intuitively, an ablated input f(x,, e) is very likely to not include any perturbed pixel [10% is bounded and is relatively small, and thus the predicted labels of the smoothed classifier not influenced by the perturbation. Formally, 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 show that / E gx(x + 5) when ||o||o S rt, where rı is the certified radius. Our key idea to derive the certified radius is to guarantee that, when taking as input, the label probability for label is larger than the smallest one among the label probabilities of any & labels from all labels except 1. We let I = {1, 2, ... c} \ {(}. i.e., I denotes the set of all labels except 1. We use T3 to denote a set of & labels in r. Then, we aim to find maximum certified radius r such that:
goal is to show that label 1 {1,2. ... .c}
Pr(f(V) 1) > max min Pr(f(V) = j). JAcrJets
(2)
3

---

Published as a conference paper at ICLR 2022
Roughly speaking, the above equation means that: ensure 1 exists in the set of top-k labels, Pr(f(V)= = 1) should be larger than the minimum probability observed by taking any set of k labels I' excluding! l. To reach the goal, we derive a lower bound of Pr(f(V) = I) and upper bound of maxr, cr min Pr( (r( = 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 A | = r. Then, we can leverage binary search to find the maximum such that the lower bound is larger than the upper bound and treat the maximum radius rt. Next, we respectively introduce how to derive lower and upper bounds and use them to compute certified radius.
the certified
Deriving a lower bound of Pr(f(V) 1) and an upper bound of maxr,, CT minjer, PV( = j): We show our intuition to derive the upper and lower bounds. Our formal analysis is shown in the proof of Theorem | Our idea to derive the bounds is to divide the discrete space S in an innovative way such that we can leverage the Neyman-Pearsoe
Lemma (Neyman & Pearson [933). Suppose for the random variable U, we have a lower bound of the label probability for and an upper bound of the label probability for every other label. Formally, we have pt. P1 ... -.---- PI Pr. ... .P. that satisfy
the following:
Pt S Pr(f(U) = 1),,, 2 Pr(f(U)= - j). 44,
(3)
where p and p denote the lower and upper bounds of p. respectively. Multiplying each term in Equation 30 by (c), we have pt-()) S Pr(J(U) 1). (2. .y (1) 2 Pr(S(U) ().()) Vj + L. Since Pt and py [Vj + () are integer multiples of (.)
we have [pt (:1 = Pr(f(U) = 0) (9) 18, (1)2
Pr(J(U)= j) ( Vj # Therefore, we have the following:
Pr (91 < Pr((())= = 1.
P3
pt
> Pr([(U)= j).j
(4)
Let Pog 2 Pax_1 2 Po1 be the i largest ones among {P) ... are broken uniformly at random. We denote Y, = {a1. 02 ... a₂) as the set of labels with the smallest label probability upper bounds in the le largest ones and denote by F'r, Σjer, Pj the sum of the t label probability bounds, where t 1,2, K.
.Po), where ties
We define regions A, B, and C in as the sets of ablated inputs that can be derived only from x. only from + 5, and from both x and + 8, respectively. In particular, the region A is set of ablated inputs that can only be obtained via sampling e features (pixels) from x. The region B is set of ablated inputs that can only be obtained via sampling features from the perturbed and the region C is a set of ablated inputs that can be obtained via sampling e features from both and x + 8. Then, assume we can find such a region A'' since we aim to find sufficient condition. Similarly, we can find Hr, such that we have Pr(U E Hr,) PT. Then, can apply the Jeyman-Pearson Lemma (Neyman & Pearson|
5,
find region A' C C such that Pr(U A' A) = p/-- Note that
1933) to derive lower bound of Pr( = 1) and an upper bound of maxr, cr minjer', PV( 3) by leveraging the probabilities of V in regions A' U A and Hr, U B. Formally, we have the following:
Pr(V E Hr, UB)
Pr(f(V) 2 Pr(V E A'UA),, max min Pr(f(V)= j) < min
(5)
F&CT jel's
L
Computing certified radius: Given the lower and upper bounds, we can find the maximum r = |0%
such that the lower bound Pr(V E A' U A) is larger than the upper bound min Pr(VE UB) The maximum r is the certified radius. Formally, we have the following theorem:
Theorem (fo-norm Certified Radius for Top-k Predictions). Suppose we have an imput x with d features, a deterministic base classifier f, an integer e, smoothed classifier y where 9x(x) is set of le labels predicted for x, an arbitrary label I E [1,2,.... ... .c,. pt.Pr. p.. "a.....Pp .Pi-1. 1.41. .e. that satisfy Equation (3), and ple (1 + 1) that are defined in Equation (4). If the th following optimization problem has a sotution Ti:
DT. + (1
T1 arg maxT S.L. P - (1 r20
min
(6)
4

---

Published as a conference paper at ICLR 2022
Then, we have the following:
LE 9x + +),V1 m.
Proof. Please refer to Appendix
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 n--nrrm radius that is larger than ri + I(k: o 1) for top-k predictions.
Theorem 2 (Almost Tightness of our Certified Radius). Assuming we have (!--)²) 2 1, pi
Ejer, F3 S. L, and pi1 + E F, 2 1. If no assumption the base classifier is made, then, for any perturbation ||ōl|, r1 + I(k & 1), there exists a base classifier f consistent with Equation (3) but we have 1 & (x + 8) or there exist ties.
Proof. Please refer to Appendix B
Comparing with Levine & Feizi (019 when k 1: Our certified radius reduces to the maximum
r that satisfies p/ Plo, > (1
when k 1. In contrast, the certified radius in Levine
& Feizi (2019) is the maximum r that satisfies Pa. > 2
Since pi 2 Pr and
Pai Pay. our certified radius is the same or larger than that in Levine & Feizi (011)) Note
that the method by Levine & Feizi (2019) cannot be extended a stranghttorward 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 for an ablated clean input (i.e., Pr(J(U) = i)) 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 jointly derive the bounds for multiple label probabilities (i.e., Equation (5)). Moreover, because of the difference in deriving label cabel-probability bounds, our techniques are significantly different. particular, Levine Feizi only need the law of total probability while we leverage Neyman- 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. (020)): Jia et al. (2020) proved the exact tightness of their &g 2n-morm 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 region via the Intermediate Value Theorem, which relies on the continuity of space of ablated inputs is discrete. Therefore, given 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 result, we cannot prove the exact tightness of the fn-nrrm certified radius when l: > 1. To address the challenge, we find a region whose probability measure is slightly smaller than the given upper bound, which enables to prove the almost tightness of our certified radius. Second, since Gaussian noise is not uniform, they need 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.
Gaussian noise. However,
Computing in practice: When applying our Theorem I to calculate the certified radius ri in practice, we need the probability bounds P and Fr, 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 (pr and Pj. Vj # 1) with probabilistic guarantees. Then, we can use them to estimate pi and Pr.,- Moreover, given the probability bounds pi and pr.,- can use binary search to solve Equation (6) to find the certified radius ri-
Specifically, the probabilities P1, P..... Pe can be viewed as a multinomial distribution over the label set {1, ......ch Given h(x, e) input, f(((x,)) e)) can be viewed sample from the multinomial distribution. Therefore, estimating Py and P; for + is essentially a one-sided simultaneous confidence interval estimation problem. In particular, we leverage the simultaneous
5

---

Published as a conference paper at ICLR 2022
confidence interval estimation method called SimuEM (Jia al.) 2020) to estimate these bounds with a confidence level at least 1 - a. Specifically, given an input x and parameter e, we randomly create n ablated imputs, i.e. c¹ c2,c..... ,e". We denote by nj the frequency of the label predicted by the base classifier for the n ablated inputs. Formally, we have n, > I(f(e") j), where j E {1, 2, , o} and is the indicator function. According to Jia et al. 22200) we have the following probability bounds with confidence level at least
p B E - nu n Tu + +1) .P3 B(1 iing + 1, nz), Vj H1,
(8)
where B(g; 5, is the gth quantile of a beta distribution with shape parameters & and Ç. Then, compute pl and 74,, Vj + 1 based on Equation (4. Finally, estimate Pr, as pTr
min EjEr, 11,1-p)) ph).
3 EVALUATION
3.1 EXPERIMENTAL SETUP
We use CIFARIO (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 implementation of randomized ablation to train our models. In particular, we use ResNet- 10 and RestNet-50 as the base classifiers for CIFAR10 and ImageNet, respectively. Moreover, as Lee et al. (2019), we use 500 testing examples for both CIFAR10 and ImageNet.
Datasets and models:
Parameter setting: Unless otherwise mentioned, we adopt the following default parameters. We set 50 and 1, 000 for CIFARIO and ImageNet, respectively. We set A: = 3. 100, 000, and a = 0.001. We will study the impact 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 number of perturbed pixels, certified top-k accuracy is the fraction of testing images, whose true labels have fn-nrmm certified radiuses for top-k predictions that are no smaller than the given number of perturbed pixels. Note that our fo-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 testing image and derives light fy-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 fy-norm certified number of perturbed pixels r can be obtained from an l2 fo-norm certified radius /3ri-
Lee et al. (2019). This method derives an fg-norm certified radius for top-1 predictions. This method is applicable discrete features. Like Lee al. (2019), we treat the pixel values as discrete in the domain (0, 1/256, 2/256, ... 255/256), Since their fo-norm certified radius for pixel channels (each pixel has 3 color channels), a certified number of perturbed pixels can be obtained from their 4o-norm certified radius 37y.
Levine & Feizi 2019). This method derives an fo-norm certified number of perturbed
pixels for top-1 predictions in randomized ablation. This method requires 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 We also found that the top-1 certified accuracies based on our derived certified radius and their derived certified radius have negligible differences CIFARIO 10 and ImageNet, and thus we do not show the differences for simplicity.
derived certified radius when evaluating this method.

---

Published as a conference paper at ICLR 2022
Table 1: Certified top-k accuracies of the compared methods on CIFARIO.
#Perturbed pixels
5
Cohen et al. (2019)
0.1
0.056
0.018
0.0
Lee et al. (2019)
0.188
0.018
0.004
0.002
Levine & Feizi 2019
0.704
0.680
0.670
0.646
0.610
Certified top-1 accuracy
Levine & Feizi 2019
0.746
0.718
0.690
0.660
0.636
SiiuEE (Jia at.
2020
Our method
0.746
0.718
0.690
0.660
0.636
Jia (2020)
0.244
0.124
0.070
0.028
0.004
Cortified top-3 accuracy
Our method
0.886
0.860
0.838
0.814
0.780
Table 2: Certified top-k accuracies of the compared methods on ImageNet.
#Perturbed pixels
2
3
5
Cohen et al. (2019)
0.226
0.152
0.120
0.088
0.0
Lee et 2019)
0.338
0.196
0.104
0.092
0.070
Levine Feizi 2019
0.602
0.600
0.596
0.588
0.586
Certified top-1 accuracy
Levine & Frzzzi 20199
0.634
0.628
0.618
0.616
0.608
SSmuEEM [Jia et al.
2020
Our method
0.634
0.628
0.618
0.616
0.608
Jia al. (2020)
0.326
0.232
0.160
0.120
0.090
Certified top-3 accuracy
Our method
0.740
0.730
0.712
0.698
0.692
Levine & Feizi (2019) SimuEM (Jia et al.
2020). This is the Levine & Feizi (2019)
method with the lower/upper bounds of label probabilities estimated using the simultaneous confidence interval estimation method called SimuEM. Again, we use our derived certified radius for top-1 predictions in this method.
Jia al. (2020). This work extends Cohen al. 2019) from top-1 predictions to top-k predictions. In detail, they derive tight 22 2o-m certified radius of top-k predictions for randomized smoothing with Gaussian noise. An Lu 4--norm certified number of perturbed pixels for top-k predictions can be obtained from an l -norm certified radius /3r,.
Our method. Our method produces an almost tight 4n-norm certified number of perturbed pixels of top-k predictions.
Note that we compare with Cohen et al. 2019) and Jia al, (2020) because we aim to show that suboptimal to derive fo-norm certified robustness for top-k predictions by leveraging the relationship between fg-m and norm.
3.2 EXPERIMENTAL RESULTS
Comparison results: Table T and respectively show the certified top-k accuracies of the compared methods on CIFARIO and ImageNet when an attacker perturbs certain number of pixels. The Gaussian noise in Cohen et al. (019) and Jia et al. (2020) has mean 0 and standard deviation a. We obtain the certified top-k accuracies for different a, i.e., we explored a 0.1, 0.12, 0.25, 0.5, 1.0. Lee et al. (2019) has a noise parameter B. We obtain the certified top-1 accuracies for different 3. 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. (2119) Lee et al. (2019) and Jia et al. (2020) for each given number of perturbed pixels. We use the default values for Levine & Feizi (2019) and our method.
We have two observations from Table and 2 First, our method substantially outperforms Jia et al. (2020) for top-k predictions, while Levine & Feizi (2099) substantially outperforms Cohen et al. (201)) and Lee et al. (2019) for top- predictions. Since our method Levine & Feizi Feizi[(001) use randomized ablation, while the remaining methods use additive noise (Gaussian discrete noise) to randomize testing input, our results indicate that randomized ablation superior to additive noise certifying fo-m robustness. Second, Levine & Feizi (019) SimuEM (Jia al. 2020
7

---

Published as a conference paper at ICLR 2022
Candall Tip- Aemaaa
k-1
k-3
3.0
26
(a) CIFAR10
(b) ImageNet
Figure 1: Impact of ls on certified top-k accuracy.
Candall Tapk Armra
H H
e-
500
100
c-10000
26
20
125
Narrer Poraatid Plods
Sunder Pritubed Park
(a) CIFAR10
(b) ImageNet
Figure 2: Impact of on certified top-3 accuracy.
Cendial Armmor
D-=10
D- 10
E
Niviorrd Derrrrlod Pooks
Stmiee of Perturbed Phoii
(a) CIFARIO
(b) ImageNet
Figure 3: Impact of certified top-3 accuracy.
0 0.00
001
c1 010000
0001
Simbered Peerrrood Prods
Strboe Pestubee Prak
(a) CIFARIO
(b) ImageNet
Figure 4: Impact of on certified top-3 accuracy.
outperforms Levine Feizi (2019). This because SimuEM can more accurately estimate the label
probability bounds via simultaneous confidence interval estimations.
and show the certified top-k accuracy of method vs. number of perturbed pixels for different k, e, and a, respectively. Naturally, the certified top-k accuracy increases k increases. For instance, when pixels are perturbed, the certified top-1 and top-3 accuracies are 63.6% and 78.0% on CIFAR 10, respectively. We observe that provides a tradeoff between accuracy under attacks and robustness. Specifically, when is larger, the accuracy under no attacks (i.c., certified accuracy with perturbed pixels) is higher, while the certified accuracy decreases to more quickly as the number of perturbed pixels increases. As becomes larger, the curve of the certified accuracy may become higher. The reason is that larger n makes the estimated label probability bounds pt and Fr, tighter and thus the fo-norm certified radius may be larger, which result in a larger certified accuracy. Theoretically, as the confidence level 1- a decreases, the curve of the certified accuracy may become higher. This is because a smaller confidence level leads tighter estimated label probability bounds pt and Fr, and thus the certified accuracy may be larger. However, we observe the differences between different confidence levels are negligible when the confidence levels high enough (i.e., is small enough).
Impact of k;, e, n, and Figure
8

---

Published as a conference paper at ICLR 2022
4 RELATED WORK
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 & Magantil 2017 Fischetti & Jo 2018 Bunel et al.
2018; Wong & Kolter 2018; Wong et al. 22018) semidefinite programming (Raghunathan et al.
2018a b). dual optimization (Dvijotham et al.) 2018a b), abstract interpretation (Gehr al. 20018
Mirman et al. 2018 Singh et 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-Lo-norm and to 4o-norm robustness.
Randomized smoothing for non-Lo-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. [ee et al. (2019) derived certified robustness for such uniform random noise. Lecuyer iet al. (2019) was the first to derive formal le and -orm robustness guarantee randomized smoothing with Gaussian or Laplacian noise via differential privacy techniques. Subsequently, Li jet al. (2019) leveraged information theory to derive a tighter ln-nomm robustness guarantee. [Cohen
al. (2019) leveraged the Seymann-Peasoon Lemma (Neyman & Pearson 1933 to obtain tight
ce-nfrr certified robustness guarantee for randomized smoothing with Gaussian noise. Other studies include al. (2019); Carmon al. (2019); Salman et al. (2019); Zhai et al. (2020); Dvijotham ict (2019)) Blum et al. (2020); Levine & Feizi (2020); K Kumar et al. (2020); Yang et al. (2000); Zhang et (2020) Salman 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.
?2-norm
Randomized smoothing for fo-norm robustness: All the above randomized smoothing based provable defenses were not (specifically) designed to certify ty f--norm robustness. They can be transformed to fo-norm robustness via leveraging the relationship between l, norms. However, such transformations lead to suboptimal fn-norm certified robustness. In response, multiple studies (Lee)
et al. 2019 Levine& & Feizi| 2019; Dvijotham et al.
2019 Bojchevski et al. 2020; Jia al. 2020
proposed new randomized smoothing schemes (2019) derived an lo -o-nr certified robustness for classifiers with discrete features using randomized smoothing. In particular, for each feature, they keep its value with 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 fo-momm 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 by -orm certified robustness guarantee of top-k predictions for randomized ablation.
Zhang et al. 2021 Wang et al. [iu et al. 2021 1)
to certify Eo norm robustness. For instance, Lee et al.
5 CONCLUSION
In this work, we derive an almost tight fy-norm certified robustness guarantee of top-k predictions against adversarial perturbations for randomized ablation. We show that label is provably among the top-k labels predicted by a classifier smoothed by randomized ablation for a testing input when an attacker arbitrarily modifies bounded number of features of the testing input. Moreover, prove our derived bound is almost tight. Our empirical results show that our formorm certified robustness is substantially better than those transformed from no-mrrm certified robustness. Interesting future works include exploring other noise to certify &g fn-norm robustness for top-k predictions and incorporating the information of the base classifier derive larger certified radiuses.
ACKNOWLEDGMENTS
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. W911 1NF2110112122

---

Published as a conference paper at ICLR 2022
REFERENCES
Amazon AWS. wwwp://..w..aaaz.c...o.oo wwt.:/nn.ccc/ccooaeeoee http://www..aaaaccc....oeeeentot April 2021.
Anish Athalye and Nicholas Carlini. On the robustness of the cvpr 2018 white-box adversarial example defenses. arXiv, 2018.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In ICML, 2018.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify Lo robustness for high-dimensional images. arXiv preprimi arXiv:2002.03517. 2020.
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In ICML, 2020.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In ICLR, 2018.
Rudy Bunel, liker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. In NeurIPS, 2018.
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks to deep neural networks via region-based classification. In ACSAC, 2017.
Nicholas Carlini and David Wagner. Adversarial examples not easily detected: Bypassing detection methods. In AlSec, 2017.
Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. Provably minimally-distorted adversarial examples. arXiv, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang, Unlabeled data improves adversarial robustness, In Advances Neural Information Processing Systems, pp- 11192-11203, 2019.
Chih-Hong Cheng. Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In ATVA, 2017.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein. Certified defenses for adversarial patches. arXiv preprint arXiv:2003.0666 2020.
Clarifai.
wtt.commo/////ee April 2021.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. ICML, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Guneet S Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. In ICLR, 2018.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli, Training verified learners with learned verifiers. arXiv, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, 2018b.
Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference Learning Representations, 2019.
10

---

Published as a conference paper at ICLR 2022
Ruediger Ehlers. Formal verification of piece- wise linear feed-forward neural networks. In ATVA, 2017.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 2018.
Timon Gehr, Matthew Mirman, Dana Drachsler- Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev, Ai2: Safety and robustness certification of neural networks with abstract interpretation. In IEEE S & P. 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Google Cloud Vision. https://cclee wwwp://wwwwoooe..ooooooooo. conooiiiooo//vvsiooo April 2021.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv, 2018.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations. In ICLR, 2018.
Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of com- munity detection against adversarial structural perturbation via randomized smoothing. In WWW, 2020.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In CAV, 2017.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In ICML, 2020.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE S & P. 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In NewrlPS, 2019.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. arXiv preprint arXiv:1911.09277 2019.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 3938-3947, PMLR. 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. In NeurIPS, 2019.
Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. Pointguard: Provably robust 3d point cloud classification. In CVPR, 2021.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. Towards robust neural networks via random self-ensemble. In ECCV, 2018
Alessio Lomuscio and Lalit Maganti. An approach reachability analysis for feed-forward relu neural networks. arXiv, 2017.
Xingjun Ma, Bo Li, Yisen Wang. Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck. Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In ICLR, 2018.

---

Published as a conference paper at ICLR 2022
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. In ICLR, 2017.
Microsoft.
April 2021.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In /CMI,, 2018.
Taesik Na, Jong Hwan Ko, and Saibal Mukhopadhyay. Cascade adversarial machine learning regularized with a unified embedding. In ICLR, 2018.
Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231 (394-77766))299333333 1933.
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization. In NeurlPS, 2019.
Charles R Qi. Hao Su. Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In ICLR, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In NeurlPS, 2018b.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In NeurlPS, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and Zico Kolter. Black-box smoothing: A provable defense for pretrained classifiers. arXiv preprint 2xXiv:0003.0/00 2020.
Karsten Scheibler, Leonore Winterer, Ralf Wimmer, and Bernd Becker. Towards verification of artificial neural networks. In MBMV, 2015.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev, Fast and effective robustness certification. In NewrlPS, 2018.
Yang Song. Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models understand and defend against adversarial examples. In ICLR, 2018.
Jan Svoboda, Jonathan Masci, et al. Peernets: Exploiting peer wisdom against adversarial attacks. In ICLR, 2019.
Jonathan Uesato, Brendan O' D'onogguue Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In ICMI, 2018.
Binghui Wang, Xiaoyu Cao, Jinyuan Jia, Neil Zhenqiang Gong, et al. On certifying robustness against backdoor attacks via randomized smoothing. CVPR 2020 Workshop on Adversarial Machine Learning in Computer Vision, 2020.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In KDD, 2021.
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In USENIX Security Symposium, 2018
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. In ICML., 2018.
12

---

Published as a conference paper at ICLR 2022
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In HCML,, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. In NewrIPS, 2018.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In ICLR, 2018.
Greg Yang. Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In ICML, 2020.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. In ICLR, 2020.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: A functional optimization based framework. arXiv preprint arXhv:2002.09169, 2020.
Huan Zhang, Tsui-Wei Weng, Pun-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NeurIPS, 2018.
Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. SACMAT, 2021.
Tianhang Zheng, Di Wang, Baochun Li, and Jinhui Xu. Towards assessment of randomized mecha- nisms for certifying adversarial robustness. arXiv preprint arXiv:2005.07347, 2020.
13

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM
1
We define the following two random variables:
U = h(x, e), V h(x + 6,
(9)
where 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-Pearse Lemma (Neyman Pearson 1933), and we present it as follows:
Lemma 1 (Neyman-Pearson Lemma). Suppose U and V are two rundom variables in the space with probability distributions Pu and pv, respectively. Let F S - {0, 13 be a random or deterministic function. Then, we have the following:
Z1 = {s E S (s( > J. (-)( and Z₂ = {s S ps)ss) = p. (s( for some # p> 0. Let 7. 71 U Z3, where Z3 C Z.2. If we have Pr(F(U) = 1) 2 Pr(U Z), then Pr(V E 2)
(M(F(V)=1)
If 21 {ss :: :p((s) s (s) and Ze = (s S ps(s) p. (c())) for some
μ 0. Let Z U where Z3 S Zz. If we have Pr(F(U)= = 1) S Pr(U E 2), then Pr(F(V)= =) Pr(V Z).
Proof. We show the proof of the first part, and the second part be proved similarly. For simplicity, we use F(][s) and F(O]s) to denote the conditional probabilities that F(s) = 0 and F(s) = 1, respectively. We use Ze denote the complement of i... Ze S Z. We have the following:
Pr(F(V)) 1) Pr(V E Z) Σ F(]ss) (s) - Σ (s())
(10)
(11)
SE
SEZ
Σ F(1ss) pP((s) + Σ F(1(s) Po(s) - pr(s) - Σ F(Ols) ps(s)
(12)
*EZ"
SEZ
SEZ
SEZ
Σ F(L(s) Po(s) Σ F(O)s): (s(s)
(13)
SEZ=
sEZ
2
F(1(s) (s())
Σ F(Ols) (s()))
(14)
J
2EZe
8EZ
1
F(1[s) Pa(s)) + Σ
F(1(s) pa(s) Σ F(1ls) pu(s) - Σ
F(O)s) Pu(s)) (15)
SE
NEZ
.EZ
.E7
1
F(1|s) ps(s) Σ (s()))
(16)
J
SES
SEZ
1 (Pr(F(U) = -) Pr(U Z))
(17)
20.
(18)
We obtain 14 from 13 because (s) 2 n. (s), Vs Z and Pu(s) S # po(s), Vs E 2 We have the last inequality because Pr Pr(F(UU= = 1) 2 Pr(U E Z).
Next, we will derive our certified robustness guarantee. For simplicity, we denote r (1, 2, ... c) (T}, i.e., P denotes the set of all labels except 1. We use r3 to denote a set of k labels in r.
Calibrating the lower and upper bounds: Recall that pl and Pj. Vj * are integer multiple of
(c)
Then, given the probability lower and upper bounds in Equation 3 we have the following:
Pr
Pr(J(U) = 1).3/ A P3
P1
Pr(j(U)= = -j.
(19)
14

---

Published as a conference paper at ICLR 2022
Deriving lower bound of Pr(f(V) l): We will derive lower bound of the probability
Pr(f(V) = 1). For simplicity, we define the following regions:
A = {s S|s 3 x, A x 5), {s E S|s A x, 1 x 6), {s E S|s 3 x, s 3 x + d}.
(20)
where we say s 3 x if (r(h(x, e)= s) O, and we say s A if Pr(h(xx, e) = 0. Intuitively, the notations I and A mean that an ablated input can or cannot be derived from an input, respectively, For instance, region contains ablated inputs that can be derived from x but cannot be derived from x + 5, region B contains ablated inputs that can be derived from x + 5 but cannot be derived from x, and region C contains ablated inputs that can be derived from both x and + Suppose we have r ||ō]|o- Then, the size of would be (d-"" since - r features are the same for x and 6. Similarly, we know the size of A and B would be (a) ("="). Since we keep features randomly sampled from x or + å without replacement and set the remaining features to a special value, we have the following probability mass functions:
if AUC
Pr(U =)
(21)
otherwise.
i
Pr(V =) =
(22)
0,
otherwise.
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 PC) = (027)
(2-7)
Pr(U EA)= =1
Pr(U EB) =0
(23)
(a-7)
(d-)
Pr(V E C)
Pr(V B) =
Pr(V E A) 0.
(24)
We consider the case of pl 24214
Note that we can do this because we aim to find a sufficient
condition. We let A' C C such that it satisfies the following:
Pr(U A') pi Pr(U A).
(25)
Given region A', we construct the following region: m A' A
(26)
Then, we have the following probability based on Equation 25
Pr(U E E) = Pr(U e A) + Pr(U E A') = -
(27)
We define binary function F(s) [[f((s) = 1). Then, have the following:
Pt(F(U)= = 1) = Pr(f
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 E A, and Pr(U s) 1-Pr(V it's E A'. Therefore, we can apply Lemma and we have the following:
Pr(F(V) 1) Pr(S(V) = 1) 2 Pr(V E).
(29)
Therefore, we have the following lower bound for Pr(j(V)= = l):
Pr(V E
(30)
=Pr(V A') + PP(V E A)
(31)
=Pr(V A')
(32)
=Pr(U A')
(33)
15

---

Published as a conference paper at ICLR 2022
p1
(34)
Note that we have Equation 34 from
33 based on Equation 25
Deriving an upper bound of maxr, cr maa.xccr.minnerrr Pr(s(V) = j): We use A to denote an arbitrary subset of Tx, i.e., A S T'- We denote F/A = _jen jEA Fj, which is the sum of the upper bound of the probability for the labels in A. We assume FAA S Pr(U' E C). We can make this assumption because we aim to find sufficient condition. Given PA we can find region HA S C such that we have the following:
PA Pr(U E HA).
(35)
Given the region HA. we construct the following region:
IA = HA U BB.
(36)
Then, have the following probability:
Pr(U E IA) = Pr(U E H.) + Pr(U E B) = -
(37)
Furthermore, for any given A, we define a binary function G((s) = I(f(s) A). Then, we have the following:
Pr(G(U) = 1) P A) Σ Pr(f(U) - S Pr(U IA).
(38)
JEA
We have Σ jea Pr(f(U)= j) S PAA based on Equation
19 and we have rightmost equality from Equation 37 Then, we can apply Lemma D and we have the following:
Pr(G(V) 1) S Pr(V IA).
(39)
The value of Pr(V E IA) can be computed as follows:
Pr(V E IA)
(40)
=Pr(V E HA) Pr(V B)
(41)
(d-T)
=Pr(U E HA)+ + (1
(42)
-
(43)
where the last equality is from Equation
35
Therefore, we have the following:
Σ Cr(((V)=))
(44)
JEA
Pr(J(V) EA)
(45)
Pr(G(V) 1)
(46)
<Pr(V EIA)
(47)
d-r) (d)
=P (1
(48)
Moreover, we have the following:
min Pr(s(V) = < min Pr((V) j] EjEn Pr(s(V)= = Pr(S(V) E A) JET
(49)
JEA
A
JA
We have the leftmost inequality because C Tk. and have the middle inequality because the smallest value in a set is no larger than the average value of the set. Taking all possible A into consideration and we have the following:
min Pr(f(V) = jj jET,
(50)
16

---

Published as a conference paper at ICLR 2022
Pr([(V) EA)
min AST
(51)
[A
& min
Pr(S(V) EA)
min [-1 AgTiJJA =t
(52)
A
A
Pr(f(V) E TT)
min
(53)
Pr. (1
min
(54)
where T, is the set of t labels in F' whose probability upper bounds the smallest, where ties are broken uniformly at random. The upper bound of Pr(j(V) E Y,) is increasing as pr, increases.
Therefore, the upper bound of P(((V))))) reaches the maximum value when Hs = {a, 02 ag } i.e., F3 is the set of labels in I with the largest probability upper bounds. In other words, we have the following:
Pr. + (1
max min Pr(S(V) = S min JET'
(55)
==1
t
where T, = (a1, 02," ,.)-
Deriving the certified radius: Our goal is to make Pr(f(V) = 1) > max minzer, Pr(f(V)- = j). Therefore, is sufficient to satisfy the following:
PT, + (1
p
(56)
where Y, {aı, ... ae). condition. Formally, we can solve the following optimization problem to find rı:
Therefore, find the maximum that satisfies the above
r arg max
(57)
Fr. + (1 min
s.t. pi- - (1 (
(58)
t
where T, {aı, .2, ,.... Note that make two assumptions in derivation, i.e., p/ 2 (1
and pr. S In particular, when Equation (58) is satisfied, we must have p/¹ 2 (1 (:)
since the left-hand side of Equation (58) is non-negative. In addition, we have pl + Fr. S 1 in
practice. Therefore, we have Fr, <
pl
Technical differences with Jia et al. (020):: Our technical contribution in proving the theorem is the construction of new discrete regions such that the Keyman-Pearsen Lemma can be used. Our proof of Theorem has the following differences with Jia et al. First, the construct of the regions A/B/C (Eq 18) are different from Jia al. due the discrete space. Second, deriving the lower bound of PV( = () faces two new challenges in our case. The first challenge is that we need to find two regions AA and .'' while Jia et 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 .'' 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) = I), our work is also different from Jia et al. at deriving the upper bound of maxr.er er minjer. Pr(f(V) z).
B PROOF OF THEOREM 2
We consider two scenarios: 1 and * 1. In particular, we first consider the scenario where k 1. We have I (a1) when h: 1. We consider two cases.
17

---

Published as a conference paper at ICLR 2022
(
Case I: In this case, consider piz < (1 following:
We let A S A be the region that satisfies the
M = Pr(U Ar).
(59)
We let D: Ar and we have the We can find such region because of an integer multiple of (c) following:
/ Pr(U E Di), Pr(V E Di) = 0.
(60)
Then, can divide the remaining region (AUC) \ Dj into 1 disjoint regions such that we have the following:
Vj {1.2, .c) Pr(U sy.
(61)
We can find these regions because we have pi + E. Ps 2 Moreover, we have the following:
Vj E (1,2. , Pr(V E D2) 20 O.
(62)
Given these regions, we construct the following base classifier:
(z) = j. if z E Dj-
(63)
Note that f" is well defined and is consistent with Equation (3) It easy see that label is not the predicted label by the corresponding smoothed classifier 9 when ||0llo >
Case II: In this case, we consider p 2 (1
Since ri is the maximum value that satisfies
Equation (6) we have the following condition when |611o ri + 1:
d (c)
pi
Pa, pa, +
(64)
We let A: = A and we can find Ci E C. such that the following equation holds:
(d
Pr(U Ci) = pi
(65)
Then, we let Dj = Ct U Ar and we have the following:
Pr(U Di) pi-
(66)
Furthermore, we have the following:
Pr(V D:)
(67)
=Pr(V Gi) + Pr(V e Ai)
(68)
-Pr(U E +C)+0 +0
(69)
dd d-
-pi (1
(70)
where the last equality is from Equation 65
Since we have p\ Pa, I 1, we can find region
Ca, E C. ) Ci such that have the following:
Pr(U E C.,) - =
(71)
We define Da, = Ca, U.. Then, we have Pr(U E Day)) = Pr(U E Ca,) = =Ya,- Similarly, we have the following:
Pr(V E Do.)
(72)
=Pr(V E C..)
+ Pr(V B)
(73)
(d---1)
-Fey + (1
(74)
18

---

Published as a conference paper at ICLR 2022
Finally, we can divide the remaining region AUC) (Di Cor) into 2 disjoint regions such that we have the following:
Vj E (1,2,-.., ,c) U (m1)), c S 1/4-
(75)
We can find these region because p/- - E P' 2 1. Given these regions, we construct the following base classifier:
(x) j, if
(76)
Note that f is well defined and consistent with Equation 3 Next, we show that label is not in the top-1 predicted labels by the smoothed classifier or there exist ties when the Eo perturbation is larger than ry. In particular, we have the following:
(v( =a 1101o r
(77)
-Pr(V Daj 11011o > r
(78)
ri-
FVa
(79)
(d-r-1)
2/1 (1
(80)
PP Di > rt)
(81)
(V)(f = 1lóllo n)).
(82)
We have Equation (80) from 79) based on Equation (64).
Therefore, the label / 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 almost tight when * 1. In particular, we will show we can construct classifier f such that the label is not among the top-k predicted labels there exist ties when the adversarial perturbation is larger than Fi + 1. Similarly, we consider two cases.
Case I: In this case, we consider p/ < <1 following:
We let A S A be the region that satisfies the
y Pr(U E At).
(83)
We can find such region because pf is an integer multiply of = We let Dj = Ai and we have the following:
p Pr(U E Di), E Dt) 0.
(84)
Then, can divide the remaining region (AUC) Di into 1 disjoint regions such that we have the following:
Vj E f1,2,... ,ct (1), Pr(U E (D) s/
(85)
We can find these regions because we have p/1 + Σ 411 F. 2 1. Moreover, we have the following:
Vj E (1,2. .c] c} Given these regions, construct the following base classifier:
Pr(V E D2) 2 0.
(86)
fz) = j, if E Dj.
(87)
Note that f is well defined and is consistent with Equation 33. It is easy to see that label | is not among the top-k predicted labels or there exist ties when |lóllo 11
Case II In this case, we consider p 2 (1 quantity:
For simplicity, we denote the following
1
(88)
19

---

Published as a conference paper at ICLR 2022
Since is the maximum value that satisfies Equation (6) we have the following condition:
(d-ri-))
Fr. (1
pi (1
min
(89)
In other words, the left-hand side of Equation 6 is no larger than its right-hand side when r = -+++ Based on the recurrence relation of the binomial coefficient, we have the following:
= (
d ri 11-1--2 e
d r 2)
(90)
6
e
Combining with the condition
(C---2) 2 1, we have the following:
pi - (1
(91)
d
-V- (1
(92)
dd e-1
dd
-
(93)
d
1-r--2
2p + v (1
(94)
Similarly, we have the following:
dd-r-11
Fr. + (1
min
(95)
Pr. (d-re-)) 2)
(1
min
(96)
t
(d-12-
Pr. v + (1
min
(97)
Then, based on Equation
89
we have the following:
( n
dd-r:-
p'r. + (1
(c)
p + (1
< min
(98)
1
(d-1-2))
Dr. - v-t-v + (1
p (1 < min
(99)
t
dd (d-r
dd 2
T'. -. (1
pp| (1
min
(100)
For simplicity, we denote the following:
(d-r
PT. - -t. + (1
w- arg min
(101)
t
where ties are broken uniformly at random. Then, based on Equation 100). we have the following:
11-1-2 2 d
Pru..
+ (1
F/1 - (1
(102)
20

---

Published as a conference paper at ICLR 2022
Given Equation (101). we have the following if w k:
(- 2)
Twu (w + 1) v + (1
pTr w v + (1
(103)
w +1 1 (--(-2)
(4-1--
+ (1
Pr. + (1
(*)
(104)
w + 1
dd-r
p'r, + (1
DTo11 + +(1
(w + 1).
(105)
w
Drr + (1
P -Prr 2
(106)
PT. + (1 (d-re
Towss
(107)
w
where Tw {{a,, 02,,00...... .w... Similarly, we have the following if w >>
dd-r
Dr. 1 - (w - 1) v +
Pr. - wv + (1
(108)
W-
w
TT x-1 + +(1 4-1
(d-1-2 (:)
Pr (1
(109)
w
w
dd-1-2
PrT + (1
>T + +(1
2 (w- 1)
(110)
W
(d-
Pr. (1
(111)
w
1111) also holds when w = 1. Next, we will show we can build a base classifier f such that the label is not in the top-k predicted labels or there exist ties when the adversarial perturbation is larger than + 1. Our proof relies on constructing disjoint regions for label I, T.. and {1, .............................. .c} \ (1I U TR), respectively.
Note that the Equation
We let A = A and we can find C E C such that the following equation holds:
dd-ri-
Pr(U E C₁) pl (1
(112)
Then, we let Dj Ct U. Ar and we have the following:
Pr(U E Di) =
(113)
Furthermore, we have the following:
Pr(V E Di)
(114)
-Pr(V G) + Pr(V E Ad)
(115)
-Pr(U CG)+ +0
(116)
d- r
- (1
(117)
where the last equality is from Equation
112 For simplicity, we denote the following value:
F/r + (1
(118)
w
21

---

Published as a conference paper at ICLR 2022
Next, we will construct the region for Vj Y Based Equation 112
we have the following:
Pr(U E C (()
(119)
=Pr(U C) Pr(U E ECi)
(120)
(
(d-12-2
= (1
- (p/ - (1
(121)
(122)
For vj E Tw, we can find disjoint region C₁ _ Ci such that we have the following:
Pr(U E Cj) p'--
(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 C₁ i.c., we have the following:
Σv.- S pi Pr(U EC
(124)
JET
where the middle inequality is from the condition pi + ExEr, P/ and the right equality is based (122). Given these regions, we have the following:
on Equation (119)-
Vj T Pr(V EC, P..
(125)
Based on Equation following:
111 definition of r in Equation (18). and Vj Yw. P/j S Pan,, we have the
Vj T Tw., D, S P.... ST. Then, for Vjj E Tw. we can find disjoint region Bj E B such that we have the following:
(126)
F,J S Pr(V E B,) ST F...
(127)
We construct these regions for three reasons: 1) the value of r p/J is no smaller than 0 based on Equation 126). 2) Vij Yw., there exists number in the range [r plj, T p`] that is integer
multiple ( and 3) the summation of the probability of V these regions no larger than the probability of V B, i.c., we have the following:
Σ Pr(V E Bj)
(128)
JET
Σ (T-P/)
(129)
JET
d-r1-2
-Tr +
PT.
(130)
<1 (d (d-r(-
(131)
Pr B).
(132)
For Vjj E Tw. we let De C, U B.. Then, we have the following:
Pr(V E D2) =Pr(V E C,)++ e BJ)
(133)
(134)
2F' + ------- - P
(135)
(136)
where the Equation (35) from 134 is based on Equation 123 and (27). Next, we will construct
the regions for the labels in Y w. In particular, for Vj (w+t1,a0t2." ax), we can find
disjoint region D, E (C, (U.er... C.)) such that we have the following:
Pr(U E D,) = p/J
(137)
22

---

Published as a conference paper at ICLR 2022
Note that we can find these regions because p + Eeer, P. < 1. Similarly, have the following for jj E Yx Yw
Pr(V E D2) - TT.
(138)
We have the left inequality because Vj E T. \ Tw. / based on Equation 107 Finally, we can
divide the remaining region D, SCU A \ (Di J (,)ET,C,)) into k disjoint regions such that we have the following:
Vj (1,2,-., ,c] ((1) U UT), E D2) s s/j-
(139)
We can find these region because pl base classifier:
E.ft Ps 2 1. Given these regions, we construct the following
((z)= - j, i
(140)
Note that f is well defined and consistent with Equation ( Next, we show that label is not in
the top-k predicted labels by the smoothed classifier when the perturbation is larger than ry 1. In particular, for Vij E Yx, we have the following:
Pr(f" (V) = 1811 > m 1)
(141)
=Pr(V E DjI |661
> Ti + 1)
(142)
(143)
Prr + (1
(144)
>pi (1 (d-r-2)
(145)
Pr(V Dil 11ō10o ri 1)
(146)
Pr(S" (V) = /| |666| > ri + 1).
(147)
We have Equation (145) from 144 based on Equation [02 Therefore, the label / 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 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 prove that the certified robustness guarantee 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 normr certified robustness guarantee.
C OTHER APPLICATIONS
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 experi- ments for 3D deep learning. 2015) benchmark dataset and use PointNet (Qi al.) (017) the base classifier. We set n = 10, 000, and a 0.001. When the number of modified points is 10, 20, 30, 40, and 50, the certified accuracies for top-1 prediction 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.
particular, we evaluate our methods on the ModelNet40 (Wu et al.)
16.
D COMPARING WITH CHIANG ET AL. (0200)
We also compare with our method with Chiang et al. (020). 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 method are respectively 0. 0.746,
23

---

Published as a conference paper at ICLR 2022
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. (020). We note that certified robustness guarantee is probabilistic while Chiang et al. (2020) can give a deterministic certified robustness guarantee.
24


Reviews:
[{"review_id": "fBbJX96YgBv", "reviewer": "Reviewer_NNyi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strength]\n1.\tThe writing is concise and easy to understand in general.\n2.\tThe paper makes nontrivial theoretical progress. Also, the authors provided enough explanation about how this progress can be distinguished from other existing works, so the contribution looks to be unique.\n\n[Weakness]\n1.\tI don’t see any severe weakness (to reject this paper) in this work.\n\n[Comments]\n1.\tI enjoyed reading this paper, and I think that the approach is “kind of good”. For the following reasons, I’d not put a score of 8 for this paper.\nA.\tThe suggested proof approach is not easily generalizable, so it would be hard to say that this is a major discovery in the theory of certified robustness. (If possible, some discussion on the possible uses of the proof strategy would make the paper better.)\nB.\tI might have missed some potential weaknesses that I should have found. For this comment, I want to discuss with other reviewers during the review process.\n2.\tI can understand how the authors compared their method ($\\ell_0$-certified robustness) to existing counterparts (some of them are $\\ell_2$-certified robustness) and I can see there are not that many possible ways to compare them. However, I’m still not convinced whether it is a fair comparison or not, and I’m not even sure whether we can directly compare those methods or not. Also, in my personal opinion, there could be better experiment questions than just showing “our method is excelling other methods”.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "I vote for accepting. First, the paper proved a nontrivial result about the certified robustness of top-$k$ predictions. Also, the paper provided enough justifications for its unique contribution to the defenses using randomized smoothing & randomized ablation type, so I believe this paper can be distinguished from other existing works. While I believe that the work itself is publishable, I’m a little bit reluctant to give a score of 8 for this paper yet due to the reasons I provided in Comments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CXFL1fzyx-Z", "reviewer": "Reviewer_PF8K", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In total, this is a good work both in the theoretical perspective and the experimental perspective. The authors provide a solid proof on the l0-norm certified robustness guarantee for top-k predictions, which is different from previous works of Levine & Feizi (2019) and Jia et al. (2020). The detailed experiments show its consistent improvement in certified top-k accuracy on CIFAR-10 and ImageNet and the ablation study provides a view on how these hyperparameters affect the performance.", "summary_of_the_paper": "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.", "summary_of_the_review": "The author derives an almost tight l0-norm certified robustness guarantee of top-k predictions against adversarial perturbations for randomized ablation. The corresponding theoretical analysis show both the l0-norm certified radius and the tightness. The empirical results demonstrate that the l0-norm certified robustness is substantially better than those transformed from l2-norm certified robustness. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BC9jBU58tJL", "reviewer": "Reviewer_AjCc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There are several key pros of the paper that contribute to my favorable opinion. In particular, the authors do a good job of highlighting recent and related works and ensuring that readers understand the contribution they are making relative to those works that it builds on. Further, the advances that the authors suggest in terms of improving tightness are stated in an intuitive way which allows for greater appreciation of the relatively simple modification they make. Finally, I think the introduction of top $k$ predictions rather than top 1 prediction is an interesting contribution which extends the applicability of randomized ablation (i.e. $\\ell_0$ smoothing). \n\nThe primary cons of this paper are in its potentially incremental impact. I think the clear exposition of prior works may make this paper's contributions seem simple or incremental, but I think ultimately that these are important developments/extensions of prior work that constitutes a strong enough contribution for acceptance. \n\nThe second primary con (and perhaps the more noteworthy one) is the applications that this method is tested on. It is rare for the $\\ell_0$ metric to be tested on images in practice. However, for graph neural networks and 3D deep learning this is a primary threat model. I think it would greatly strengthen the paper if such networks were certified and would add yet another point of contribution for this paper. \n\n\n", "summary_of_the_paper": "In this paper the authors extend the tightness guarantees of other works on randomized smoothing to the $\\ell_0$ case and also tighten the guarantees given by previous works by noting the discrete nature of the predictive distribution induced by randomized ablation. In addition, they extend previous $\\ell_0$ methods to certify top $k$  predictions rather than just top $1$ predictions which is typically the case for smoothing. ", "summary_of_the_review": "Though one might see the contributions of this paper as incremental over other works in smoothing, I think these are valuable and important developments in the field of smoothing which can enable further applications to gain guarantees via smoothing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2Cvoc523ZPt", "reviewer": "Reviewer_5Exk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I appreciate the theoretical analysis and the impressive empirical results in the paper. \nConcerns and questions:\n* The \"Deriving the certified radius for the smoothed classifier\" sections is rather difficult to understand. I recommend the authors to reorganize this section and define the notations separately in a clearer way.\n* The paper states that for $k=1$ the certified radius is tight. But this statement is only true if there is no assumption on the base classifier is made, and this is not true for a given base classifier, therefore this statement may be overclaimed.\n* In Table 1&2, the comparisons of Top-1 prediction for 'Our methods' are missing.\n* I recommend the author to compare with another L0 verification methods like https://openreview.net/pdf?id=HyeaSkrYPH. ", "summary_of_the_paper": "The paper proposed a tighter L0 verification method for Top-K predictions of classifiers based on randomized smoothing.", "summary_of_the_review": "I appreciate the theoretical analysis and the impressive empirical results in the paper but the written is not clear. I also have some questions on the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission to ICLR.  The reviewers ultimately have mixed opinions on this paper, but reading in a bit more depth I don't feel that the critical comments raised by the sole negative reviewer really raise valid points.  Specifically, the fact that this reviewer directly asks e.g. for comparisons to Levine and Feiz 2019, when the paper (before its revisions) contains an entire section devoted to exactly this comparison, strikes me as not sufficient for a thorough review.

However, while I'm thus going to recommend the paper for acceptance (it does present a notable, if somewhat minor, advance upon the state of the art in randomized smoothing), I also feel the paper is generally rather borderline for more straightforward reasons.  Specifically, given the _very_ narrow focus of the proposed improvements (improvements to the bounds of randomized smoothing, for L0 perturbations, for Top-k accuracy), I ultimately don't think the paper presents that significant an advance in the field.  The paper could go other way, thought definitely not doing so due to the issues that the sole critical reviewer takes.
Decision: Accept (Poster)