A FRAMEWORK  FOR ROBUSTNESS CERTIFICATION  OF SMOOTHED CLASSIFIERS USING  F-DIVERGENCES
Authors: Krishnamurthy (Dj) Dvijotham
Jamie Hayes
Borja Balle
Zico Kolter
Chongli Qin
Andras Gyorgy
Kai Xiao
Sven Gowal
Pushmeet Kohli
Venue:  (2020)
Keywords: verification of machine learning
certified robustness of neural networks

Abstract: Formal verification techniques that compute provable guarantees on properties of machine learning models, like robustness to norm-bounded adversarial perturbations, have yielded impressive results. Although most techniques developed so far require knowledge of the architecture of the machine learning model and remain hard to scale to complex prediction pipelines, the method of randomized smoothing has been shown to overcome many of these obstacles. By requiring only black-box access to the underlying model, randomized smoothing scales to large architectures and is agnostic to the internals of the network. However, past work on randomized smoothing has focused on restricted classes of smoothing measures or perturbations (like Gaussian or discrete) and has only been able to prove robustness with respect to simple norm bounds. In this paper we introduce a general framework for proving robustness properties of smoothed machine learning models in the black-box setting. Specifically, we extend randomized smoothing procedures to handle arbitrary smoothing measures and prove robustness of the smoothed classifier by using f-divergences. Our methodology improves upon the state of the art in terms of computation time or certified robustness on several image classification tasks and an audio classification task, with respect to several classes of adversarial perturbations. 

Published as a conference paper at ICLR 2020
A FRAMEWORK FOR ROBUSTNESS CERTIFICATION OF SMOOTHED CLASSIFIERS USING F-DIVERGENCES
Krishnamurthy (Dj) Dvijotham?
Jamie Hayes Borja Balle'
J. Zico Kolter
Chongli Qin András György
Kai Xiao Sven Gowal
Pushmeet Kohlit
*DeepMind, London, UK University College London, UK o Carnegie Mellon University, USA Bosch Center for AI, USA
Massachusetts Institute of Technology, USA
[dvij, bballe, chongliqin, agyorgy, sgowal, pushmeet / @google.com com (zkoiter) emu.edu Jj.hayesJeucl- uc (kaix) eduu
ABSTRACT
Formal verification techniques that compute provable guarantees on properties of machine learning models, like robustness norm-boundel adversarial pertur- bations, have yielded impressive results. Although most techniques developed far require knowledge of the architecture of the machine learning model and remain hard to scale to complex prediction pipelines, the method of randomized smoothing has been shown to overcome many of these obstacles. By requiring only black-box access to the underlying model, randomized smoothing scales to large architectures and agnostic to the internals of the network. However, past work on randomized smoothing has focused on restricted classes of smoothing measures or perturbations (like Gaussian or discrete) and has only been able prove robustness with respect simple norm bounds. In this paper we introduce general framework for proving robustness properties of smoothed machine learning models in the black-box setting. Specifically, extend randomized smoothing procedures to handle arbitrary smoothing measures and prove robustness of the smoothed classifier by using f-divergences. Our methodology improves upon the state of the art in terms of computation time or certified robustness on several image classification tasks and an audio classification task, with respect to several classes of adversarial perturbations.
INTRODUCTION
Predictors obtained from machine learning algorithms have been shown to be vulnerable to making errors when the inputs are perturbed by carefully chosen small but imperceptible amounts (Szegedy
et al. 2014 Biggio et al.) 2013). This has motivated significant amount of research in improving adversarial robustness of a machine learning model (see, e.g. e.g. Goodfellow et al. 2015) Madry et al. 2018). While significant advances have been made, it has been shown that models that were estimated to be robust have later been broken by stronger attacks (Athalye et al.) 2018 Uesato et al.) 2018). This has led to the need for methods that offer provable guarantees that the predictor cannot be forced to misclassify an example by any attack algorithm restricted to produce perturbations within a certain set (for example, within an lp norm ball). While progress has been made leading methods that able to compute provable guarantees for several image and text classification tasks (Wong & Kolter 2018: Wong al.) 2018 Raghunathan et al.) 2018 Dvijotham al. 2018 Katz et al.) |017]] [ Huang et al. 2019 Jia et al. 2019). these methods require extensive Enowledge the architecture of the predictor and are not easy extend to new models or architectures, requiring specialized algorithms for each new class of models. Furthermore, the computational complexity of these methods grows
significantly with input dimension and model size.
To deal with these obstacles, recent work has proposed the randomized smoothing strategy for verifying the robustness of classifiers. Specifically, Lecuyer al.) (219) and Cohen al. (2019)
Work done during an intersship DeepMind.

---

