Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
Authors: Jinyuan Jia
Xiaoyu Cao
Binghui Wang
Neil Zhenqiang Gong
Venue:  (2020)
Keywords: Certified Adversarial Robustness
Randomized Smoothing
Adversarial Examples

Abstract: It is well-known that  classifiers are vulnerable to adversarial perturbations. To defend against adversarial perturbations, various certified robustness results have been derived. However, existing certified robustnesses are limited to top-1 predictions. In many real-world applications, top-$k$ predictions are more relevant. In this work, we aim to derive certified robustness for top-$k$ predictions. In particular, our certified robustness is based on randomized smoothing, which turns any classifier to a new classifier via adding noise to an input example. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any classifier. We derive a tight robustness in $\ell_2$ norm for top-$k$ predictions  when using randomized smoothing with Gaussian noise. We find that generalizing the certified robustness  from top-1 to top-$k$ predictions faces significant technical challenges. We also empirically evaluate our method on CIFAR10 and ImageNet. For example, our method can obtain an ImageNet classifier with a certified top-5 accuracy of 62.8\% when the $\ell_2$-norms of the adversarial perturbations are less than 0.5 (=127/255). Our code is publicly available at: \url{https://github.com/jjy1994/Certify_Topk}. 

Published as a conference paper at ICLR 2020
CERTIFIED ROBUSTNESS FOR TOP-k PREDICTIONS AGAINST ADVERSARIAL PERTURBATIONS VIA RAN- DOMIZED SMOOTHING
Jinyuan Jia, Xiaoyu Cao, Binghui Wang, Neil Zhenqiang Gong
Duke University
(jinyuan. jia, xiaoyu.. cao, binghui. .wang, neil g.o.gggouoo..eee.....
ABSTRACT
It is well-known that classifiers are vulnerable to adversarial perturbations. To defend against adversarial perturbations, various certified robustness results have been derived. However, existing certified robustnesses are limited to top- pre- dictions. In many real-world applications, top-k predictions are more relevant. In this work, we aim to derive certified robustness for top-k predictions, In par- ticular, our certified robustness is based on randomized smoothing, which turns any classifier to a new classifier via adding noise to an input example. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any classifier. We derive tight robustness in l norm for top- k predictions when using randomized smoothing with Gaussian noise. We find that generalizing the certified robustness from top-1 to top-k predictions faces significant technical challenges. We also empirically evaluate our method on CI- FARIO and ImageNet. For example, our method can obtain ImageNet classi- fier with a certified top-5 accuracy of 62.8% when the f2-norms of the adversar- ial perturbations are less than 0.5 (=127/255). Our code is publicly available at: https: / / thub. com/ jjyl/jjyll 994 /tt.e/yyyyy//eetityyyyoooooyo Topk.
INTRODUCTION
Classifiers are vulnerable to adversarial perturbations (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini Wagner, 2017b; Jia & Gong, 2018). Specifically, given an example and classifier f. an attacker can carefully craft perturbation 8 such that f makes predictions for x + 8 as the attacker desires. Various empirical defenses (e.g.. Goodfellow et al. (2015); Svoboda et (2019): Buckman et al. (2018); Ma et al. (2018); Guo et al. (2018); Dhillon et al. (201 8); Xie et al. (2018); Song et al. (2018)) have been proposed to defend against adversarial perturbations. However, these empirical defenses were often soon broken by adaptive adversaries (Carlini & Wagner, 2017a; Athalye al., 2018). As a response, certified robustness (c.g.. Wong & Kolter (2018); Raghunathan et al. (2018a); Liu et al. (2018); Lecuyer al. (2019); Cohen et al. (2019)) against adversarial perturbations has been developed. In particular, a robust classifier verifiably predicts the same top-1 label for data points in a certain region around any example x.
In many applications such as recommender systems, web search, and image classification cloud ser- vice (Clarifai; Google Cloud Vision), top-k predictions are more relevant. In particular, given an example, a set of k most likely labels are predicted for the example. However, existing certified robustness results are limited top-1 predictions, leaving top-k robustness unexplored. To bridge this gap, we study certified robustness for top-k predictions in this work. Our certified top-k ro- bustness leverages randomized smoothing (Cao & Gong, 2017: Cohen al., 2019), which turns any base classifier ff to be robust classifier via adding random noise to example. For instance, Cao & Gong (2017) is the first to propose randomized smoothing with uniform noise as an empirical defense. We consider random Gaussian noise because of its certified robustness guarantee (Cohen et al., 2019). Specifically, we denote by P; the probability that the base classifier I predicts label i for the Gaussian random variable N I). The smoothed classifier Is (x) predicts the lo labels with the largest probabilities p, 's for the example x. We adopt randomized smoothing because is scalable to large-scale neural networks and applicable to any base classifier.

---

Published as a conference paper at ICLR 2020
Our major theoretical result is tight certified robustness bound for top-k predictions when using randomized smoothing with Gaussian noise. Specifically, given an example x, a label I is verifiably among the top-k labels predicted by the smoothed classifier gk gx + 6) when the norm of the ad- versarial perturbation is less than a threshold (called certified radius). The certified radius for top-1 predictions derived by Cohen et al. (2019) is a special case of certified radius when k 1. As our results and proofs show, generalizing certified robustness from top-1 to top-k predictions faces significant new challenges and requires new techniques. Our certified radius the unique solution to an equation, which depends on Pt, and the & largest probabilities, pi 's (excluding pt). However, computing our certified radius in practice faces two challenges: 1) hard exactly compute the probability pr and the & largest probabilities pi ss and 2) the equation about the certified radius does not have an analytical solution. To address the first challenge, we estimate simultaneus confidence intervals of the label probabilities via the Clopper-Pearson method and Bonferroni correction in statistics. To address the second challenge, we propose an algorithm to solve the equation to obtain a lower bound of the certified radius, where the lower bound can be tuned to be arbitrarily close to the true certified radius. We evaluate our method on CIFAR1O (Krizhevsky & Hinton, 2009) and ImageNet (Deng al., 2009) datasets. For instance, ImageNet, our method respectively achieves approximate certified top-1, top-3, and top-5 accuracies as 46.6%, 57.8%, and 62.8% when the normms of the adversarial perturbations are less than 0.5 (127/255) and a 0.5.
Our contributions are summarized as follows:
Theory. We derive the first certified radius for top-k predictions. Moreover, prove certified radius is tight for randomized smoothing with Gaussian noise. Algorithm. We develop algorithms to estimate our certified radius in practice. Evaluation. We empirically evaluate our method on CIFARIO and ImageNet.
2 CERTIFIED RADIUS FOR TOP-k PREDICTIONS
Suppose we have a base classifier f. which maps an example x E E to one of e candidate labels 21. .c-- f can be any classifier. Randomized smoothing (Cohen et al., 2019) adds an isotropic Gaussian noise N[0, o²T) I) to an example x. We denote p; as the probability that the base classifier predicts label when adding a random isotropic Gaussian noise the example x, i.e., Ps Pr([(x +)) = i). where
Ni0,, o²),,²1)) The smoothed classifier ga (x) returns the set of k labels with the largest probabilities p when taking an example as input. Our goal is to derive a certified radius Ri such that we have I E gx + 5) for all |ol|e < Rj. Our main theoretical results are summarized in the following two theorems.
Theorem (Certified Radius for Top-k Predictions). Suppose we are given example x, arbi- trary base classifier J. é ~ N (O, QT)), a smoothed classifier g, an arbitrary label I E (1,2, ... c). and pt, Py.
P1-1.P4411 - Pe E [0, 1] that satisfy the following conditions:
Pr(f(x + é) = 1) 2 Pt and Pr(f(x + = Sp.
(I)
Po, be the k largest ones among {P..... 1. P.. .P... where ties are broken uniformly at random. Moreover, we denote by S. = {br, b2. bt) the set of labels with the smallest probability upper
where p and p indicate lower and upper bounds of p. respectively. Let Po. 2 2
bounds in the k largest ones and by Ps. Σim Do, the sum of the t probability upper bounds, where 1. 1,2,... k.. Then, we have:
LE gx(x 8), V|11|2 < Rs.
where R₁ is the unique solution to the following equation:
R1) ) - - (ps,) 11)
( (p:
(3)
where to and - are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively.
Proof. See Appendix A.
2

---

Published as a conference paper at ICLR 2020
Algorithm 1: PREDICT
Input: k, o, x, n, and
Output: ABSTAIN predicted top-k labels.
=
x, C2,02, ... c++1 = top-(k + 1 indices in counts (ties are broken uniformly at random) Mei :'..".. Mex++1 = counts(ca], counts[e2], , counts[ex++]
counts = SAMPLEUNDER
for 1. 4- 1 to k do
BINOMPVALUE((E) noe + nec1 0.5) S a then
== T=TUc
else
return ABSTAIN
return T
Theorem 2 (Tightness of the Certified Radius). Assuming we have pt + EE=,Po, 1 and + Eis,..
J-1,++,,.. -- e 2 1. Then, for any perturbation ||0||2 > Rí, there exists base classifier f consistent with (1) but we have I & gk(x (x++x) 6).
Proof. We show proof sketch here. Our detailed proof is in Appendix B. In our proof, we first show that, via mathematical induction and the intermediate value theorem, we can construct k disjoint regions C, i {L} U b,,,,,,. b2. 6b} that satisfy Pr(x + E Ci) Pt. Pr(x + C,) = and Pr(x + 5 + C,) is no smaller than some critical value for i E {bz, b2 b Moreover, we divide the remaining region I2 (Uj by. C,) into c k
regions, which we denote as Ca 2 ,Ch. and satisfy Pr(x + C.) P: for i = b 2 .b-1- Then, construct a base classifier f* that predicts label for an example if and only if the example is the region C, where E 21,2, ... .c. As Pt + Σ Pb; S and pt + Ei=t... 1-...-11441 1. .................. Fb 2 1, f" is well-defined. Moreover, f satisfies the conditions in (1). Finally, we show that if ||0||2 > Rd, then we have (r(f"(x 8 + c) = 1) < min
شj=1
(x c) = by), i.e., I 9h 9x(x 6). Li
We have several observations about our theorems.
Our certified radius is applicable to any base classifier f.
According to Equation our certified radius Rú depends on a, Pt, and the largest prob- ability upper bounds (Fr,, P ... .b,,} excluding Pt- When the lower bound Pt and the upper bounds (Pr,, Pb.-1.
Pb, are tighter, the certified radius R₃ is larger. When Rí < 0, the label is not among the top-k labels predicted by the smoothed classifier even if no perturbation is added, i.c.. & gx)...
When using randomized smoothing with Gaussian noise and no further assumptions are made on the base classifier, it is impossible to certify a la radius for top-k predictions that is larger than Ri.
When à 1, we have R: = -0-=--$-110 (Φ- - Φ
(pr, )), where Pb, is upper bound of the largest label probability excluding Pt. The certified radius derived by Cohen al. (2019) for top-1 predictions (i.e., their Equation 3) is special case of our certified radius with k A. and b
3 PREDICTION AND CERTIFICATION IN PRACTICE
3.1 PREDICTION
challenging to compute the top-k labels (x) predicted by the smoothed classifier, because it is challenging to compute the probabilities p; exactly. To address the challenge, resort to a Monte Carlo method that predicts the top-k labels with probabilistic guarantee. In particular, leverage the hypothesis testing result from recent work (Hung al., 2019). Algorithm
3

---

Published as a conference paper at ICLR 2020
shows PREDICT function to estimate the top-k labels predicted by the smoothed classifier. The function SAMPLEUNDERNOISEE// o, x, n) first randomly samples n noise é1, C2. ..... Cn from the Gaussian distribution N I)), uses the base classifier to predict the label of x + e for each EE 11. n), and returns the frequency of each label, i.e., counts = شÿ= [([(x + 65) = i) for i E 21, ... et. The function BINOMPVALUE performs the hypothesis testing to calibrate the abstention threshold such that we can bound with probability a of returning an incorrect set of top-k labels. Formally, we have the following proposition:
Proposition 1. With probability at least 1 a over the randomness in PREDICT, if PREDICT returns a set T (i.e., does not ABSTAIN), then we have g T.
Proof. See Appendix C.
3.2 CERTIFICATION
Given a base classifier f. an example x, label and the standard deviation of the Gaussian noise, we aim to compute the certified radius Rs. According to our Equation 3, our R relies on a lower bound of pt. i.e., Pt, and the upper bound of ps.. i.e., Ps., which are related to f. x, and a. We first discuss two Monte Carlo methods to estimate pt and Ps, with probabilistic guarantees. However, given pt and Ps. it is still challenging to exactly solve RS as the Equation 3 does not have an analytical solution. To address the challenge, we design an algorithm to obtain lower bound of R via solving Equation 3 through binary search. Our lower bound can be tuned to be arbitrarily
close to Ri.
3.2.1 ESTIMATING PL AND Ps.
Our approach has two steps. The first step is to estimate pl and p, for i + I. The second step is to estimate Ps, using P, for * I.
Estimating pl and p. for # 1: The probabilities P2. Pe can be viewed as a multinomial distribution over the labels 21, ... If sample Gaussian noise uniformly random, then the label f(x + <) can be viewed as a sample from the multinomial distribution. Therefore, estimating Pt and P. for + l essentially a one-sided simultaneous confidence interval estimation problem. In particular, we aim to estimate these bounds with a confidence level at least a. In statistics, Goodman (1965); Sison & Glaz (1995) are well-known methods for simultaneous confi- dence interval estimations. However, these methods are insufficient for our problem. Specifically, Goodman's 's method based on Chi-square test, which requires the expected count for each label to be no less than 5. We found that this is usually not satisfied, e.g., ImageNet has 1,000 labels, some of which have close-to-zero probabilities and do not have more than counts even if we sample large number of Gaussian noise. Sison & Glaz's method guarantees a confidence level of approximately a, which means that the confidence level could be (slightly) smaller than - a. However, we aim to achieve confidence level of at least 1 a. To address these challenges, we discuss two confidence interval estimation methods as follows:
1) BinoCP. This method estimates Pt using the standard one-sided Clopper-Pearson method and treats P. as P. = 1 Pt for each i 7 L. Specifically,, we sample n random noise from (0, al²), i.e. 62, ... 6n. We denote the count for the label 1 as ni = E T[J(x + ez) = l). my follows a binomial distribution with parameters n and pt, ie., ny ~ Bin(n, pi). Therefore, according to the Clopper-Pearson Pearsson method, we have:
Pt B(a; T4 1),
(4)
where 1- a is the confidence level and B(a; u, v) the ath quantile of the Beta distribution with shape parameters u and v. We note that the Clopper-Pearson method was also adopted by Cohen et al. (2019) to estimate label probability for their certified radius of top-1 predictions.
2) SimuEM. The above method estimates F3 as 1 Pt. which may be conservative. A conserva- tive estimation makes the certified radius smaller than what it should be. Therefore, we introduce SimuEM to directly estimate D; together with pl. We let n; = -)=1 + e,) = i) for each
i E (1,2, .c.. Each n, follows binomial distribution with parameters and pt. We first use
4

---

Published as a conference paper at ICLR 2020
Algorithm 2: CERTIFY
Input: f, k, G, x, I, n, μ4, and a.
Output: ABSTAIN or Ri.
counts = SSMMPLUNDERNOISSI,.... x,
[pt. PP.PP...... PPt-1,Pt41:" .Pal BINoCP(counts, a) or SIMuEM(counts, a)
R1
for f- to k: do
Ps: = min(E; j=1 Pb.: 1o p-)
R -BINARYSEARCH Pt. Ps. ,
if T / Rg then
R₁ R Ri then
return R
11
else
12
return ABSTAIN
the Clopper-Pearsen method to estimate one-sided confidence interval for each label i, and then we obtain simultaneous confidence intervals by leveraging the Bonferroni correction. Specifically, if we can obtain confidence interval with confidence level at least _ for each label i, then Bon- ferroni correction tells us that the overall confidence level for the simultancous confidence intervals at least 1 a, i.c., have confidence level at least 1 that all confidence intervals hold at the same time. Formally, we have the following bounds by applying the Clopper-Pearte method with confidence level 1 to each label:
= B
T4 +1) ( -
a
(5)
= B(1 m + 1,n-n:)) Vi L
a
(6)
Estimating Ps.: One natural method to estimate Ps. = ビÿ= Pb. However, this bound may be loose. For example, when using BinoCP to estimate the probability bounds, we have Ps, t- (1 - (I) which may be bigger than 1. To address the challenge, from another perspective. Specifically, we have ps, < Lizi P; S pt. Therefore, we can use 1 pt as upper bound of ps,, i.e., Ps, = pr. Finally, we combine the above two estimations by taking the minimal one, i.e., Ds. min min(E,
derive another bound for Ps,
j=1 Poy pi).
3.2.2 ESTIMATING A LOWER BOUND OF THE CERTIFIED RADIUS R
It is challenging to compute the certified radius R; exactly because Equation 3 does not have an analytical solution. To address the challenge, we design method to estimate lower bound of R3 that can be tuned to be arbitrarily close to Rr. Specifically, we first approximately solve the following equation for each E {1,2, 2, kj:
R
② (Ps.) + m
Φ (p)
0.
We note that it is still diffficult to obtain analytical solution to Equation 7 when >> 1. However, we notice that the left-hand side has following properties: 1) it decreases as I? increases; 2) when Rj -c,, it is greater than 0; 3) when Ri + oo, it is smaller than 0. Therefore. there exists unique solution Ri to Equation 7. Moreover, we leverage binary search to find lower bound R that be arbitrarily close to the exact solution R;. In particular, run the binary search until the left-hand side of Equation 7 is non-negative and the width of the search interval less than a parameter p > Formally, we have:
R S < S + M, WE ...2....,4
(8)
5

