summaries: The 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.

summaries: This 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.

abstractText: 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 `2 norm for topk 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 `2-norms of the adversarial perturbations are less than 0.5 (=127/255). Our code is publicly available at: https://github.com/jjy1994/Certify_Topk.

authors:
Cem Anil
James Lucas
Roger Grosse

title: Sorting out lipschitz function approximation

venue: In International Conference on Machine Learning,

authors:
Anish Athalye
Nicholas Carlini

title: 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

authors:
Anish Athalye
Nicholas Carlini
David Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

authors:
Jacob Buckman
Aurko Roy
Colin Raffel
Ian Goodfellow

title: Thermometer encoding: One hot way to resist adversarial examples

venue: In ICLR,

authors:
Rudy R Bunel
Ilker Turkaslan
Philip Torr
Pushmeet Kohli
Pawan K Mudigonda

title: A unified view of piecewise linear neural network verification

venue: In Advances in Neural Information Processing Systems,

authors:
Xiaoyu Cao
Neil Zhenqiang Gong

title: Mitigating evasion attacks to deep neural networks via region-based classification

venue: In Proceedings of the 33rd Annual Computer Security Applications Conference,

authors:
Nicholas Carlini
David Wagner

title: Adversarial examples are not easily detected: Bypassing ten detection methods

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Nicholas Carlini
Guy Katz
Clark Barrett
David L Dill

title: Provably minimally-distorted adversarial examples

venue: arXiv preprint arXiv:1709.10207,

authors:
Chih-Hong Cheng
Georg Nührenberg
Harald Ruess

title: Maximum resilience of artificial neural networks

venue: In International Symposium on Automated Technology for Verification and Analysis,

authors:
Moustapha Cisse
Piotr Bojanowski
Edouard Grave
Yann Dauphin
Nicolas Usunier

title: Parseval networks: Improving robustness to adversarial examples

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Jeremy M Cohen
Elan Rosenfeld
J Zico Kolter

title: Certified adversarial robustness via randomized smoothing

venue: arXiv preprint arXiv:1902.02918,

authors:
Francesco Croce
Maksym Andriushchenko
Matthias Hein

title: Provable robustness of relu networks via maximization of linear regions

venue: In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: IEEE conference on computer vision and pattern recognition,

authors:
Guneet S Dhillon
Kamyar Azizzadenesheli
Zachary C Lipton
Jeremy Bernstein
Jean Kossaifi
Aran Khanna
Anima Anandkumar

title: Stochastic activation pruning for robust adversarial defense

authors:
Souradeep Dutta
Susmit Jha
Sriram Sanakaranarayanan
Ashish Tiwari

title: Output range analysis for deep neural networks

venue: arXiv preprint arXiv:1709.09130,

authors:
Krishnamurthy Dvijotham
Sven Gowal
Robert Stanforth
Relja Arandjelovic
Brendan O’Donoghue
Jonathan Uesato
Pushmeet Kohli

title: Training verified learners with learned verifiers

venue: arXiv preprint arXiv:1805.10265,

authors:
Krishnamurthy Dvijotham
Robert Stanforth
Sven Gowal
Timothy A Mann
Pushmeet Kohli

title: A dual approach to scalable verification of deep networks

venue: In UAI,

title: Formal verification of piece-wise linear feed-forward neural networks

authors:
Matteo Fischetti
Jason Jo

title: Deep neural networks and mixed integer linear optimization

authors:
Timon Gehr
Matthew Mirman
Dana Drachsler-Cohen
Petar Tsankov
Swarat Chaudhuri
Martin Vechev

title: Ai2: Safety and robustness certification of neural networks with abstract interpretation

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: In International Conference on Learning Representations,

title: On simultaneous confidence intervals for multinomial proportions

venue: Technometrics, 7(2):247–254,

authors:
Henry Gouk
Eibe Frank
Bernhard Pfahringer
Michael Cree

title: Regularisation of neural networks by enforcing lipschitz continuity

venue: arXiv preprint arXiv:1804.04368,

authors:
Sven Gowal
Krishnamurthy Dvijotham
Robert Stanforth
Rudy Bunel
Chongli Qin
Jonathan Uesato
Timothy Mann
Pushmeet Kohli

title: On the effectiveness of interval bound propagation for training verifiably robust models

venue: arXiv preprint arXiv:1810.12715,

authors:
Chuan Guo
Mayank Rana
Moustapha Cisse
Laurens Van Der Maaten

title: Countering adversarial images using input transformations

authors:
Xiaowei Huang
Marta Kwiatkowska
Sen Wang
Min Wu

title: Safety verification of deep neural networks

venue: In International Conference on Computer Aided Verification,

authors:
Kenneth Hung
William Fithian

title: Rank verification for exponential families

venue: The Annals of Statistics,

authors:
Jinyuan Jia
Neil Zhenqiang Gong

title: AttriGuard: A practical defense against attribute inference attacks via adversarial machine learning

venue: In USENIX Security Symposium,

authors:
Guy Katz
Clark Barrett
David L Dill
Kyle Julian
Mykel J Kochenderfer

title: Reluplex: An efficient smt solver for verifying deep neural networks

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alexey Kurakin
Ian J. Goodfellow
Samy Bengio

title: Adversarial machine learning at scale

authors:
Mathias Lecuyer
Vaggelis Atlidakis
Roxana Geambasu
Daniel Hsu
Suman Jana

title: Certified robustness to adversarial examples with differential privacy

venue: In IEEE Symposium on Security and Privacy (SP),

authors:
Guang-He Lee
Yang Yuan
Shiyu Chang
Tommi Jaakkola

title: Tight certificates of adversarial robustness for randomly smoothed classifiers

authors:
Bai Li
Changyou Chen
Wenlin Wang
Lawrence Carin

title: Second-order adversarial attack and certifiable robustness

venue: arXiv preprint arXiv:1809.03113,

authors:
Xuanqing Liu
Minhao Cheng
Huan Zhang
Cho-Jui Hsieh

title: Towards robust neural networks via random self-ensemble

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Xuanqing Liu
Yao Li
Chongruo Wu
Cho-Jui Hsieh

title: Adv-bnn: Improved adversarial defense through robust bayesian neural network

authors:
Alessio Lomuscio
Lalit Maganti

title: An approach to reachability analysis for feed-forward relu neural networks

venue: arXiv preprint arXiv:1706.07351,

authors:
Xingjun Ma
Bo Li
Yisen Wang
Sarah M Erfani
Sudanthi Wijewickrema
Grant Schoenebeck
Dawn Song
Michael E Houle
James Bailey

title: Characterizing adversarial subspaces using local intrinsic dimensionality

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

authors:
Dongyu Meng
Hao Chen

title: Magnet: a two-pronged defense against adversarial examples

venue: In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security,

authors:
Jan Hendrik Metzen
Tim Genewein
Volker Fischer
Bastian Bischoff

title: On detecting adversarial perturbations

authors:
Matthew Mirman
Timon Gehr
Martin Vechev

title: Differentiable abstract interpretation for provably robust neural networks

authors:
Taesik Na
Jong Hwan Ko
Saibal Mukhopadhyay

title: Cascade adversarial machine learning regularized with a unified embedding

authors:
Jerzy Neyman
Egon Sharpe Pearson

title: On the problem of the most efficient tests of statistical hypotheses

venue: Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character,

authors:
Nicolas Papernot
Patrick McDaniel
Xi Wu
Somesh Jha
Ananthram Swami

title: Distillation as a defense to adversarial perturbations against deep neural networks

venue: In 2016 IEEE Symposium on Security and Privacy (SP),

authors:
Rafael Pinot
Laurent Meunier
Alexandre Araujo
Hisashi Kashima
Florian Yger
Cedric GouyPailler
Jamal Atif

title: Theoretical evidence for adversarial robustness through randomization

authors:
Aditi Raghunathan
Jacob Steinhardt
Percy Liang

title: Certified defenses against adversarial examples

authors:
Aditi Raghunathan
Jacob Steinhardt
Percy S Liang

title: Semidefinite relaxations for certifying robustness to adversarial examples

authors:
Hadi Salman
Jerry Li
Ilya Razenshteyn
Pengchuan Zhang
Huan Zhang
Sebastien Bubeck
Greg Yang

title: Provably robust deep learning via adversarially trained smoothed classifiers

authors:
Pouya Samangouei
Maya Kabkab
Rama Chellappa

title: Defense-gan: Protecting classifiers against adversarial attacks using generative models

authors:
Lukas Schott
Jonas Rauber
Matthias Bethge
Wieland Brendel

title: Towards the first adversarially robust neural network model on mnist

authors:
Gagandeep Singh
Timon Gehr
Matthew Mirman
Markus Püschel
Martin Vechev

title: Fast and effective robustness certification

authors:
Cristina P Sison
Joseph Glaz

title: Simultaneous confidence intervals and sample size determination for multinomial proportions

venue: Journal of the American Statistical Association,

authors:
Yang Song
Taesup Kim
Sebastian Nowozin
Stefano Ermon
Nate Kushman

title: Pixeldefend: Leveraging generative models to understand and defend against adversarial examples

authors:
Jan Svoboda
Jonathan Masci
Federico Monti
Michael M Bronstein
Leonidas Guibas

title: Peernets: Exploiting peer wisdom against adversarial attacks

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Vincent Tjeng
Kai Xiao
Russ Tedrake

title: Evaluating robustness of neural networks with mixed integer programming

venue: In ICML,

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian Goodfellow
Dan Boneh
Patrick McDaniel

title: Ensemble adversarial training: Attacks and defenses

authors:
Yusuke Tsuzuku
Issei Sato
Masashi Sugiyama

title: Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks

authors:
Jonathan Uesato
Brendan O’Donoghue
Pushmeet Kohli
Aaron Oord

title: Adversarial risk and the dangers of evaluating against weak attacks

authors:
Shiqi Wang
Yizheng Chen
Ahmed Abdou
Suman Jana

title: Mixtrain: Scalable training of formally robust neural networks

venue: arXiv preprint arXiv:1811.02625,

authors:
Shiqi Wang
Kexin Pei
Justin Whitehouse
Junfeng Yang
Suman Jana

title: Efficient formal safety analysis of neural networks

authors:
Tsui-Wei Weng
Huan Zhang
Hongge Chen
Zhao Song
Cho-Jui Hsieh
Duane Boning
Inderjit S Dhillon
Luca Daniel

title: Towards fast computation of certified robustness for relu networks

venue: arXiv preprint arXiv:1804.09699,

authors:
Eric Wong
Zico Kolter