Published as a conference paper at ICLR 2020
have shown that robustness properties can be more easily verified for the smoothed version of base classifier producing labels in some set y:
(z) = arg max P. yEY X~u(æ)
(x( y]
(I)
where the labels returned by the smoothed classifier ha are obtained by taking a "majority vote" over the predictions of the original classifier h on random inputs drawn from probability distribution ((x), called the smoothing measure. Lecuyer et al. (2019) showed that verifying the robustness of this smoothed classifier is significantly simpler than verifying the original classifier h and only requires estimating the distribution of outputs of the classifier under random perturbations of the input, but does not require access to the internals of the classifier h. We refer to this as black-box verification.
In this work, we develop a general framework for black-box verification that recovers prior work as special cases, and improves upon previous results in various ways.
Contributions Our contributions are summarized as follows:
1. We formulate the general problem of black-box verification via a generalized randomized smoothing procedure, which extends existing approaches to allow for arbitrary smoothing measures. Specifically, we show that robustness certificates for smoothed classifiers can be obtained by solving a small convex optimization problem when allowed adversarial perturbations can be characterized via divergence-based bounds on the smoothing measure.
2. We prove that our certificates generalize previous results obtained in related work (Lecuyer et al.) (2019) Cohen et al., [019 Li et al., 2019), and vastly extend the class of perturbations and smoothing measures that can be used while still allowing certifiable guarantees.
3. We introduce the notion of full-information and information-limen
settings, and show that the information-limin setting that has been the main focus of prior work leads to weaker certificates for smoothed probabilistic classifiers, and can be improved by using additional information (the distribution of label scores under randomized smoothing).
4. We evaluate framework experimentally image and classification tasks, obtaining ro- bustness certificates that improve upon other black-box methods either in terms of certificate tightness computation time robustness to la l &2 perturbations MNIST, CIFAR-10 and ImageNet. & perturbations result from worst-case realizations of white noise that is common in many image, speech and video processing. to perturbations can model missing data (missing pixels in an image, or samples in a time-domain audio signal) while l perturbations can be used to model convex combinations of discrete perturbations 2019). We also obtain the first, to the best of our knowledge, certifiably robust model for an audio classification task, Librispeech (Panayotov et al. 2015), with variable-length inputs.
text classification (Jia al.,
2 BLACK-BOX VERIFICATION FOR SMOOTHED CLASSIFIERS
Consider a binary classifier h X + {+1} given to us as a black box, so we can only access the inputs and outputs of h but not its internals. We are interested in investigating the robustness of the smoothed classifier h2 (defined in [) against adversarial perturbations of size at most e with respect to a given norm ||-I|- To determine whether norm- mom-bounded adversarial attack on fixed input x E X with (x) = +1 could be successful, we can solve the optimization problem
min |
IP [h(X') = +1]
(2)
X' ('m)
and check whether the minimum value can be smaller than 1. This is a non-convex optimization problem for which we may not even be able to compute gradients since we only have black-box access address this problem, obtaining provable guarantees
to h. While techniques have been developed on whether these algorithms actually find the worst-case adversarial perturbation is difficult since we do not know anything about the nature of h.
Motivated by this difficulty, we take a different approach: Rather than studying the adversarial attack in the input space X, we study it in the space of probability measures over inputs, denoted by P(X).
2

---

Published as a conference paper at ICLR 2020
Formally, this amounts to rewriting Eq. 2
min
P [h(x)) +1]
(3)
This is an infinite dimensional optimization problem over the space probability measures v E P(x) subject to the constraint deal with, we can consider relaxations of this set defined by divergence constraints between v and
D = {u(x²) || x||| S ct. While this set is still intractable to
p(z), i.e., D C (v= D [p) < <p} where 1) denotes some divergence between probability distributions. We will show Section 3 that for several commonly used divergences (in fact, for any f-divergence; cf. Ali & Silvey 1966). the relaxed problem can be solved efficiently.
2.1 A GENERAL FRAMEWORK FOR ROBUSTNESS CERTIFICATION
To formulate the general verification problem, consider a specification : 2 C R: a generic function the input space (that typically is function of the classifier output) that want to verify has certain properties. Unless otherwise specified, we will assume that X' S Rd (we work in a d dimensional input space). Our framework also involves reference measure p (in the above example we would take fx())) and collection of perturbed distributions 'D (in the above example we would take Dr,, (u(x') || || S c)).
Verifying that given specification é is robustly certified is equivalent to checking whether the optimal value of the optimization problem
OPT D) = min E (x(X)) VED X
(4)
is non-negative. Solving problems of this form is the key workhorse of our general framework for black-box bbx certification of adversarial robustness for smoothed classifiers.
Using these ingredients we introduce two closely related certification problems: information- robust certification and full-information robust certification. the former case, we assume that we are given only given access to IPx xPxxplo (x( +1], xxxxxlo(xX) +1]. In the latter case, we are given full-access to specification ø. The definitions are below.
Definition 2.1 (Information-limict robust certification). Given reference distribution p E P(X), probabilities la, Og that satisfy l., 0, 2 0, 0, + 0, < 1 and collection of perturbed distributions D C P(X) containing p. define the class specifications S as
s { b: x (-1,0++1,,+1)) s.t.
IP [6(X) +1] 2 Ba, X-p
P (x(X) -1] -1 0b X-p
X
We say that is information- limitte robustly certified at with respect to the following condition holds: Ex=r 2 0 for all DD.d S.
Note since we don't have access to o, we need to prove that Ex [o(())())))))))) 2 0 Vv E D is satisfied for all specifications in set S. Although the information-limites case may seem challenging because we need to provide guarantees that hold simultaneously over whole class of specifications, it turns out that, for perturbation sets D specified by an f-divergence bound, this certification task can be solved efficiently using convex optimization.
Definition 2.2 inul-minformttinn robust certification). Given a reference distribution p E P(X), a specification ò X + Z C R and collection of perturbed distributions D C P(x) containing p. we say that Φ is full-iffrrmation robustly certified at p with respect to DD if the following condition for all D.
holds: [ob
Most often we are dealing with the case where we have full access to the specification d, thus we should be able certify using full-information robust certification. However, prior works, Cohen et al. (2019) and Lecuyer et al. (2019), have only provided solutions to certify with respect to the information- limitied case where we cannot use all of the information about Φ. The framework we develop is a more general method that can be used in both information-limite. and full-information scenarios. We will demonstrate that our framework recovers certificates provided by Cohen et al. (2019). Li al. 2019) and dominates Lecuyer et al. (019) in the information-lime -imitedd setting (see section S}. Further, it can utilize full informatin about the specification ő to provide tighter certificates for smoothed probabilistic classifiers (see section
works,,Cohen
3

---

Published as a conference paper at ICLR 2020
2.1.1 ROBUSTNESS SPECIFICATION FOR SMOOTHED HARD CLASSIFIERS
We first note that the definitions above are sufficient capture the standard usage of randomized smoothing as it has been used in past work (e.g. Lecuyer et al. 2019) Cohen et al. 2019) to verify the robustness of smoothed multi-class classifiers. Specifically. consider smoothing a classifier h: X' - y with finite set of labels y using a smoothing measure μ X + P(2). The resulting randomly smoothed classifier ht defined Eq. Our goal is to certify that the prediction (ar) is robust perturbations of size at most measured by distance function d X' x X + IR+, i.e.,
hg (2') (x) Vx' such that d(z,, x²) e
To pose this question within our framework, we choose the reference distribution u(xx), the set of perturbed distributions Dz.e {u(x') x'x,,") <), and the following specifications. Let c = lt, (z). For every E E {c}. we define the specification &eee : : + {-1,0,+1) +1]++1 as follows:
+1
if (Tx)) =c
d (2))
if hf) =d
otherwise
Then, Eq. holds if and only if every ee, d is robustly certified u(x) with respect to Dr. (see Appendix A.I.
2.2 CONSTRAINT SETS FROM F-DIVERGENCES
Dealing with the set Dr,, directly is difficult due to its possibly non-convex geometry. In this section, we discuss specific relaxations of this set, i.c., choices for sets D such that Dz. S D that are easier to optimize over. In particular,
focus on a general family of constraint sets defined in terms of f-divergences. These divergences satisfy number of useful properties and include many well-known instances (e-g. relative entropy, total variation); see Appendix [A.2 details.
Definition 2.3. (f-divergence constraint set). Given P. P(X), their f-divergence is defined as
((X)
Dy((llp) = E X~p ((X)
where f RR, R is convex function with f(1) O. Given reference distribution p. an f-divergence D, and bound e, 2 O, we define the f-divergence constraint set to be:
Dj = (v P(X) Dy(vllp) S sc
Technically, this definition depends on the Radon- Radon-Nikodyn derivative of with respect to p. but we ignore measure-theoretic issues in this paper for simplicity of exposition. For continuous distributions, # and should be treated as densities, and for discrete distributions as probability mass functions.
Relaxations using f-divergence This construction immediately allows to obtain relaxations of Da..- For example, by choosing fu) = u (ug( we have the KL-divergence. Using KL-divergence yields the following relaxation between norm-based and divergence- constraint sets for Gaussian smoothing measures, i.e. p(x) = -x o²T):
Da. (u(x') || - (v:(((ll))) < 221(222))
Tighter relaxations can be constructed by combining mul- tiple divergence-based constraints. particular, suppose F is collection of convex functions each defining f-divergence, and assume each ʃ E has a bound e associated with it. Then we can define the constraint set containing perturbed distributions where all the bounds hold simultaneously (Fig. D:
P (X)
D
Da.e
D
D = n D = = Dy(vile) sef
JEF
Intersecting f-divergence con- 'd is an arbitrary distance function (not necessarily metric e-garittt obtain better relaxations Dz (de-
Figure I:
picted by the orange region) of Dr.c.
4

---

Published as a conference paper at ICLR 2020
In this paper, we work with the following divergences:
(1) Rényi: Ra (v = log(1 + D - 1) where
f() x -1 (for a 1), and R. (ellz) = log(1 - D)(()ll)))((a-1))))> with f(z) = 1- (for 0 v
S 1). The limit a + oo yields the infinite order Rényi divergence Rx (ulpp) = (u p(x))
(2) (T((Vlp) (y(llp)) with f(x) x: log(z))
(3) Hockey-Stice Sticck: (us.s(v(lp) = (vllpp) with f(x) = max(x - 3,0) - max(1 3, 0).
It turns out that the Rényi and KL divergences computationally attractive for broad class of smoothing measures, while the Hockey- Seckeey-tiikk divergences are theoretically attractive as they lead to optimal certificates in the information-limin to estimate general, so we only use them for Gaussian smoothing measures.
setting. However, Hockey-Stick divergences harder
2.3 COMPUTING F-DIVERGENCE BOUNDS
In general, our framework can be used with any family of smoothing measures and any family of divergences such that an upper bound on maXpeD... D [lp) can be estimated efficiently. We describe how f-divergence bounds can be obtained for several classes of smoothing measures:
Product measures Product measures are of the form μ(xx) (L=144(;; where X'
X
and is a smoothing measure on Xg We note that the discrete smoothing measure used in Lee al. 2019), the Gaussian measure used in (Cohen et al., 2019) and the Laplacian measure used in (Li et al. 2019) are all of this form. For such measures, one can construct bounds on Rényi- divergences subject to any lp norm constraint using a Lagrangian relaxation of the optimization problem max Se Ra ((((a))]l(()) (see Appendix A.3 for details).
Norm-based smoothing measures Appendix A.9.1 also shows how we can obtain bounds on the infinite-order Rényi divergence Rxx, well as on several classes of f-divergences, for norm-based smoothing measures of the form [X] x exp(-IIX - x=]).
3 OUR CERTIFICATION PROCEDURES
We now show how to reduce the problems of full-information and information-llimite robust black- box certification to simple convex optimization problems for general constraint sets D defined in terms of f-divergences. This allows us, by extension, to solve the problem for related divergences like Rényi divergences. The following two theorems provide the main foundation for the verification procedures in the paper.
Theorem 1 (Verifying full-information robust certification). Let DD be the constraint set defined by F ......., SM and f; e;. Define fx(u) = EM (u) and denote its convex conjugate by fx- The specification o is robustly certified at P with respect to D,= (cf. Definition 2.2) if a'and only if the optimal value of the following convex optimization problem is non nognnegativ::
max A 20.6
A
E [2(K - -(())
(6)
X~p
The proof Theorem D given in Appendix A.4 uses standard duality results to show that the dual of the verification optimization problem has the desired form. We note that the special case where M = 1 reduces to Proposition I of Duchi & Namkoong 2008)) although the result is used a completely different context in that work.
To build a practical certification algorithm from Theorem I we must do two things: 1) compute the optimal values of À and и; and 2) estimate the expectation in Eq. Since the estimation of the expectation cannot be done in closed form (due to the black-bor nature of Φ), we must rely on sampling. In step 1 of Algorithm I expectation and solve the "sampled" optimization problem using an off-the-shelf solver (Diamond
N samples taken independently from p estimate the
For any function, f: IR + R. its convex conjugate is defined f'(()) max.20 (uv f(w)).
5

---

Published as a conference paper at ICLR 2020
Algorithm 1 Full information certification (see appendix [A.9 for details of subroutines)
Inputs: Query access to specification & X - |a, b]. sampling access to reference distribution p. divergences fü and bounds e,, sample sizes N, _N, confidence level Ç.
I: k², X + ESTIMATTBOOT( o, N, {ff ) { (=))))))
a, , ,(). 3: xf E/ Ma Eu return CERTIFIED else return NOT CERTIFIED.
2: Eut t UPPERCONFEENEEBOUNDD Ø, N,,
Boyd, 2016). This gives us k"; X", the estimated optimal values of и and X, respectively. Then we take these values and compute high-confidence lower bound on the objective function of Eq. 6 which is then used to verify robustness. In particular, in step 2, we compute a high-confidence upper bound Eus on the expectation term in the objective such that Eus 2 Ex~plfX (x* x(X)) with probability least Ç: this computation involves taking Ñ independent samples from P and finding confidence interval around the resulting empirical estimate of the expectation (for details, see Eq. 25 in Appendix I.9.I]. Plugging in this estimate back into Eq. gives the desired high-confidence lower bound in step 3. Details of both subroutines ESTIMATEOPT and UPPERCONFDENCHBOIIN used in Algorithm| D are given in Algorithm 3 in Appendix(A.92.
Our next theorem concerns the specialization of this verification procedure to the information-limited setting.
Theorem (Verifying information- limited robust certification). Let Dy be as in Theorem [ and S and 0a. 0g be as in Definition [21] The class of specifications S is information-limited robustly certified at p with respect to Dz (cf. Definition 2.1 Il if and only if the optimal value of the following
convex optimization problem is non-negative:
min 6o.50:6020
Sa - co
Subject to
Sa + co + 11= (x((0)0) Sa i i= M,
where 0- = (0a, 0o. O₂ - 0,) and Ç (Sa: Cbs Se) are interpreted as probability distributions.
The proof of Theorem 2 is presented in Appendix A.5 It is based on the fact that in the information- limited setting, it is possible directly compute the expectation in Eq. 6 and in fact this expectation only depends on & via the probabilities 0g and 0g.
Theorem 2 naturally leads a certification algorithm, presented in Algorithm It simply uses the same procedure as Cohen et al.19) Section 3.2) to compute a high-confidence lower bound On on the probability of the correct class under randomized smoothing and then solves the convex optimization problem Fq. 7 Again, we can use an off-the-shelf solver CVXPY (Diamond & Boyd 2016) in step 2 for the general MM case, but flosed-form solutions are also available for M 1;
these are given in Table 4 in Appendix A.6
Algorithm 2 Information-limited certification
Inputs: Query access classifier h, correct label y, sampling access to reference distribution p. divergences fa and bounds et, sample sizes N, N. confidence level Ç.
1: Sample X ..... XN ~ p and tes
3 whether y = arg max Ey IP Pxmp [h(X)= = v/
2: Sample X1 ..... X. p and compute bound I' I'xx y'l 0g with confidence Ç.
3: Obtain o* by solving Eq. 7 with 0g + Dg and 02 + 1 - On.
4: of 2 0 return CERTIFIED else return NOT CERTIFIED.
4 THEORETICAL ANALYSIS OF CERTIFICATION METHODS
We now present theoretical results characterizing certification methods and show the following:
Using the algorithm from Hung & Fithian 2019 Using the algorithm from Clopper & Pearson 1934

---

Published as a conference paper at ICLR 2020
1. For smoothed probabilistic classifiers, the full-information certificate dominates the information- limited one.
2. In the information-limite setting, if we define the f-divergence relaxation Dz using Hockey- Stick divergences with specific parameters, then the computed certificate is provably tight.
4.1 ADVANTAGE OF FULL-INFORMATION CERTIFICATION
Consider soft binary classifier I1 X - [o, I] that outputs the probability of label +1 and consider
point v E X' with (x) > 1/2. We define the specification Φ(x)) = H(x) - -3. Then, the smoothed
classifier (z) = Ex-r(m) (X)] predicts label +1 for all x' with || x/| S and only if Φ is
full-information robustly certified (a(r)) with respect to Dz., {u(x²) || - xr|| S <). Note that
the optimization in Theorem I depends on the full distribution of 6(X) E 1-1/2. X ~ p(x). On the other hand, to certify this robustness in the information-
setting is equivalent taking the specification ((x) (x) > 1/2] (the indicator function of the event ((x) > 1/2), in which case the only information available la (x) = Ex~u(a) [X]].
To compare the two approaches, consider the objective of Eq. 6 with single f-divergence constraint D (w(lp))) S e. Then, we have
fx 1 -- ((x) + 1)
k - de
E X~u(w)
[F - x(x))) = n de AE-
E X~p(())
1 - H(X) +
1
(1- H(X)) ]
= R dc E
f1
11+ 2
16
X~H((E)
2)
2 k - dτ - E
k [k- H(X) + 12
(x+ 2
1
(1 H(X))
x~u(X)
1 - 2 - (1 - 0x)f2 x+() 1
= dE - 0afx
K
where the third line follows from Jensen's inequality. The proof of Theorem shows that maximizing the final expression above with respect K, À is equivalent the dual of the information- certification problem Eq. 7 Thus, the information-limite setting computes a weaker certificate than the full-information setting for soft classifiers:
Corollary 3. The optimization problem of Eq. with the specification & defined above has an optimal value that greater than or equal to that of the optimization problem defined in Eq, 7
4.2 TIGHT RELAXATIONS FOR INFORMATION-LIMITED ROBUST CERTIFICATION
Ideally, we would like to certify robustness of specifications with respect to sets of the form Dz,e {u(x') d(æ,x') x²) S e). The following result shows that the gap between the ideal Dz. and the tractable constraint sets DD= can be closed in the context of information iiromattio-limitedd robust certification provided that we can measure hockey-stick divergences of every non-negative order B 2 The proof is given in Appendix[A.1
Theorem 4. Let Oay Ob p, D, S be in Definition 2.1 Define Eg = maxxeD Dus,s(ullp) for all B3 2 0 and let 3% 3g be chosen as follows:
92.33 arg max A. 2.20.0
1- 1- -aa) BBbo - (cs. [1 - Bal+)) - (co, + +11 (bl+) (8)
Define the constraint set
Dns {v E P(X): Dus:: (v p) f P(X): Dusse (v/ 1l p) S <
Then, S is information-limiter robustly certified at p with respect to D if and only if S is information- limited robustly certified at p with respect to Dns. Thus, the optimal information-limite. certificate in this case can be obtained by applying theorem to DHs.
5 CONNECTIONS WITH PRIOR WORK
Table I summarizes the differences between our work and prior work in terms of the set of smoothing measures admitted, the offline computation cost of the certification procedure (which needs to
7

---

Published as a conference paper at ICLR 2020
be performed once for every possible perturbation size and choice of smoothing measure), the perturbations considered, whether they can use information beyond 0a &g to improve the certificates and whether they compute optimal certificates for given smoothing measure in the information- limited setting.
(A(z)
Computation
II-1
Use additional
Optimal
information?
Cohen et al. (2019)
Gaussian
0(1)
82
X
Yes
Lee et al.
2019)
Finite
0(dy)
Eo
Only decision trees
Yes
Support
Li et al.
(2019)
Gaussian
O(1)
&2
X
No
Laplacian
&
Lecuyer et al. (2019)
Arbitrary
All Ep O(L)
X
No
Our work
Arbitrary
O(1)
All Ep
Arbitrary classifiers
Yes
Table 1: Comparison between black-box verification methods. Technically, Lee et al. (2019) can handle smoothing measures such that the likelihood ratios take finite set of values, but most practical instances of this correspond to finite-support distributions.
Cohen et al. 2019) study the problem of verifying hard classifiers smoothed by Gaussian noise, and derive optimal certificates with respect to l2 perturbations the input. Their results can be recovered as a special case of our framework when applied to sets defined via constraints on hockey-stick divergences. Theorem shows that the optimal certificate in the information ieformation-limitedd setting can be computed by applying theorem to constraint with two hockey-stice divergences.
can be computed closed form and is purely function the lz distance || - x 2'112- This enables us to efficienctly compute the 3g Pf in theorem Thus, we obtain the following result (see Appendix
For the Gaussian measure μ(x) = N(z,o²1) the HS divergence
A.7.2 for proof):
Corollary 5. Let p (zz,0²1) Dr..- = (M(z',0)) ||-- x'112 S and > 0g 0g
Let Das be defined as in theorem [ Then, applying theorem 2 the constraint set DHS gives the following condition for robust certification:
( :) V.
0,)
>
where V is the CDF of a standard normal random variable WO0 1). With straightforward algebra (worked out in appendix A.7.2) this can be shown to be equivalent
2c
9 (O,) 1 v
which is the certificate from Theorem of Cohen et al. (2019)
Lee et al. 2019) derive optimal certificates in the information-limiiee setting under the assumption
that the likelihood ratio between measures *(X)
s(X) (where pux'), ((z)) only take values
from a finite This is restrictive assumption that prevents the authors from accommodating natural smoothing measures like Gaussian or Laplacian measures. Further, the complexity of computing the certificates in their framework is significant: is needed to certify smoothness to to perturbations. The authors also derive tighter certificates for the special case of certain classes of decision trees by exploiting the tree structure. In contrast, our framework can derive tighter certificates in the full-infornation setting for arbitrary classifiers.
(dd) computation (where d the input dimension)
Li al. 2019) use properties of Rényi divergences to derive robustness certificates for classifiers smoothed by Gaussian (resp. Laplacian) noise under la (resp. L1) perturbations. Their results can be obtained as special cases ours; in particular, the Rényi divergence certificates in Table X (in Appendix A.6) recover the results of Lemma of Li al. 2019), but the latter only applicable for Gaussian and Laplacian smoothing measures.
Lecuyer et al. (2119) introduce the notion of pixel differential privacy (pixelDP) and show that smoothing measures μ satisfying pixelDP with respect to a certain type of perturbations lead to adversarially robust classifiers. We can show that piXelDP can be viewed special instance of our
8

---

Published as a conference paper at ICLR 2020
certification framework with two specific hockey-stick divergences, and that the certificates derived from the pixelDP are provably dominated by the certificates from our framework (Theorem I with the same choice of divergences (see Corollary 7 Appendix ).7.3)
EXPERIMENTS
6.1 FULL-INFORMATION IMPROVES UPON INFORMATION- CERTIFICATION
To compare full-information certificates with limited- information certificates, trained a ResNet-152 model on ImageNet with data augmentation by adding noise via sampling from zero-mean Gaussian with variance 0.5 for each coordinate; during certification we sample from the same distribution to estimate lower bounds the probability of the top predicted class. For the full- information certificate,
Infomation-lmitted certificate
10
hockey-stick diver- gences for the certificate and tune the parameters 3 to obtain the highest value in the optimization problem in step 2 of Algorithm| [ For the infromation-limiiee certifi- cate, our approach reduces to that of (Cohen et al.) (2019) and we follow the same certification procedure. We use N = 1000 Ñ = 1000000, = .99 for both certification procedures.
2
010
2
8
10
Full information certificate
Figure 2: Information -iimitedd vs full- information certificates for ImageNet for & perturbations. The dashed line represents equal certificates and every point below the dashed line has stronger certificate from the full information verification setting. We run the comparison 50 randomly selected examples from the validation set. Each blue dot in Figure corresponds one test point, with its x coordinate representing the radius for full information certificate (from Algo- rithm D and y coordinate the information- limited certificate (which is equivalent to the certification procedure of Cohen et al. 2019). The running time of the full-iitormation cer- tification procedure is .2s example (ex- cluding the sampling cost) while the limited- information certification takes .002s per ex- ample. Both procedures incur the same sam- pling cost as they use the same number of samples.
Figure Firresssswwws the difference between the two certificates. The certificate provided by the full-information method is always stronger than the one given by the information- limited method. The difference is often substantial for one of the test samples, the full-information setting can certify robustness to f2 perturbations of radius e = 9.42 in the full-information certificate can only be provided for perturbation radius 2.69.
while the umited-informatioon
6.2 SCALABILITY AND TIGHTNESS
In this section consider tu perturbations for both Ima- geNet and Binary MNIST (that is, we consider the number of pixels that be perturbed without changing the pre- diction). To test for scalability and tightness trade-offs of our framework. we compare our methodology that of Lee et al.) (2019), as their work obtains the optimal bound for to We computed certificates for single model for each classification task; for Binary MNIST we used the same model and training procedure as Lee et al. (2019) and for ImageNet, we used the model released in the Github code accompanying the paper of Lee et al. (2019). We use the discrete smoothing measure (appendix(A.I) Io with parameter
0.8 for Binary MNIST certification, and
0.2 for ImageNet certification.
In our experiments we ran the certification procedures on all test examples from the Binary MNIST dataset, while for ImageNet, following prior work (Lee et al.) 2019) Cohen et al. 2019), on every 100th example from validation set. The proportion of the examples for which accuracy can be certified are reported in Table 2 for various values of e. Comparing with the optimal certificates obtained by the certification method of Lee et al. (2019), the table shows that our bounds remains tight for Binary MNIST up until 3, and we do so with 130 times speed-up. For ImageNet. our bounds differ only about 7-15% in terms of accuracy, and we obtain this with approximately 20 million times speed-up.

---

Published as a conference paper at ICLR 2020
Dataset
Cortificate
Smoothing Value
Computation Time
Cortified Accuracy
<= 2
==3
3
c
==
5
==7
Binary MNIST
Lee et al.
2019
0.8
3.68s 0.028s
0,919
0.767
0.530
0,513
0.348
0.194
0.095
Ours
0,919
0.767
0.530
0.296
0.162
0.080
0.015
ImageNet
Lee al. 2019
0.2
days
0.488
0.418
0.310
0.250
0.244
0.234
0.224
Ours
0,028s
0,362
0.262
0.224
0.186
0.136
0
Table 2: Proportion of the examples with verified fo-robustness for different accuracy (e) parameters.
6.3 CERTIFICATION FOR AUDIO CLASSIFICATION: LIBRISPEECH
Audio classification systems have been shown to be susceptible to adversarial attacks (Qin et al. 2019). However, building audio classifiers that provably robust to adversarial attacks has been hard due to the complexity of audio processing architectures. We take a step towards provably robust audio classifiers by showing that our approach can certify robustness of classifier trained for speaker recognition on a state-of-the-ar model for this task. We focus on to perturbations that zero out fraction of the audio sample, as they correspond missing data in an audio signal. Missing data can occur due to errors in recording audio or packets dropped while transmitting an audio signal over a network and is a common issue (Turner 2010 Smaragdis al.. 2009).
In principle, the method of Lee ct al. (2019) is applicable to compute robustness certificates, but at an impractically large computational cost, since the computation needs to be repeated whenever an input of a new length (for which certificate has not previously been computed) arrives. Concretely, this constitutes an (dd)) computation for the length ranging from 38 to 522,320 (the set of audio sequence lengths observed in the Librispeech test dataset (Panayotov et al. 2015)).
The results are shown in Table 3 To the best our knowledge, these are the first results showing certified robustness of audio classifier. We believe this is significant advance towards certification of classifiers in audio and classifiers operating on variable- inputs more generally.
Dataset
Certificate
Smoothing Value
Computation Time
Certified Accuracy
6=1 1
<=2
6
3
<=
4
<
5
=
<=
0.5
0.511
0.225
0.091
0.091
0.091
0.091
0.091
0
Librispooch
Ours
0.7
0.028s
0.885
0.634
0.405
0,405
0.405
0.405
0
0.9
0.872
0.772
0.711
0.711
0.711
Table 3: to robustness results for Librispeech (Panayotov et al. 2015). From the Librispeech dataset, we created corpus of sentence utterances from ten different speakers. The classification task is, given audio sample, predict whom speaking. The test set consisted of 30 audio samples for each of the speakers. We use a DeepSpeaker architecture (Li et al. (017). trained with Adam optimizer (3, 0.9, B2 0.5) for 50,000 steps with a learning rate of 0.0001. The architecture is the same as that Li et al. (2017). 7. except for changing the number of neurons in the final layer for speaker identification with ten classes. Three models were trained with smoothing values of p 0.5, p 0.7, and p 0.9, respeetively, and we used the same values for certification. Certification was performed using N = 1000, Ñ = 1000000, Ç = .99 using M = 1 Rényi divergence, with tuned to obtain the best certificate. The proportion of samples with certified robustness for different accuracy values are reported, computed on 300 test set samples.
7 CONCLUSION
We have introduced a general framework for black-box verification using f-divergence constraints. The framework improves upon state-of-the-art results on both image classification and audio tasks by a significant margin in terms of robustness certificates or computation time. We believe that our framework potentially enable scalable computation of robustness verification for more complex predictors and structured perturbations that can be modeled using f-divergence constraints.
REFERENCES
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological) 28
10

---

Published as a conference paper at ICLR 2020
(1):131-142, 1966.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
Yves Audibert, Rémi Munos, and Csaba Szepesvári. cuploratioo-exploittttiee tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):187--100, 2009.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference Machine Learning, pp. 403-412, 2018.
Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs. In International Colloquium on Automata, Languages, and Programming, pp. 49 60. Springer, 2013.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Sindic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Sebastian
Bubeck.
Or1523
(advanced
optimization): Introduction. intpiiiiiitttiiiinttouuuiiitooo
2013.
Charles Clopper and Egon Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404 413, 1934.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized 2019.
smoothing. arXiv preprint
Imre Csiszár, Paul C Shields, et al. Information theory and statistics: A tutorial. Foundations and Trends(R Communications and Information Theory, 1(4):417-528, 2004.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embeddded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2999-9113 2016.
John Duchi and Hongseok Namkoong, Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:/810.08750, 2018
Krishnamuthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli, Towards scalable verification of neural networks: dual approach. Conference on Uncertainty in Artificial Intelligence, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Machine Learning, 2015.
Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishna- murthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. arXiv preprint arXiv: 990.00142, 2019.
Kenneth Hung and William Fithian. Rank verification for exponential families. The Annals of Statistics, 47(2):758-782. 2019.
Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified robustness to adversarial word substitutions. arXiv preprint 190.0099,,000966, 2019.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
11

---

Published as a conference paper at ICLR 2020
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. A stratified approach to robustness for randomly smoothed classifiers. arXiv preprint 12Xiv:990.004944 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noises. In Advances Neural Information Processing Systems, 2019.
Chao Li, Xiaokong Ma, Bing Jiang, Xiangang Li, Xuewei Zhang, Xiao Liu, Ying Cao, Ajay Kannan, and Zhenyao Zhu. Deep speaker: end-to-end neural speaker embedding system. arXiv preprint 1755v:1705.02304, 2017.
Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions on Information Theory, (1110)4334444122 2006.
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
V. Panayotov, G. Chen, D. Povey, and S. Khudanpur. Librispeech: An asr corpus based on public domain audio books. In 2015 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 5206-5210, April 2015. doi: 10. 10.109//CASS22215..77785
Yao Qin, Nicholas Carlini, Ian Goodfellow, Garrison Cottrell, and Colin Raffel. Imperceptible, robust, and targeted adversarial examples for automatic speech recognition. arXiv preprint arXiv:1903.10344 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018. URL https:// openreview net forum? (it.orummmddBBssob-o-a--
Paris Smaragdis, Bhiksha Raj, and Madhusudana Shashanka. Missing data imputation for spectral audio signals. In 2009 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1-6. IEEE, 2009.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
Richard E Turner. Statistical models for natural sounds. PhD thesis, UCL (University College London), 2010.
Jonathan Uesato, Brendan O' O'Donoghue, Aaron van den Oord, and Pushmeet Kohli. Adversarial risk and the dangers of evaluating against weak attacks. International Conference on Muchine Learning, 2018
Eric Wong and J Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. International Conference on Machine Learning, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-8409, 2018.
12

---

Published as a conference paper at ICLR 2020
A
APPENDIX
A.1
ADVERSARIAL SPECIFICATION FOR SMOOTHED CLASSIFIESS
Note that for any v E Dz,e we have
lon (X)]= P [M(X)= = d- P (M(X) =
Xau
X-
Xve
Therefore, Oxx-lood arg maxxxx Px-= ((x) w/. For v = u(x'), this means that (2,)2)) (assuming the argmax is unique). In other words, E. Ex_. c (X) 2 0 for all c' E y {c} and all u(x²) E Dz.c if and only (x(x)) = c for all x' such that d(x, x²) S proving the required robustness certificate.
2 0 for all d' E Y {c} is equivalent to
A.1.1 ROBUSTNESS SPECIHICATION FOR SMOOTHED SOFT CLASSIFIERS
Consider soft classifier H : X - P(Y)) that for each input returns probability distribution H (a) over the set of potential labels y' (e.g. H might represent the outputs of the soft-max layer of a neural network). As in the case of hard classifiers, our methodology can be used provide robustness guarantees for smoothed soft classifiers obtained by applying smoothing measure u(z) to the input.
In this case, the smoothed classifier is again soft classifier given by (z( Ex~p(z)
(H())) (X)).
Let be fixed input point and write p Hzxx) E P(Y) to denote the distribution over labels. number of robustness properties about the soft classifier H, at I can be phrased in terms of Definition 2.2 For example, let y {1...., K} and suppose that p1 P2 2 2 Px so that {1,.... kj are the top k labels at x. Then we can verify that the set of top l: labels will not change when moving the input from x x' with || pe--r" x'1 e by defining the specifications (z, = H()) Hz), for i E [1, k] and
[k + 1, K]. and showing that all of these dv, are robustly certified at μu(x) with respect to the set Dz, defined above. The case k 1 corresponds to robustness of the standard classification rule outputting the label with the largest score.
Another example is robustness of classifiers which are allowed to abstain. For example, suppose we build a hard classifier out of He which returns the label with the maximum score as long as the gap between this score and the score of any other label is at least otherwise it produces no output. Then we can certify that h will not abstain and return the label arg max Py at any point close to by showing that every (2) = H()). H(z)e y, d' * is robustly certified at μ(x) with respect Da,c-
A.2 BACKGROUND ON F-DIVERGENCES
number of well-known properties about f-divergences are used throughout the paper, both explicitly and implicitly. Here we review such properties for the readers' convenience. Proofs and further details can be found in, e.g.. (Csiszár et al. 2004 Liese & Vajda 2006).
Recall that the f f-divergences can be defined for any convex function f R. - R such that f(1) 0.
We note that this requirement holds without loss of generality as the map x + f(x) f(1) is convex whenever is convex. Any f-divergence Dy satisfies the following:
1. (y(p))p) 2 0.
2. (y(el))) = 0, and (y(p))p) = 0 implies v = whenever f is strictly convex at 1.
3. (F(((())))F.())) < (Pllp) for any function F, where (p(p) is the push-forward of p.
4. Dy(elle) Df(pllu) where f(() uf ( is again convex with f(1) 0.
A.3 BOUNDING RENYT DIVERGENCES
We being with the optimization problem
max R., (m(=')ll((()
(10)
subject to || - x x'11p Se
13

---

Published as a conference paper at ICLR 2020
Since have Ra(u(=')llu(a E, Ra(m(())))l The constraint be rewritten as
Σ l0s - Se
Forming the Lagrangian relaxation, we obtain
Σ Ra (a( +y Σ |z xjI 2)
max at: ='11//-2115
where the constraint each 2 to obtain
|ar/ xzsl S e is implied by ||æ1 - x1l S... We can maximize separately over
ycP + Σ
max s(lccl-,,cted
(a + Ma. -2:1"
By weak duality, for any 7 2 O, this an upper bound on Eq. TO can minimize this bound over y 0 to obtain the tightest bound.
The minimization over zy for each can be solved in closed-form or via as simple I-dimensional minimization problem for most smoothing measures.
A.4 PROOF OF THEOREM
For simplicity of exposition (and to avoid measure theoretic issues), we focus on the case where v, p have well defined densities v(z), p(z) such that p(x:) whenever v(x) O.
We begin by rewriting the optimization problem in terms of the likelihood ratio r(X) have
v(x), We p(X)
X~u [[(]] [ (XX)
(j.(pl))= = x-p I,((()))))
E ix()] 11, X~D
X-pp x-p
where the first two equalities follow directly by plugging in (x) ((X)r(X) and the third is obtained using the fact that is probability measure. Using these relations, the optimization over can be rewritten as
min (x())x(X) r20 X~p
(1I)
subject to E [f((((X)]] c. X-p
E [ 1 X~p
where r 2 0 denotes that r(x) 20 Vr E X. The optimization over is a convex optimization problem and can be solved using Lagrangian duality as follows we first dualize the constraints on to obtain
min E (XX)((X)) +Σ r20 Xmp
N E X -0 + k x 1
E. [x())) Xmp
min E r(X)o(X) Exi((())) - xT(X) -x(()) + +x -x-Exe
r20 X~p
Exee-
E
max ro(x) Σ (us((tt)
Xmpp
+20
Σ XiGs Exic=
F.
max (r(n: - ((()) Sa(r))
X~pp
r20
Σ A. ENG
E [fA( x(x))
X~p
By strong duality, it holds that maximizing the final expression with respect to À 2 0, achieves the optimal value in Eq. II robustly certified and if it larger than 0, the specification is robustly certified. Finally, since
Thus, the optimal value smaller than 0, the specification is not
14

---

Published as a conference paper at ICLR 2020
ultimately interested in proving that the objective is non-negative, restrict ourselves to À 2 such that E; A; = 1 (since if the optimal added up to something larger, we could simply rescale the values to add up to 1 and multiply by the same scaling factor without changing the sign of the objective function).
This concludes the proof of correctness of the certificate Eq. 6
A.5 PROOF OF THEOREM
For the next result, we observe that when @ is ternary valued, the optimization over K, À ahove can be written
Σ>rE: Mrs 0nf2(K 1) 0xf2 0x)2(k))
Σ
max k,A20
where 02 xx-p
(o()
-1, =1xp0==xx~pp((x7 --1,, (Pxxpll()) 0J.
Writing out the expression for , we obtain
Σ Aec 8a (15 - 1)Ya - E Aafi(Taa) Ensi(laa) - 0b -0(( - (efi((o))
max min A
1)/10
A20 720
0e KYf - Σ (afs((aa
= min max R11 - %
0b% - 0e7c) + Σ X
Σ (yfi(%)) - cs
+ Oa - 087
720 A20,*
(a,bcc)
where the second inequality follows from strong duality. The inner maximization is unbounded unless
Σ
7,0, =1
Σ
0gfilTy) 6
vE(.bb.c)
vEta.b.))
One thing to note is that, we can rewrite these constraints in terms of ( = 0 o i.e. G. = fyy for y {a, b, c). These constraints ensure that is probability distribution over (+1,0, -1} and furthermore
Σ 0gfilTy) Dr, (C|10) (a,bb.)))
Thus, the second constraint above equivalent to D (C]l S e;. Writing the optimization problem in terms of ç, obtain
min 20.
Sa -a 56
subject to D, (5110) S G i I....,M
Sa + Gb + Se =
A.6 CLOSED-FORM CERTIFICATES FOR THE INFORMATION-LIIIIA SETTING
In this section we present closed-form certificates for information limined setting which can be derived from Theorem for M 1. The results summarized in Table In the next subsections we present the derivation of the certificates for Hockey-Stie -tckky-Stickkao and Rényi divergences. The certificates for the KL and infinite Rényi divergence can be derived by taking limits of the Rényi certificate (as a > 1, oo respectively).
A.6.1 CALCULATION CERTIFICATE FOR HOCKEY-STICK DIVERGENCE
The function f(u) max(u- 8,0) max(1 -3,0) convex function with f(1) Then, have
fx( = max (wv Amx((u - -3,0) + A max(11 - -3,0) 220
max((Bu, 0) + Amxxx1111 - 3)
if $ if u > X
15

---

Published as a conference paper at ICLR 2020
Divergence constraint KL divergence
f(u) logguu)
Certificate
EKL S - log 1 --0V - -0D)
von)
pL(v S CKL
<R,a S - log - 02 0b + 27)
Rényi divergences (a 2 0)
sign(a 1)(w1=(()))
(1-.)
Ra(v)Ip) CR,a
0, 0,(1-0) 4.0 (1-a)
7
Infinite Rényi divergence
RR,00 I -log(1 (1 (0a 0b))
Rs. (vllp) 6R.00
Hockey-stick divergences (B 0) a < EHS,8
(u B] - B)+ CHS,3
8(00 (0l0--1))-
B 8-11
Table 4: Certificates for various f-divergences for the information- setting. Note that the Rényi divergences not proper f-divergences, but defined as (a((l))) o- log(1 + ()(vlpp)). The infinite Rényi divergence, defined sup, log(v(x)) p(x))), is obtained by taking the limit - xc. All certificates depend on the gap between 0g and 0g. Notation: [w] = (ax 0).
The certificate given by Eq. in Theorem ! for this divergence in the case of a smoothed hard classifier takes the form
[52(K ((x))) de 2 Xmp
max xER,A20
K
E.
where the specification takes the values
+1
w.p. 0g
((X)=
w.p. 0,
w.p. 0g - 0,
Plugging in the expression for f" the objective function above takes the form
(0. j + + 0/| + 1] + (1 11-6,. 6, (,)[m),) - X(e max(1 - 3,0))
where we use the notation [u] = max(u, (u. 0) and assumed the constraints S À - since the
objective is -o otherwise. If 3 < 1, the objective is increasing monotonically K, so the optimal value is to set its upper bound À 1. Plugging this in, the possible values of the derivative with respect to are
331 0.) _0,
if <<1,
if < <
>
Thus, if S 30., the maximum is attained at 2, if 30,, < S B(1 - 0b). the maximum is attained at else the maximum is attained at 0, leading to the certificate:
if 2 3(1 0g)
B(1 0.) -c-1
if A0, < c S B(1 6b) if 39,
[[1 + (0. 0b)) 2c
Thus, the certificate is non-negative only if
(3 (0.. 0b)) .0)
C max
The case B21 be worked out similarly, leading to
3(-1+ (0, 0b)) + 0
S max
The cases can be combined as
3(0, - -06) - -13 0)
6 S max
2
16

---

Published as a conference paper at ICLR 2020
A.6.2 CALCULATION CERTIFICATE FOR RÉNYI DIVERGENCE
We consider the cases and < separately.
Case 1 (a 2 1) If a 2 1, the function f(u) = (u- is a convex function with f(1) = 0. Then, we have
if
fu(u) = max un 1(00 -1 Y A -a 000
if
max((. 0)
= A(a 1aa- 1)
Ace
Suppose we have bound on the Rényi divergence Ra (wllp) S Then we know Dy(vllp) s exp((a - 1)e) 1. Let 3 = T and
B = 0g (0ax(0, k 1))² + 0, (max(0, + 1))² + (1 - 0₂ - ())(ma x))
Then the certificate Eq. simplifies to (after some algebra)
max Aexp((a 1)e) BX BX (a (a-11 x20
a²3
Setting the derivative with respect to À to 0 and solving for X, we obtain
B (1)
A exp((a 1)e)
and the optimal certificate reduces to For this number to be positive, we need that 2 and
(
max K B exp
exp
B
The LHS above evaluates to
-
(0, max(0,1 7)8 0 max(0, 1 + 7 0, -0,)
where 7 = - 2 0. Maximizing this expression with respect to 7, we obtain
ga-1 1 05-1
7 00 0g
so that the certificate reduces
+ - 0, -0b) 00)) 2 exp
(t)
c
3
Taking logarithms now gives the result.
Case 2 (0 < 1) When 0 < 1, the function f(u) (1 u²)) is a convex function with
f(1) = 0. Then, we have
x a - { (-1%a)
(1(w) = max uv A(1 - A(1- 200
-2))=
if u 5 otherwise
x
Further, a bound (v(p)) implies
Dy(ullp) < 11-exp((a 1)c)
17

---

Published as a conference paper at ICLR 2020
Then the certificate from Eq. reduces
max & + Xexp((a 1)c) - (1 - a (ol(1 x))=aaa k,A20
r + 00(-11 k) T + 0c(-x) 1
with the constraint K. < (otherwise the certificate is -0o). Setting the derivative with respect to and solving for X, we obtain
exp((a-1)e( 1)e((-9) 1-
aw
where
[oa(1 - + 0s(-1 k) 1 + Oel-o 0o(-x)
Plugging this back into the certificate and setting B a we obtain
exp (-$)
K +
For this number to be positive, require that
exp
kW
3
The LHS of the above expression evaluates to
(#)
(1((1)) 0,(1 - 7-)(-0) + 0a -6,)
where y 11 Maximizing this expression over
[0, 1], obtain the final certificate to be
(-))
1 1 0n 11-0--00 - 0, +
01-a + 0 -a
exp
2
3
Taking logarithms, obtain
01-a
02-a
(TL
c < -log 1- 0a -6 +
2
A.7 INFORMATION-LIMITA ROBUST CERTIFICATION AND TIGHT RELAXATIONS
A.7.1 PROOF OF THEOREM
At a high level, the proof shows that, in the information-limited case, achieve robust certification under an arbitrary set of constraints D it suffices to know the "envelope" of with respect to all hockey-stick divergences of order 3 > 0, i.c. the function 3 + maxvED DHs, (v|pp) captures all the necessary information to provide information-limite robust certification with respect to D.
We start by considering the following optimization problem:
min (-X++1110. (10.00++)..e +I X
E [XX]
subject to
E [X()(( = +1]] 2 0 x-p
(12)
E [1 (XX) = =-1] s 0,
X~p
In the information-liminnn setting, this problem attains the minimum expected value over ø E Here (x)( 1] denotes the indicator function.
18

---

Published as a conference paper at ICLR 2020
It will be convenient write this in slightly different form: Rather than looking at the outputs of y as the +1, 0, -1, we look at them as vectors in R
2
0
1
and define
1
a
a+
a
0
Then, we can write the optimization problem Eq. 12 equivalently as
min
E a
V:A-ZZ
Xav
subject to
F. a+ X~p
[(X) 2 0g
(13)
E [a (X)] - 0,
We first consider the minimization over V for a fixed value of v. We begin by observing that since the objective linear, the optimization over V can replaced with optimization over the convex hull of the set of V that satisfy the constraints (Bubeck 2013). Since each input E X can be mapped independently the rest, the convex hull simply the cross product the convex hull at every x, to obtain the constraint set
W X + P(Z) such that E X~p
[[a[
2 tar E a [x)) S $b x-p
Therefore, the optimization problem reduces to
E a (X)) VxX+P((2) Xor
min
subject to
E
Jay
TV (X)]
2 0,
(14)
X~p
E aa X~p
T v < 0,
This is convex optimization problem in V. Denote
r(X) v (XX
p(X)
Considering the dual of this optimization problem with respect to the optimization variable V we obtain
min F. Xap
- Xo
E. Xmp
Ja+ T [V)) - 0a + Ao
E.
[a_ TV(X)] 0bb
Xmp
min Ng. 2oo + E (r(X)a- Aaa_ Asaa) ) " T(((
Xmpl
r(X)- do T
min XaO, XaOs + E
0 -r(X)++
v(X)
Xeup
Ao
Since can choose (x) independently for each X, we minimize each term in the expectation independently to obtain
rxx)
T ((x) min(r(x) - -, -r(x))r)) + X²)
min ((x))((2)
0
(((x) + Ao
This implies that the Lagrangian evaluates to
XaOa dso, Xmp
E [min(((X) Aa. O, + Av))]
We now consider cases:
19

---

Published as a conference paper at ICLR 2020
Case 1 (Au 2 d 0) In this case,
that
min(r(X) - Aa O, -r(X) As) = min(r(X) - Xa, 0) + min(-r(X) + ),,
= r(x) Aa max(r(X) Xa, 0) max(r(X)- 0)
Then, the Lagrangian reduces to AaOa - Λgo + E Xmp
[xx) dal E mmax(r(X) Xa, 0)] - E mmax(r(X) Ab,0)] 0]] Xmp
X-p
=1 -a(a 0a) 200 - (Dus, (wlpp) + max(1 da, 0)) - (Dns. (ulpp) + max(1 Ao, 0))
Case 2 (A6 2 Aa 200 0) In this case, we can see that
min(r(X)- Aa, -X()
An) min(r(X) Xa, -r(X) ( Ad)
Ae d
=r(X) Aa + 2in
0,
r(x)
Aa + Ao
do .0) 00.
-((X) Aa max
r(X)
2
Then, the Lagrangian reduces to
Aa + d
AaBa -b00 + E [r(x) - -al- - Xmp Xmp
max r(x)
2
=1 Aa - 0a) 20b - 2 -2 Aost Aot (wllp) + max 1
Aa d 1))
We know that 1 - 02 > 0b and As Ao. A6 Ao by choosing X = A and X/, d k for some small &: > O, we know that the the sum of the first three terms would reduce while the final term would remain unchanged. Thus, at the the optimum in this case, we obtain
assume A A and
1 Aa 0.) 2go 2(DHs.A. (wllp) max(1 Xa 0))
Final analysis of the Lagrangian Combining the two cases we can write the dual problem as
max - >a (1- 0a) Agos - (DHs. (vllp) + max(1 - Aa, 0))
A 2,
(15)
(DHS,A, (w|pp) + max(1 \o, 0))
By strong duality, the optimal value of the above problem precisely matches the optimal value of Eq. 14 (and hence Eq. 12]. Thus, information limited robust certification with respect to holds
and only if Eq. 15 has non-negative optimal value for each D. Since we have that
max DHS.A, (vlpp) = C2 max DHS. (Vllp) CAo
DED
DED
information- limited robust certification holds and only if the optimal value of
max 1 Aa 0.) - -,00- - (Ex. max(1 - >o. 0)) - (Ex, + max(1 - Ao, 0)) (16) A. 2,2020
non-negative. Further, since the optimal value only depended on the value of (Hsl)(H()p) for 3 2 0, it is equivalent to information-limin limited robust certification with respect to DHs.
The above argument also shows that in this case, information-limin robust certification with respect to 'D is equivalent to requiring that the following convex optimization problem has a nog-negat optimal value:
max 2,2200
1- -(11-.) 0.)) Xudo (Ex. + [1- -1-1)l4)) (Ex, + --bl+))
(17)
Let X5 X; be the optimal values attained. Since this certificate depends only the value of two Hockey-stick divergences at Ag Xg, it must coincide with the application of theorem the constraint set DHs defined by constraints these hockey-stick divergences (as know that 2 computes the optimal certificate for any constraint set defined only by a set of f-divergences). This observation completes the proof.
20

---

Published as a conference paper at ICLR 2020
A.7.2 GAUSSIAN SMOOTHING MEASURES
Theorem 4 gives us optimal limited- initee-iiformmtton certificate problem provided that we can compute
max D (a))
xx [0)0())))) Se
for each 3 2 0. In particular, when is a Gaussian measure p(x) NMx, o2), can leverage the following result from Balle Wang (2018).
Lemma 6, Let Vg be the CDF of a standard normal random variable (0, 1). For any B 2 0 and x E Rd we have
Dus,o(u(z')lu(a)) = V, ( log(3)o
BV4 (
log(3)o
max wt -- Se
[1 31
20
2e
2o 2e
Applying Eq. 17
to the expression in Lemma 6 proves Corollary
Proof of Corollary
5
With the notation from Theorem
we have, for / 2 0,
log(3)o
log(3)o
CB
V
3V
max -,0)
20
2E
2x
2c
Plugging this expression into Eq.
17 allows us to verify information-limited robust certification of x'll2 S c} by solving
N(x, o² I) with respect Dz,
N2'',0211 ||
max 1 - Aa 0a) Xuo Aa2A.20
log()a)o
log(Aa)o
e
V/
Aa Vg
20
2F
2x
2
log(Ao)o
log (Nolo
V g
A V
2x
2c
2a
2c
Eq. 9 then follows from setting the derivatives of this expression to with respect to Aas A and imposing the condition that the optimal solution is non-negative.
To check that Corollary is equivalent to the optimal certification in (Cohen et al. 2019 Theorem first recall that,
notation, their result be stated as: the class of specifications in Definition 2.1 is information-limited robustly certified at = W(x,o21) with respect to Dr.r (N(x' o0
| x'112 }} if and only if
(0.) 1/ (0,)
(18)
The equivalence between Eq. and Eq. now follows from the identity (,( (- and the monotonicity of L g:
V (8.) )) + V (1- -0.-,,, 06) - 2) 21
2 1 - V, 11 0b) - 2)
V
V (0.)
V (0.) )) > v. ( V. 0b)
+
V. (0.)
1 0.)
2e
1 (0.) + 1 - 0)) 2
26
(..) -. (0)) z
21

---

Published as a conference paper at ICLR 2020
A.7.3 RELATION TO PIXELDP
Pixel differential privacy (pixelDP) was introduced in Lecuyer al. (2019) using the same similarity measure between distributions used in differential privacy: a distribution-valued function G R
P(2)) satisfies (e, T) -ppielDD with respect to Ep perturbations if for any | x'Ilp S it holds that DDP,e= (G())))(( S T, where
or (G(z)) = sup
X e
X E Fi) X'
P
(19)
X~G(x))
and the supremum over all (measurable) subsets E Z. In particular, Lecuyer al. show that using smoothing measure μ satisfying pixelDP with respect to fo leads to adversarially robust classifiers against S perturbations.
To show that their result fits particular instance of our framework, take p= u(x)) and fix 2 0 and r E [0, 1]. Due to the symmetry of the constraint || - ='I1p S 1, p satisfies (c, -ixxelDD with
respect to Ep perturbations, then we have the relaxation condition [u(x²) || - x'Ilp S 13 C D2. where
- Drp, (ullp) S and Dr (ollv) ST}
(20)
Now we recall that Barthe & Olmedo 2013) noticed that DDP, e equivalent to the hockey-stick divergence DHs.3 of order 3 = e". Thus, since f-divergences are closed under reversal (property 4 in Appendix A.2). we see that the constraint set De,7 can be directly written in the form Dy (cf.
Section 2.2
The main result Lecuyer al. (2019) uimited-informant black-box certification method for smoothed classifiers. The resulting certificate for, which provides certification with respect to De.r. given by
2
T S e +
(21)
For comparison, the certificate obtain for the relaxation {v DDP (w]lp) < J of De.r (HS
certificate Table 4 already improves on the certificate by Lecuyer et al. whenever 0g - 0, 2
(B (1 - 0g 0z), which, e.g., always holds in the binary classification case. Furthermore, since
Theorem 2 provides optimal certificates for D, we have the following result.
Corollary 7. The optimal certificates for the constraint set D (cf. Eq. 20 obtained from Theorem are stronger than those obtained from Eq. 21
A.8 EFFICIENT SAMPLING AND E-DIVERGENCE COMPUTATION FOR NORM-BASED SMOOTHING MEASURES
Lemma 8. The smoothing measure μ x P(X) with density [<x)[=] x exp(-11> xl)) satisfies max Rox (M(z + 0)]lm())) s [
||>||| any norm. Further, convex function with f(1) such that ((2) convex and
monotonically increasing in then
max (y((( +[(((+)))((<))) ())l(()) X
B max E [[(exp(-1]))))) - 8l1 (XI)
(22)
[
Proof. By the triangle inequality, we have
M [ exp(11> - x|1 1|| x'1)) s exp(11= - z'1l)
so that
R (a(a'))) < ||æ - x'll
Similarly, for of that satisfy the conditions of the theorem, can be shown that D is convex in x' that its maximum over the convex set ||æ' sell S attained on the boundary. []]
22

---

Published as a conference paper at ICLR 2020
For several norms, the optimization problem in Eq. 22 be solved in closed form. These include l1, l2, loe norms and the matrix spectral norm and nuclear norm (the final two are relevant when X' is space of matrices). The results are documented in Table Thus, every f-divergence that meets the conditions of Lemma can be estimated efficiently for these norms, In particular, the divergences that are induced by the functions f(u for any monotonic convex function and a 2 0 satisfy this constraint. This gives us a very flexible class of f-divergences that can be efficiently estimated for these norm-based smoothing measures.
Constraint on 8 Bound on Eq. 22
Sampling from X ~ xn(0)
|| S
E
[f(exp[|X ccoll1 [x]]
X₃ Lap(0. 1) iid
X~p)(0)
||ó|| S e
[/(exp[]IX - ceall2 ||
X Ru
X~uu(0)
R 1)d u ~ u(832)
100 6
E (0)
[[(exp[|XX - el - 1l
X = Ru
R I(d+ 1,1)
E u(B3))
160lmuc Se
[S(exp[]|U [[bp]]]][[b]]TTT.> [[col]lluuc [[=]])))]
X U [[s]]V
s~m((0) U.V-l(())
8~ p1, M..UV U. U(O)
||011 S
E (x) ~.V)
[f(exp(||U [[s]]V] [[eol]ll. [(c))
X U [[s]VT
8~ Moo. U, U())
Table Bounds on f-divergences: eg is the vector with the first coordinate and zeros in all other coordinates and 1 is the vector with all coordinates equal to 1. Hp refers to the smoothing measure induced by the Ê norm, (S) refers the uniform measure over the set S, the set of orthogonal matrices and B3, {||=1|, I } is the unit ball in the L, norm.
Efficient sampling The only other requirement for obtaining a certificate computationally is to be able to sample from µu(z) to estimate 6a, 0g. Since μ(z) is log-concave, there general purpose polynomial time algorithms for sampling from this measure. However, for most norms, more efficient methods exist, as outlined below.
The random variable X ~ ((x) can be obtained as X = x + with ~ (()). Thus, to sample from µu(x) for any is enough to be able to sample from (()). For ||-I|1 this reduces sampling from Laplace distribution which can be done easily. For Il (Steinke & Ullman| (016) give the following efficient sampling procedure: first sample from Gamma distribution with shape + 1 and mean d + 1, i.e. r ~ I'dd + 1, 1), and then sample each Z,, i E [d], uniformly from [-r, r). Theorem
9 gives a short proof of correctness for this procedure. Theorem also has similar result for the case of ||-1|2 and Table lists the sampling procedures for several norms.
Theorem 9. The random variable Z E _dd obtained by first sampling R [(d+1, and then sampling each Zi, i [d], uniformly from [-R, R] has density -1=ll,,.
Proof. We first compute the normalization constant for a density of the form x -1=1= as follows:
/ elellll dz -= 1/00
||=
(/111l 1||==1bc =1dzz E e'd 1 dl -dl d!2d
Next we show the density of Z satisfies pz(2) e -1==1||,, (d!22d by noting that conditioned on
R we have (=) 1|||=|| S ( because of the uniform sampling used in each
23

---

Published as a conference paper at ICLR 2020
coordinate, and integrating over R sampled from a Gamma distribution with shape d 1 and mean + 1 yields
00 1 111 S erlree" / Pz (2)
1 dr
e -1
(z(2)=
(2r) d! dr d!2d 1121
d!2d
Theorem 10. The random variable Z E F obtained by first sampling Z' ~ NV(,,)) I) and R ~
T pd 1) and then taking Z -R z' 1 has density e- Here pd a) denotes the generalized Gamma distribution order p > with shape d and scale a.
Proof. First note that W z' ((2): i.. it uniform on the &g ball of radius 1. Therefore, 1z
RW is uniform on the & ball of radius R and the conditional density of Z given R is given by Since R has density pn(r) rdd e-r", get
PZJ (2) =[]=/))=-\((d/)) 27d/2,6-1
(z(2) =
R= (2)pa(r)dr
1||2=11 rd/ , 6- dr
x
2/d
X e -1=1||
A.9 ALGORITIM FOR FULL-INFORMATION CERTIFICATION
In this section we describe the subroutines used in Algorithm | First we describe a generic procedure provide high-probability confidence intervals for estimating expectations, then we give detailed description of the subroutines.
A.9.1 HIGH-CONHIDENCE ESTIMATES OF EXPECTED VALUES
Let , ZN be independent, identically distributed random variables with range R and mean m.
Let the empirical mean be ž N Σ Z, and the empirical variance be x² > E (Z, 2) Applying Bernstein's inequality to the sum and the sum of the squares of these random variables, we get the empirical Bernstein bound (Audibert al. 2009). which states that with probability least
1 1-6.
25 log (3(()
3R log(3/C)
12 mmmm S
(23)
The main benefit of the above inequality is that as long as the variance of the sample Zi, Z is small, the convergence rate becomes essentially O(1NN) instead of the standard O11//N) Also, since Eq. 23 only contains empirical quantities apart from the range R, it can be used to obtain computable bounds for the expectation j.: with probability at least 1 C.
22 log(3/() 3Rlog(3/C)
20 log (3(() 3R 3R log(C//))
7
S S 7 +
+
(24)
N
N
N
N
A.9.2 SUBROUTINES FOR ALGORITHM
The bound in Eq. 24 can be applied approximate the expectation in Eq. 6 with high probability for
given values of À and k. More specifically, if the function fr (x - x(.)) is bounded with range R. then taking N samples X,...., XN independently from p, and defining Z, = fī(K o(X.)), and
Z and x² above. Eq. 24 implies that with probability at least - C.
27 (3/C)
3R logg(33/4
E ([ - ((x)) s 2 + X~p
+
(25)
N
N
24

---

Published as a conference paper at ICLR 2020
Plugging in this bound to Eq. Ggves a high-probability lower bound for the function to be maximized for any given À and K.
Details of the above procedures given in Algorithm We use off-the-shelf convex optimization solver (Diamond & Boyd 2016) in the ESTIMETEOPT subroutine.
Algorithm 3 Subroutines for Algorithm
function ESTIMATEOPPOPP ø, N, (ft): (
Sample X X p and obtaín x² and X by solving Eq. with Ex~ - x(x))
replaced by E fx o(x:)) and the additional constraints fi (n a) < c0. f1- < 00.
return =²,,". end function
function UPPRRCONFIDENCHHOONTY o, N, 1
Sample X ,..., ~ p and compute Z + fx(x - o(x))) for i = 1, I....,N.
Set 2 + ΣN 2'
N
Set o + E 22'
N
Set I = max (K x) minge((,b) [ī(K- - =x).
Set
20 log(3/C)
lRlog(3/
Eub 2 2+1
N
N
return Exb- end function
A. 10 to SMOOTHING MEASURE
We can also handle discrete perturbations our framework. A natural case to consider is to perturbations. In this case, we assume that X' = Ad where
A [K,
discrete Then, we can choose
1(2
M (x=)
II m.
(26)
K-1
where p, 2 2 0, and denotes the probability that the measure retains the value of x and R- denotes a uniform probability of switching different value. In this case, it can be shown that for every 0 that
log (((x--1)))
(a) + R-
(
( (K-1))) (a)
(K=))g)
Ro (=(())))l)(z) |00 2'1lo
so that we can derive a certificate with respect to fy perturbations using any set of Rényi divergences (or combinations of theses).
This can be extended to structured discrete perturbations by introducing coupling terms between the perturbations:
1[z;
d-1
[2) & Marzil 9
Σ nl[2, 2:|1[2241 m.41l)
cxp
K-1)
This would correlate perturbations between adjacent features (which for example may be useful to model correlated perturbations for time series data). Since this can viewed as a Markov Chain, Rényi divergences between puxx), p(x²)) are still easy compute.
25

---

Published as a conference paper at ICLR 2020
A.11 COMPARISON WITH LECUYER ET AL. (2019) ON & PERTURBATIONS
Here we compare our certificates to Lecuyer et al. (2019) on the MNIST, CIFAR-I0 and ImageNet datasets. The smoothing distribution is described A.8 a smoothing value defined by the scale of the distribution. We first describe the hyperparameters used in training and certification for each of the datasets. For all datasets, images were normalized into [0,1] range.
Laplacian distribution with
MNIST hyperparameters: We trained a standard three layer CNN ReLU classifier 50,000 steps with batch size of 128 and learning rate of 0.001. The smoothing value during training use N IK, .N 10A, .99, and sweep range of smoothing values between 0.5 and 1.5 and report the best certificate found. Certified accuracy is reported 1,000 MNIST test set images.
was set to 1.0. For certification
CIFAR-10 hyperparameters: We trained a Wide ResNet classifier for 50,000 training steps with batch size of 32 and learning rate 0.001. The smoothing value during training was set to 0.2. For certification we use 1K, N 1M, .99, and sweep over range of smoothing values between 0. and 0.5 and report the best certificate found. Certified accuracy is reported on 1,000 CIFAR-10 10 test set images.
ImageNet hyprraarameters: We trained a ResNet-152 classifier for I million training steps with a batch size of 16 and an initial learning rate of 0.1 that is decayed by a factor ten every 25,000 steps. The smoothing value during training was set to For certification we use range of smoothing values between 0.05 and 0.25 and report the
1K, N
100K, .99, and sweep best certificate found. Certified accuracy is reported on 500 ImageNet validation set images.
Table 6: l comparison with Lecuyer et al. (0019) on MNIST.
Certificate
Certified Accuracy
2
6
3
4
=
6
7
Lecuyer et al. (2019)
0.772
0.548
0.424
0.061
0
0
0 0.017
Ours
0.860
0.716
0.584
0.447
0.325
0.201
1.0
1.0
Ours
Ours
Certified Accuracy
Lecuyer al., 2018
Certified Accuracy
Lecuyer al., 2018
0.8
0.8.
0.6
0.6
0.2
0.2
0.0
0.0
3
0.0
1.0
1.5
2.0
2.5
3.0
3.5
E
E
(a) CIFAR-10: é robustness
(b) ImageNet: robustness
Figure 3: Certified accuracy under E perturbations on CIFAR-10 and ImageNet.
Results for MNIST can be seen in Table 6 CIFAR-10 and ImageNet results are shown in Figure We significantly outperform Lecuyer et al. 2019 on all three datasets.
26


Reviews:
[{"review_id": "r1eYLSiotr", "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: This submission proposes a unified framework for black-box adversarial certification. Based on cohen's and lee's result, it extends the \\lambda_TV distance to more general f-divergence. Besides, some other techniques, e.g. reference distribution, are also included in the framework. For L_0 and L_1 perturbation, the proposed framework comes to better results than all the related methods.\n\nStrengths:\n[+] Detailed analysis and theorem.\n[+] Describing the background and conclusions clearly.\n\nWeaknesses:\n[-] In the experiment section, for ImageNet, baselines use ResNet-50 but the authors use ResNet-152. I wonder whether this is fair enough.\n[-] Renyi divergence is not a proper f-divergence. Therefore, maybe the title should be changed.\n[-] The theorem part contains too many details and some important parts (e.g. tightness) are in appendix. It should be re-organized.\n\nQuestions:\n[.] In Appendix A.7, Lagrangian strong-duality has been used to show the tightness, but I wonder whether the tightness holds for any kind f-divergence? If the authors can write down some theorem about the tightness, it will be better.\n\np.s. Could you give me some quick responses to my questions (e.g. ResNet-152 v.s. ResNet-50) ? Once you convince me, I would revise the score to 6. If not, I will turn down the score to 3. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SylnaDVqYr", "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": "The paper introduces a generalization of the randomized smoothing approach for certifying robustness of black-box classifiers, allowing the smoothing measure to be an arbitrary distribution (whereas previous work almost exclusively focused on Gaussian noise), and facilitating the certification with respect to different metrics under the same framework.\n\nGiven the wide interest in certified robustness based on randomized smoothing, the generalizations considered in this paper could have a high potential. I found the motivation, the definition of the framework and the statement of the main theoretical results, up to Section 3.2, very clear. The following sections were not as well organized, in my opinion, and need improvement. In particular, I found it not very clear how the framework can applied to recover previous results, in particular the results from Cohen et al. (2019). All the ingredients seem to be there, among Theorem 3, the result from Balle & Wang (2018), and Corollary 5, but the arguments could be presented in a better organized way.\n\nWhat I also found is missing is a clear descriptions of practical algorithms for applying the framework. Again, most of the ingredients seem to be there (e.g. Table 1 in the main body, Lemma 6 as well as the discussion about sampling mechanism in the Appendix), but they are not well organized. Presumably, the same statistical methodology as in Cohen et al. is used to obtain estimates of theta_a and theta_b, but this doesn't seem to be clearly stated anywhere. How is certification practically performed for intersections of contraint sets as introduced at the end of section 2? How the full-information certification can be applied based on empirical estimates is unclear to me, too.\n\nFinally, the description of the experiments need improvements: For instance, in Section 5.1, which smoothing measure was used? Was the ResNet classifier trained using samples from this measure? Which sets of f-divergences were used? What does Figure 3 (a) exactly show? Do the blue points correspond to the 50 data samples? The number of random samples for computing empirical estimates and the confidence bounds are missing.\nIn Figure 4 (a), as the l_0 norm counts the number of altered pixels I don't understand why the certified accuracy varies e.g. for epsilon *between* 0 and 1.\nThe experiment on the Librispeech model seems interesting, but the paper does not contain sufficient information to understand and assess the experimental set-up or the results.\n\nIn summary, while I believe that the generalizations proposed in this paper have potential, in its present form the manuscript doesn't describe clearly and accurately enough how the framework can be applied to recover previous theoretical results or perform certification in practice.\n\n----------\n\nI acknowledge I have read the authors' response. As it addresses my main concerns I have changed my rating from \"weak reject\" to \"weak accept\".\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkealMyptB", "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": "This paper extends existing work on certified robustness using smoothed classifier.  \nThe fundamental contribution is a framework that allows for arbitrary smoothing measure, in which certificates can be obtained by convex optimization.  \nA good number of technical contributions\nFramework for certificate under arbitrary smoothing measure -> Theorem 1, and proof in A.4 (good use of duality)\nFull calculation/result of certificates under different divergneces in Table 1.\nReasonable set of empirical evidence. \n\nOverall a lot of good things to be said, below are some questions/comments that could improve the paper:\n*Technical*\nPersonally, I cannot get a lot of value out of the distinction between full-information and information-limited certification.  It’d be great if I can get some clarification on this.  \n*Experiments*\nGenerally, more details of the experiments should be included.  \nHow are the convex optimization problems actually solved (e.g., what methods/tools)?  \nHow much more computational overhead is there?\nOddly, seems like we’re missing CIFAR10 results completely. \n\nSec 5.1., \nWhat does each dot in Figure 3a represent?\nSec 5.2, \nSomewhat strangely, Figure 3b is results on l0 perturbation, but not l2.  What happens for l2 when we use M>1?  How does this compare to other extensions (likely the SOTA) like [1]?\nSec 5.3,\nIt is unclear from the writing whether the comparisons to previous works were done on the same ResNet architecutre with the same clean accuracy.  Please clarify. \nI’m not sure why we need the Librispeech results.  It’s not motivated clearly.  Also, from writing it seems the adversary zeros out a segment.  It’s unclear if this is a reasonable kind of attack to expect on speech.  If I block out a segment of the speaker, we probably don’t expect any system to do well on speaker recognition.  I suggest removing this result, or somehow make it a lot more better motivated/conducted.  Clarify if I missed reasons why simply showing your method works on speech is impressive.\n\nHere are suggestions on writing:\nContribution --- in both the abstract and introduction, the experimental results should be stated clearer.  Be more specific, e.g., “Show SOTA certified l2 robustness on X,Y,Z, establish first certified robustness on Librispeech, and first results on certified l0, l1 robustness on A,B,C.”\nMore broadly in the introduction, please motivate why “adversarial attacks as measured by other smoothing measure is important”.  Past studies focus on l2-norm not just because they are do-able, but also white noise (which is naturally measured by l2-norm) is something to expect in practice.  Justify why l0, l1 would also be important.\n\nI recommend accepting this paper, but would do so with more passion if some of the comments/questions can be addressed.\n\nBest,\n\nReference:\n[1] https://arxiv.org/abs/1906.04584\n", "extra_scores": {"experience_assessment": "I do not know much about 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: This submission proposes a black-box method for certifying the robustness of smoothed classifiers in the presence of adversarial perturbations. This work goes beyond previous works in certifying robustness for arbitrary smoothing measures.

Strengths:
-Sound formulation and theoretical justification to tackle an important problem.

Weaknesses
-Experimental comparison was at times not fair.
-The presentation and writing could be improved.

These two weaknesses were sufficiently addressed during the discussion. All reviewers recommend acceptance.
Decision: Accept (Poster)