---

Published as a conference paper at ICLR 2020
1.0
1,0
k=
centfed accanayy
k= 3
conteec accursyy
==5 5
redius
radius
(a) CIFARIO
(b) ImageNet
Figure 1: Impact of k on the certified top-k accuracy.
After obtaining Re we let Rg - max Ri be our lower bound Rg Based on Rg = max R2 and Equation 8, we have the following guarantee:
R
R
S
R
+
(9)
3.2.3 COMPLETE CERTIFICATION ALGORITHM
Algorithm 2 shows algorithm estimate the certified radius for a given example and la- bel I. The function SAMPLEUNDERNOIS is the same as in Algorithm 1. Functions BINOCP and SIMUEM return the estimated probability bound for each label. Function BINARY per- forms binary search to solve the Equation 7 and returns solution satisfying Equation 8. Formally, our algorithm has the following guarantee:
Proposition 2. With probability at least 1 a over the randomness in CERTIFY, // CECRRTFYY returns radius Ri (i.e., does ABSTAIN), then have E gb(x + 6), |||0||2 < Rg.
Proof. See Appendix D.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets and models: We conduct experiments on the standard CIFARIO (Krizhevsky Hinton, 2009) and ImageNet (Deng al., 2009) datasets evaluate method. We the publicly available pre-trained models from Cohen et al. (2019). Specifically, the architectures of the base classifiers are ResNet- 110 and ResNet-50 for CIFARIO and ImageNet, respectively.
Parameter setting:
We study the impact of k the confidence level a, the noise level a, the number of samples n, and the confidence interval estimation methods on the certified radius. Unless otherwise mentioned, we use the following default parameters: 100, 000, and = 10-5, Moreover, we use SimuEM to estimate bounds of label probabilities. When studying the impact of one parameter on the certified radius, we fix the other parameters to their default values.
a 0.001,
0.5,
Approximate certified top-k accuracy: For each testing example x whose true label is I, we compute the certified radius R₁ using the CERTIFY algorithm. Then, we compute the certified top- I accuracy at a radius as the fraction of testing examples whose certified radius are at least r. Note that our computed certified top-k accuracy an approximate certified top-k accuracy instead of the true certified top-k accuracy. However, we can obtain lower bound of the true certified top-k accuracy based on the approximate certified top-k accuracy. Appendix shows the details. Moreover, the gap between the lower bound of the true certified top- accuracy and the approximate top-k accuracy is negligible when a small. For convenience, we simply use the term certified top-k accuracy in the paper.