title: Provable defenses against adversarial examples via the convex outer adversarial polytope

authors:
Eric Wong
Frank Schmidt
Jan Hendrik Metzen
J Zico Kolter

title: Scaling provable adversarial defenses

authors:
Cihang Xie
Jianyu Wang
Zhishuai Zhang
Zhou Ren
Alan Yuille

title: Mitigating adversarial effects through randomization

authors:
Weilin Xu
David Evans
Yanjun Qi

title: Feature squeezing: Detecting adversarial examples in deep neural networks

venue: In NDSS,

authors:
Huan Zhang
Tsui-Wei Weng
Pin-Yu Chen
Cho-Jui Hsieh
Luca Daniel

title: Efficient neural network robustness certification with general activation functions

title: Lemma 2. Given an example x, a number q ∈ [0, 1], and regions A and B defined as follows: A = {z : δ (z−

title: Assuming we have a test dataset

heading: 1 INTRODUCTION

text:
Classifiers are vulnerable to adversarial perturbations (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017b; Jia & Gong, 2018). Specifically, given an example x and a classifier f , an attacker can carefully craft a perturbation δ such that f makes predictions for x + δ as the attacker desires. Various empirical defenses (e.g., Goodfellow et al. (2015); Svoboda et al. (2019); Buckman et al. (2018); Ma et al. (2018); Guo et al. (2018); Dhillon et al. (2018); Xie et al. (2018); Song et al. (2018)) have been proposed to defend against adversarial perturbations. However, these empirical defenses were often soon broken by adaptive adversaries (Carlini & Wagner, 2017a; Athalye et al., 2018). As a response, certified robustness (e.g., Wong & Kolter (2018); Raghunathan et al. (2018a); Liu et al. (2018); Lecuyer et al. (2019); Cohen et al. (2019)) against adversarial perturbations has been developed. In particular, a robust classifier verifiably predicts the same top-1 label for data points in a certain region around any example x.
In many applications such as recommender systems, web search, and image classification cloud service (Clarifai; Google Cloud Vision), top-k predictions are more relevant. In particular, given an example, a set of k most likely labels are predicted for the example. However, existing certified robustness results are limited to top-1 predictions, leaving top-k robustness unexplored. To bridge this gap, we study certified robustness for top-k predictions in this work. Our certified top-k robustness leverages randomized smoothing (Cao & Gong, 2017; Cohen et al., 2019), which turns any base classifier f to be a robust classifier via adding random noise to an example. For instance, Cao & Gong (2017) is the first to propose randomized smoothing with uniform noise as an empirical defense. We consider random Gaussian noise because of its certified robustness guarantee (Cohen et al., 2019). Specifically, we denote by pi the probability that the base classifier f predicts label i for the Gaussian random variable N (x, σ2I). The smoothed classifier gk(x) predicts the k labels with the largest probabilities pi’s for the example x. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any base classifier.
Our major theoretical result is a tight certified robustness bound for top-k predictions when using randomized smoothing with Gaussian noise. Specifically, given an example x, a label l is verifiably among the top-k labels predicted by the smoothed classifier gk(x + δ) when the `2-norm of the adversarial perturbation δ is less than a threshold (called certified radius). The certified radius for top-1 predictions derived by Cohen et al. (2019) is a special case of our certified radius when k = 1. As our results and proofs show, generalizing certified robustness from top-1 to top-k predictions faces significant new challenges and requires new techniques. Our certified radius is the unique solution to an equation, which depends on σ, pl, and the k largest probabilities pi’s (excluding pl). However, computing our certified radius in practice faces two challenges: 1) it is hard to exactly compute the probability pl and the k largest probabilities pi’s, and 2) the equation about the certified radius does not have an analytical solution. To address the first challenge, we estimate simultaneous confidence intervals of the label probabilities via the Clopper-Pearson method and Bonferroni correction in statistics. To address the second challenge, we propose an algorithm to solve the equation to obtain a lower bound of the certified radius, where the lower bound can be tuned to be arbitrarily close to the true certified radius. We evaluate our method on CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009) datasets. For instance, on ImageNet, our method respectively achieves approximate certified top-1, top-3, and top-5 accuracies as 46.6%, 57.8%, and 62.8% when the `2-norms of the adversarial perturbations are less than 0.5 (127/255) and σ = 0.5.
Our contributions are summarized as follows:
• Theory. We derive the first certified radius for top-k predictions. Moreover, we prove our certified radius is tight for randomized smoothing with Gaussian noise. • Algorithm. We develop algorithms to estimate our certified radius in practice. • Evaluation. We empirically evaluate our method on CIFAR10 and ImageNet.
2 CERTIFIED RADIUS FOR TOP-k PREDICTIONS
Suppose we have a base classifier f , which maps an example x ∈ Rd to one of c candidate labels {1, 2, · · · , c}. f can be any classifier. Randomized smoothing (Cohen et al., 2019) adds an isotropic Gaussian noise N (0, σ2I) to an example x. We denote pi as the probability that the base classifier f predicts label i when adding a random isotropic Gaussian noise to the example x, i.e., pi = Pr(f(x + ) = i), where ∼ N (0, σ2I). The smoothed classifier gk(x) returns the set of k labels with the largest probabilities pi’s when taking an example x as input. Our goal is to derive a certified radius Rl such that we have l ∈ gk(x + δ) for all ||δ||2 < Rl. Our main theoretical results are summarized in the following two theorems. Theorem 1 (Certified Radius for Top-k Predictions). Suppose we are given an example x, an arbitrary base classifier f , ∼ N (0, σ2I), a smoothed classifier g, an arbitrary label l ∈ {1, 2, · · · , c}, and pl, p1, · · · , pl−1, pl+1, · · · , pc ∈ [0, 1] that satisfy the following conditions:
Pr(f(x + ) = l) ≥ pl and Pr(f(x + ) = i) ≤ pi,∀i 6= l, (1)
where p and p indicate lower and upper bounds of p, respectively. Let pbk ≥ pbk−1 ≥ · · · ≥ pb1 be the k largest ones among {p1, · · · , pl−1, pl+1, · · · , pc}, where ties are broken uniformly at random. Moreover, we denote by St = {b1, b2, · · · , bt} the set of t labels with the smallest probability upper bounds in the k largest ones and by pSt = ∑t j=1 pbj the sum of the t probability upper bounds, where t = 1, 2, · · · , k. Then, we have:
l ∈ gk(x + δ),∀||δ||2 < Rl, (2)
where Rl is the unique solution to the following equation:
Φ(Φ−1(pl)− Rl σ ))− k min t=1
Φ(Φ−1(pSt) + Rl σ ))
t = 0, (3)
where Φ and Φ−1 are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively.
Proof. See Appendix A.
Algorithm 1: PREDICT Input: f , k, σ, x, n, and α. Output: ABSTAIN or predicted top-k labels.
1 T = ∅ 2 counts = SAMPLEUNDERNOISE(f, σ,x, n) 3 c1, c2, · · · , ck+1 = top-{k + 1} indices in counts (ties are broken uniformly at random) 4 nc1 , nc2 , · · · , nck+1 = counts[c1], counts[c2], · · · , counts[ck+1] 5 for t← 1 to k do 6 if BINOMPVALUE(nct , nct + nct+1 , 0.5) ≤ α then 7 T = T ∪ ct 8 else 9 return ABSTAIN
10 return T
Theorem 2 (Tightness of the Certified Radius). Assuming we have pl + ∑k j=1 pbj ≤ 1 and pl +∑
i=1,··· ,l−1,l+1,··· ,c pi ≥ 1. Then, for any perturbation ||δ||2 > Rl, there exists a base classifier f∗ consistent with (1) but we have l /∈ gk(x + δ).
Proof. We show a 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 + 1 disjoint regions Ci, i ∈ {l}∪ {b1, b2, · · · , bk} that satisfy Pr(x+ ∈ Cl) = pl, Pr(x+ ∈ Ci) = pi, and Pr(x + δ + ∈ Ci) is no smaller than some critical value for i ∈ {b1, b2, · · · , bk}. Moreover, we divide the remaining region Rd \ (∪i=l,b1,b2,··· ,bkCi) into c− k− 1 regions, which we denote as Cbk+1 , Cbk+2 , · · · , Cbc−1 and satisfy Pr(x + ∈ Ci) ≤ pi for i = bk+1, bk+2, · · · , bc−1. Then, we construct a base classifier f∗ that predicts label i for an example if and only if the example is in the region Ci, where i ∈ {1, 2, · · · , c}. As pl + ∑k j=1 pbj ≤ 1 and pl + ∑ i=1,··· ,l−1,l+1,··· ,c pi ≥ 1, f∗ is well-defined. Moreover, f∗ satisfies the conditions in (1). Finally, we show that if ||δ||2 > Rl, then we have Pr(f∗(x + δ + ) = l) < minkj=1 Pr(f ∗(x + δ + ) = bj), i.e., l /∈ gk(x + δ).
We have several observations about our theorems.
• Our certified radius is applicable to any base classifier f . • According to Equation 3, our certified radius Rl depends on σ, pl, and the k largest prob-
ability upper bounds {pbk , pbk−1 , · · · , pb1} excluding pl. When the lower bound pl and the upper bounds {pbk , pbk−1 , · · · , pb1} are tighter, the certified radius Rl is larger. When Rl < 0, the label l is not among the top-k labels predicted by the smoothed classifier even if no perturbation is added, i.e., l /∈ gk(x). • When using randomized smoothing with Gaussian noise and no further assumptions are
made on the base classifier, it is impossible to certify a `2 radius for top-k predictions that is larger than Rl. • When k = 1, we have Rl = σ2 (Φ −1(pl)− Φ−1(pb1)), where pb1 is an upper bound of the
largest label probability excluding pl. The certified radius derived by Cohen et al. (2019) for top-1 predictions (i.e., their Equation 3) is a special case of our certified radius with k = 1, l = A, and b1 = B.

heading: 3 PREDICTION AND CERTIFICATION IN PRACTICE

heading: 3.1 PREDICTION

text:
It is challenging to compute the top-k labels gk(x) predicted by the smoothed classifier, because it is challenging to compute the probabilities pi’s exactly. To address the challenge, we resort to a Monte Carlo method that predicts the top-k labels with a probabilistic guarantee. In particular, we leverage the hypothesis testing result from a recent work (Hung et al., 2019). Algorithm 1
shows our PREDICT function to estimate the top-k labels predicted by the smoothed classifier. The function SAMPLEUNDERNOISE(f, σ,x, n) first randomly samples n noise 1, 2, · · · , n from the Gaussian distribution N (0, σ2I), uses the base classifier f to predict the label of x + j for each j ∈ {1, 2, · · · , n}, and returns the frequency of each label, i.e., counts[i] = ∑n j=1 I(f(x + j) = i) for i ∈ {1, 2, · · · , c}. The function BINOMPVALUE performs the hypothesis testing to calibrate the abstention threshold such that we can bound with probability α of returning an incorrect set of top-k labels. Formally, we have the following proposition:
Proposition 1. With probability at least 1−α over the randomness in PREDICT, if PREDICT returns a set T (i.e., does not ABSTAIN), then we have gk(x) = T .
Proof. See Appendix C.

heading: 3.2 CERTIFICATION

text:
Given a base classifier f , an example x, a label l, and the standard deviation σ of the Gaussian noise, we aim to compute the certified radius Rl. According to our Equation 3, our Rl relies on a lower bound of pl, i.e., pl, and the upper bound of pSt , i.e., pSt , which are related to f , x, and σ. We first discuss two Monte Carlo methods to estimate pl and pSt with probabilistic guarantees. However, given pl and pSt , it is still challenging to exactly solve Rl as the Equation 3 does not have an analytical solution. To address the challenge, we design an algorithm to obtain a lower bound of Rl via solving Equation 3 through binary search. Our lower bound can be tuned to be arbitrarily close to Rl.
3.2.1 ESTIMATING pl AND pSt
Our approach has two steps. The first step is to estimate pl and pi for i 6= l. The second step is to estimate pSt using pi for i 6= l.
Estimating pl and pi for i 6= l: The probabilities p1, p2, · · · , pc can be viewed as a multinomial distribution over the labels {1, 2, · · · , c}. If we sample a Gaussian noise uniformly at random, then the label f(x + ) can be viewed as a sample from the multinomial distribution. Therefore, estimating pl and pi for i 6= l is essentially a one-sided simultaneous confidence interval estimation problem. In particular, we aim to estimate these bounds with a confidence level at least 1 − α. In statistics, Goodman (1965); Sison & Glaz (1995) are well-known methods for simultaneous confidence interval estimations. However, these methods are insufficient for our problem. Specifically, Goodman’s method is based on Chi-square test, which requires the expected count for each label to be no less than 5. We found that this is usually not satisfied, e.g., ImageNet has 1,000 labels, some of which have close-to-zero probabilities and do not have more than 5 counts even if we sample a large number of Gaussian noise. Sison & Glaz’s method guarantees a confidence level of approximately 1 − α, which means that the confidence level could be (slightly) smaller than 1 − α. However, we aim to achieve a confidence level of at least 1 − α. To address these challenges, we discuss two confidence interval estimation methods as follows:
1) BinoCP. This method estimates pl using the standard one-sided Clopper-Pearson method and treats pi as pi = 1 − pl for each i 6= l. Specifically, we sample n random noise from N (0, σI2), i.e., 1, 2, · · · , n. We denote the count for the label l as nl = ∑n j=1 I(f(x + j) = l). nl follows a binomial distribution with parameters n and pl, i.e., nl ∼ Bin(n, pl). Therefore, according to the Clopper-Pearson method, we have:
pl = B(α;nl, n− nl + 1), (4)
where 1 − α is the confidence level and B(α;u, v) is the αth quantile of the Beta distribution with shape parameters u and v. We note that the Clopper-Pearson method was also adopted by Cohen et al. (2019) to estimate label probability for their certified radius of top-1 predictions.
2) SimuEM. The above method estimates pi as 1 − pl, which may be conservative. A conservative estimation makes the certified radius smaller than what it should be. Therefore, we introduce SimuEM to directly estimate pi together with pl. We let ni = ∑n j=1 I(f(x + j) = i) for each i ∈ {1, 2, · · · , c}. Each ni follows a binomial distribution with parameters n and pi. We first use
Algorithm 2: CERTIFY Input: f , k, σ, x, l, n, µ, and α. Output: ABSTAIN or Rl.
1 counts = SAMPLEUNDERNOISE(f, σ,x, n, α) 2 [pl, p1, · · · , pl−1, pl+1, · · · , pc] = BINOCP(counts, α) or SIMUEM(counts, α) 3 Rl = 0 4 for t← 1 to k do 5 pSt = min( ∑t j=1 pbj , 1− pl) 6 Rl t =BINARYSEARCH( pl, pSt , t, σ, µ) 7 if Rlt > Rl then 8 Rl = Rl t
9 if Rl > 0 then 10 return Rl 11 else 12 return ABSTAIN
the Clopper-Pearson method to estimate a 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 a confidence interval with confidence level at least 1− αc for each label i, then Bonferroni correction tells us that the overall confidence level for the simultaneous confidence intervals is at least 1− α, i.e., we 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-Pearson method with confidence level 1− αc to each label:
pl = B (α c ;nl, n− nl + 1 )
(5)
pi = B(1− α
c ;ni + 1, n− ni), ∀i 6= l. (6)
Estimating pSt : One natural method is to estimate pSt = ∑t j=1 pbj . However, this bound may be loose. For example, when using BinoCP to estimate the probability bounds, we have pSt = t · (1− pl), which may be bigger than 1. To address the challenge, we derive another bound for pSt from another perspective. Specifically, we have pSt ≤ ∑ i 6=l pi ≤ 1 − pl. Therefore, we can use 1− pl as an upper bound of pSt , i.e., pSt = 1− pl. Finally, we combine the above two estimations by taking the minimal one, i.e., pSt = min( ∑t j=1 pbj , 1− pl).
3.2.2 ESTIMATING A LOWER BOUND OF THE CERTIFIED RADIUS Rl
It is challenging to compute the certified radius Rl exactly because Equation 3 does not have an analytical solution. To address the challenge, we design a method to estimate a lower bound of Rl that can be tuned to be arbitrarily close to Rl. Specifically, we first approximately solve the following equation for each t ∈ {1, 2, · · · , k}:
Φ(Φ−1(pl)− Rtl σ ))− Φ(Φ−1(pSt) + Rtl σ )) t = 0. (7)
We note that it is still difficult to obtain an analytical solution to Equation 7 when t > 1. However, we notice that the left-hand side has the following properties: 1) it decreases as Rtl increases; 2) when Rtl → −∞, it is greater than 0; 3) when Rtl →∞, it is smaller than 0. Therefore, there exists a unique solution Rtl to Equation 7. Moreover, we leverage binary search to find a lower bound Rl t that can be arbitrarily close to the exact solution Rtl . In particular, we run the binary search until the left-hand side of Equation 7 is non-negative and the width of the search interval is less than a parameter µ > 0. Formally, we have:
Rl t ≤ Rtl ≤ Rl t + µ, ∀t ∈ {1, 2, · · · , k}. (8)
After obtaining Rlt, we let Rl = maxkt=1Rl t be our lower bound of Rl. Based on Rl = maxkt=1R t l and Equation 8, we have the following guarantee:
Rl ≤ Rl ≤ Rl + µ. (9)

heading: 3.2.3 COMPLETE CERTIFICATION ALGORITHM

text:
Algorithm 2 shows our algorithm to estimate the certified radius for a given example x and a label l. The function SAMPLEUNDERNOISE is the same as in Algorithm 1. Functions BINOCP and SIMUEM return the estimated probability bound for each label. Function BINARYSEARCH performs binary search to solve the Equation 7 and returns a solution satisfying Equation 8. Formally, our algorithm has the following guarantee:
Proposition 2. With probability at least 1−α over the randomness in CERTIFY, if CERTIFY returns a radius Rl (i.e., does not ABSTAIN), then we have l ∈ gk(x + δ), ∀||δ||2 < Rl.
Proof. See Appendix D.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP

text:
Datasets and models: We conduct experiments on the standard CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009) datasets to evaluate our method. We use the publicly available pre-trained models from Cohen et al. (2019). Specifically, the architectures of the base classifiers are ResNet-110 and ResNet-50 for CIFAR10 and ImageNet, respectively.
Parameter setting: We study the impact of k, the confidence level 1 − α, the noise level σ, the number of samples n, and the confidence interval estimation methods on the certified radius. Unless otherwise mentioned, we use the following default parameters: k = 3, α = 0.001, σ = 0.5, n = 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.
Approximate certified top-k accuracy: For each testing example x whose true label is l, we compute the certified radius Rl using the CERTIFY algorithm. Then, we compute the certified topk accuracy at a radius r as the fraction of testing examples whose certified radius are at least r. Note that our computed certified top-k accuracy is an approximate certified top-k accuracy instead of the true certified top-k accuracy. However, we can obtain a lower bound of the true certified top-k accuracy based on the approximate certified top-k accuracy. Appendix E shows the details. Moreover, the gap between the lower bound of the true certified top-k accuracy and the approximate top-k accuracy is negligible when α is small. For convenience, we simply use the term certified top-k accuracy in the paper.

heading: 4.2 EXPERIMENTAL RESULTS

text:
Figure 1 shows the certified top-k accuracy as the radius r increases for different k. Naturally, the certified top-k accuracy increases as k increases. On CIFAR10, we respectively achieve certified top-1, top-2, and top-3 accuracies as 45.2%, 58.8%, and 67.2% when the `2-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 `2-norm of the adversarial perturbation is less than 0.5. On CIFAR10, the gaps between the certified top-k accuracy for different k 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 k 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 3 shows the influence of σ. We observe that σ controls a trade-off between normal accuracy under no attacks and robustness. Specifically, when σ is smaller, 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. 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, pl is relatively large, and thus 1−pl already provides a good estimation for pi, where i 6= l.

heading: 5 RELATED WORK

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

heading: 5.1 EMPIRICAL DEFENSES

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

heading: 5.2 CERTIFIED DEFENSES

text:
To end the arms race between defenders and adversaries, researchers have developed certified defenses against adversarial perturbations. Specifically, in a certifiably robust classifier, the predicted top-1 label is verifiably constant within a certain region (e.g., `2-norm ball) around an input example, which provides a 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 interpretation 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; Tsuzuku et al., 2018; Anil et al., 2019; Wong & Kolter, 2018; Wang et al., 2018a;b; Raghunathan et al., 2018a;b; Wong et al., 2018; Dvijotham et al., 2018a;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 on the architectures of the neural networks. For example, these defenses are not scalable/applicable to the complex neural networks for ImageNet.
Randomized smoothing was first proposed as an empirical defense (Cao & Gong, 2017; Liu et al., 2018) without deriving the certified robustness guarantees. For instance, Cao & Gong (2017) proposed randomized smoothing with uniform noise from a hypercube centered at an example. Lecuyer et al. (2019) was the first to prove the certified robustness guarantee of randomized smoothing for top-1 predictions. Their results leverage differential privacy. Subsequently, Li et al. (2018) further leverages information theory to improve the certified radius bound. Cohen et al. (2019) obtains a tight certified radius bound for randomized smoothing with Gaussian noise by leveraging the Neyman-Pearson Lemma. Pinot et al. (2019) theoretically demonstrated the robustness to adversarial attacks of randomized smoothing when adding noise from Exponential family distributions and devised an upper bound on the adversarial generalization gap of randomized neural networks. Lee et al. (2019) generalized randomized smoothing to discrete data. Salman et al. (2019) employed adversarial training to improve the performance of randomized smoothing. Unlike the other certified defenses, randomized smoothing is scalable to large neural networks and applicable to arbitrary classifiers. Our work derives the first certified robustness guarantee of randomized smoothing for top-k predictions. Moreover, we show that our robustness guarantee is tight for randomized smoothing with Gaussian noise.