---

Published as a conference paper at ICLR 2020
confidencee 91.%% confidence
confisince
00.8% confidinnce
0.8
0.8
ourifed aocummy
aosumiyy
confidence 99 900% confidience
contiled accursty
90.00 00.000%% confidence
0.6
0.6
0.4
0.4
02
0.2
0.0
radiss
(a) CIFARIO
(b) ImageNet
Figure 2: Impact of the confidence level the certified top-3 accuracy.
== 0.25
a= 0.25
0.50
carifed anturaay
0- 1.00
Contfed acsursyy
d- 1.00
0.0
radius
radius
(a) CIFAR1O
(b) ImageNet
Figure 3: Impact of a on the certified top-3 accuracy.
1.0
1.0
BinoCP SimMEM
BiroCP
0.8
0.8
SimuEM
cartfeed aerr
comfoed scaurac
0.0
0.8
0.4
0.4
radius
radius
(a) CIFARIO
(b) ImageNet
Figure 4: BinoCP vs. SimuEM, where k: 3.
4.2 EXPERIMENTAL RESULTS
Figure shows the certified top-k accuracy as the radius r increases for different k. Naturally, the certified top-k accuracy increases lo increases. On CIFAR10, respectively achieve certified top-1, top-2, and top-3 accuracies as 45.2%, 58.8%, and 67.2% when the f2-norm of the adversarial perturbation is less than 0.5 (127/255). On ImageNet, we respectively achieve certified top-1, top-3, and top-5 accuracies as 46.6%, 57.8%, and 62.8% when the f--norm of the adversarial perturbation less than 0.5. On CIFAR1O, the gaps between the certified top-k accuracy for different are smaller than those between the top-k accuracy under no attacks, and they become smaller as the radius increases. On ImageNet, the gaps between the certified top-k accuracy for different à remain similar to those between the top-k accuracy under no attacks as the radius increases. Figure 2 shows the influence of the confidence level. We observe that confidence level has a small influence on the certified top-k accuracy as the different curves almost overlap. The reason is that the estimated confidence intervals of the probabilities shrink slowly as the confidence level increases. Figure shows the influence of We observe that controls trade-off between normal accuracy under no attacks and robustness. Specifically, when ø is smaller, the accuracy under no attacks (i.c., the accuracy when radius is 0) is larger, but the certified top-k accuracy drops more quickly as the radius

---

Published as a conference paper at ICLR 2020
increases. Figure 4 compares BinoCP with SimuEM. The results show that SimuEM is better when the certified radius is small, while BinoCP is better when the certified radius is large. We found the reason is that when the certified radius is large, pr is relatively large, and thus 1 pr already provides a good estimation for Ps, where + I.
5 RELATED WORK
Numerous defenses have been proposed against adversarial perturbations the past several years. These defenses either show robustness against existing attacks empirically, or prove the robustness against arbitrary pounded--ertuurbations (known as certified defenses).
5.1 EMPIRICAL DEFENSES
The community has proposed many empirical defenses. The most effective empirical defense is adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017; Tramèr et al., 2018; Madry et al., 2018). However, adversarial training does not have certified robustness guarantees. Other examples of empirical defenses include defensive distillation (Papernot et al., 2016), MagNet (Meng & Chen, 2017), PixelDefend (Song al., 2017), Feature squeezing (Xu et al., 2018), and many others (Liu et al., 2019; Svohoda et al., 2019; Schott et al., 2019; Buckman et al., 2018; Ma et al., 2018; Guo et al., 2018; Dhillon et al., 2018; Xie al., 2018; Song al., 2018; Samangouei et al., 2018; Na et al., 2018; Metzen al., 2017). However, many of these defenses were soon broken by adaptive attacks (Carlini & Wagner, 2017a; Athalye et al., 2018; Uesato al., 2018; Athalye & Carlini, 2018).
5.2 CERTIFIED DEFENSES
To end the arms race between defenders and adversaries, researchers have developed certified de- fenses against adversarial perturbations. Specifically, in certifiably robust classifier, the predicted top-1 label is verifiably constant within a certain region (e.g., 4--norm ball) around an input exam- ple, which provides lower bound of the adversarial perturbation. Such certified defenses include satisfiability modulo theories based methods (Katz et al., 2017; Carlini et al., 2017: Ehlers, 2017; Huang et al., 2017), mixed integer linear programming based methods (Cheng et al., 2017: Lomuscio & Maganti, 2017; Dutta et al., 2017; Fischetti & Jo. 2018; Bunel et al., 2018), abstract interpreta- tion based methods (Gehr et al., 2018; Tjeng et al., 2018), and global (or local) Lipschitz constant based methods (Cisse et al., 2017: Gouk et al., 2018; 8; Tsuzuku et al., 2018; Anil et al., 2019; Wong & Kolter, 2018; Wang et al., 2018a:b; Raghunathan et al., 201 Sa;b; Wong et al., 2018; Dvijotham et al., 201 Sa;b; Croce et al., 2018; Gehr et al., 2018; Mirman et al., 2018: Singh et al., 2018; Gowal et al., 2018; Weng et al., 2018; Zhang et al., 2018). However, these methods are not scalable to large neural networks and/or make assumptions the architectures of the neural networks. For example, these defenses are not scalablc/applicable to the complex neural networks for ImageNet.
Randomized smoothing was first proposed as empirical defense (Cao & Gong, 2017: Liu et al., 2018) without deriving the certified robustness guarantees. For instance, Cao & Gong (2017) pro- posed randomized smoothing with uniform noise from hypercube centered an example. Lecuyer et al. (2019) was the first to prove the certified robustness guarantee of randomized smoothing for top-1 predictions. Their results leverage differential privacy. Subsequently, Li et al. (2018) further leverages information theory to improve the certified radius bound. Cohen et al. (2019) obtains tight certified radius bound for randomized smoothing with Gaussian noise by leveraging the Neyman- Peaassn Lemma. Pinot et al. (2019) theoretically demonstrated the robustness to adversar- ial attacks of randomized smoothing when adding noise from Exponential family distributions and devised an upper bound on the adversarial generalization gap of randomized neural networks. Lee et al. (2019) generalized randomized smoothing to discrete data. Salman al. (2019) employed ad- versarial training to improve the performance of randomized smoothing. Unlike the other certified defenses, randomized smoothing is scalable to large neural networks and applicable to arbitrary clas- sifiers. Our work derives the first certified robustness guarantee of randomized smoothing for top-k predictions. Moreover, we show that our robustness guarantee is tight for randomized smoothing with Gaussian noise.
8

---

Published as a conference paper at ICLR 2020
6 CONCLUSION
Adversarial perturbation poses fundamental security threat to classifiers. Existing certified de- fenses focus on top-1 predictions, leaving top-k predictions untouched. In this work, derive the first certified radius under f--norm for top-k predictions. Our results are based on randomized smoothing. Moreover, we prove that our certified radius tight for randomized smoothing with Gaussian noise. In order to compute the certified radius in practice, we further propose simultane- ous confidence interval estimation methods as well as design an algorithm to estimate a lower bound of the certified radius. Interesting directions for future work include 1) deriving a tight certified ra- dius under other norms such as l and loc. 2) studying which noise gives the tightest certified radius for randomized smoothing, and 3) studying certified robustness for top-k ranking.
ACKNOWLEDGMENTS
We thank the anonymous reviewers for insightful reviews. This work was supported by NSF grant No. 1937786.
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference on Machine Learning, 2019.
Anish Athalye and Nicholas Carlini. On the robustness of the cvpr 2018 white-box adversarial example defenses. The Bright and Dark Sides of Computer Vision: Challenges and Opportunities for Privacy and Security (CV-COPS), 2018.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning. pp. 274-2822 283, 2018
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In ICLR, 2018
Rudy R Bunel, llker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Process- ing Systems, pp. 4799-47799,.. 2018.
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, pp. 278-287. ACM, 2017.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 3-14. ACM, 2017a.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEFE, 2017b.
Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. Provably minimally-distorted adver- sarial examples. arXiv preprint orXiv:1709 70...1000700.0... 2017.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 854 863. JMLR. org, 2017.
Clarifai, https:://// http://wwwwllarraee// clari fai demo. July 2019.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.02900002/11 2019.

---