heading: 6 CONCLUSION

text: Adversarial perturbation poses a fundamental security threat to classifiers. Existing certified defenses focus on top-1 predictions, leaving top-k predictions untouched. In this work, we derive the first certified radius under `2-norm for top-k predictions. Our results are based on randomized smoothing. Moreover, we prove that our certified radius is tight for randomized smoothing with Gaussian noise. In order to compute the certified radius in practice, we further propose simultaneous confidence interval estimation methods as well as design an algorithm to estimate a lower bound of the certified radius. Interesting directions for future work include 1) deriving a tight certified radius under other norms such as `1 and `∞, 2) studying which noise gives the tightest certified radius for randomized smoothing, and 3) studying certified robustness for top-k ranking.

heading: ACKNOWLEDGMENTS

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

heading: A PROOF OF THEOREM 1

text:
Given an example x, we define the following two random variables: X = x + ∼ N (x, σ2I), (10) Y = x + δ + ∼ N (x + δ, σ2I), (11)
where ∼ N (0, σ2I). The random variables X and Y represent random samples obtained by adding isotropic Gaussian noise to the example x and its perturbed version x + δ, respectively. 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 1 (Neyman-Pearson for Gaussians with different means). Let X ∼ N (x, σ2I), Y ∼ N (x+ δ, σ2I), and M : Rd −→ {0, 1} be a random or deterministic function. Then, we have the following: (1) If Z = {z ∈ Rd : δT z ≤ β} for some β and Pr(M(X) = 1) ≥ Pr(X ∈ Z), then Pr(M(Y) = 1) ≥ Pr(Y ∈ Z) (2) If Z = {z ∈ Rd : δT z ≥ β} for some β and Pr(M(X) = 1) ≤ Pr(X ∈ Z), then Pr(M(Y) = 1) ≤ Pr(Y ∈ Z)
Moreover, we have the following lemma from Cohen et al. (2019). Lemma 2. Given an example x, a number q ∈ [0, 1], and regions A and B defined as follows:
A = {z : δT (z− x) ≤ σ ‖δ‖2 Φ −1(q)} (12) B = {z : δT (z− x) ≥ σ ‖δ‖2 Φ −1(1− q)} (13)
Then, we have the following equations: Pr(X ∈ A) = q (14) Pr(X ∈ B) = q (15)
Pr(Y ∈ A) = Φ(Φ−1(q)− ‖δ‖2 σ ) (16) Pr(Y ∈ B) = Φ(Φ−1(q) + ‖δ‖2 σ ) (17)
Proof. Please refer to Cohen et al. (2019).
Based on Lemma 1 and 2, we derive the following lemma: Lemma 3. Suppose we have an arbitrary base classifier f , an example x, a set of labels which are denoted as S, two probabilities pS and pS that satisfy pS ≤ pS = Pr(f(X) ∈ S) ≤ pS , and regions AS and BS defined as follows:
AS = {z : δT (z− x) ≤ σ ‖δ‖2 Φ −1(pS)} (18) BS = {z : δT (z− x) ≥ σ ‖δ‖2 Φ −1(1− pS)} (19)
Then, we have: Pr(X ∈ AS) ≤ Pr(f(X) ∈ S) ≤ Pr(X ∈ BS) (20) Pr(Y ∈ AS) ≤ Pr(f(Y) ∈ S) ≤ Pr(Y ∈ BS) (21)
Proof. We know that Pr(X ∈ AS) = pS based on Lemma 2. Combined with the condition that pS ≤ Pr(f(X) ∈ S), we obtain the first inequality in (20). Similarly, we can obtain the second inequality in (20). We define M(z) = I(f(z) ∈ S). Based on the first inequality in (20) and Lemma 1, we have the following:
Pr(Y ∈ AS) ≤ Pr(M(Y) = 1) = Pr(f(Y) ∈ S), (22)
which is the first inequality in (21). The second inequality in (21) can be obtained similarly.
Next, we restate Theorem 1 and show our proof. Theorem 1 (Certified Radius for Top-k Predictions). Suppose we are given an example x, an arbitrary base classifier f , ∼ N (0, σ2I), a smoothed classifier g, an arbitrary label l ∈ {1, 2, · · · , c}, and pl, p1, · · · , pl−1, pl+1, · · · , pc ∈ [0, 1] that satisfy the following conditions:
Pr(f(x + ) = l) ≥ pl and Pr(f(x + ) = i) ≤ pi,∀i 6= l, (1)
where p and p indicate lower and upper bounds of p, respectively. Let pbk ≥ pbk−1 ≥ · · · ≥ pb1 be the k largest ones among {p1, · · · , pl−1, pl+1, · · · , pc}, where ties are broken uniformly at random. Moreover, we denote by St = {b1, b2, · · · , bt} the set of t labels with the smallest probability upper bounds in the k largest ones and by pSt = ∑t j=1 pbj the sum of the t probability upper bounds, where t = 1, 2, · · · , k. Then, we have:
l ∈ gk(x + δ),∀||δ||2 < Rl, (2)
where Rl is the unique solution to the following equation:
Φ(Φ−1(pl)− Rl σ ))− k min t=1
Φ(Φ−1(pSt) + Rl σ ))
t = 0, (3)
where Φ and Φ−1 are the cumulative distribution function and its inverse of the standard Gaussian distribution, respectively.
Proof. Roughly speaking, our idea is to make the probability that the base classifier f predicts l when taking Y as input larger than the smallest one among the probabilities that f predicts for a set of arbitrary k labels selected from all labels except l. For simplicity, we let Γ = {1, 2, · · · , c} \ {l}, i.e., all labels except l. We denote by Γk a set of k labels in Γ. We aim to find a certified radius Rl such that we have maxΓk⊆Γ mini∈Γk Pr(f(Y) = i) < Pr(f(Y) = l), which guarantees l ∈ gk(x+ δ). We first upper bound the minimal probability mini∈Γk Pr(f(Y) = i) for a given Γk, and then we upper bound the maximum value of the minimal probability among all possible Γk ⊆ Γ. Finally, we obtain the certified radius Rl via letting the upper bound of the maximum value smaller than Pr(f(Y) = l).
Bounding mini∈Γk Pr(f(Y) = i) for a given Γk: We use S to denote a non-empty subset of Γk and use |S| to denote its size. We define pS = ∑ i∈S pi, 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:
BS = {z : δT (z− x) ≥ σ ‖δ‖2 Φ −1(1− pS)} (23)
We have Pr(f(Y) ∈ S) ≤ Pr(Y ∈ BS) by applying Lemma 3 to the set S. In addition, we have∑ i∈S Pr(f(Y) = i) = Pr(f(Y) ∈ S). Therefore, we have:∑
i∈S Pr(f(Y) = i) = Pr(f(Y) ∈ S) ≤ Pr(Y ∈ BS) (24)
Moreover, we have:
min i∈Γk Pr(f(Y) = i) ≤ min i∈S Pr(f(Y) = i) (25) ≤ ∑ i∈S Pr(f(Y) = i)
|S| (26)
≤ Pr(Y ∈ BS) |S| , (27)
where we have the first inequality because S is a subset of Γk and we have the second inequality because the smallest value in a set is no larger than the average value of the set. Equation 27 holds for any S ⊆ Γk. Therefore, by taking all possible sets S into consideration, we have the following:
min i∈Γk Pr(f(Y) = i) ≤ min S⊆Γk Pr(Y ∈ BS) |S|
(28)
= k
min t=1 min S⊆Γk,|S|=t Pr(Y ∈ BS) t
(29)
= k
min t=1 Pr(Y ∈ BSt) t , (30)
where St is the set of t labels in Γk whose probability upper bounds are the smallest, where ties are broken uniformly at random. We have Equation 30 from Equation 29 because Pr(Y ∈ BS) decreases as pS decreases.
Bounding maxΓk⊆Γ mini∈Γk Pr(f(Y) = i): Since Pr(Y ∈ BSt) increases as pSt increases, Equation 30 reaches its maximum value when Γk = {b1, b2, · · · , bk}, i.e., when Γk is the set of k labels in Γ with the largest probability upper bounds. Formally, we have:
max Γk⊆Γ min i∈Γk
Pr(f(Y) = i) ≤ k
min t=1 Pr(Y ∈ BSt) t , (31)
where St = {b1, b2, · · · , bt}.
Obtaining Rl: According to Lemma 3, we have the following for S = {l}: Pr(f(Y) = l) ≥ Pr(Y ∈ A{l}) (32)
Recall that our goal is to make Pr(f(Y) = l) > maxΓk⊆Γ mini∈Γk Pr(f(Y) = i). It suffices to let:
Pr(Y ∈ A{l}) > k
min t=1 Pr(Y ∈ BSt) t . (33)
According to Lemma 2, we have Pr(Y ∈ A{l}) = Φ(Φ−1(pl) − ||δ||2σ )) and Pr(Y ∈ BSt) = Φ(Φ−1(pSt) + ||δ||2 σ )). Therefore, we have the following constraint on δ:
Φ(Φ−1(pl)− ||δ||2 σ ))− k min t=1
Φ(Φ−1(pSt) + ||δ||2 σ ))
t > 0. (34)
Since the left-hand side of the above inequality 1) decreases as ||δ||2 increases, 2) is larger than 0 when ||δ||2 → −∞, and 3) is smaller than 0 when ||δ||2 → ∞, we have the constraint ||δ||2 < Rl, where Rl is the unique solution to the following equation:
Φ(Φ−1(pl)− Rl σ ))− k min t=1
Φ(Φ−1(pSt) + Rl σ ))
t = 0. (35)

heading: B PROOF OF THEOREM 2

text:
Following the terminology we used in proving Theorem 1, we define a region A{l} as follows:
A{l} = {z : δT (z− x) ≤ σ ‖δ‖2 Φ −1(pl)}. (36)
According to Lemma 2, we have Pr(X ∈ A{l}) = pl. We first show the following lemma, which is the key to prove our Theorem 2.
Lemma 4. Assuming we have pl + ∑k j=1 pbj ≤ 1. For any perturbation ‖δ‖2 > Rl, there exists k disjoint regions Cbj ⊆ Rd \ A{l}, j ∈ {1, 2, · · · , k} that satisfy the following: Pr(X ∈ Cbj ) = pbj , ∀j ∈ {1, 2, · · · , k} (37)
Pr(Y ∈ Cbj ) ≥ k
min t=1 Pr(Y ∈ BSt) t , ∀j ∈ {1, 2, · · · , k}, (38)
where the random variables X and Y are defined in Equation 10 and 11, respectively; and {b1, b2, · · · , bk} and St are defined in Theorem 1.
Proof. Our proof is based on mathematical induction and the intermediate value theorem. For convenience, we defer the proof to Appendix B.1.
Next, we restate Theorem 2 and show our proof. Theorem 2 (Tightness of the Certified Radius). Assuming we have pl + ∑k j=1 pbj ≤ 1 and pl +∑
i=1,··· ,l−1,l+1,··· ,c pi ≥ 1. Then, for any perturbation ||δ||2 > Rl, there exists a base classifier f∗ consistent with (1) but we have l /∈ gk(x + δ).
Proof. Our idea is to construct a base classifier such that l is not among the top-k labels predicted by the smoothed classifier for any perturbed example x + δ when ||δ||2 > Rl. First, according to Lemma 4, we know there exists k disjoint regions Cbj ⊆ Rd \ A{l}, j ∈ {1, 2, · · · , k} that satisfy Equation 37 and 38. Moreover, we divide the remaining region Rd \ (A{l} ∪kj=1 Cbj ) into c−k−1 regions, which we denote as Cbk+1 , Cbk+2 , · · · , Cbc−1 and satisfy Pr(X ∈ Cbj ) ≤ pbj for j ∈ {k+ 1, k+ 2, · · · , c−1}. Note that b1, b2, · · · , bc−1 is some permutation of {1, 2, · · · , c}\{l}. We can divide the remaining region into such c−k−1 regions because pl+ ∑ i=1,··· ,l−1,l+1,··· ,c pi ≥ 1. Then, based on these regions, we construct the following base classifier:
f∗(x) = { l, if x ∈ A{l} bj , if x ∈ Cbj ,∀j ∈ {1, 2, · · · , c− 1}
(39)
Based on the definition of f∗, we have the following:
Pr(f∗(X) = l) = Pr(X ∈ A{l}) = pl (40) Pr(f∗(X) = bj) = Pr(X ∈ Cbj ) = pbj , j = 1, 2, · · · , k (41) Pr(f∗(X) = bj) = Pr(X ∈ Cbj ) ≤ pbj , j = k + 1, k + 2, · · · , c− 1 (42)
Therefore, f∗ satisfies the conditions in (1). Next, we show that l is not among the top-k labels predicted by the smoothed classifier for any perturbed example x+δ when ||δ||2 > Rl. Specifically, we have:
Pr(f∗(Y) = l| ‖δ‖2 > Rl) (43) =Pr(Y ∈ A{l}| ‖δ‖2 > Rl) (Definition of f ∗) (44) <Pr(Y ∈ A{l}| ‖δ‖2 = Rl) (Pr(Y ∈ A{l}) increases as ‖δ‖2 decreases) (45)
= k
min t=1 Pr(Y ∈ BSt | ‖δ‖2 = Rl) t
(Definition of Rl) (46)
< k
min t=1 Pr(Y ∈ BSt | ‖δ‖2 > Rl) t
(Pr(Y ∈ BSt) increases as ‖δ‖2 increases) (47)
≤Pr(Y ∈ Cbj | ‖δ‖2 > Rl) (Lemma 4) (48) =Pr(f∗(Y) = bj | ‖δ‖2 > Rl) (Definition of f ∗), (49)
where j = 1, 2, · · · , k. Since we have found k labels whose probabilities are larger than the probability of the label l, we have l /∈ gk(x + δ) when ‖δ‖2 > Rl.
B.1 PROOF OF LEMMA 4
We first define some key notations and lemmas that will be used in our proof. Definition 1 (C(q1, q2), C′(q1, q2), rx(q1, q2), ry(q1, q2)). Given two values q1 and q2 that satisfy 0 ≤ q1 < q2 ≤ 1, we define the following region:
C(q1, q2) = {z : σ ‖δ‖2 Φ −1(1− q2) < δT (z− x) ≤ σ ‖δ‖2 Φ −1(1− q1)} (50) According to Lemma 2, we have:
Pr(X ∈ C(q1, q2)) = q2 − q1, (51) where the Gaussian random variable X is defined in Equation 10. Moreover, assuming we have pairs of (qi1, q i 2), i = 1, 2, 3, · · · , where qi1, qi2 ∈ [q1, q2], ∀i. We define the following region:
C′(q1, q2) = C(q1, q2) \ (∪iC(qi1, qi2)). (52)
C′(q1, q2) is the remaining region of C(q1, q2) excluding C(q11 , q12), C(q21 , q22), · · · . Given two values qλ1 and q λ 2 that satisfy q1 ≤ qλ1 ≤ qλ2 ≤ q2, we also define the following two functions:
rx(q λ 1 , q λ 2 ) = Pr(X ∈ C′(q1, q2) ∩ C(qλ1 , qλ2 )) (53)
ry(q λ 1 , q λ 2 ) = Pr(Y ∈ C′(q1, q2) ∩ C(qλ1 , qλ2 )), (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 rx(qλ1 , q λ 2 ) and ry(q λ 1 , q λ 2 ).
Lemma 5. If rx(qκ1 , qκ2 ) ≤ rx(qλ1 , qλ2 ) and qκ2 ≥ qλ2 (or qκ1 ≥ qλ1 ), then we have ry(qκ1 , qκ2 ) ≤ ry(q λ 1 , q λ 2 ).
Proof. We consider three scenarios.
Scenario I: qκ2 ≥ qκ1 ≥ qλ2 ≥ qλ1 . We denote hx and hy as the probability densities for the random variables X and Y, respectively. Then, we have hx(z) = ( 1√2πσ ) d exp(− ∑d i=1(zi−xi) 2 2σ2 )
and hy(z) = ( 1√2πσ ) d exp(−
∑d i=1(zi−xi−δi) 2
2σ2 ). Therefore, the ratio of the probability density of Y and the probability density of X at a given point z is as follows:
hy(z) hx(z) = exp( δT (z− x) σ2 − ‖δ‖2 2σ2 ) (55)
Next, we compare the ratio for the points in different regions and have the following:
hy(z|z ∈ C′(qκ1 , qκ2 )) hx(z|z ∈ C′(qκ1 , qκ2 ))
(56)
≤ exp( σ ‖δ‖2 Φ−1(1− qκ1 ) σ2 − ‖δ‖2 2σ2 ) (57) ≤ exp( σ ‖δ‖2 Φ−1(1− qλ2 )
σ2 − ‖δ‖2 2σ2 ) (58)
≤hy(z|z ∈ C ′(qλ1 , q λ 2 ))
hx(z|z ∈ C′(q′1, qλ2 )) (59)
The Equation 57 from 56 is based on Equation 55 and the fact that δT (z−x) ≤ σ ‖δ‖2 Φ−1(1−qκ1 ) for any point z in the region C′(qκ1 , qκ2 ) from Definition 1. Similarly, we can obtain Equation 59 from 58. We note that the Equation 58 from 57 is because qλ2 ≤ qκ1 . Based on Equation 57 and 58, we know that there exists a real number u such that:
exp( σ ‖δ‖2 Φ−1(1− qκ1 ) σ2 − ‖δ‖2 2σ2 ) ≤ u ≤ exp( σ ‖δ‖2 Φ−1(1− qλ2 ) σ2 − ‖δ‖2 2σ2 ) (60)
Combining the Equation 56, 57, and 60, we have the following:
hy(z|z ∈ C′(qκ1 , qκ2 )) ≤ u · hx(z|z ∈ C′(qκ1 , qκ2 )) (61)
Taking an integral on both sides of the Equation 61 in the region C′(qκ1 , qκ2 ) and recalling the definition of rx(qκ1 , q κ 2 ) and ry(q κ 1 , q κ 2 ), we have the following:
ry(q κ 1 , q κ 2 ) ≤ u · rx(qκ1 , qκ2 ) (62)
Similarly, we have:
u · rx(qλ1 , qλ2 ) ≤ ry(qλ1 , qλ2 ) (63)
Based on Equation 62, 63, and the condition that rx(qκ1 , q κ 2 ) ≤ rx(qλ1 , qλ2 ), we have the following:
ry(q κ 1 , q κ 2 ) ≤ ry(qλ1 , qλ2 ) (64)
Scenario II: qκ2 ≥ qλ2 ≥ qκ1 ≥ qλ1 . We have:
rx(q κ 1 , q κ 2 ) = rx(q κ 1 , q λ 2 ) + rx(q λ 2 , q κ 2 ) ≤ rx(qλ1 , qκ1 ) + rx(qκ1 , qλ2 ) = rx(qλ1 , qλ2 ) (65)
Therefore, we have the following equation:
rx(q λ 2 , q κ 2 ) ≤ rx(qλ1 , qκ1 ) (66)
Similar to Scenario I, we know that there exists u such that: hy(z|z ∈ C′(qλ2 , qκ2 )) hx(z|z ∈ C′(qλ2 , qκ2 )) ≤ u ≤ hy(z|z ∈ C ′(qλ1 , q κ 1 )) hx(z|z ∈ C′(qλ1 , qκ1 )) (67)
Similar to Scenario I, we have the following based on Equation 66:
ry(q λ 2 , q κ 2 ) ≤ ry(qλ1 , qκ1 ) (68)
Therefore, we have the following:
ry(q κ 1 , q κ 2 ) = ry(q κ 1 , q λ 2 ) + ry(q λ 2 , q κ 2 ) ≤ ry(qλ1 , qκ1 ) + ry(qκ1 , qλ2 ) = ry(qλ1 , qλ2 ) (69)
Scenario III: qκ2 ≥ qλ2 ≥ qλ1 ≥ qκ1 . As rx(qκ1 , qκ2 ) ≤ rx(qλ1 , qλ2 ), we have rx(qκ1 , qκ2 ) = rx(qλ1 , qλ2 ). Therefore, we have ry(qκ1 , q κ 2 ) = ry(q λ 1 , q λ 2 ).
Next, we list the well-known Intermediate Value Theorem and show several other properties of our defined functions rx(qλ1 , q λ 2 ) and ry(q λ 1 , q λ 2 ). Lemma 6 (Intermediate Value Theorem). If a function F is continuous at every point in the interval [a, b] and (F (a)− v) · (F (b)− v) ≤ 0, then there exists x such that F (x) = v.
Roughly speaking, the Intermediate Value Theorem tells us that if a continuous function has values no larger and no smaller (or no smaller and no larger) than v at the two end points of an interval, respectively, then the function takes value v at some point in the interval. Lemma 7. Given two probabilities qx, qy , if we have:
qx ≤ rx(q1, q2) (70) Then, there exists q′1, q ′ 2 ∈ [q1, q2] such that:
rx(q1, q ′ 2) = qx (71) rx(q ′ 1, q2) = qx (72)
Furthermore, if we have:
(ry(q1, q ′ 2)− qy) · (ry(q′1, q2)− qy) ≤ 0, (73)
then there exists q′′1 , q ′′ 2 ∈ [q1, q2] such that:
rx(q ′′ 1 , q ′′ 2 ) = qx (74) ry(q ′′ 1 , q ′′ 2 ) = qy (75)
Proof. We define function F (x) = rx(q1, x). Then, we have (F (q1) − qx) · (F (q2) − qx) ≤ 0 since F (q1) = 0 ≤ qx and F (q2) = rx(q1, q2) > qx based on Equation 70. Therefore, according to Lemma 6, there exists q′1 ∈ [q1, q2] such that:
rx(q1, q ′ 2) = qx (76)
Similarly, we can prove that there exists q′2 ∈ [q1, q2] such that rx(q′1, q2) = qx. For any qe2 ∈ [q′2, q2], we define H(x) = rx(x, qe2). Then, we know H(q1) = rx(q1, qe2) ≥ rx(q1, q ′ 2) = qx since q e 2 ≥ q′2. Moreover, we have H(qe2) = 0 ≤ qx. Therefore, we have (H(q1) − qx) · (H(qe2) − qx) ≤ 0. According to Lemma 6,we know there exists qe1 ∈ [q1, qe2] such that rx(qe1, q e 2) = qx for arbitrary q e 2 ∈ [q′2, q2]. We define G(x) = ry(qe1, x) where x ∈ [q′2, q2], and qe1 are a value such that rx(q e 1, x) = qx for a given x. When x = q ′ 2, we can let q e 1 = q1 since rx(q1, q ′ 2) = qx, and when x = q1, we can let q e 1 = q ′ 2 since rx(q ′ 2, q2) = qx. Based on Equation 73 and Lemma 6, we know that there exists x ∈ [q′2, q2] such that G(x) = qy . Therefore, there exists q′′1 and q ′′ 2 such that:
rx(q ′′ 1 , q ′′ 2 ) = qx (77) ry(q ′′ 1 , q ′′ 2 ) = qy (78)
Lemma 8. Assuming we have qλ1 = 0, qλ2 = pSt . If q λ 2 = pSt ≤ mini q i 1, then we have the following:
rx(q λ 1 , q λ 2 ) = q λ 2 − qλ1 = pSt (79) ry(q λ 1 , q λ 2 ) = Pr(Y ∈ BSt) (80)
Proof. If qλ2 ≤ mini qi1, then we have C′(q1, q2)∩C(qλ1 , qλ2 ) = C(qλ1 , qλ2 ) since no region is excluded. Therefore, we have ry(qλ1 , q λ 2 ) = Pr(Y ∈ C′(q1, q2)∩C(qλ1 , qλ2 )) = Pr(Y ∈ C(qλ1 , qλ2 )) = qλ2−qλ1 = pSt based on Equation 51. We note that C(q λ 1 , q λ 2 ) = BSt when qλ1 = 0 and qλ2 = pSt . Therefore, we can obtain Equation 80 based on the definition of ry(qλ1 , q λ 2 ) from Definition 1.
Lemma 9. If we have q1 ≤ qo2 ≤ q2, then we have the following:
ry(q1, q o 2) ≥
ry(q1, q2)
drx(q1, q2)/rx(q1, qo2)e (81)
Proof. By applying Lemma 5.
We further generalize Lemma 5 to two regions. Specifically, we have the following lemma:
Lemma 10. Assuming we have a region Cw ⊆ C(qw1 , qw2 ) and we have C′(q1, q2) ∩ C(qw1 , qw2 ) = ∅. If q1 ≥ qw1 , q2 ≥ qw2 and rx(q′1, q′2) ≤ Pr(X ∈ Cw), then we have:
ry(q1, q2) ≤ Pr(Y ∈ Cw) (82)
Proof. We let q1 = max(q1, qw2 ). As C′(q1, q2) ∩ C(qw1 , qw2 ) = ∅ and q1 ≥ qw1 , we can obtain the conclusion by applying Lemma 5 on C′(q1, q2) ∪ Cw.
Next, we restate Lemma 4 and show our proof. Lemma 4. Assuming we have pl + ∑k j=1 pbj ≤ 1. For any perturbation ‖δ‖2 > Rl, there exists k disjoint regions Cbj ⊆ Rd \ A{l}, j ∈ {1, 2, · · · , k} that satisfy the following:
Pr(X ∈ Cbj ) = pbj , ∀j ∈ {1, 2, · · · , k} (37)
Pr(Y ∈ Cbj ) ≥ k
min t=1 Pr(Y ∈ BSt) t , ∀j ∈ {1, 2, · · · , k}, (38)
where the random variables X and Y are defined in Equation 10 and 11, respectively; and {b1, b2, · · · , bk} and St are defined in Theorem 1.
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, we show that if the statement is true for themth iteration, then it also holds for the (m+1)th iteration. Without loss of generality, we assume τ = argminkt=1 Pr(Y∈BSt ) t . Therefore, we have the following:
∀i 6= τ, Pr(Y ∈ BSi) i ≥ Pr(Y ∈ BSτ ) τ
(83)
Recall the definition of BSτ and we have the following:
BSτ = {z : δT (z− x) ≥ σ ‖δ‖2 Φ −1(1− pSτ )}, (84) where pSτ = ∑ j∈Sτ pj . We can split BSk into two parts: BSτ and BSk \ BSτ . We will show that ∀j ∈ [1, τ ], we can find disjoint Cbj ⊆ BSτ whose union is BSτ such that:
Pr(X ∈ Cbj ) = pbj (85)
Pr(Y ∈ Cbj ) = Pr(Y ∈ BSτ )
τ (86)
For the other part, we will show that ∀j ∈ [τ + 1, k], we can find disjoint Cbj ⊆ BSk \ BSτ whose union is BSk \ BSτ such that:
Pr(X ∈ Cbj ) = pbj (87)
Pr(Y ∈ Cbj ) ≥ Pr(Y ∈ BSτ )
τ (88)
We first show that ∀j ∈ [1, τ ], we can find Cbj ⊆ BSτ that satisfy Equation 85 and 86. Since our proof leverages Mathematical Induction, we iteratively construct each Cbj ,∀j ∈ [1, τ ]. Specifically, we first show that we can find Cbτ ⊆ BSτ that satisfies the requirements. Then, assuming we can find Cbτ , · · · , Cbτ−m+1 , we show that we can find Cbτ−m ⊆ BSτ \ (∪τj=τ−m+1Cbj ). We will leverage Lemma 7 to prove the existence for each Cbj . Next, we show the two steps.
Step I: We show that we can find Cbτ ⊆ BSτ that satisfies Equation 85 and 86. We let q1 = 0 and q2 = pSτ , and we define the following region:
C′(q1, q2) = C(0, pSτ ) = BSτ (89)
We have:
rx(q1, q2) = Pr(X ∈ C′(q1, q2)) = pSτ (90) ry(q1, q2) = Pr(Y ∈ C′(q1, q2)) = Pr(Y ∈ BSτ ), (91)
which can be directly obtained as C′(q1, q2) = BSτ . As we have pbτ ≤ rx(q1, q2) = pSτ =∑τ j=1 pbj , there exist q ′ 1 = pSτ − pbτ , q ′ 2 = pbτ such that:
rx(q1, q ′ 2) = pbτ (92) rx(q ′ 1, q2) = pbτ (93)
Moreover, we have the following:
ry(q1, q ′ 2) ≥ ry(q1, pb1) = Pr(Y ∈ C(q1, pb1)) = Pr(Y ∈ BS1) ≥ Pr(Y ∈ BSτ ) τ
(94)
The equality in the middle is from Lemma 8, the left inequality is because q′2 = pbτ ≥ pb1 , and the right inequality is from Equation 83. Furthermore, we have the following:
ry(q ′ 1, q2) (95) =Pr(Y ∈ C′(q1, q2) ∩ C(q′1, q2)) (96) =Pr(Y ∈ C(pSτ − pbτ , pSτ )) (97) =Pr(Y ∈ C(0, pSτ ))− Pr(Y ∈ C(0, pSτ − pbτ )) (98) =Pr(Y ∈ C(0, pSτ ))− Pr(Y ∈ C(0, pSτ−1)) (99) =Pr(Y ∈ BSτ )− Pr(Y ∈ BSτ−1) (100)
≤Pr(Y ∈ BSτ )− (τ − 1) · Pr(Y ∈ BSτ )
τ (101)
= Pr(Y ∈ 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(q ′ 1, q2)− Pr(Y ∈ BSτ ) τ ) · (ry(q1, q′2)− Pr(Y ∈ BSτ ) τ ) ≤ 0 (103)
Thus, there exists (qτ1 , q τ 2 ) such that rx(q τ 1 , q τ 2 ) = pbτ , ry(q τ 1 , q τ 2 ) = Pr(Y∈BSτ ) τ based on Lemma 7. Then, we have the following based on the definition of rx, ry:
Pr(X ∈ C′(q1, q2) ∩ C(qτ1 , qτ2 )) = pbτ (104) Pr(Y ∈ C′(q1, q2) ∩ C(qτ1 , qτ2 )) = Pr(Y ∈ BSτ )
τ (105)
Finally, we let Cbτ = C′(q1, q2) ∩ C(qτ1 , qτ2 ), which meets our goal.
Step II: Assuming we can find {(qτ1 , qτ2 ), (qτ−11 , q τ−1 2 ), · · · , (q τ−m+1 1 , q τ−m+1 2 )} (∀j ∈ [τ −m+ 1, τ ], q1 ≤ qj1 ≤ q j 2 ≤ q2) where 1 ≤ m ≤ τ − 1 such that ∀j ∈ [τ −m+ 1, τ ], we have:
Pr(X ∈ Cbj ) = pbj (106)
Pr(Y ∈ Cbj ) = Pr(Y ∈ BSτ )
τ , (107)
as well as the following:
∀j, t ∈ [τ −m+ 1, τ ] and j 6= t, Cbj ∩ Cbt = ∅ (108) We denote e = τ −m. We show we can find Cbe such that we have:
Pr(X ∈ Cbe) = pbe (109) Pr(Y ∈ Cbe) = Pr(Y ∈ BSτ )
τ (110)
∀j ∈ [e+ 1, τ ], Cbe ∩ Cbj = ∅ (111) We let q1 = 0, q2 = pSτ and denote
C′(q1, q2) = C(q1, q2) \ ∪τj=e+1Cbj (112) We have the following:
rx(q1, q2) (113) =Pr(X ∈ C′(q1, q2) ∩ C(q1, q2)) (114) =Pr(X ∈ C(q1, q2))− Pr(X ∈ ∪τj=e+1Cbj ) (115)
=Pr(X ∈ C(q1, q2))− τ∑
j=e+1
Pr(X ∈ Cbj ) (116)
= τ∑ j=1 pbj − τ∑ j=e+1 pbj (117)
= e∑ j=1 pbj (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:
ry(q1, q2) (119) =Pr(Y ∈ C′(q1, q2) ∩ C(q1, q2)) (120) =Pr(Y ∈ C(q1, q2))− Pr(Y ∈ ∪τj=e+1Cbj ) (121)
=Pr(Y ∈ C(q1, q2))− τ∑
j=e+1
Pr(Y ∈ Cbj ) (122)
=Pr(Y ∈ BSτ )− m · Pr(Y ∈ BSτ )
τ (123)
= (τ −m) · Pr(Y ∈ BSτ )
τ (124)
The Equation 123 from 122 is because C(q1, q2) = BSτ and the Equation 107. We have pbe ≤ rx(q1, q2). Therefore, based on Lemma 7, there exist q′1, q ′ 2 such that:
rx(q1, q ′ 2) = pbe (125) rx(q ′ 1, q2) = pbe (126)
We have:
ry(q1, q ′ 2) (127)
≥ry(q1, q2) · 1
drx(q1, q2)/rx(q1, q′2)e (128)
≥ry(q1, q2) · 1 d( ∑e j=1 pbj )/pbee
(129)
≥Pr(Y ∈ BSτ ) τ
(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 is obtained from Equation 91 and the fact that d( ∑e j=1 pbj )/pbee ≥ τ . Next, we show:
ry(q ′ 1, q2) ≤ Pr(Y ∈ BSτ ) τ
(131)
In particular, we consider two scenarios.
Scenario 1). q′1 ≥ minτj=τ−m+1 q j 1. We denote t = argmin τ j=τ−m+1 q j 1. We let Cw = Cbt ⊆ C(qt1, qt2). As q′1 ≥ qt1, q2 ≥ qt2 and rx(q′1, q2) = pbe ≤ Pr(X ∈ Cw) = pbt , we have the following based on Lemma 10:
ry(q ′ 1, q2) ≤ Pr(Y ∈ Cw) = Pr(Y ∈ BSτ ) τ
(132)
Scenario 2). q′1 < min τ j=τ−m+1 q j 1. We have the following:
C′(q1, q2) ∩ C(q1, q′1) = C(q1, q′1) (133) Furthermore, we have:
rx(q1, q ′ 1) (134) =rx(q1, q2)− rx(q′1, q2) (135)
= e∑ j=1 pbj − pbe (136)
= e−1∑ j=1 pbj (137)
Moreover, we have rx(q1, q′1) = q ′ 1 − q1 from Lemma 8. The above two should be equal. Thus, we have q′1 = ∑e−1 j=1 pbj = pSτ−m−1 since e = τ −m. we have:
ry(q ′ 1, q2) (138) =ry(q1, q2)− ry(q1, q′1) (139) =ry(q1, q2)− Pr(Y ∈ BSτ−m−1) (140)
≤ (τ −m) · Pr(Y ∈ BSτ ) τ − (τ −m− 1) · Pr(Y ∈ BSτ ) τ
(141)
= Pr(Y ∈ BSτ )
τ (142)
We obtain Equation 140 from Equation 139 based on Lemma 8.
Therefore, we have the following in both scenarios:
ry(q1, q ′ 2) ≥ Pr(Y ∈ BSτ ) τ
(143)
ry(q ′ 1, q2) ≤ Pr(Y ∈ BSτ ) τ
(144)
Based on Lemma 7, there exist qe1, q e 2 such that rx(q e 1, q e 2) = pbτ , ry(q e 1, q e 2) = Pr(Y∈BSτ ) τ . Then, we have the following based on the definition of rx, ry:
Pr(X ∈ C′(q1, q2) ∩ C(qe1, qe2)) = pbe (145)
Pr(Y ∈ C′(q1, q2) ∩ C(qe1, qe2)) = Pr(Y ∈ BSτ )
τ (146)
We let Ce = C′(q1, q2) ∩ C(qe1, qe2). From the definition of C′(q1, q2), we have ∀j ∈ [e + 1, τ ], C′(q1, q2) ∩ Cbj = ∅. Thus, we have ∀j ∈ [e+ 1, τ ], Cbe ∩ Cbj = ∅ since Cbe ⊆ C′(q1, q2). Therefore, we reach our goal by Mathematical Induction, i.e., for ∀j ∈ [1, τ ], we have:
Pr(X ∈ Cbj ) = pbj (147)
Pr(Y ∈ Cbj ) = Pr(Y ∈ BSτ )
τ (148)
We can also verify that ∪τj=1Cbj = BSτ .
Next, we show our proof based on Mathematical Induction for the other part, i.e., BSk \ BSτ . Our construction process is similar to the above first part but has subtle differences. Step I: Let q1 = ∑τ j=1 pbj and q2 = ∑k j=1 pbj . We define:
C′(q1, q2) = C(q1, q2) = BSk \ BSτ (149)
Then, we have:
rx(q1, q2) = q2 − q1 = k∑
j=τ+1
pbj (150)
ry(q1, q2) (151) =Pr(Y ∈ C′(q1, q2) ∩ C(q1, q2)) (152) =Pr(Y ∈ C(0, q2))− Pr(Y ∈ C(q1, q2)) (153) =Pr(Y ∈ BSk)− Pr(Y ∈ BSτ ) (154) ≥k · Pr(Y ∈ BSτ ) τ − Pr(Y ∈ BSτ ) (155) = (k − τ) · Pr(Y ∈ BSτ )
τ (156)
The Equation 150 is based on the fact that C′(q1, q2) = C(q1, q2) and Definition 1, and we obtain Equation 154 from 155 based on Equation 83. We have pbk ≤ rx(q1, q2). Therefore, based on Lemma 7, we know that there exists q′1 = q2 − pbk , q ′ 2 = q1 + pbk such that:
rx(q1, q ′ 2) = pbk (157) rx(q ′ 1, q2) = pbk (158)
We consider two scenarios.
Scenario 1). In this scenario, we consider ry(q′1, q2) > Pr(Y∈BSτ ) τ . We let q k 1 = q ′ 1, q k 2 = q2, i.e., we have Cbk = C(q′1, q2) ∩ C′(q1, q2). Then, we have:
Pr(X ∈ Cbk) = rx(q′1, q2) = pbk (159) Pr(Y ∈ Cbk) = ry(q′1, q2) ≥ Pr(Y ∈ BSτ )
τ (160)
Therefore, we have the following:
Pr(Y ∈ C(q1, q2) \ Cbk) (161) =Pr(Y ∈ C(q1, q′1)) (162) =Pr(Y ∈ C(0, q′1))− Pr(Y ∈ C(0, q1)) (163) =Pr(Y ∈ BSk−1)− Pr(Y ∈ BSτ ) (164)
≥ (k − τ − 1) · Pr(Y ∈ BSτ ) τ
(165)
Scenario 2). In this scenario, we consider ry(q′1, q2) ≤ Pr(Y∈BSτ ) τ . We have the following:
ry(q1, q ′ 2) (166)
≥ry(q1, q2) · 1
drx(q1, q2)/rx(q1, q′2)e (167)
≥ (k − τ) · Pr(Y ∈ BSτ ) τ · 1 k − τ
(168)
= Pr(Y ∈ BSτ )
τ (169)
We obtain Equation 167 from 166 via Lemma 9, and we obtain Equation 168 from 167 based on Equation 150 to 156 and the fact rx(q1, q2)/rx(q1, q′2) = ∑k j=τ+1 pbj pbτ+1
≥ k−τ . We have (ry(q′1, q2)− Pr(Y∈BSτ )
τ ) · (ry(q1, q ′ 2) − Pr(Y∈BSτ ) τ ) ≤ 0. Therefore, from Lemma 7, we know that there exist
(qk1 , q k 2 ) such that:
Pr(X ∈ Cbk) = rx(qk1 , qk2 ) = pbk (170) Pr(Y ∈ Cbk) = ry(qk1 , qk2 ) = Pr(Y ∈ BSτ )
τ (171)
We also have the following:
Pr(Y ∈ C(q1, q2) \ Cbk) (172) =ry(q1, q2)− ry(qk1 , qk2 ) (173)
≥ (k − τ − 1) · Pr(Y ∈ BSτ ) τ
(174)
Similarly, we let Cbk = C′(q1, q2) ∩ C(qk1 , qk2 ). Based on the conditions of our constructions in the two scenarios, we know that if Pr(Y ∈ Bbk) > Pr(Y∈BSτ )
τ , then we have q k 2 = q2.
Step II: We show that if we can find (qk1 , qk2 ), · · · , (qk−m+11 , q k−m+1 2 ) where m ∈ [1, k − τ − 1] and Cbj ,∀j ∈ [k, k −m+ 1] such that:
Pr(X ∈ Cbj ) = pbj (175)
Pr(Y ∈ Cbj ) ≥ Pr(Y ∈ BSτ )
τ (176)
Pr(Y ∈ C(q1, q2) \ ∪kt=k−m+1Cbt) ≥ (k − τ −m) · Pr(Y ∈ BSτ )
τ (177)
Then, we can find (qk−m1 , q k−m 2 ) such that:
Pr(X ∈ Cbk−m) = pbk−m (178)
Pr(Y ∈ Cbk−m) ≥ Pr(Y ∈ BSτ )
τ (179)
Pr(Y ∈ C(q1, q2) \ ∪kt=k−mCbt) ≥ (k − τ −m− 1) · Pr(Y ∈ BSτ )
τ (180)
For simplicity, we denote e = k −m, we let q1 = ∑τ j=1 pbj and q2 = ∑k j=1 pbj , and we define:
C′(q1, q2) = C(q1, q2) \ ∪kj=e+1Cbj (181) Then, we have:
rx(q1, q2) = Pr(X ∈ C(q1, q2) \ ∪kj=e+1Cbj ) = e∑
j=τ+1
pbj (182)
ry(q1, q2) = Pr(Y ∈ C(q1, q2) \ ∪kj=e+1Cbj ) ≥ (k − τ −m) · Pr(Y ∈ BSτ )
τ (183)
We have pbe ≤ rx(q1, q2). Therefore, based on Lemma 7, we know that there exists q ′ 1, q ′ 2 such that:
rx(q ′ 1, q2) = pbe (184) rx(q1, q ′ 2) = pbe (185)
Similarly, we consider two scenarios:
Scenario 1). In this scenario, we consider that the following holds:
ry(q ′ 1, q2) > Pr(Y ∈ BSτ ) τ
(186)
We let qe1 = q ′ 1, q e 2 = q2, i.e., Cbe = C(q′1, q2) ∩ C′(q1, q2). Then, we have:
Pr(X ∈ Cbe) = rx(q′1, q2) = pbe (187) Pr(Y ∈ Cbe) = ry(q′1, q2) ≥ Pr(Y ∈ BSτ )
τ (188)
We note that we have q′1 ≤ minkj=e+1 qi1 in this scenario. Otherwise, Equation 186 will not hold based on Lemma 10. We give a short proof.
Assuming q′1 > min k j=k−m+1 q j 1. We denote w = argmin k j=k−m+1 q j 1. We let Cw = Cbw ⊆ C(qw1 , qw2 ). Note that in this case, we have qw2 < q2 because qw2 = q2 and q′1 > qw1 cannot hold at the same time as long as ry(q′1, q2) > 0. Thus, we have Pr(Y ∈ Cw) = Pr(Y∈BSτ ) τ because if Pr(Y ∈ Cw) > Pr(Y∈BSτ )τ , we have q w 2 = q2. As we have q ′ 1 > q w 1 , q2 > q w 2 and rx(q ′ 1, q2) = pbe ≤ Pr(X ∈ Cw) = pbw . We have the following based on Lemma 10:
ry(q ′ 1, q2) ≤ Pr(Y ∈ Cw) = Pr(Y ∈ BSτ ) τ
(189)
Since Equation 186 and Equation 189 cannot hold at the same time, the assumption q′1 > minkj=k−m+1 q j 1 must be wrong. Therefore, we have q ′ 1 ≤ minkj=k−m+1 q j 1.
Based on q′1 ≤ minkj=k−m+1 q j 1, we have the following:
C′(q1, q2) ∩ C(q1, q′1) = C(q1, q′1) (190) Therefore, we have rx(q1, q′1) = q ′ 1 − q1 from Definition 1. Moreover, we have the following:
rx(q1, q ′ 1) (191) =rx(q1, q2)− rx(q′1, q2) (192)
= e∑ j=τ+1 pbj − pbe (193)
= e−1∑ j=τ+1 pbj (194)
The above two should be equal. Therefore, we have q′1 = ∑e−1 j=τ+1 pbj + q1 = ∑e−1 j=1 pbj . Recall that we let Cbe = C′(q1, q2) ∩ C(q′1, q2). Thus, we have:
Pr(Y ∈ C(q1, q2) \ ∪kj=eCbj ) (195) =Pr(Y ∈ C′(q1, q2) \ Cbe) (196) =Pr(Y ∈ C(q1, q′1)) (197) =Pr(Y ∈ C(0, q′1))− Pr(Y ∈ C(0, q1)) (198) =Pr(Y ∈ BSe−1)− Pr(Y ∈ BSτ ) (199)
≥ (k − τ −m− 1) · Pr(Y ∈ BSτ ) τ
(200)
Scenario 2). In this scenario, we consider that the following holds:
ry(q ′ 1, q2) ≤ Pr(Y ∈ BSτ ) τ
(201)
Note that we have:
ry(q1, q ′ 2) (202)
≥ry(q1, q2) · 1
drx(q1, q2)/rx(q1, q′2)e (203)
≥ry(q1, q2) · 1
k − τ −m (204)
≥Pr(Y ∈ BSτ ) τ
(205)
We obtain Equation 203 from 202 via Lemma 9, and we obtain Equation 204 from 203 based on Equation 183 and the fact rx(q1, q2)/rx(q1, q′2) = ∑e j=τ+1 pbj pbτ+1
≥ k− τ −m. We have (ry(q′1, q2)− Pr(Y∈BSτ )
τ ) · (ry(q1, q ′ 2) − Pr(Y∈BSτ ) τ ) ≤ 0. Based on Lemma 7, we can find (q e 1, q e 2) such that we
have:
Pr(X ∈ C′(q1, q2) ∩ C(qe1, qe2)) = rx(qe1, qe2) = pbe (206) Pr(Y ∈ C′(q1, q2) ∩ C(qe1, qe2)) = ry(qe1, qe2) = Pr(Y ∈ BSτ )
τ (207)
We let Cbe = C′(q1, q2) ∩ C(qe1, qe2). We also have the following:
Pr(Y ∈ C(q1, q2) \ ∪kj=eCbj ) (208) =Pr(Y ∈ C′(q1, q2) \ Cbe) (209) =ry(q1, q2)− ry(qe1, qe2) (210)
≥ (k − τ −m) · Pr(Y ∈ BSτ ) τ − Pr(Y ∈ BSτ ) τ
(211)
≥ (k − τ −m− 1) · Pr(Y ∈ BSτ ) τ
(212)
Similar to Step I, we still hold the conclusion that if Pr(Y ∈ Cbe) > Pr(Y∈BSτ ) τ , we have q e 2 = q2. Then, we can apply Mathematical Induction to reach the conclusion. Also, we can verify ∪kj=τ+1Cbj = BSk \ BSτ .

heading: C PROOF OF PROPOSITION 1

text:
The function SAMPLEUNDERNOISE(f, k, σ,x, n, α) works as follows: we first draw n random noise from N (0, σ2I), i.e., 1, 2, · · · , n. Then, we compute the values: ∀i ∈ [1, c], ci =∑n j=1 I(f(x + j) = i). The function BINOMPVALUE(nct , nct + nct+1 , p) returns the result of p-value of the two-sided hypothesis test for nct ∼ Bin(nct + nct+1 , p).
Proposition 1: With probability at least 1−α over the randomness in PREDICT, if PREDICT returns a set T (i.e., does not ABSTAIN), then we have gk(x) = T .
Proof. We aim to compute the probability that PREDICT returns a set which not equals to gk(x), which happens if and only if gk(x) 6= T and PREDICT doesn’t abstain. Specifically, we have:
Pr(PREDICT returns a set 6= gk(x)) (213) =Pr(gk(x) 6= T, PREDICT doesn’t abstain) (214) =Pr(gk(x) 6= T ) · Pr(PREDICT doesn’t abstain|gk(x) 6= T ) (215) ≤Pr(PREDICT doesn’t abstain|gk(x) 6= T ) (216)
Theorem 1 in Hung et al. (2019) shows the above conditional probability is as follows:
Pr(PREDICT doesn’t abstain|gk(x) 6= T ) ≤ α (217)
Therefore, we reach the conclusion.

heading: D PROOF OF PROPOSITION 2

text:
Proposition 2: With probability at least 1−α over the randomness in CERTIFY, if CERTIFY returns a radius Rl (i.e., does not ABSTAIN), then we have l ∈ gk(x + δ),∀ ‖δ‖2 < Rl.
Proof. From the definition of BINOCP and SIMUEM, we know the probability that the following inequalities simultaneously hold is at least 1− α over the sampling of counts:
pi ≤ Pr(f(x+ ) = i) if i = l (218) pi ≥ Pr(f(x+ ) = i) if i 6= l (219)
Then, with the returned bounds, we can invoke Theorem 1 to obtain the robustness guarantee if the calculated radius is larger than 0. 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 is similar to that Cohen et al. (2019) used to derive a lower bound of the certified top-1 accuracy based on the approximate certified top-1 accuracy. Specifically, we have the following lemma from Cohen et al. (2019). Lemma 11. Let zi be a binary variable and Yi be a Bernoulli random variable. Suppose if zi = 1, then Pr(Yi = 1) ≤ α. Then, for any ρ > 0, with probability at least 1− ρ, we have the following:
1
m m∑ i=1 zi ≥ 1 1− α ( ∑m i=1 Yi m − α− √ 2α(1− α) log 1ρ m − log( 1ρ ) 3m ) (220)
Proof. Please refer to Cohen et al. (2019).
Assuming we have a test dataset Dtest = {(x1, y1), (x2, y2), · · · , (xm, ym)} as well as a radius r. We define the following indicate value:
ai = I(yi ∈ gk(xi + δ)),∀||δ||2 < r (221)
Then, the certified top-k accuracy of the smoothed classifier g at radius r can be computed as 1 m ∑m i=1 ai. For each sample xi, we run the CERTIFY function with 1 − α confidence level and we use a random variable Yi to denote that the function CERTIFY returns a radius bigger than r. From Proposition 2, we know:
Pr(Yi = 1) ≤ α, if ai = 1 (222) The approximate certified top-k accuracy of the smoothed classifier at radius r is 1m ∑m i=1 Yi. Then,
we can use Lemma 11 to obtain a lower bound of 1m ∑m i=1 ai. Specifically, for any ρ > 0, with probability at least 1− ρ over the randomness of CERTIFY, we have:
1
m m∑ i=1 ai ≥ 1 1− α ( ∑m i=1 Yi m − α− √ 2α(1− α) log 1ρ m − log( 1ρ ) 3m ) (223)
We can see that the difference between the certified top-k accuracy and the approximate certified top-k accuracy is negligible when α is small.