Published as a conference paper at ICLR 2020
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu net- works via maximization of linear regions. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255 Icve, 2009.
Guneet S Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial de- fense. In ICLR, 2018.
Souradeep Dutta, Susmit Jha, Sriram Sanakaranaraaaaaan, and Ashish Tiwari. Output range analysis for deep neural networks, arXiv preprint arXiv:1709.09133, 2017.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint arXiv: 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAL, pp. 550 559, 2018b.
Ruediger Ehlers. Formal verification of piece-wise linear ferwaro neural networks. In Interna- lional Symposium on Aulomated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23:296-309, 2018.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Leo A Goodman. On simultaneous confidence intervals for multinomial proportion............oo.oo Technometries, 7(2):247-2544 1965.
Google Cloud Vision. https: http:://///ooooooollllleeeo.oeee
July 2019.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint arXiv:18044 04368, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint
2018.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations. In ICLR, 2018
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference Computer Aided Verification, pp. 3-29. Springer, 2017.
Kenneth Hung. William Fithian, et al. Rank verification for exponential families. The Annals of Statistics, 47(2):758-782, 2019.
Jinyuan Jia and Neil Zhenqiang Gong. AttriGuard: A practical defense against attribute inference attacks via adversarial machine learning. In USENIX Security Symposium, 2018.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 17- Springer, 2017.
10

---

Published as a conference paper at ICLR 2020
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In JEEE Symposium on Security and Privacy 2019.
Gu Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 491 1-4222 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. arXiv preprint arXiv:1809.0311 2018.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 369-385, 2018.
Xuanqing Liu, Yao Li, Chongruo Wu, and Cho-Jui Hsieh. Ady-bnn: Improved adversarial defense through robust bayesian neural network. In ICLR, 2019.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arXiv:1706.07335 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.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Dongyu Meng and Hao Chen. Magnet: two-pronged defense against adversarial examples. In Proceedings of the 20/7 ACM SIGSAC Conference on Computer and Communications Security, pp. 135-147 147. ACM, 2017.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. In ICLR, 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Taesik Na, Jong Hwan Ko, and Saibal Mukhopadhyay. Cascade adversarial machine learning regu- larized with unified embedding. In ICLR, 2018.
Jerzy Neyman and Egon Sharpe Pearson. the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing 1933.
Papers of a Mathematical or Physical Character, (396669770)2289-11119
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597. IEEF, 2016.
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cedric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization. In Advances Neural Information Processing Systems, pp. 11838-11848 2019.
Aditi Raghumathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference Learning Representations, 201 Sa.

---

Published as a conference paper at ICLR 2020
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp- 10877-10887, 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 Advances in Neural Information Processing Systems, pp. 11289-11306 11300, 2019.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense- gan: Protecting classifiers against adversarial attacks using generative models. In ICLR, 2018.
Lukas Schott, Jonas Rauber, Matthias Bethge, and Wieland Brendel. Towards the first adversarially robust neural network model on mnist. In ICLR, 2019.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp. 10802-10813, 2018.
Cristina P Sison and Joseph Glaz. Simultaneous confidence intervals and sample size determination for multinomial proportions. Journal of the American Statistical Association, 90(429):366-366 1995.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. In ICLR, 2017.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. In ICLR, 2018.
Jan Svoboda, Jonathan Masci, Federico Monti, Michael M Bronstein, and Leonidas Guibas, Peer- nets: Exploiting peer wisdom against adversarial attacks. ICLR, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICML,, 2018.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. In ICLR, 2018.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz- marginn training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems, pp. 6541 -6550, 2018.
Jonathan Uesato, Brendan O' O'Donoghue, Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning, pp. 5032-5041, 2018.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint arXiv:1811.0262. 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp- 6367- 2377,20188
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. arXiv preprint arXiv: X8X::180440969,, 2018
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference Machine Learning, pp. 5283-529,, 2018.
12

---

Published as a conference paper at ICLR 2020
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-84000 2018
Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In ICLR, 2018.
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. In NDSS, 2018.
Huan Zhang, Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in Neural Information Processing Systems, pp. 4939-4948, 2018.
A PROOF OF THEOREM
Given an example x, we define the following two random variables:
x=x+e~Nixx
(10)
==x+ 8,
(11)
where 6 ~ N(0,0²1). The random variables X and Y represent random samples obtained by adding isotropic Gaussian noise to the example x and its perturbed version ô, respectively. Cohen et al. (2019) applied the standard Neyman-Pearson Lemma (Neyman & Pearson, 1933) to the above two random variables, and obtained the following lemma:
Lemma (Neyman- Pearson for Gaussians with different means). Let X ~ N(x (2x,,21), Y N(x+ I), and M: R + {0,11 be a random or finirii Then, we have the following:
(f) = {z E Rdd : z S 3} for some 3 and (X) = 1) 2 Pr(X E Z), then PY(M(Y)- = 1) Pr(Y E)
(2) = {z E Rdd: : 2 3} for some 3 and (x( = =1) Pr(X & Z), then Pr(M(Y) =
1) Pr E Z)
Moreover, we have the following lemma from Cohen et al. (2019).
Lemma 2. Given an example x, a number q E [0, 1], and regions A and B defined as follows:
A = {z 8T (z x) S a |0 + (g)}
(12)
B {z 6"h (z x) 2 ||1|,2 Φ -1 9)}
(13)
Then, we have the following equations:
Pr(X E A) =q
(14)
Pr(X E B) =q
(15)
||0||
Pr(Y A) (
(16)
|111|2]
Pr(Y B) +( (g))
(17)
Proof. Please refer to Cohen et al. (2019).
Based on Lemma and 2, we derive the following lemma:
Lemma 3. Suppose we have arbitrary base classifier f. example x, set of labels which are denoted as S. two probabilities ps and Ps that satisfy ps S ps = (X) E S) $ Ps. and regions As and Bg defined as follows:
As = 1z:5T (z x) 5 50
(18)
Bg {z: 8T (z x) 20 x (1 ps))
(19)
Then, we have:
Pr(X E As) E Px) ES) < Pr(X E Bs)
(00)
Pr(Y E As) S (P(((Y) E ES) Pr(Y E BBs)
(21)
13

---

Published as a conference paper at ICLR 2020
Proof. We know that Pr(X As) ps based Lemma 2. Combined with the condition that Ps Pr(f(X) E S), obtain the first inequality in (20). Similarly, we can obtain the second
inequality in (20). We define M 1(f(z) E S). Based on the first inequality in (20) and Lemma 1, we have the following:
Pr(Y E As) < PY( = 1) = Pr(J(Y) e), which is the first inequality in (21). The second inequality in (21) can be obtained similarly.
(22)
L
Next, we restate Theorem and show our proof.
Theorem (Certified Radius for Top-k Predictions). Suppose are given example x, arbi- Irary base classifier J. ~ N(0 TT, a smoothed classifier g, an arbitrary label I & [1,2, . (1,,,
,c).
and pL; Pvs" ". P1-1:PP411 ' Pe E [0, 1] that satisfy the following conditions:
where p and p indicate lower and upper bounds of p. respectively. Ler Po, 2 Po.-, 22, .... Pb. be Pr(s(x+e) 1) 2 pt and
( =i)
the k largest ones among {p1,... -P-1-- P141,''. .Po). where ties are broken uniformly at random. Moreover, we denote by St = (bb, b2. ,b, the set of labels with the smallest probability upper
bounds in the k largest ones and by Ps. = Σÿ= Pby the sum of the t probability upper bounds, where = 1,2, ,k. Then, we have:
E gx 8), 1| Rs,
(2)
where Ry is the unique solution to the following equation:
R1
( - (ps,) + B)
Φ
(p1
0,
(3)
where T and 1-1 are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively.
Proof. Roughly speaking, our idea to make the probability that the base classifier / predicts I when taking Y as input larger than the smallest one among the probabilities that f predicts for set of arbitrary & labels selected from all labels except l. For simplicity, we let I' = {1, .......... .e \ {1), i... all labels except L. We denote by I'x set of & labels in I. We aim to find certified radius R2 such that we have maxp, Sr minger, Pr(f(Y) = i) < Pr(f(Y) = l), which guarantees E (x(x+ + 8). We first upper bound the minimal probability minter, Pr(f(Y) i) for given k' and then we upper bound the maximum value of the minimal probability among all possible r; S T. Finally, we obtain the certified radius R2 via letting the upper bound of the maximum value smaller than Pr(S(Y)= I)).
Bounding min,er, Pr( =) i) for given Tg: We use S to denote non-empty subset of I and use [S] to denote its size. We define ys = Eigs P;, which is the sum of the upper bounds of the probabilities for the labels in S. Moreover, we define the following region associated with the set S:
Bg {z: : 5t (z x) 2 1|0|| - ps))
(23)
We have Pr(f(Y) E S) S Pr(Y E By) by applying Lemma to the set S. In addition, we have Eies -i) PY( E S). Therefore, we have:
Σ Pr(f(() i) Pr(f(Y) E S) < Pr(Y Bs) IES
(24)
Moreover, we have:
min Pr(S(Y) i) < min Pr(S(Y) =) TET
(25)
Eies Pr(f(Y) i)
(26)
|S|
Pr(Y E Bs)
(27)
|
14

---

Published as a conference paper at ICLR 2020
where we have the first inequality because S is subset of F and we have the second inequality because the smallest value in a set is no larger than the average value of the set. Equation 27 holds for any S x.. Therefore, by taking all possible sets S into consideration, we have the following:
Pr(Y E Bs)
min Pr(f(Y) S ier'
min sgr,
(28)
|S|
Pr(Y Bs)
min SCT
min
(29)
Pr(Y E Bs.)
(30)
where St is the set of labels in Fa whose probability upper bounds the smallest, where ties are broken uniformly at random. We have Equation 30 from Equation 29 because Pr(Y E Bs)
decreases as Pg decreases.
Bounding Cr minger, Pr(ʃ(Y) = i): Since Pr(Y E Bs.) increases as Ps, increases,
Equation 30 reaches its maximum value when F& {bi, by. ... ,b ie., when F3 is the set of labels in P with the largest probability upper bounds. Formally, we have:
Pr(Y E Bs.)
max min Pr(f(Y) = i) $ min TIE T
(31)
t
where S. {b1, b2. ,,, .b).
Obtaining Re: According to Lemma 3, we have the following for S (1):
Pr(ʃ(Y) = 1) 2 Pr(Y Aqu)) Recall that our goal is to make Pr(f(Y) = 1) maxr,gr minter, Pr(f(Y) = 1). It suffices to let:
(32)
Pr(Y E Bs.)
Pr(Y E A(y)) > min [=1
(33)
According to Lemma 2, we have Pr(Y E A()) ( (ps,) + [ )). Therefore, we have the following constraint on 5:
( (pi) [ and Pr(Y Bs.)
& [0]l2] min
④ (Ps.) + 16112
(Φ (( (pt)
(34)
t
Since the left-hand side of the above inequality 1) decreases as ||öl|2 increases, 2) is larger than when ||0||2 -00, and 3) is smaller than 0 when ||8||2 - co, we have the constraint ||0||2 Ri, where R2 is the unique solution to the following equation:
( (ps,) + R
(
min
0.
(35)
B PROOF OF THEOREM 2
Following the terminology we used in proving Theorem 1, we define region Aqr follows:
An = (z: 8T (T - x) S a ||ō||| Φ (pt))
(36)
According to Lemma 2. we have Pr(X E A(t)) = Pt- We first show the following lemma, which is the key to prove our Theorem
Lemma 4. Assuming we have pt + -j=1 1j=1Pb; S For any perturbation 1|ó112 > R₁, there exists disjoint regions Co C \ A(j. j E {,, 11,2... ... kb that satisfy the following:
Pr Co,) -pny Vj 21.2.... .).
(37)
k Pr(Y Bs,) 1.
P 2 min t=1
Vj 21, ... ,k}.
(38)
where the random variables X and Y are defined in Equation 10 and 11, respectively: and (bi, bz.... bbe and St are defined in Theorem 1.
15

---

Published as a conference paper at ICLR 2020
Proof. Our proof is based mathematical induction and the intermediate value theorem. For convenience, we defer the proof to Appendix B.1.
Next, we restate Theorem 2 and show our proof.
Theorem (Tightness of the Certified Radius). Assuming we have Pt + E Ej=I S and pt + ---1,---11441,.- ,c 2 1. Then, for any perturbation ||ō||2 > Rs there exists a base classifier f 1-1,41,,..
consistent with (1) but we have I & g + 6).
Proof. Our idea is to construct a base classifier such that / is not among the top-k labels predicted
by the smoothed classifier for any perturbed example x + 8 when ||ó|2 Rs. First, according
to Lemma 4, we know there exists k disjoint regions Co S R AAg. j E {1,2, ... _k3 that
satisfy Equation 37 and 38. Moreover, we divide the remaining region F (A(z U C2 into 1 c-k 1 regions, which we denote as Chz41: Cheezr Co._, and satisfy Pr(X E Co S Pb, for e {K- + 1, 1, 2,
e- 1). Note that bi, b2. .b-1 is some permutation of (1, 2, .. ,c) (1). We can divide the remaining region into such c- regions because pt + 1-1,1,1,-
1.
Then, based on these regions, we construct the following base classifier:
fT. -1) Lbs. if E Cayy
if E An Cbj.Vje VjE (1,,,..,,..
[(x)=
(39)
Based on the definition of f", we have the following:
Pr(S"(X)= = -)) Pr(X A(4)) - pt
(40)
Px( = b;) Pr(X Cb2)) - -bo, j = 1,2,
(41)
Px( = -b,) Pr(X Cn2) S Po,, j= 1, c
(42)
Therefore, f satisfies the conditions in (I). Next, show that 1 is not among the top-k labels predicted by the smoothed classifier for any perturbed example x + when ||ā1|2 > Ri Specifically, have:
Pr( = 1| || > R:)
(43)
-Pr(Y E App ||0|| > Ri)
(Definition of f*)
(44)
<Pr(Y E A(03 A009|118112- = Rd)
(Pr(Y E A(y) increases as ||0|| decreases)
(45)
Pr(Y E 1|0111 Ri)
min
(Definition of R:)
(46)
(=1
Pr(Y E Bs. |181|2 Ri)
min t=1
(Pr(Y Bs.) increases ||ōl|, increases)
(47)
<Pr(Y E Co,1118811 Rı)
(Lemmna 4)
(48)
-Pr(f((Y) by1 [|01|2 > Ri)
(Definition of f*).
(49)
where j = 1, k. Since we have found & labels whose probabilities are larger than the proba- bility of the label (, we have l & (x(xx 6) when [|0]| > R,
B. PROOF OF LEMMA 4
We first define some key notations and lemmas that will be used in our proof.
Definition 1 (C(91, 92). C'(g1. 92). Tz (2(92,00 92), ry (9(91, 92)). Given two values qu and qe that satisfy
0 S Q2 S 1, we define the following region:
C(g..92) {z ||ā]|2 t --1(1 92) 5t ff(2 x) a |10|| Φ --1(1 91)
(50)
According to Lemma 2, we have:
Pr(X E C(qi, q2)) = 91
(51)
where the Gaussian random variable X is defined in Equation 10. Moreover, assuming have pairs of (g), o)), i 1,2,3,.... where of of E 42), Vi. We define the following region:
C' C(q,, 92) (U.Clgi, ob))
(52)
16

---

Published as a conference paper at ICLR 2020
(1 92) is the remaining region of C(1 92) excluding C(gi, 92), C(gi 92). .... Given two values
ot and 92 that satisfy q1 I q5 I 92 1 92. we also define the following two two functions:
Fx (q (2) = Pr(X E C' (q,, 42) n n(g (iqii.9)1 .b))
(53)
Ty (9 .22) Pr(Y & C' (41. 92) CC(g 92)),
(54)
where the random variables X and Y are defined in Equation 10 and 11, respectively.
Next, we show a key property of our defined functions Tz "=( gb) and ry(9i 92). Lemma 5. (a (5) < rr v and q 2 o (or of 2 g)). then we have rylaf ( S ry(g).93 .2)).
Proof. We consider three scenarios.
Scenario I:
25 of v ot. We denote hi and hg as the probability densities for the --
random variables X and Y, respectively. Then, we have hz(z) 2in
exp(
2n
and h (2) 22n )a exp(- 1 (25-x1=61)) Therefore, the ratio of the probability density of Y 20t and the probability density of at given point z is as follows:
(z) exp(
8T (z (z- |811
(55)
(z)
o²
20
Next, we compare the ratio for the points in different regions and have the following:
(z E C' (g"""" :5)))
(56)
(z 2 E C'(a"' gf))
<exp( a |18|| $ (1 gft)
1811
(57)
20
|00|| $ --1(11 (z))
|
<exp("
(58)
0²
20²
1z E C'
(ur g²))
(59)
he (z/z E (9'.
The Equation 57 from 56 is based on Equation 55 and the fact that (T (z-x) S a || 1b (1 Φ
for any point in the region (' og from Definition Similarly, we can obtain Equation 59 from 58. We note that the Equation 58 from 57 is because o I 47 Based on Equation 57 and 58, we know that there exists real number such that:
exp( || (1 (1144- 9
||11|
S u S expl T ||ô1|2 x --1(1=11111 z
|10|
(60)
a²
20
o2
20
Combining the Equation 56, 57, and 60, we have the following:
h (z|z C'fff ( of)) S h (z ('fffi g())))
(61)
Taking an integral on both sides the Equation 61 in the region C' .g)) and recalling the defini- tion of rx (g 4 and (y o²), we have the following:
rolaf g S u 1r.2
(62)
Similarly, have:
r- 25.) (y (
(63)
Based on Equation 62, 63, and the condition that T (9) 93) (a .3) have the following:
rolof g8 ,,(g),1))
(64)
Scenario I:: of 22 o. 2 Φ.. We have:
( r- (o/. v T= Φ5) rrloi gft + +r(lff -r(aa)
(65)
17

---

Published as a conference paper at ICLR 2020
Therefore, we have the following equation:
rhe r2 g S Tx (2 .f)
(66)
Similar to Scenario I, we know that there exists u such that:
(y E (' (1155.05))) 0z))
My(2/a E C' (9))
h (z,(2 C' 9))) I S hz E C' 9f))
(67)
Similar to Scenario I, have the following based on Equation 66:
rg(92 2 S rr(9), 9f)
(68)
Therefore, we have the following:
Ty ) Tyl
(9 ) ( oi) + r x =ro(oi.0))
(69)
Scenario III: C 2 0 Therefore, we have Ty
of
As Ta (q
of 4 S Ts (of ) we have To (g 4 = Tx (9 o3
Next, we list the well-known Intermediate Value Theorem and show several other properties of our defined functions (g) o$) and ry (y 9
Lemma 6 (Intermediate Value Theorem). Ifa functio F is continuous at every point in the interval [a, b] and (F(a) v) (F(b) - v) S 0. then there exists x such that F(x) v.
Roughly speaking, the Intermediate Value Theorem tells us that if a continuous function has values no larger and no smaller (or no smaller and no larger) than v at the two end points of an interval, respectively, then the function takes value u at some point in the interval.
Lemma 7, Given two probabilities qr my if we huve:
Oz &rll1i
(70)
Then, there exists of &2 E [91, Q2] such that:
(2(11, 122 = 9a
(71)
ry r=(41, = 9r
(72)
Furthermore, if we have:
(ryla), gb2) 9g) (ry(dh, 92) -2222))-) 9v) S 0,
(73)
then there exists n. oi E [91, 12) such that:
r= 1/ 9r
(74)
rg ( 9/2) 4y
(75)
Proof. We define function F(x) = T2 (g1, x).
Then, we have (F(g1) - 9z) (F((2) - 9z) < 0
since F(11) = 0 S qu and F(gz) r. (91 92) Oz based on Equation 70. Therefore, according to
Lemma 6, there exists of E [q) 92] such that:
(2 4 = 9-
(76)
Similarly, we can prove that there exists 9/2 [gı, q2l such that r2 "=('''100 42) 9r
For any o E Igé. 42]. we define H(x) (2( Then, we know H(q)) Ta 9 > Tr 962 = 4z since of 2 dz2 Moreover, we have H(gs) = 0 I qz. Therefore, we have 9z) 9z) S O. According Lemma 6,we know there exists of [/1 08] such that Tz (gf, g Or for arbitrary of E Igh, 92). We define G(r) = (f) where x E 1/2 92l.
(H)))) (x) (H(9h)
and of are a value such that r- (uf x) = qu for a given x. When x o/ we can let of = qi since Ta( 4/))
Jn. and when and Lemma 6, we know that there exists x E [g6, qal such that G(z) = 4y- Therefore, there exists
Qi. we can let of = 1/2 since (2 92) = qu. Based on Equation 73
of and of such that:
r=(g 1/) -x Ti ( o/2) 4y
(77)
(78)
n
18

---

Published as a conference paper at ICLR 2020
Lemma 8. Assuming we have qi following:
0, q² =ss. If 1/ Ps. S min, g.. then have the
(a ( = 22 - q) = =Ps.
(79)
ru(a 2 Pr(Y E Bss))
(80)
Proof. If oz S. min; g:. then we have (2) (8)) = C(a) 43 since no region is excluded.
Therefore, we have (y g = Pr(Y (q), (2) - = Pr(Y E C( ) = 9 9
Ps, based on Equation 51. We note that C(gi, (2)) Bs, when qi 0 and g = Ps. Therefore, we can obtain Equation 80 based on the definition of ry , 9 from Definition
Lemma 9. If we have 9i S q8 S Q2. then we have the following:
Ty [g 92
ry(q (
(81)
[2 42) f2))/r(( (g 92)
Proof. By applying Lemma
We further generalize Lemma to two regions. Specifically, we have the following lemma:
Lemma 10. Assuming we have a region Cue S "[qT"99"' and we have (² (2) n C(""" " = 0. If n q 92 2 q2 and r2(11, ( I Pr(X E Cw). then we have:
T 92) Pr(Y E Cw)
(82)
Proof. We let @1 max 1 As C1 42) C(aF ;44) 0 and Φ1 q/. can obtain the conclusion by applying Lemma 5 on C' (q(1 Q2) U Cw.
Next, we restate Lemma 4 and show our proof.
Lemma 4, Assuming we have pt + Σ}= Pb, I 1. For any perturbation [|ó]|2 > R4, there exists
disjoint regions Co₃ CR A (1, ... ,k} that satisfy the following:
Pr(X E Co,) = - Vj f1,2..... ,k]
(37)
Pr(Y E Bs.)
Pr(Y E C.2)) 2 min 1=1
VjE {1,2. ... .kk], kk)
(38)
t
where the random variables X and Y are defined in Equation 10 and 11, respectively; and {bi, .2. and S, are defined in Theorem
Proof. Our proof leverages Mathematical Induction, which contains two steps. In the first step, we show that the statement holds initially. In the second step. show that if the statement is true for the mtth iteration, then it also holds for the 11+h))th iteration. Without loss of generality, we assume argmin
Pr(YEBs,) Therefore, we have the following:
Vi A Pr(Y Bs.) Pr(Y E Bs.)
(83)
Recall the definition of Bs, and we have the following:
Bs, (z 6T x) 2 ||ō||2 - 1-'001111111 (11-1s.)
(84)
where Ps, Ejes, py. We split Bs, into parts: Bs, and Bs, \ Bs. We will show that yj E [1, r], we can find disjoint Co S Bs, whose union is Bs, such that:
Pr(X E Co2)) = Po, Pr(Y E Ca,)
(85)
Pr(Y E Bs.)
(86)
19

---

Published as a conference paper at ICLR 2020
For the other part, will show that vjj E [r + 1, k,,, we can find disjoint Co2 S Bs. \ Bs, whose union is Bs, Bs, such that:
Pr(X E Cb₂)) Po,
(87)
Pr(Y E Bs.)
Pr(Y E ECo,) 2
(88)
We first show that Vj E [], we can find Co. S Bs, that satisfy Equation 85 and 86. Since our proof leverages Mathematical Induction, we first show that we can find Co. S Bs. that satisfies the requirements. Then, assuming we can find Co,. ... Co show that we can find Co--m C Bs. \ (U]=--m+1 ). We will leverage Lemma 7 to prove the existence for each Cb.- Next, we show the two steps.
iteratively construct each Co Vj E [1. Specifically,
Step I: We show that can find Co, S Bs, that satisfies Equation 85 and 86. We let qı 0 and 42 Ps., and we define the following region:
(2( = C(O.Ps,) = Bs.
(89)
We have:
(g 92) = Pr(X E (2((1, - Ps,
(90)
(q) 92) = Pr(Y E (4()) = Pr(Y E Bsr).
(91)
which can be directly obtained as (91, 92) = Bs,, As we have Por I rx(91.92) = Ps, =
Ej= Po,, there exist of = Ds. - Po, 4/2 Do. such that:
(a 122 -o.
(92)
rr 92) = Po.
(93)
Moreover, we have the following:
Ty g 2 (q Po.) Pr C(q..Po,)) Pr(Y Bs.) Pr(Y Bs.)
(94)
T
The equality in the middle from Lemma 8, the left inequality is because d/2 = Do, 2 Do, and the right inequality is from Equation 83. Furthermore, we have the following:
(95)
=Pr(Y E C'(gi, 92) (2(
(96)
-Pr(Y E C(ps, - Ph., .Ps.).
(97)
-Pr(Y& E C(0,Ps.) -P((Y E C(O,Ds, Poo))
(98)
-Pr(Y E C(0,Ps.)) -Pr(Y E C(O. ))
(99)
-Pr(Y& E Bs.) Pr(Y E BB...)
(100)
(T - 1) Pr(Y e Bs.)
<Pr(Y E Bs.)
(101)
Pr(Y E Bs.)
(102)
We obtain Equation 100 from Equation 99 based on Lemma 8, and Equation 101 from Equation 100
based on Equation 83, Therefore, we have the following:
(ry(dis (2) Pr( E Bs.) ) (ry(g1,4)) 16)
Pr E Bs.
< 0
(103)
.b5) = Po, rr 93) Thus, there exists (qī, Ø3) such that Th (q (xT.))5))
Pr(Y
based on Lemma 7.
Then, we have the following based on the definition of rx, Ty.
Pr(X E C'(1 92) C((
Po. Pr(Y E Bs.)
(104)
Pr(Y E C'(91,92) 42) C(qf.
(105)
20

---

Published as a conference paper at ICLR 2020
Finally, we let Co. C' (g1: (g1:92) C(( 92), which meets our goal.
Step II: Assuming we can find {(gī 92), (9ì -1 .92 -9 ) ... (qf (qi- -92 -92- --m++1) }} (Vj E El 1mmm- m
1,71. 91 oं S o S 92) where S m 11 such that Vj [T m + 1, T, we have:
Pr(X Cby) = Pb;
(106)
Pr(Y E Co,) Pr(Y Bs.)
(107)
as well the following:
Vj,LE [T- m + 1, and j + i, Co, nCs = 0
(108)
We denote m. We show can find Co. such that we have:
Pr(X E Cr.) = Poe
(109)
Pr(Y E Co.) Pr(Y E Bs.))
(110)
T
Vj le C,, CC,
(111)
We let Q1 0, 42
Ps, and denote
(2(,, = C(n,, 92) \ Ug=
(112)
We have the following:
92)
(113)
-Pr(X C' (g1, 42) (((())92)
(114)
-P E C(11, Pr(X E Cos)
(115)
_Pr(X E C(qi,
Σ Pr(X E Co.) ==++1
(116)
Phs
Po:
(117)
J=1
i=0+1
Pby
(118)
The Equation 116 from 115 is based on the Equation 108, and the Equation 117 from 116 is based the Equation 51 and 106. Furthermore, we have the following:
r,(21, 42)
(119)
-Pr(Y E C' n C(91.92))
(120)
-Pr(Y E C((q, (2))
Pr(Y U)zc+iCl,)
(121)
=Pr(Y E (((1))0))
Σ Pr(Y Ch,))
(122)
==++1
=Pr(Y E Bs.) m PM(P Bs.)
(123)
(T (r-m) m) Pr(Y E Bs.)
(124)
The Equation 123 from 122 is because C(gi, q2) Bs. and the Equation 107. We have Pb_ S
Ta(gi. 92). Therefore, based on Lemma 7, there exist g/, 42 such that:
rz 96) Pr.
(125)
Ts (2) = Ph.
(126)
We have:
(y(2) %b)
(127)
21

---

Published as a conference paper at ICLR 2020
1
27 92)
(128)
(91, 92)/r 92)
1
2r 92)
(129)
[ Pb,)/Pb
Pr E Bg,)
(130)
Equation 128 from 127 is based on Lemma 9, Equation 129 from 128 is based on Equation 90 and 125, and Equation 130 from 129 obtained from Equation 91 and the fact that [(]== pb,) /Pb. z T, Next, we show:
Pr(Y E Bs.)
Ty (11 S
(131)
T
In particular, consider two scenarios.
Scenario 1). of 2 min of. We denote = argmin =r- G.- We let C.
Cs. 3
C(gi,gh) As d 2 qi 92 o and ra (x(1 Pd. < Pr(X E Cw.) Pb. have the following
based on Lemma 10:
r (, 92) & Pr(Y E Cw)= Pr(Y Bs.)
(132)
Scenario 2). d1 < ming j 1 g. We have the following:
C' ("(1,, (2) n Clgn, d() C(n..g) o
(133)
Furthermore, we have:
(=(11, x1) = rr(99, - rx rr(sh, 92)
(134)
(135)
Pb;
-Pb.
(136)
j=1
Pb;
(137)
1=1
Moreover, have rz (= 91) 11 21 from Lemma 8. The above two should be equal. Thus,
have of Σラ= Pb, Ds.- since e T m. we have:
(y( 92)
(138)
=T (r 92) ry((1,9()
(139)
(T 92) - Prr(Y E Bs
(140)
m) Pr(Y E Bs.)
(T (T-m mmmm- - 1). Pr(Y e Bs.)
(141)
Pr(Y E Bs.)
(142)
We obtain Equation 140 from Equation 139 based on Lemma Therefore, we have the following in both scenarios:
T Ta. gbb Pr(Y E Bs.) )
(143)
T Pr(Y e Bs.)
Ty To 92) v
(144)
T
Based Lemma 7, there exist of o such that ra o8) = Poo Ty1 (5) have the following based on the definition of rr, ry:
Pr(Y
Then,
Pr(X E C'(q,, 92) (C(... gf)) Po.
(145)
22

---

Published as a conference paper at ICLR 2020
Pr(Y E (' (2) C (5)) Pr(Y Bs.)
(146)
We let C. = (11 22) n Clgi, 1 From the definition of C' (11, 92), we have Vij E [e + 1. 92) ni, = 0. Thus, have vjj [e+ L,7 CC, B since Co S (q1 (2).
Therefore, we reach our goal by Mathematical Induction, i.c., for Vj E [1, 7], we have:
Pr(X E Ch.)) = Pbş Pr(Y E Co,) Pr(Y E Bs.)
(147)
(148)
We can also verify that Co Bs.-
Next, show our proof based Mathematical Induction for the other part, i.c., Bs, Bs.. Our construction process is similar to the above first part but has subtle differences.
Step I: Let Ejm Po, and 42 Σラ Pb.. We define:
C'1, C(q1, 92)
Bs.
Bs.
(149)
Then, we have:
rx(91,22 92 91
Σ |=++1
Poş
(150)
T2(91,92)
(151)
=Pr(Y E C'n, (2) (C((, (eln,,100 92))
(152)
=Pr(Y C(0, - Pr(Y E C(n,,
(153)
=Pr(Y& E Bs.) - Pr(Y E Bs.)
(154)
k Pr(Y E Bs.) Pr(Y E Bs.)
(155)
T (k - T) Pr(Y E Bs.)
(156)
The Equation 150 is based on the fact that C' 92) = C(g1, (2) and Definition 1, and obtain
Equation 154 from 155 based on Equation 83. We have Po, I Tx (z(41, 92). Therefore, based on Lemma 7, we know that there exists of G2 Pr. %/ 91 + Ph. such that:
Tí (g g/2 Pbe
(157)
Tí rr q2) = Pbe
(158)
We consider two scenarios.
Scenario 1). In this scenario, consider ry (g' 92) Pr(YEBs,). We let gf 21. -2, i.e.,
have Co. = C(gh 92) (q1, Then, we have:
Pr(X E Co..) = ( 92) = Pon
(159)
Pr(Y Bs.)
Pr(Y E C..,) = ry(s (2)
(160)
Therefore, we have the following:
Pr(Y E C(qi, Cr,,)
(161)
=Pr(Y E ((91.91))
(162)
-Pr(Y C((O, - -Pr(Y E c(),
(163)
-Pr(Y E Bs, - E Bs.)
(164)
(K) T 1) Pr(Y E Bs.)
(165)
23

---

Published as a conference paper at ICLR 2020
Scenario 2). In this scenario, consider (y 92)
Pr(YeBs.) We have the following:
ry(21: 922
(166)
27y (ry 92)
(167)
[1 42
(k: - r) Pr(Y E Bs.)
(168)
T Pr(Y E Bs.)
k k-
(169)
We obtain Equation 167 from 166 via Lemma 9, and we obtain Equation 168 from 167 based on
Σ E K-T. We have (ry(gi: 92)
Equation to 156 and the factr=((1s (e/1:/(11//////// 42)//2(0// (o 1/2) Fy
Pr(YEBs=)) (r (91, (6)) Pr(EBa-)) s 0. Therefore, from Lemma 7, we know that there exist
T (of. .55 such that:
Pr(X E Co.) = = (3) = Pr(Y E Co..) = r s3) Pr(Y E Bs.)
(170)
(171)
We also have the following:
Pr(Y E C(q,, 92) \ Cooe
(172)
=r,(91,9 92) (g s/2) (k - r - 1) Pr(Y E Bs.)
(173)
(174)
Similarly, we let Co. C' 92) C( : og))
Based on the conditions of our constructions in the two scenarios, we know that if Pr(Y E Box) >
Pr(YEBs.) then have o² Q2-
Step II: We show that if we can find (gf .g)).... (gi- k-m++ and Co,, Vj E k m + 1] such that:
.92 ) where m E [L, T 1]
Pr(X E Co.))
Ph; Pr(Y E Bs.)
(175)
Pr(Y E CC,,) 2
(176)
Pr(Y E Clgi, 92) \ U m+ Co,) (k (k-T- m) Pr(Y E Bs,)
(177)
7
Then, we can find (m--m ,92 m) such that:
Pr(X E Cr. m))
Por-m
(178)
Pr(Y E Bs.)
Pr(Y e Cor-m)
(179)
(k (K-T- -1) Pr(Y E Bs.)
Pr(Y E C(q1. 92) \ U k Co,))
(180)
T
mh For simplicity, we denote k m, we q1 91 - Pb; and 02 Σ/ Po. and we define:
C' c'(qn, 42) = C(qi, 92) 18
(181)
Then, have:
(2) Pr(X C(g,, 92) \\ UF
Σ Pb;
(182)
1=
(k 7 m) Pr(Y E Bs.)
ry (91.942) = -Pr(Y E C(q,, 42) \ ( 2
(183)
24

---

Published as a conference paper at ICLR 2020
We have Po, (2((91.92). Therefore, based on Lemma 7, we know that there exists & oá such that:
rx 92) = Pb.
(184)
Tx (9 (2) = Pb.
(185)
Similarly, we consider two scenarios:
Scenario 1). In this scenario, consider that the following holds:
Ty(di: 92) Pr(Y E Bs.)
(186)
T
We let of = -6 92, i.e. Co. = 92) (22))0 n C² (1): 92). Then, we have:
Pr(X E Cb.) = Tx
=T (41, 92) = -bb
(187)
Pr(Y E Co.) = ( 92) 2 Pr(Y Bs.)
(188)
We note that we have of S min ==++ oi in this scenario. Otherwise, Equation 186 will not hold based on Lemma 10. We give short proof.
Assuming & min of. We denote w = g.. We let Cw. Co.,. S Clal,, : )) Note that in this case, we have Ø < 42 because 92 = 92 and gi of cannot hold
at the same time as long as (y(d (2) > O. Thus, we have Pr(Y E C.)) = Pr(YeBs.) because
Pr(Y E C.n) > Pb. I Pr(X E Cw. Pow. We have the following based on Lemma 10:
Pr(YEBs.) we have 93" = 92- As we have 4i > q/" 99 > 9 and ra (21.9)))
7
ry( S Pr(YY E Cw)) = Pr(Y Bs-)
(189)
T
Since Equation 186 and Equation 189 cannot hold at the same time, the assumption of > min j= of must be wrong. Therefore, have of I minj-k-m+1 o7.
Based on of S
G. we have the following:
C' (2) n C(gi. Φ) C(q1.9/) 9
(190)
Therefore, we have rz(q1. ④ = di a1 from Definition 1. Moreover, we have the following:
(191)
1r 92) r 92)
(192)
Σ Pb, Pb.
(193)
e-1
Σ To;
(194)
#=1+1
The above should be equal. Therefore, we have of E5= Pb; +
Σ5= Pb.-
Pb.. Recall
that we let Co_ = (2()), C((g 92). Thus, we have:
Pr(Y E C(q1, \ C)
(195)
=Pr(Y E C2()1, \ \Ca.)
(196)
-Pr(Y E c(q1,g1))
(197)
-Pr(Y E C((0, g)) - -Pr(Y E C(O,
(198)
-Pr(Y E Bs._)) -Pr(Y Bs.)
(199)
( 1) Pr(YY E Bs.)
(200)
Scenario 2). this scenario, we consider that the following holds:
Pr(Y E Bs.) )
Ty (o/. g2) <
(201)
T
25

---

Published as a conference paper at ICLR 2020
Note that we have:
Ty(q (22
(202)
1
2ry 2rg(91.02) 92)
(203)
(r=(91,92)/ra (2)/r=((1, 92)
1
2ry(qi, 92)
(204)
h - m
Pr(Y E Bg,) T
(205)
We obtain Equation 203 from 202 via Lemma 9, and we obtain Equation 204 from 203 based on Equation 183 and the fact r= (91 (2),12))////0 / (21.1111)) 922 Ejar+1
Pbr41 2 k T m. We have (ry 92)
Pr(YeBs))) (ry(gi, (6) P)(YEBg.) < 0. Based on Lemma 7, can find (99 9 such that we
have: 7
Pr(X E (² 92) n C((gi, Txlgi, (5) =
Poo
(206)
Pr(Y Bs.)
Pr(Y E C' (g), 92) n (C (((i.19) ( = Ty (gi 95)
(207)
We let Co. = (c( (5). We also have the following:
Pr(Y E C(qi, 92) \ Co,)
(208)
-Pr(Y E (2), (C,)
(209)
[g, 92) (9)
(210)
(k T - m) Pr(Y E Bs,) Pr(Y E Bs.)
(211)
(k r 1) Pr(Y E Bs.)
(212)
Similar to Step we still hold the conclusion that Pr(Y E Co.) Pr(Y we have gf 42. Then, we can apply Mathematical Induction to reach the conclusion. Also, we can verify U Cb,, Bs, \ Bs..
C PROOF OF PROPOSITION ]
The function SAMPLEUNDERNOISE/// ki, o, X. n, a.) works as follows: we first draw n random noise from V(0,a²T), i.e., 61, ,nn- Then, compute the values: Vi [1, G
Ej= [([(x + ()) = i). The function BINOMPVALUR(MPe, Re, + Pe returns the result of p-value of the two-sided hypothesis test for nee Bin(na, + :).1.
Proposition With probability at least over the randomness in PREDICT, if PREDICT returns set T (i.e., does not ABSTAIN), then we have ga (x) = T.
Proof. We aim compute the probability that PREDICT returns which not equals gı (x), which happens if and only if gu (x) + T and PREDICT doesn't 't abstain. Specifically, we have:
Pr(PREDICT returns a set * (x)))
(213)
=x)(g(()) * T, PREDICT doesn't abstain)
(214)
-ri(g (x) TT) Pr(PREDICT doesn't 't abstain (x) + T)
(215)
<Pr(PREDICT doesn't 't abstain (x) + T')
(216)
Theorem in Hung al. (2019) shows the above conditional probability is follows:
Pr(PRDIICT doesn't abstain (x) F S a
(217)
Therefore, reach the conclusion.
n
26

---

Published as a conference paper at ICLR 2020
D PROOF OF PROPOSITION 2
Proposition 2: With probability at least 1 - a over the randomness in CERTIFY, if CERTIFY returns
radius R2 (i.e., does not ABSTAIN), then have É 9l (x + 8), 4 1 < Ra.
Proof. From the definition of BINOCP and SIMUEM, we know the probability that the following inequalities simultaneously hold is at least a over the sampling of counts:
ps P. 2 c)
(218)
(219)
Then, with the returned bounds, invoke Theorem to obtain the robustness guarantee if the calculated radius is larger than O. Note that otherwise CERTIFY abstains.
E CERTIFIED TOP-K ACCURACY
We show how to derive a lower bound of the certified top-k accuracy based on the approximate certified top-k accuracy. The process similar that Cohen al. (2019) used derive lower bound the certified top-1 accuracy based on the approximate certified top-1 accuracy. Specifically, have the following lemma from Cohen al. (2019).
Let be binary variable and Y, be Bernoulli random variable. Suppose 1, then Pr(Y; = 1) S a. Then, for any > O, with probability at least 1 - p. we have the following:
Lemma 11.
1
Σ 11
Vi
2a a) log p log(?)
(220)
1
3m
Proof. Please refer to Cohen et al. (2019).
Assuming we have test dataset Drest = {(x1, (x2, (x2, 12), (Xms (mm) as well as a radius r. We define the following indicate value:
a = I(H E (x + 6)), V|18||2 <
(221)
Then, the certified top-k accuracy of the smoothed classifier g at radius can be computed as 1 Σ 0g For each sample x,, mi
the CERTIFY function with 1 confidence level and we use a random variable Y; to denote that the function CERTIFY returns a radius bigger than r. From Proposition 2, we know:
Pr(Y; 1) < a
(222)
The approximate certified top-k accuracy the smoothed classifier radius r 1 m Y. Then, we can use Lemma to obtain a lower bound of 1 Em a. Specifically, for any P 0, with probability least 1 p over the randomness of CERTIFY, have:
m
m
1
m i
Y,
20(1 a) log 1
log(
04
(223)
m
3m
We that the difference between the certified top-k accuracy and the approximate certified top-k accuracy negligible when a is small.
27


Reviews:
[{"review_id": "SkgZDld6Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper builds upon the random smoothing technique for top-1 prediction proposed by Cohen et al. for certifying top-k predictions with probabilistic guarantees, which enjoys good scalability to large neural networks and in principle can be applied to any classifier. \n\n- Contributions:\n1. The authors aim to provide (probabilistic) certification on top-k predictions, which to my knowledge is the first work to consider this setup. Many applications such as recommendation systems indeed use top-k predictions as a performance measure. The problem setup is new and important in the research of robustness certification.\n\n2. In terms of technical contributions, the authors identify the difficulty of extending top-1 prediction to top-k prediction, due to the requirement of simultaneous confidence interval estimation of the bounds on the actual class predictions. To cope with this difficulty, the authors proposed simultaneous confidence interval estimation based on Clopper-Pearson method and Bonferroni correction. However, I am not sure the difficulty is caused by the necessity of estimating multiple probability bounds, or simply the limitation of the proposed algorithm. I hope the authors can address my concerns in the Questions below. \n\n3. Experimental results on Cifar-10 and ImageNet showed improved lower bound on certified L2-norm radius when increasing k. The authors also performed an ablation study of different parameters in the proposed algorithm.\n\n- Questions:\n1. Intuitively, when extending top-1 certification to top-k certification, one would expect using ordered statistics of the prediction outputs from the randomly perturbed inputs. As long as the original label's prediction probability is in the top-k label set, the smoothed classifier is directly certified. Instead of ordered statistics, the authors tackle this problem by considering estimating upper and lower bounds of each class prediction probability. Therefore, the problem becomes more difficult as k increases, since this indirect approach needs to simultaneous estimate those probability bounds. I wonder the current approach will be suboptimal when compared to the ordered statistics approach. I would like to know the authors thoughts on this regard. That is, is the claimed difficulty an outcome when using the proposed indirect bound estimation for certification, or it's provably more difficult?\n\n2. The discussion on Fig.3 says \"We observe that \u001b \\sigma controls a trade-off between normal accuracy under no attacks and robustness. Specifically, when \u001b is larger, the accuracy under no attacks (i.e., the accuracy when radius is 0) is larger, but the certified top-k accuracy drops more quickly as the radius increases.\" However, it seems that larger \\sigma actually gives lower accuracy under no attacks in Figure 3. Please clarify.\n\nOverall, this paper brings some new insights and results in robustness certification, but some claims and statements need to be further justified. I am happy to increase my rating if my concerns are addressed. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyxynw6pFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper studies the certifiable bounds for adversarial perturbations in \\ell_2 radius for top-k predictions instead of top-1 predictions.  The paper obtains a certifiable radius of \\ell_2 perturbations in the case of top-k predictions (Theorem 1) and shows that the bounds are tight (Theorem 2). The result thus generalizes the results obtained in Cohen et al. (2019) by setting k=1.\nSince Theorem 1 requires lower and upper bounds, the paper proposes two methods for calculating the bounds on multinomial probabilities. Experimental evidence suggests that one indeed obtains a better certifiable radius for the top-k radius vs. the top-1 radius.\n\nMy evaluation of the paper is positive: The theoretical results (Theorem 1 and 2) are new and study practical use cases of these models. The experimental results (Figure 1) support the claim that there is a non-trivial difference between the certified radii of top-1 and top-k predictions.  \nHowever, the level of technical novelty is relatively low. The proof of Theorem 1 follows the similar procedure for top-1 predictions and the methods proposed for estimating probabilities (BinoCP and SinuEM) are standard procedures.  \n\nOther comments:\n\n1. What is the trend of top-k-clean-accuracy and top-k-adversarial-accuracy as a function of k? Is this trend similar across different radii? \n\n2. What is the value of k in Figure 3 and Figure 4?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkxarun2tB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary.\nThe paper proposes an extension to the work of Cohen et al. where a certified radius is deduced using a randomized smoothing approach. In particular, the authors show the radius at which a smoothed classifier g at under Gaussian perturbations is certified for the top k predictions. That is to say that the prediction will remain within the top k predictions of g. Setting k=1, one recovers Cohen et al. results. The authors show that the derived radius is tight.\n\nComments.\n\nI generally find the work interesting and I do not have any major criticism. The paper is also easy to read. I did not go through the tightness proof but I skimmed through proof of the certified radius and I find that the argument follows in a similar fashion to previous works using NP lemma.\n\nMay the authors comment on the following.\n\na) How does the method scale with k? - speedwise particularly when estimating the lower and upper bounds of the output probabilities.\n\nb) I do not understand Figure 3. Can the authors comment why for the radius = 0 the certified accuracy of the larger sigma (1.0) is actually worse than the smaller sigma? At least when k=1, increasing sigma increases the certified radius in which I expect to see that most of the samples to be actually within the radius and it should perform much better than lower sigma {0.25,0.5}. \n\nc) Based on the previous comment, I find the performance in Figure 3 in not consistent with the authors' discussion in page 7 \"when sigma is larger, the accuracy under no attacks (i.e. the accuracy when radius is 9) is larger .. \".\n\nd) Authors use bisection to find the solution to the certified accuracy for every t. Bisection is known to only enjoy linear convergence rate. Have the authors considered using algorithms that are much faster such as the sueprlinear secant method?\n\ne) Page 3 bullet point 3. \"it is impossible to certify a L_2 radius\" >> \"it is impossible to certify an \\ell_2 radius\". Consider changing all L_2 to \\ell_2.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends the work on randomized smoothing for certifiably robust classifiers developed in prior work to a weaker specification requiring that the set of top-k predictions remain unchanged under adversarial perturbations of the input (rather than just the top-1). This enables the authors to achieve stronger results on robustness of classifiers on CIFAR10 and ImageNet (where the authors report the top-5 accuracy).

This is an interesting extension of certified defenses that is likely to be relevant for complex prediction tasks with several classes (ImageNet and beyond), where top-1 robustness may be difficult and unrealistic to achieve.

The reviewers were in consensus on acceptance and minor concerns were alleviated during the rebuttal phase.

I therefore recommend acceptance.
Decision: Accept (Poster)