ANCER: Anisotropic Certification via Sample-wise Volume Maximization
Authors: Francisco Eiras
Motasem Alfarra
Philip Torr
M. Pawan Kumar
Puneet K. Dokania
Bernard Ghanem
Adel Bibi
Venue: Accepted by TMLR ()

Abstract: Randomized smoothing has recently emerged as an effective tool that enables certification of deep neural network classifiers at scale. All prior art on randomized smoothing has focused on isotropic $\ell_p$ certification, which has the advantage of yielding certificates that can be easily compared among isotropic methods via $\ell_p$-norm radius. However, isotropic certification limits the region that can be certified around an input to worst-case adversaries, i.e., it cannot reason about other "close", potentially large, constant prediction safe regions. To alleviate this issue, (i) we theoretically extend the isotropic randomized smoothing $\ell_1$ and $\ell_2$ certificates to their generalized anisotropic counterparts following a simplified analysis. Moreover, (ii) we propose evaluation metrics allowing for the comparison of general certificates - a certificate is superior to another if it certifies a superset region - with the quantification of each certificate through the volume of the certified region. We introduce ANCER, a framework for obtaining anisotropic certificates for a given test set sample via volume maximization. We achieve it by generalizing memory-based certification of data-dependent classifiers. Our empirical results demonstrate that ANCER achieves state-of-the-art $\ell_1$ and $\ell_2$ certified accuracy on CIFAR-10 and ImageNet in the data-dependence setting, while certifying larger regions in terms of volume, highlighting the benefits of moving away from isotropic analysis.

Published in Transactions on Machine Learning Research (08/2022)
ANCER: Anisotropic Certification via Sample-wise Volume Maximization
Francisco Eiras*
einss@robots.oz.ccm
University of Oxford, Five AT Ltd., UK
Motasem Alfarra*
King Abdullah University of Science and Technology (KAUST)
M. Pawan Kumar University of Orford
pawan@robots.or.cc.o
Philip H. S. Torr University of Orford
phillp.torr@enn.ozx www.tttoe@eenooo..c..ooo oz.ac.
Puneet K. Dokania
puneet@robots.or.cc.uk
University of Oxford, Five AT Ltd., UK
Bernard Ghanem
benaard.ghceem@@kuuss.eee...
King Abdullah University of Science and Technology (KAUST)
Adel Bibi*
adel, bebibbbii@eggg.oo or.ac.u..... uk
University of Ouford
Reviewed on OpenReview: https: // openreview. net/ forun? id= 7J0GI66PPi
Abstract
Randomized smoothing has recently emerged as an effective tool that enables certification of deep neural network classifiers at scale. All prior art randomized smoothing has focused on isotropic fp certification, which has the advantage of yielding certificates that can be easily compared among isotropic methods via n--morm radius. However, isotropic certification limits the region that can be certified around an input to worst-case adversarics, f.e. cannot reason about other "close", potentially large, constant prediction safe regions. To alleviate this issue, (i) we theoretically extend the isotropic randomized smoothing & and & certificates to their generalized anisotropic counterparts following a simplified analysis. Moreover, (ii) we propose evaluation metrics allowing for the comparison of general certificates certificate is superior to another if it certifies a supersel region with the quantification of each certificate through the volume of the certified region. We introduce ANCER, framework for obtaining anisotropic certificates for a given test set sample via volume maximization. We achieve by generalizing memory- based certification of data-dependent classifiers. Our empirical results demonstrate that A ANCER achieves state-of-the-an & and & certified accuracy on CIFAR-10 and ImageNet in the data-dependence setting, while certifying larger regions in terms of volume, highlighting the benefits of moving away from isotropic analysis. Our code is available in this repository.
1 Introduction
The well-studied fact that Deep Neural Networks (DNNs) are vulnerable to additive imperceptible noise perturbations has led to a growing interest in developing robust classifiers (Goodfellow et al., 2015; Szegedy
Equul contribution; order of first two aut hors decided by coin flips.

---

Published in Transactions on Machine Learning Research (08/2022)
Antsotropk: tsotr OpIC
Anisotropic Isotropic
Antscot Isotropic
Antsetropic
1cotropic
(a)
(b)
(c)
(d)
Figure 1: Illustration of the landscape of fo (blue corresponds to a higher confidence in y, the true label) for region around input in toy, 2-dimensional radially separable dataset. For two dataset examples, in (a) and (b) we show the boundaries of the optimal & isotropic and anisotropic certificates, while (c) and (d) are the boundaries of the optimal & isotropic and anisotropic certificates. A thorough discussion of this figure is presented in Section 3.
et al., 2014). A recent promising approach to achieve state-of-tho-art provable robustness (i.e. theorctical bound on the output around every input) at the scale of ImageNet (Deng et al., 2009) is randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019). Given an input x and a network f. randomized smoothing constructs g(x) = E. [f + such that g(x) = g(x 8) V5 R, where the cortification region R characterized by 2, f. and the smoothing distribution D. For instance, Cohen al. (2019) showed that D NN o² I), then R is ba-ball whose radius is determined by x, ʃ and a. Since then, there has been significant progress towards the design of D leading to the largest R for all inputs The interplay between R characterized by 4,, lg and Pal-balls, and notion of optimal distribution D has been previously studied (Yang et al., 2020).
Despite this progress, current randomized smoothing approaches provide certification regions that are isorropcc in nature, limiting their capacity to certifying smaller and worst-case regions. We provide an intuitive example of this behavior Figure The isotropic nature of in prior art is due to the common assumption that the smoothing distribution D identically distributed (Yang al., 2020; Kumar al., 2020; Levine & Feizi, 2021). Moreover, comparisons between various randomized smoothing approaches were limited to methods that produce the same E, certificate, with no clear metrics for comparing with other certificates. In this paper, we address both concerns and present new state-of-the-ar certified accuracy results on both CIFAR-10 and ImageNet datasets.
Our contributions are threefold. (i) We provide a general and simpler analysis compared to prior art (Cohen et al., 2019; Yang al., 2020) that paves the way for the certification of anisotropic regions characterized by any norm, holding prior art as special cases. We then specialize our result to regions that, for a positive definite A, are ellipsoids, i.e. ||Ao||2 S c, O, and generalized cross-polytopes, f.e. ||A8]] S c, generalizing both & (Cohen et al., 2019) and & (Lecuyer et al., 2019; Yang et al., 2020) certification (Section 4). (ii) We introduce a new evaluation framework to compare methods that certify general (isotropic or anisotropic) regions. We compare two general certificates by defining that a method certifying R, is superior to another certifying R2, if R2 is a strict superset to R2. Further, we define a standalone quantitative metric as the volume of the certified region, and specialize for the cases of ellipsoids and generalized cross-polytopes (Section 5). (iii) We propose ANCER, an anisotropic certification method that performs sample-wise (i.e. per sample in the test set) region volume maximization (Section 6), generalizing the data-dependent, memory-based solution from Alfarra et al. (2022). Through experiments on CIFAR-10 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009), we show that restricting ANCEr's certification region to l and balaals outperforms statc-of-the-art & and & results from previous works (Yang el al., 2020; Alfarra el al., 2022). Further, we show that the volume of the certified regions are significantly larger than all existing methods, thus setting a new state-of- saate-of-the-ar the-art in certified accuracy. We highlight that while we effectively achieve state-of-the-art performance, comes at high cost given the data-dependency requirements. A discussion of the limitations of the solution is presented in Section 6.
2

---

Published in Transactions on Machine Learning Research (08/2022)
Notation. We consider a base classifier f R² - P(K), where P(K) is probability simplex over K classes, i.e. / 2 0 and 1 f- 1, for i E (1...., KJ. Further, we use (I, to be sample input a and its corresponding true label drawn from a test set D,, and f to be the output of f at the correct class. We use bp to be the typically defined || lp norm (p 2 1), and eo or || -l..p for p= (1,2) to be a composite norm defined with respect to positive definite matrix A ||A -1/Pollp.
2 Related Work
Verified Defenses. Since the discovery that DNNs are vulnerable against input perturbations (Goodfellow et al, 2015; Szegedy et al., 2014), range of methods have been proposed to build classifiers that are verifiably robust (Huang et al., 2017; Gowal et al., 2019; Bunel et al., 2018; Salman et al., 2019b). Despite this progress, these methods do not yet scale to the networks the community is interested in certifying (Tijng et al., 2019; Weng ct al., 2018).
Randomized Smoothing. The first works randomized smoothing used Laplacian (Lecuyer et al., 2019; Li et al., 2019) and Gaussian Cohen et al. (2019) distributions to obtain & and Ez-ball certificates, respectively. Several subsequent works improved the performance of smooth classifiers by training the base classificr using adversarial augmentation (Salman ct al., 2019a), regularization (Zhai et al., 2019), or general adjustments to training routines (Jeong & Shin, 2020). Recent work derived fy-norm certificates for other isotropic smoothing distributions (Yang al., 2020; Levine & Feizi, 2020; Zhang et al., 2019). Concurrently, Dvijotham et al. (2020) developed framework to handle arbitrary smoothing measures in any fy-norm; however, the certification process requires significant hyperparameter tuning. Similarly, Mohapatra et al. (2020) introduces larger certificates that require higher-order information, yet do not provide a closed-form solution. This was followed by a complementary data-dependent smoothing approach, where the parameters of the smoothing distribution were optimized per test set sample to maximize the certified radius at an individual input (Alfarra et al., 2022). All prior works considered smoothing with isotropic distributions and hence cortified isotropic bp-ball regions. In this paper, we extend randomized smoothing to certify anisotropic regions, by pairing it with a generalization of the data-dependent framework (Alfarra al., 2022) to maximize the certified region at each input point.
3 Motivating Anisotropic Certificates
Certification approaches aim to find the safe region R, where arg max, f'(x) arg max, ('r + +8) Vo E R. Recent randomized smoothing techniques perform this certification by explicitly optimizing the isotropic Ep certified region around each input (Alfarra et al., 2022), obtaining state-of-the-art performance as a result. Despite this lp optimality, we note that any fp-norm certificate is worst-case from the perspective of that norm, as it avoids adversary regions by limiting its certificale to the fy-closest adversary. This means that it can only enjoy a radius that at most equal to the distance to the closest decision boundary. However, decision boundarics of general classifiers are complex, non-linear, and non-radially distributed with respect to generic input sample (Karimi et al., 2019). This is evidenced by the fact that, within reasonably small fp-ball around an input, there are often only small set of adversary directions (Tramèr et al., 2017; 2018) (e.g. see the decision boundaries in Figure 1). As such, while f--norm certificates are useful to reason about worst-case performance and are simple to obtain given previous works (Cohen et al., 2019; Yang et al., 2020; Lee et al., 2019), they are otherwise uninformative in terms of the shape of decision boundaries, i.e. which regions around the input are safe.
To visualize these concepts, we illustrate the decision boundaries of a base classifier f trained on toy 2-dimensional, radially separable (with respect to the origin) binary classification dataset, and consider two different input test samples (sce Figure 1). We compare the optimal isotropic and anisotropic certified regions of different shapes at these points. In Figures la and 1b, we compare an isotropic cross-polylope (of the form [|6]] < r) with an anisotropic generalized cross-pos pooss-poyy (of the form ||Aб]] < r), while in Figures Ic and 1d we compare an isotropic & ball (of the form [|ö]]2 I r) with an anisotropic cllipsoid (of the form || S r). Notice that in Figures la and 1c, due to the curvature of the classification boundary (shown in white), the optimal certification region is isotropic in nature, which is evidenced by the sinilarities of the
3

---

Published in Transactions on Machine Learning Research (08/2022)
Figure 2: Visualization of a CIFAR-10 image and an example x + 5 of an imperceptible change that is not inside the optimal isotropic certified region, but is covered by the anisotropic certificate.
optimal isotropic and anisotropic certificates. On the other hand, in Figures 1b and 1d, the location of the decision boundary allows for the anisotropic certified regions to be considcrably larger than their isotropic counterparts, they are not as constrained by the closest decision boundary, i.e. the worsl-oase performance. We note that these differences are further highlighted in higher dimensions, and we study them for a single CIFAR-10 test set sample in Appendix A.1.
As shown, anisotropic certification reasons more closely about the shape of the decision boundaries, allowing for further insights into constant prediction (safe) directions. In Figure 2, we present a series of test set images F, as well as practically indistinguishable + 5 images which are not inside the optimal certified isotropic fz-balls for each imput sample, yet within the anisotropic certified regions. This showcases the merits of using anisotropic certification for characterizing larger safe regions.
4 Anisotropic Certification
One of the main obstacles in enabling anisotropic certification is the complexity of the analysis required. To alleviate this, we follow a Lipschitz argument first observed by Salman et al. (2019a) and Jordan & Dimakis (2020) and propose a simple and general certification analysis. We start with the following two observations. All proofs are Appendix B.
Proposition 1. Consider a differentiable function g - R. If sup [V[x)l I L where || 1|+ has dual norm ||=||| max, Txx s.t. ||~||| S 1, then g is L-Lipschitz under norm || ll,,, that is (g(x)) 9(v)e L|| vll-
+
Given the previous proposition, we formalize || certification as follows:
Theorem 1. Let g R= + RK g be L-Lipschitz continuous under norm -1- Vi E {I....,Kk KJ. and arg (z). Then, we have arg mag, g' (x + 5) CA for all 5 satisfying:
1 || S 2L (g max te (x))
Theorem provides an ||. || norm robustness certificate for any L-Lipschitz classifier g under || Il.. The certificate is only informative when one can attain tight non-trivial estimate of L, idcally sup, [g(x)) which is generally difficult when g is an arbitrary neural network.
Framework Recipe. In light of Theorem 1, randomized smoothing can be viewed differently an instance of Theorem 1 with the favorable property that the constructed smooth classifier g enjoys an analytical form for I= li==uup,l[Vppp (>>) by design. As such, to obtain an informative || certificate, one must, for an arbitrary choice of a smoothing distribution, compute the analytic Lipschitz constant under || ll. for g. While there can exist a notion of "optimal" smoothing distribution for a given choice of || I| certificate, as in part addressed earlier for the isotropic &,, lg and for certificates (Yang et al., 2020), this is not the focus of this paper. The choice of the smoothing distribution in later sections is inspired by previous work for the purpose of granting anisotropic certificates. This recipe complements randomized smoothing works based on Seyman-Pearson 's lemma (Cohen et al., 2019) or the Level-Set and Differential Method (Yang et al., 2020).
We will deploy this framework recipe to show two specializations for anisotropic certification, namely ellipsoids (Section 4.1) and generalized cross- cooss-polytops (Section 4.
'Our analysis also grants a certificate for mixture of Gaussians smoothing distribution (see Appendix B.1).
4

---

Published in Transactions on Machine Learning Research (08/2022)
4.1 Certifying Ellipsoids
In this section, we consider the certification under E norm, or ||]|| VOTE- that has a dual norm ||ölx 4,2. Note that both | S r and ||ō]| 1,2 S r define an ellipsoid. Despite that the following results hold for any positive definite Σ, we assume for efficiency reasons that E is diagonal throughout. First, we consider the anisotropic Gaussian smoothing distribution E) with the smooth classifier defined as gx(x) = (0) (f + <)]. Considering the classifier o (gx(()), where t the standard Gaussian CDF, and following Theorem to grant an Eg certificate for t -- (gx(x)), we derive the Lipschitz constant L under || ||x-1 in the following proposition.
Proposition 2. (gx((x) is 1 1-Lipschitz (i.e. L= under the || 1|x-1,2 norm.
Since --1 is a strictly increasing function, by combining Proposition with Theorem 1, we have: Corollary 1. Let CΛ = arg max, 9x()), then arg max; 9 8) ca for all 8 satisfying:
| - 2 4 (x)) -- mmax 93
ofea (z))
Corollary 1 holds the E certification from Zhai et al. (2019) as special case for when E = 0²I.2
4.2 Certifying Generalized Cross-Polytopes
Here we consider certification under the ef norm defining generalized cross- polytope, t.e. the set {ō: ||ō'|A,1 |||| S r), as opposed to the éz-bounded set that defines cross-pol poss-polytope, i.e. (ō: ||ô]| S r). As with the ellipsoid case and despite that the following results hold for any positive definite A, for the sake of efficiency, we assume A to be diagonal throughout. For generalized cross-polytope certification, we consider an anisotropic Uniform smoothing distribution Ut which deffnees the smooth classifier (a(z) = E.- [f + Ae)]. Following Theorem 1 and to certify under the e norm, we compute the Lipschitz constant of ga under the || norm, which is the dual norm of || |IA,1 (see Appendix B), in the next proposition. Proposition 3. The classifier gN is 1/2- Lápschitt (f.e. L = 1/2) under the || norm.
Similar to Corollary 1, by combining Proposition 3 with Theorem 1, we have that: Corollary 2. Let CA = arg max, 9 (x). then arg max, 9 (I + 6) ca for all 8 satisfying:
|| ||A- S (f) (z) max 9A (x)))())))
Corollary 2 holds the é certification from Yang et al. (2020) as a special case for when A = Al.
5 Evaluating Anisotropic Certificates
With the anisotropic certification framework presented in the previous section, the question arises: "Given two general (isotropic or anisotropie) certification regions Ri and R2, how can one effectively compare them?" We propose the following definition to address this issue.
Definition 1. For a given imput point x, consider the two certification regions R1 and R2 obtained for two classifiers fr and f2, i.e. A1 = {ō : arg max, f((xx) = arg max, ff + 6), Y8 E R1} and A = {8 : arg max, (x) = arg max, f5 + 6),48 V8 E R2} where arg max, ff(x) arg max, fz()). We say Ai is a 'superior cerlificale" to A2 (Lee Ai > A2), if and only if. Ai 3 A2.
This definition is a natural extension from the radius-based comparison of b,-ball certificates, providing a basis for evaluating anisotropic certification. To compare an anisotropic to an isotropic region of certification, it is not immediately clear how to (i) check that an anisotropic region superset to the isotropic region, and (ii) if it were a superset, how to quantify the improvement of the anisotropic region over the isotropic counterpart. In Sections 5.1 and 5.2, we tackle these issues for the particular cases of ellipsoid and generalized cross-polytope certificates.
2A similar result was derived the appendix of Fischer et al. (2020); Lá al. (2020) with more involved analysis by extending Neyman-Pearson's Pearson's lemma.
5

---

Published in Transactions on Machine Learning Research (08/2022)
5.1 Evaluating Ellipsoid Certificates
Comparing 2 to E -Elllipsoids (Specialization of Definition 1). Recall that if f o2 our ellipsoid certification in Corollary 1 recovers special case the isotropic l--ball certification of Cohen et al (2019); Salman et al. (2019a); Zhai et al. (2019). Consider the certified regions R1 = {ō ||ó1|2 S ori and R2 (6 ||]||,,2 - S r2) for given rı, 12 O. Since take Σ diag( (o?)_.) the maximum enclosed bz-ball for the ellipsoid R2 is given by the set R3 {ō ||öl|2 S min, o.re), and thus R₂ 2 R3. Therefore, it suffices that R3 2 R1 (i.e. min, 0,72 2 or1), to say that R₂ is a superior certificate to the isotropic R1 as per Definition 1.
Quantifying Ey Certificates. The aforementioned specialization is only concerned with whether our ellipsoid certified region R₂ is "superior" to the isotropic &z-ball without quantifying it. A natural solution is to directly compare the volumes of the certified regions. Since the volume of an ellipsoid given by R2 is ((R2) = /(v=*/r(</+++) I o; (Kendall, 2004), we directly compare the prory radius R defined for R₂ as R 72 VII. os since larger R correspond to certified regions with larger volumes. Note that R, which is the Th root of the volume up to constant factor, can be seen generalization to the certified radius in the case when = o Vi.
5.2 Evaluating Generalized Cross-Polytope Certificates
Comparing B-Bll to G - Geneeeelalee Pross-Polytoppe
(Specialization of Definition 1). Con-
sider the certificates S = {6 | < Xr1}, S2 = {6 | ||A S r2), and 83 = {6 : || S
min; \,22,, where we take A = (lag(((A) Note that since S 2 Sz. then as per Definition 1, it suffices that S3 2 Si (i.e. min; Arr 2 Ar1) to say that the anisotropic generalized cross pross-polytope S₂ is superior to the isotropic lballll St.
Quantifying 4 Certificates. Following the approach proposed in the & case, quantitatively compare the generalized cross-polytope certification of Corollary 2 to the & certificate through the volumes of the two regions. We first present the volume the generalized cross-polytope.
Proposition 4. V ((5: ||A- S sr]) m! ΠI. Ar.
Following this definition, we define the prozy radius for S2 in this case to be R= VIT ', As with the & case, larger Rt correspond certified regions with larger volumes. As in the ellipsoid case, I can be seen as a generalization to the certified radius when A; = À Vi.
6 AnCer: Sample-wise Volume Maximization for Anisotropic Certification
Given the results from the previous sections, ellipsoids and generalized cross-polytopes. As mentioned in Section 4, these regions generally defined R = =00 [oolle, I rP} for given parameter of the smoothing distribution θ = diag ((0:)21). an fp-norm (p E {1,2)), and a gap value of re E RR. At this point, one could simply take an anisotropic distribution with arbitrarily chosen parameters θ and certify a trained network at any input point x, in the style of what was done in the previous randomized smoothing literature with isotropic distributions. However, the choice of is more complex the anisotropic casc. fixed choice of anisotropic could severely underperform the isotropic case take, for example, the anisotropic distribution of Figure 1d applied to the input of Figure Ic.
now equipped to certify anisotropic regions, in particular
Instead of taking fixed θ, we generalize the framework introduced by Alfarra al. (2022), where parameters of the smoothing distribution are optimized per input test point (í.e. in a sample-wise fashion) so as to maximize the resulting certificate. The goal of the optimization in (Alfarra el al., 2022) is, at a point x, to maximize the isotropic l region described in Section 4.1 (i.e. {6 ||0]|2 S ""r"(z, the gap and a function of x and Th E R+ In the isotropic l, case, this generalizes to maximizing the region {6 : ||ö'| I ,", (x, 8")). which can be achieved by maximizing radius "" (z, 8d) through 6² e R obtaining ri (Alfarra al., 2022).
where re is
6

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm 1: ANCER Optimization
Function ANCER (fa. Initialize: 0 < O for h = 0... K - do
oo n, K, k):
sample 61,... En ~
(( = 1 Ei=1 fo(x + 2+)
EA(O)) = max. ";; YA = arg max, 3º; Eb(O)) = maxeşya v0
EA- - EB
p p=
(2, 0+)
( ( ($-1(Ex)) (En))
if p =
R(O = (z, 0% (II,' 61) 1/4
txr θ min, O
@+ t O + ovvrR(())
@++1 max (0*+1 .00) // alement-wise marimum projection step
return Og
For the general anisotropic casc, we propose ANCER, whose objective is to maximize the volume of the certified region through the procy radius, while satisfying the supersel condition with respect to the maximum isotropic & radius, rio In the case of the ellipsoids and generalized cross-polytopes as presented in Sections 5.1 and 5.2, respectively, ANCER's optimization problem can be written as:
arg max r (1. O²) 0z
II
TO
S.L. min 0fr (x. 0²) 2 ris
(1)
where rP (x. 0.) is the gap value under the anisotropic smoothing distribution. That is,
r (c, A²) ox max S8 Ctte (x),
r (r.
1 + (oS Φ- (maxx g8و ofea
(aaa))))~~xmx(aapaaaaa ((r)
for & and l,, respectively. This is nonlinear constrained optimization problem that is challenging to solve. As such, we relax it, and solve instead:
arg max 7 (x, @r
II
0 + +Kmin 0,r (x, s.t. 0 2
given a hyperparameter E R+. While the constraint Of 2 0 is not explicitly required to enforce the superset condition over the isotropic case, proved itself beneficial from an empirical perspective. To sample from the distribution parameterized by O² (in our case, either a Gaussian or Uniform), we make use of the reporameterization trick, in Alfarra et al. (2022). The solution of this optimization problem can be found iteratively by performing projected gradient ascent, detailed in Algorithm 1. A standalone implementatiin itio for the ANCER optimization stage is presented in Listing in Appendix C.
Memory-based Anisotropic Certification. While each of the classifiers induced by the parameter O", i.c. I0r; is robust by definition as presented in Section 4, the certification of the overall data-dependent classifier is not necessarily sound due the optimization procedure for each æ. This known issuc in certifying data-dependent classifiers, and is addressed by Alfarra al. (2022) through the use of memory-based procedure. In Appendix D, present adapted version of this algorithm to ANCER. All subsequent results are obtained following this procedure.
Limitations of AnCer. Given ANCER uses a memorization procedure similar to the one presented in Alfarra et al. (2022), it incurs limitations on memory and runtime complexity. Note that in memory-based data-dependent certification there is a single procodure for both certification and inference in contrast with the fixed setting from Cohen et al. (2019). The main limitations of the memory- certification are outlined in Appendix E. of Alfarra et al. (2022). The anisotropic increases the complexity of the
7

---

Published in Transactions on Machine Learning Research (08/2022)
isotropic framework by the increased runtime of specific functions presented in Appendix D. Certification runtime comparisons are in Section 7.4.
The memory-based procedure incurs the same memory cost as the one presented in Alfarra et al. (2022), i.e, it has a memory complexity of O(N) where N is the total number of inferred samples. This is since that the memory based method requires saving the observed instances along with their smoothing parameters. While the linear runtime dependency on memory size might appear daunting for the deployment of such a system, there are few factors that could mitigate the cost. Firstly, in practice the models deployed get regularly updated in deployment, and the memory should be reset in those situations. Secondly, there are possible solutions which might attain sublinear runtime for the post-certification stago, such as the application of k-d trees to reduce the space of comparisons and speed-up the process. As such, we believe ANCER to be suited to applications in offiine scenarios, where improved robustness is desired and inference time is not a critical issue.
A further limitation of the memorization procedure has to do with the impact of the order in which inputs are certified on the overall statisties obtained. Within a memory-based framework, certifying 22 with xı in memory can be different from certifying ø with 22 in memory if they intersect. In practice, given the low number of intersections observed with the original certified regions, this effect was almost negligible in the results presented in Section 7. For fairness of comparison with non-memory based methods, we report 'worst-case' results for ANCER in which we abstain from deciding whenever an intersection of two certified regions occurs.
7 Experiments
We now study the empirical performance of ANCER to obtain trained using randomized smoothing methods found in the literature. In this section, we show that AnCer is able to achieve (i) improved performance on those networks in terms of &2 and & certification when compared to certification basclines that smooth using a fixed isotropic a (Fixed σ) (Cohen et al., 2019; Yang et al., 2020; Salman et al., 2019a; Zhai et al., 2019) or a data-dependent and memory-based isotropic one (Isotropic DD) (Alfarra et al., 2022); and (ii) a significant improvement in terms of the &g and en-norm certified region obtained by the same methods compared by computing the prozy radius of the certified regions thus generally satisfying the conditions of a superior certificate proposed in Definition 1. Note that both data-dependent approaches (Isotropic DD and AnCer) use memory-based procedures. As such, the gains described in this section constitute tradc-off given the limitations of the method described in Section 6.
f. G. by and & certificates on networks
We follow an evaluation procedure as similar as possible to the ones described in Cohen et al. (2019); Yang et al. (2020); Salman et al. (2019a); Zhai et al. (2019) by using code and pre-trained networks whenever available and by performing experiments on CIFAR-10 (Krizhevsky, 2009) and ImageNet (Deng ct al., 2009), certifying the entire CIFAR-10 lest set and a subset of 500 examples from the Image test set. For the implementation of ANCER, we solve Equation equation with Adam for 100 iterations, where the certification gap pd (z. O*) is estimated at cach iteration using 100 noise samples per test point (sce Appendix C) and O" in Equation equation 1 is initialized with the Isotropic DD solution from Alfarra et al. (2022). Further details of the setup can be found in Appendix F.
As in previous works, l, certified accuracy at radius R is defined as the portion of the test set D, for which the smooth classifier correctly classifies with an lp certification radius of at least R. In a similar fashion, we define the anisotropic EZ/ /&/ certified accuracy at a proxy radius of R (as defined in Section 5) to be the portion of Dr in which the smooth classifier classifies correctly with an L / - certificate of an th root volume of at least R. We also report average certified radius (ACR) defined as Ey.g-D, [R, (g(z)) 2022; Zhai et al, 2019) as well average certified proxy radius (ACR) defined as ED,YD, (R, 1 (g(=x) y)], where R₂ and R2 denote the radius and proxy radius at z with a true label y for a smooth classifier g. Rocall that in the isotropic case, the proxy radius is, by definition, the same as the radius for a given fn-norm. For each classifier, we ran experiments on the a values reported in the original work (with the exception of Yang et al. (2020), see Section 7.2). For the sake of brevity, we report in this section the top-1 certified accuracy plots, ACR and ACR per radius across o, as in Salman et al. (2019a); Zhai et al. (2019); Alfarra al. (2022). The performance of each method per a is presented in Appendix G.
y)] (Alfarra et al.,
8

---

Published in Transactions on Machine Learning Research (08/2022)
CIFAR-10- - Cohon
CIFAR-10- - Smoothhld
CIFAR-10- - MAGER
ImageNet-Colf Cohen
ImageNet- SmoothAdy
0.8
Foed
0.8
Flaed
Thaa
Flaed
0.6
Fixed
lestropic
Oufffed coongyy
lnstoppic LX
burnngic DX
lecraze D2
Centedscaaeyy secaaayyy
6.6
ANGER
ANDER
Cented
ANDER
ANGER
ANGER
Bx
9.4
0.4
64
0.2
02
4 rudua
2 rod Lo
1 nad
1) rad
5 racius
Oyntfed scarge
0.6
0.8
ANGAR
Isatropko
Cyntf of
coungey
0.8
0.6
ANCER
Centied ecareey
0.8
0.8
komple: DO ANGER
0.5
ANCER
Contl co
lsstrosio ANGER
S4
0.4
04
2
X
0.
13 preay
A) procy
f proxy rackus
tadius
Figure& 3: Distribution of top-1 certified accuracy as function of & radius (top) and Eg -nrm proxy radius (bottom) obtained by different certification methods on CIFAR-10 and ImageNet.
7.1 Ellipsoid certification (&z and & norm certificates)
We perform the comparison of ball vs. efeelipsoid certificates via Gaussian smoothing using networks trainod following the procodures defined in Cohen ot al. (2019), Salman et al. (2019a), and Zhai et al. (2019). For each of these, we report results on ResNet18 trained using o E {0.12, 0.25, 0.5, 1.0} for CIFAR-10, and ResNet50 using a E {0.25, 0.5, 1.0} for ImageNet. For details of the training procedures, see Appendix F. Figure 3 plots top-1 certified accuracy as function of the l2 radius (top) and of the fz-norm proxy radius (bottom) per trained network and datasct, while Table 1 presents an overview of the certified accuracy at various l radii, as well as lz ACR and fg-norm ACR. Recall that, following the considerat ions in Section 5.1, the le certificate obtained through ANCER is the maximum enclosed isotropic balball in the Ey ellipsoid.
First, we note that sample-wise certification (Isotropic DD and AnCer) achieves higher certified accuracy than fixed a across the board. This mirrors the findings in Alfarra et al. (2022), since certifying with a fixed for all samples struggles with the robustness/ /abustness//cccuaccy accuracy trade-off first mentioned in Cohen et al. (2019), whereas the data-dependent solutions explicitly optimize a per sample to avoid it. More importantly, ANCeR achieves new state-of-the-art E2 certified accuracy al most. radii in Table 1, e.g. at radius 0.5 ANCER brings certified accuracy to 77% (from 66%) and 70% (from 62%) on CIFAR- 10 and ImageNet, respectively, yielding relative percentage improvements in ACR between 13% and 47% when compared to Isotropic DD. While the results are significant, it might not be immediately clear why maximizing the volume of an ellipsoid with ANCER results in a larger maximum enclosed bz-ball certificate in &h ellipsoid when compared to optimizing the ball with Isotropic DD. We explore this phenomenon in Appendix 7.3.
CIFAR-10-
ImageNel- RS4A
ANCER
betmppic DD
0.6
00.4
0.4
Floed
Isomopic
ANGER
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.00
0.25
0.50
0.75
1.00
1.
metiu
mediu
Corifed excurece
0.6
0.8
bczopli DD /NCER
Cerfeed excurecy
0.6
ANGER
bozropic DD
0.4
0.4
3.2
0.2
0.0
0.8
prayy radiaa
(/ (upney volume
Figure 4: Distribution of top-1 certified ac- curacy as a function of & radius (top) and 4/ -norm proxy radius (bottom) obtained by different certification methods CIFAR-10 and ImageNet.
As expected, ANCER substantially improves Ey ACÂ com- pared to rspic DD in all cases with relative improvements in ACR between 38% and 63% over both datasets. The joint results, certification with lg and Ez, establish that ANCeR certifies the balb region obtained by previous approaches, in addition to a much larger region captured by the lj certified accuracy and ACR, and therefore is, according to Definition 1, generally superior to the Tsotropic DD one.
9

---

Published in Transactions on Machine Learning Research (08/2022)
Comparison of top-1 certified accuracy at different l radii, lg average certified radius (AC') and ty average certified proxy radius (ACR) obtained by using the isotropic used for training the networks (Fixed o); the isotropic data-dependent (Isotropic DD) optimization scheme from Alfarra et al. (2022); and ANCER'S data-dependent anisotropic optimization.
Table 1:
Accuracy @ &2 radius (%)
CIFAR-10
Certification
82 ACR
& ACR
0.0
0.25
0.5
1.0
1.5
2.0
2.5
Fixed a
86
71
51
27
14
6
2
0.722
0.722
COHEN Cohen et al. (2019)
Isotropic DD
76
62
39
8
1.117
1.117
ANCER
86
85
77
53
31
17
10
1.449
1.772
Fixed
82
72
55
32
19
9
5
0.834
0.834
SMOOTHADV Salman et al. (2019a)
Isotropic DD
82
75
63
40
25
15
7
1.011
1.011
ANCER
83
81
73
48
30
17
8
1.224
1.573
Fixed a
87
76
59
37
24
14
9
0.970
0.970
MACER Zhai et al. (2019)
Isotropic DD
88
80
66
40
17
9
6
1.007
1.007
ANCER
80
34
11
9
1.136
1.481
Accuracy &
radius (%)
ImageNet
Certification
62 ACR
C ACR
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Fixed a
70
56
41
31
19
14
12
1.098
1.098
COHRN Colin et al. (2019)
Isotropic DD
71
59
46
36
19
15
1.234
1.234
ANCER
70
70
62
61
42
36
29
1.810
1.981
Fixed
65
59
44
38
26
20
18
1.287
1.287
SMOOTHADV Salman et al. (2019a)
Isotropic DD
66
62
53
41
32
24
20
1.428
1.428
ANCER
66
66
62
58
44
37
32
1.807
1.965
7.2 Generalized Pross-Polytope certification (4 and -norm certificates)
To investigate 4-lll vs. ef-gencralized pross-po certification via Uniform smoothing, we compare AnCeR to the & state-of-the-art results from RS4A (Yang et al., 2020). While the authors of the original work report best certified accuracy based on 15 networks trained at different a levels between 0.15 and 3.5 on CIFAR-10 (WideResNet40)) and ImageNet (ResNet50) and due to limited computational resources, we perform the analysis on subset of those networks with a f0.25, 0.5, 1.0]. We reproduce the results in Yang et al. (2020) as closely as possible, with details of the training procedure presented in Appendix F.2. Figure 4 shows the top-1 certified accuracy radius (bottom) for RS4A, and Table 2 shows an overview of the certified accuracy at various é radii, well as l ACR and t ACR. As with the ellipsoid case, we notice that ANCER outperforms both Fixed a and Istropic DD for most & radií, establishing new state-of-the-art results in CIFAR-10 at radií 0.5 and 1.0, and Net at radii 0.5 (compared to previous results reported in Yang et al. (2020)). Once more and as expected, AN CER significantly improves the ff ACR for all radii, pointing to substantially larger cerficates than the isotropic case. These results also establish that ANCeR certifies the fa-ball region obtained by previous work, in addition to the larger region obtained by the ep certificate, and thus we consider it superior (with respect to Definition 1) to Isotropic DD.
function of the & radius (top) and of the 4f-norm proxy
7.3 Why does AnCer improve upon Isotropic DD's e, certificates?
As observed in Sections 7.1 and 7.2, ANCER'S la and l certificates outperform the corresponding certificates obtained by Isotropic DD. To explain this, compare the l2 certified region obtained by AnCEr, defined in Section 6 as {8: ||01|2 I min; of rz, }d),, to the one by Isotropic DD defined as {ō: : ||ō]|2 S o²r(z,0")) We observe that the radius of both of these certificates can be separaled into a o-factor (o vs. of mine of) and a gap-factor (r(z, o²) vs. r(z, E") We posit the seemingly surprising result can be attributed to the computation of the faptfr r using an anisotropic, optimized distribution. However, another potential explanation would be that ANCER benefits from a prematurely stopped initialization provided by Isotropic DD, thus achieving better of than the isotropic ot when given further optimization iterations.
10

---

Published in Transactions on Machine Learning Research (08/2022)
Table 2:
Comparison of top-1 certified accuracy at different & radii, & average certified radius (AC') and 4 average certified proxy radius (ACR) obtained by using the isotropic used for training the networks (Fixed d); the isotropic data-dependent (Isotropic DD) optimization scheme from Alfarra et al. (2022); and ANCER'S data-dependent anisotropic optimization.
Accuracy @ & radius (%)
CIFAR-10
Certification
ACR
et ACR
0.0
0.25
0.5
0.75
1.0
1.5
2.0
Fixed a Isotropic
92
83
75
71
46
0
0
0.775
0.775
RS4A Yang et al. (2020)
89
76
58
6
0.946
0.946
ANCER
92
90
84
80
63
6
0.980
1.104
ImageNet
Fixed
78
73
67
63
0
0
0.683
0.683
RS4A Yang et al. (2020)
Isotropic DD
79
76
70
65
46
0
0.729
0.729
ANCER
78
76
70
66
48
0
0.730
1.513
To investigate this, we take the optimized parameters from the Isotropic DD experiments on SMOOTHADV for an initial a = 0.25 on CIFAR-10, and run the optimization step of Isotropic DD for 100 iterations more than its default number of iterations from Alfarra et al. (2022), so as match the total number of optimization steps between Isotropic DD and ANCER. The histograms of of or miin and the gap-factor т, i.e. the two factors from the fz certification results, are presented in Figure 5. While ot for Isotropic DD is similar in distribution to ANCER's miin the distribution are quite different. In particular, the ANCER certification gap is siguificantly larger when compared to Isotropic DD, and is the main contributor the improvement in the balb certificate of ANCER. That is say, ANCER generates Σ" that is better aligned with the decision boundaries, and hence increases the confidence of the smooth classifier.
100+ Isotroicc DD
ANCER
0.6
E. 0.4
2
0.2
0.0
0" or onnn
the two gaps, r(zz o²) and r(z, E"),
Figure 5: Histograms of the values of the gap (left) and the o-factor (right) obtained by AnCER initialized with Isotropic DD, and Isotropic DD when allowed to run for 100 iterations more than the baseline. Vertical lines plot the median of the data.
7.4 Certification Runtime
The certification procodures of Isotropic DD and ANCER trado- off improved certified accuracy for runtime, since they require sample-wise optimization to be run prior to the CERTIFY step described in Cohen et al. (2019), and memory-base based step as per Alfarra et al. (2022). The runtime of the optimization and certification procedures is roughly equal for &,, l2, E and EA certification, and mostly depends on network architecture. As such, we report the average certification runtime for a test set sample on an NVIDIA Quadro RTX 6000 GPU for Fixed o, Isotropic DD and ANCER (including the isotropic initialization step) in Table 3. We observe that the run time overhead for ANCeR is not significant as compared to its certification gains.
Table Average certification time for each sample per architecture used: (a) ResNet18 (f2, & CIFAR-10), (b) WideResNet40 (C1, A CIFAR-10), and (c) ResNet50 (ImageNet).
Fixed
Isotropic DD
ANCER
(a)
1.6s
1.8s
2.7s
(b)
7.4s
9.5s
11.5s
(c)
109.58
136.0s
147.0s
Finally, due to the memory based step in our approach, the inference and certification runtime are the same.
8 Conclusion
We lay the thcoretical foundations for anisotropic certification through a simple analysis, propose a metric for comparing general robustness certificates, and introduce ANCER, certification procedure that estimates
11

---

Published in Transactions on Machine Learning Research (08/2022)
the parameters of the anisotropic smoothing distribution to maximize the certificate. Our experiments show that ANCER achieves state-oftthe-art l and & certified accuracy in the data-dependent setting.
Acknowledgments
This publication is basod upon work supported by the EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems [EP/S024050/1] and Five AI Limited; by King Abdullah University of Science and Technology (KAUST) under Award No. ORA-CRG10-2021-66 Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST Al); and by the Royal Academy of Engineering under the Research Chair and Senior Research Fellowships scheme, EPSRC/MURI grant EP /N01944///1
well as, the SDATA-KAUST
References
Motasem Alfarra, Adel Bibi, Philip H. Torr, and Bernard Ghanem. Data dependent randomizod smoothing. In Proceedings of the Thirly- Eighth Conference on Uncerlainly in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pp. 64-74. PMLR, 01-05 Aug 2022. 2, 3, 6, 7, 8, 9, 10, 11, 15, 19, 20, 21, 24, 25
Rudy Buncl, Ilker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. A unified view of piecewise linear neural network verification. In Advances in Newral Information. Processing Systems (NeurIPS), 2018. 3
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2019. 2, 3, 4, 6, 7, 8, 9, 10, 11, 19, 25, 26
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In JEEE Conference Computer Vision and Pattern Recognation (CVPR), 2009. 2, 24
Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, András György, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference on Learning Representations (ICLR), 2020. 3
Mare Fischer, Maximilian Baader, and Martin Vechov. Certified defense to image transformations via randomized smoothing. In Advances in Neural Information Processing Systems (NewrIPS), 2020. 5
Igor Gilitschenski and Uwe D Hanebeck. robust computational test for overlap of two arbitrary-diimensional ellipsoids in fault-detection kalman filters. In 2012 15th International Conference on Information Pusion, 2012. 21, 22
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In
International Conference on Learning Representations (ICLR), 2015. 1,
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In IEEE International Conference on Computer Vision (ICCV), 2019. 3
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In
IEEE Conference on Computer Vision and Pattern Recognition, 2016. 24
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification deep neural networks. In International Conference on Computer Aided Verification (CAV), 2017. 3
Jongheonn Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers.
In Advances in Newral Information Processing Systems (NeurIPS), 2020. 3
12

---

Published in Transactions on Machine Learning Research (08/2022)
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. In Advances in Newral Information Processing Systems (NeurIPS), 2020. 4
Hamid Karimi, Tyler Derr, and Jiliang Tang. Characterizing the decision boundary of deep neural networks. arXiv preprint Xi: 11400, 2019. 3
Maurice G Kendall. A Course in the Geometry of n Dimensions. Courier Corporation, 2004. 6, 17
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. 2, 8, 15, 24
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning (ICML), 2020.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEFE Symposium on Security and Privacy (SP), 2019.
2, 3
Guang- He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. arXic preprint arXiw:1906.49443 2019. 3
Alexander Levine and Soheil Feizi. Robustness cortificates for sparse adversarial attacks by randomized
ablation. In Associalion for the Advancement of Arlificial Intelligence (AAAT), 2020. 3
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for 11 certified robustness. arXiv preprint 2tt:::203310834,, 2021.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems (NeurIPS), 2019. 3
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Tao Xie, Ce Zhang, and Bo Li. Provable robust learning based transfornation-specffic smoothing. arXiv preprint ar arXio:2002.122 123988 2020. 5
Jeet Mohapatra, Ching Yun Ko, Tsui Wei Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher-order cortification for randomized smoothing. Advances in Neural Information Processing Systems (NeurIPS), 2020. 3, 29
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019. 15
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, bighhpeeffrmance deep learning library. In Advonces in Neural Information Processing Systems (NewrIPS). 2019. 20, 24
Lluis Ros, Assumpta Sabater, and Federico Thomas. An ellipsoidal calculus based on propagation and fusion. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2002. 21, 22
Hadi Salman, Jerry Li, Ilya P Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advunces in Newral Information Processing Systems (NeurIPS), 2019a. 3, 4, 6, 8, 9, 10, 16, 25, 26, 28, 30
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. convex relaxation barrier to tight robust verification of neural networks. In Advances in Newral Information Processing Systems (NeurIPS), 2019b. 3
Christian Szegody, Wojeiech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014. 1,
13

---

Published in Transactions on Machine Learning Research (08/2022)
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations (TCLR), 2019. 3
Florian Tramer, Nicolas Papernot, Ian Goodfellow, Dan Bonch, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint Xixi 774.004.4.... 2017.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Tan Goodfellow, Dan Boneh, and Patrick McDaniel. En- semble adversarial training: Attacks and defenses. In International Conference on Learning Representations (ICLR), 2018.
Tsui- Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. In International
Conference on Machine Learning (ICML), 2018. 3
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Tlya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning (ICML), 2020. 2, 3, 4, 5, 8, 10, 11, 25, 29
Runtian Zhai, Chen Dan, Di Hc, Huan Zhang, Boqing Gong, Pradcop Ravikumar, Cho-Jui Hsich, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations (ICLR), 2019. 3, 5, 6, 8, 9, 10, 25, 26
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Filling the soap bubbles: Efficient black-box adversarial certification with non-gaussian smoothing. https:// net/forum?id- Skg8gJBFvr, 2019.
14

---

Published in Transactions on Machine Learning Research (08/2022)
A Qualitative Motivation of Anisotropic Certification
A.1 Visualizing CIFAR-10 Optimized Isotropic vs. Anisotropic Certificates
To extend the illustration in Figure 1 to a higher dimensional input, we now analyze an example of the isotropic & certification of randomized smoothing with ((0,o21) where optimized per input Al- larra al. (2022), against ANCER, certifying an anisotropic region characterized by diagonal fz- norm. To do so, we consider a CIFAR-10 Krizhevsky (2009) dataset point v, where the input is of size (32x32x3). We perform the 2D analysis by consid- ering the regions closest to a decision boundary. To do so, and following Klosavi-Dezzood et al. (2019), we compule the Hessian of (x) with respect to
Anistropic Isotropic
Anistropic
Isotropic
$
(b)
where y is the true label for z with f classifying correctly, i.e. arg max; (z).. In addition to the Hessian, we also compute its eigenvector decomposi- tion, yielding the eigenvectors {u:}, i ......,37722, ordered in descending order of the absolute value of the respective cigenvalues. In Figure 6a, we show the projection of the landscape of f in the highest curvature dircctions, i.e. 1/1 and V2- Note that the isotropic certification, much as in Figure Ic, in these 2 dimensions is nearly optimal when compared to the anisotropic region. However, if we take the same projection with respect to the eigenvectors with the lowest and highost eigenvalues, e. Vj and V3072, the advantages of the anisotropic certification become clear as shown in Figure 6b.
Figure 6: Illustration of the landscape of f for points around an input point and two projections of an isotropic l certified region and an anisotropic 2- norm region on a CIFAR-10 dataset example to a subset of two eigenvectors of the Hessian of fa (blue regions correspond to higher confidence in y).
Anisotropic Certification and Evaluation Proofs
Proposition (restatement). Consider a differentiable function g IR" + R. If gz)))l L where || ||x has dual norm || = max, 2 s.t. ||~||| S 1, then g is L-Lipschitz under norm I|,, that is lg(x) ι(v)l L|xx v|l-
Proof. Consider some v, y E R and parameterization in 1 as (() (1 t)x + ty At E [0, 1]. Note that 70) = x and r(1) y. By the Fundamental Theorem of Calculus we have:
L. dg(>(()) dt dt = / Vg Vydt S 1/" V / Vy
9(=) = (1() 9(>()))
$ [Vo()) 4 x||
Theorem 1 (restatement). Let g R" R g" be L-Lipschitz continuous under norm 11. Vi (1....,K] and сд argmax, g (z). Then, we have arg max; g' 5) CA for all 8 satisfying:
1
||
a max aree (3))
2T.
Proof.
Take cg = arg max, ( By Proposition 1, we got:
l (x: + 8) gd* (x) < ||]
A
(x + 2 f -L [8]
0 (z 00 - - ||
= gx 8dd + 11
15

---

Published in Transactions on Machine Learning Research (08/2022)
By subtracting the inequalities and re-arranging terms, we have that long g (x) > 9 (x) + L|
-||6||
e.e. the bound in the Theorem, then g²a (x + 8) > g (x + 8), completing the proof.
Proposition 2 (restatement), Consider (x)(s) = Ni0, [s + e)]. Φ (gx(()) is 1-Lipschitz (i.e. L 1) under the
- norm.
Proof. To prove Proposition 2, one needs to show that + (g' (x)) Vi is 1-Lipschitz under the || 1|x-111 norm. For ease of notation, we drop the superseript 9' and use only g- We want to show that (g=()ll- = V S 1. Following the argument presented in Salman et al. (2019a), it suffices to show that, for any unit norm direction and g2(x), we have:
u (T S 2
exp (-1(0-)0)))
(2)
We start by noticing that:
u Σ (z)( (v2x)" [ Jz. (()) exp exp (-2(x (r +)E ()--((01)) d
1
E [f + st) s) = Bom + v)u T - b).
We now need to find the optimal f : Rm [0, 1] that satisfies (x v v)] = p while maximizing the left hand size E If + v)u T Σ uu]. We argue that the maximizer is the following function:
()) = 1 fuTT T to - (0)
To prove that f is indeed the optimal maximizer, we first show feasibility. (i): It is clear that f R8 + [0, 1]. (ii) Note that:
E EV-N(O)))
[1(uTTe u fftJIIN -w-1 = P -
o - (p)) = - 1111-o(-a-1000 =
To show the optimality of fr, show that it attains the right upper bound:
Be-((, u T - o {u E - - = E2-N1o.1) x1l for (x))
(-1
Texp
(-20² de
V2T -
1 (0- (0))
exp
2m
obtaining the bound from Equation equation 2, and thus completing the proof.
Proposition 3 (restatement). Consider ga (x = -=- Ae)]. The classifier 9 Vi is 1/2- Lipschitt (i.e. L L= under the ||Az||oo norm.
Proof. We begin by observing that the dual norm of |,o|||,1 = ||A''/[i is ||0|-- = ||Ax|loc, since:
max I y ||A-'zlh $1
max 8 T A= ||Ay|oo.
11:1
Without loss of generality, we analyze 0g for.. Let & [xg...., zn] R= then:
\1gg A1 θ
/ [ 1-1.11-- { f'(m + A1G, + Ar)de
dx
(2x)a dr
1
(f + +, λε) - (x1 1, + 1
2n
J|-111]"
16

---

Published in Transactions on Machine Learning Research (08/2022)
Thus,
On 0m
1 1001-1,10 1, Σε) d= = 2
n [T Ag ( [-1,]]=-1 (x) +1, Åε) (x111-
The second and last steps follow by the change of variable t + d11 and Leibniz rule. Following a symmetric argument, | /ons S 1/2 Vi resulting in having ( = max, d 1000 20// s 1/2 Vi concluding the proof.
Proposition 4 (restatement). V ((0: ||A- rr) = [2r) II: A
Proof. Take A = -A-A== diag(t/ra)...... 1/r,., diag(a1...... an))
We can re-write the region as fx E, ar| S 1), from which it is clear to see that this region is an origin centered, axis-aligned simplex with the set of vertices V = e= where e, is the standard basis vector i.
Define the sets of vertices V V -VV--%a..., and V = VV cn.. Given the symmetry around the origin, each of these sets defines an n-dimensional hyperpyramid with shared base Bn-1 given by the - --dimensional hyperplane defined by all vertices where nn, = 0, and apez at the vertex 1/a,,n, (or -,/,,,, in the case of V²). The volume of each of these n 1-dimensional hyperpyramids is given by v(B,-1)/nan (Kendall (2004)), yielding total volume of V = L. applied to compute -1) which is a union of two n - 1-dimensional hyperpyramids. This forms a recursion that completes the proof.
d., V(B.1). The same argument can be
Proof. (Alternative Proof.) We consider the case that A-1 is a general positive definite matrix that is not necessarily diagonal. Note that V ((6: ||A- I <r))
V ((ő: ||(A))-1||| s 1}) = |' ({8 : [|ō|] S 1)) under a linear map and noting that {8 : ([(rA)- = frAs ||6]] S r). At last, {6 : [|6]] S 1} can be expressed as the disjoint (2r)"/nl) A| since the volume of a simplex is union of 2n simplexes. Thus, we have V ((5 ||||1 rt} l/nl completing the proof.
where [r|] denotes the determinant. The last equality follows by the volume of
For completeness, we supplement the previous result with bounds on the volume that may be useful for future readers.
Proposition 5. For any positive definite A E Ruxn, we have the following:
2r v (Z(A)) S ((16 ||A 1ol S (2r)
where ((Z(A)) = AAA A| which is the volume of the zonotope with a generator matriz A.
Proof. Let S = {8 | S r), See { ||A--- <r and S (6 nl|AA-10|le S r). Since < |||1 |||~~
- then Sxx 2 S1 S Therefore, we have V(S5z) 2 V(Si) V(S%). At last note that, 5% [5A5 ||01 < <1) and that with the change of variables 8 2u 1, where 1, is a
vector of all ones, we have 5% 2 (2r @ =A where 1 is Minkowski sum and noting that AA1, is a
single point in " Therefore, V (z((2r) 2+A @ = (2r% (Z(A).. The upper bound follows with
similar argument completing the proof.
B.1 Certification under Gaussian Mixture Smoothing Distribution
We consider general, K K-component, zero-mean Gaussian mixture smoothing distribution g such that:
K
g(far, E,(( = Σ ao Ex), s.t. 1
(3)
17

---

Published in Transactions on Machine Learning Research (08/2022)
Given f and as per the recipe described in Section 4, we are interested in the Lipschitz constant of the smooth classifier (g())) = (J * (x) Ei 0:9g; Ei ossS (00, E.)) = E, 0.9x, (x) where gx, is defined as in the Gaussian case.
Note the weaker bound when compared to Proposition 2, for each of the Gaussian components presented in the following proposition.
Proposition 6. gr is Ipps-hipschitz under ||-I|=-1,2 norm.
Proof. Following a similar argument the proof of Proposition 2, we gel:
u Vgx((>> v (2T) [2] RR
1 [t zi) exp (-2(x- (x-
(x- d't
= =EeNN((.))
[lu [s|] Ben.((0.1) [|a]] - 2/T.
With Proposition 6, we obtain a Lipschitz constant for a Gaussian mixture smoothing distribution as:
Proposition 7. 9g is V=/2-Lipschitz under || norm, where B- Σx a.
Proof.
løg(0 -00+ [g(()]] <
-
Σ a (x
(x+ +0) -g,
σT Σ 1a. 8
s 0 |x,,, S V
1
10
Obtained by first applying the triangle inequality, then Proposition followed by Jensen's inequality.
7
Thus yielding the following certificate by combining Proposition 7 and Theorem 1. Corollary 3. Let сλ arg max, (x()) then arg max; I' + 6) cA for all satisfying:
| S
1
c (z) max 9g ofen (z))
V2T
where B EK 1,
C AnCer Optimization
In this section we detail the implementation choices required to solving Equation equation 1. For ease of presentation, we restate the ANCER optimization problem (with @ = diag( }())))))
arg max e
7P (x, Ot)
II O
s.t. min 0.r (x, θt) 2 Ti
where rd (x, OF) is the gap value under the anisotropic smoothing distribution, and ri is the optimal isotropic radius, i.c. rx, 8²) for Hr e R+. This is a nonlinear constrained optimization problem that is challenging
to solve. As such, we relax it, and solve instead:
arg max p (x, 6-
y
II o + *mmnn 07r (x,
s.t. 0. 2 0
given hyperparameter E R While the constraint 0 2 0r is explicitly required enforce the supersel condition the isotropic case, proved itself beneficial from empirical perspective. To sample
18

---

Published in Transactions on Machine Learning Research (08/2022)
from the distribution parameterized by @ (in case, either Gaussian Uniform), make of the reporamederiaation trick, as in Alfarra et al. (2022). The solution of this optimization problem can be found iteratively by performing projected gradient ascent.
A standalone implementation for the ANCER optimization stage presented Listing 1, whereas the full code integrated our code base available as supplementary material. To perform certification, we simply feed the output of this optimization to the certification procedure from Cohen al. (2019).
inport torch
fron torch. autograd inport Variable import Normal
distributions
class (ertificate():
def conpate.proxy__9pp (self,,f, logits: torch. Tensor):
raise NotinplementadErro
cenple_ batch:
Tensor, repeated,thota:
raise HotinplementedBrro
def gapatt pABar: float):
raise hotimplementeddrrt
12Certificate (Cortificate):
def _.init_. (self, batch_ sizeh_ int, device: sir "ouda:0") self.n (ernal(torce zeros (batch_ to (device) torch. ones (batch_ size) (davica)) self.davicn davice
compute_prext pappptteprooy.ppppccpcp gap (solf, logits:
Tensor):
return self.n. icdf (lagita[:, o].clanp. (0.001, 0.999)) self m. icdf (logits I:, cl.clanp_ (0.001, 0.999)
def sample_ noise (self, batch: torch.Tensor, repeated_tane theta: torch torch.Tenaor) Tenaor): return torch renda, (batch, device=eelf.device repested_
compate_gap gsell, pABar: float): return norn. (pABar)
class LiCertificate (Certifiattt) -. ..iniit_ (self, device="cuda:0"); device device
def compate_ (nel logits: torch. Tansor):
logital:, 0] logital:,
cample_noise
repeated_ Tensor):
return 2 rand
devicensalf device) 0.5) pepaated_theta.
def compute_gaa _apee_apppppe (self, PABar: float):
return 2 (pABar 0.5)
def ancer aacer_ crteeooptniizaiont
model: norch.nn.Mor Nodule, batch: torch. Tansor,
certificate: Certificate, learning_rate. rate: float, isotropic_the theta:: terch Tensor, iterations:
samples: int, kappa: float, device: atr "cuda:0"): "*"ppiiaiee batch using ANCER, sssuning isotropic initialization point.
Args:
model: trained netxork
batch: inpute to certify around
certificate: instance of desired certification object learning_rate: rate: optinization learning rate for ANCER teotropic_theta: initialization isotropic iterations: number of iterations to run the optinization sanples per input kappa: relaxation hyperparaneter
per input
samples:
batch_size batch. shape [0]
ing size (batch. shapee [1:])
define variable, the optinizer, and the initial signa values (artablattsorroplc...e
(eenr (o (davice))
19

---

Published in Transactions on Machine Learning Research (08/2022)
eptinizer optii..pti..... aptin..Aann(aaaal (dan((theta)) Ir= initial theta theta. detach cllonee)
reshape vectors to have "ssaplea"" per Input in batch nov_shape [batch_size samples]
aas__haape.xtten extend [b) shapee)
nev_batch batch.rapeat ((1, samplea, 1, wie.
solve iteratively projected gradient ascend
for In renge(iterationa theta_repeated theta. samples, 1, 1). vievv (ie
Reparanatarization trick
noise certificate. sanple_noiseeter batch, theta_repeaton model(
nev_batch nolse
ressaapee (batch samples, -1) (dinn))
rals, terch topk 2)
gap cartiricate. conprricaaeccouutt.....
(va(ss)s)
pred torch prod(
(theta. reshape (batch_size, =1))==(1/igg_e/)) din-1)
proxy_radius prod gap
radius_man maxinizer =-(
proxy_radius.
kappa (torch.nin (theta.. vier (batcbach_ din-1) valuee*gap
gap).
radius_mant maxinizer......e......mm.mmmiiii backward
optinizer. ()ep()
project initial with torch no g)_ torch. march.ax(thetta. initial_theta. out-theta)
return theta
Listing 1: Python implementation of the ANCER optimization routine using PyTorch Paszke al. (2019)
Memory-based Certification for AnCer
To guarantee the soundness of the ANCER classifier, we use an adapted version of the data-dependent memory-based solution presented Alfarra et al. (2022). The modified algorithm involves a post-processing certification step that obtains adjusted certification statistics based on the memory procedure from Alfarra al. (2022) (sce the original paper for more details). We present an adapted version to ANCER of this post-processing memory-based step in Algorithm 2.
Algorithm 2: Memory-Based Certification
Input: input point ÆN+1, certified region Rx+1, prediction CN+1, and memory M Result: Prediction for vN+1 and certified region #N+1 that does not intersect with any certified region M.
for Ci, R.) E M do
if CN+1 # C, then
if ÆN+1 E R, then return ABSTAIN,
elsc if MunIntersect/Rxuun R2) and Intersect/Ryy R.) then R' LargestOuttuusse((RR RN+1);
RN+1 + R'y+1i
end
add (1 Cx+1, RN+1) to M: return CN41, RN41
Note that the proposed certified region RN+1 emerges from our certification bounds presented in Sections 4.1 and 4.2. There are few differences between proposed Algorithm 2 with respect to the original variant.
20

---

Published in Transactions on Machine Learning Research (08/2022)
presented in Alfarra et al. (2022). The first is that we remove the computation of the largest certifiable subset of certified region RN+1 when there exists an i such that IN+1 E R, with different class prediction, i.e. (LargestInnubset in Alfarra et al. (2022)) due to the complexity of the operation in the anisotropic case. As an example, is generally difficult to find the largest volume ellipsoid contained in another ellipsoid. Due to this complexity, we choose to simply ABSTAIN instead. Given the high dimensionality of the data, empirically, we never found certificate in this situation within our experiments. Further, to case the computational burden of the Intersect function, we introduce and instantiate the function MaxIntersect first which checks whether the Ep-ball over-approximation of the region RN+1 intersects with Ep over-approximation of RR This follows since when the Ep balls over-approxination to the anisotropic regions RN++ and R2 do not intersect, then RN+1 and R, do not intersect either. Only in cases in which those over-approximation regions intersect, we run the more expensive Intersect procedure. We present practical implementations for MaxIntersect, Intersect and LargestOutSuubeet for the ellipsoids and generalized cross-polytoper considered in this paper.
D.1 Implementing MaxIntersect (RA, RB) in the Ellipsoid and Generalized Cross-Polytope Cases
Given the two regions RA and RB, consider bp-ball approximations of those regions, R - {x E I= || - allp S ra] and RB = fx E R": || - bllp $ rb] such that RA S RÁ and RB S RB. Lemma 1. If la - b > ra tb, then RA n RB = 0.
Proof- For the sake of contradiction, let ||a bllp > ra +r and x RA NRg- Then, have that || $ ra
and || bll S. Tb. However:
Fa + rb
< |aa b/1, < | all, + || bll, S ra + Tb:
forming a contradiction. Thus, RA N R 0, which in turn implies RA n RB = 0 since RA and RB are subsets of R and RB, respectively.
This forms a fast, maximum intersection check for ellipsoids, i.e. = 2, and generalized cross-polytopes, ie. p == 1. The MaxIntersect function returns False if ||a - bllp > ra + The and True otherwise.
D.2 Implementing Intersect(Ra, RB) in the Ellipsoid Case
The problem of efficiently checking if two ellipsoids intersect is not trivial. We rely on the work of Ros et al. (2002); Gilitschenski & Hanebeck (2012) with missing proofs from Gilitschenski & Hanebeck (2012) for completeness.
13 and RB = fr (r- B 1 define two ellipsoids centered at a and b, respectively. We have that R = (x: :(: A (1- B (x b) s 1} for any E [0, 1] satisfies RA ARB R S RAAU RRARRa RB.
Lemma 2. Let = f E"; (x-a)
Proof. By considering the convex combination of the RA and RB, it becomes obvious that I E RA n RB = I E R, concluding the left side of the property. As for the right side, it suffices to show that if x & RA and x E R then x E RB and, similarly, that if x & RB and x E R then x E RA. We show the first case since the second follows by symmetry. Without loss of generality, we assume that b On- Now, let x be such that TTAr Ar and tx T Ar (1 t)x Br
side of the inequalities defining the regions
since & RA and x E R. Then, since E R, we have that (1 t)x Br < 1 - tx Ar < 1 since x Ax which implies that RB.
Note that the previous result holds without loss of generality when for the radius as the radius can be absorbed in A and B. As the following Lemma was shown by Gilitschenski & Hanebeck (2012) without proof, we complement it below for completeness.
Lemma 3. The set R equivalent the following ellipsoid R {a (a m) E, m) S K(t)) where E, /A (1 B)B, m E," (LAa + (1 - -))b,, and K(t) ta T Aa (1 1)b Bb m E.m.
21

---

Published in Transactions on Machine Learning Research (08/2022)
Proof.
t(x - a) A(x - a) + (1 (z 6) B(x b) 1
<x
(IA (1 (1]]B) x 2x (IAa (1 ()BBi)
laa Aa (1 1)b* Bb
Pr
Fam
(x m) TE m) 1 la TA Aa 1)6 BB m E
The last equality follows by adding and subtracting m Emm and concluding the proof.
Proposition 8. The set of points salisfying R. for E (0,1) is either an emply sel, a single point, or the ellipsoid R.
Proof. We first observe that since A and B are positive definite, then E, is positive definite. Then observe that for choice of t E (0, 1) such that (t) < 0, the set R is empty set, and since R 2 RA n RB, the two sets do not intersect. If (t) = O, then the only point satisfying R is the center at m. Following similar argument, then the two ellipsoids intersect at a point. At last for choice of such that K(I) > 0, then R defines an ellipsoid.
As per Theorem 8, it suffices to find some t E [0, 1] under which (tt < to guarantee that the ellipsoids do not intersect. To that end, we solve the following convex optimization problem: t" jo. ((t and check the condition if k(t*) < Morcover, shown by Ros et al. (2002); Gilitschenski & Hancbeck (2012) ((I) convex in the domain I (0, 1). With several algebraic manipulations, one can show that K(L) has the following equivalent forms:
((t) - ta T Aa - (1 t]bb Bb + m
EE
((t)= t(1 t)(b 10--0 -a) "BE," A( a)
((I) = (b-a)² a)T (1-, B 1 (
(b ab-a)
Observe that for ANCER, we have that both A and B to be diagonals with diagonal clements {A and (B respectively, resulting in the following simple form for K(I):
k(t) = Σ (b. 0,)² 1(1 - A) tA + (1 - tt)B
i=1
The Intersect function in the ellipsoid case returns False there exists a E (0, such that K(t) < 0, i.c. ellipsoids do not intersect, and True otherwise.
D.3 Implementing Intersect(Ra: RB) in the Generalized Cross-Polytope Case
Let RA and Rg be two generalized cross-polytopes RA = fa R" ||Ax - a)ll I 1} and RB = {o e R [B - b)ll S 1), where A and B are positive definite diagonal matrices with elements {A,)% and [B respectively. We are interested in deciding whether RA and RB intersoct. However, given the conservative context in which Intersect is used in Algorithm 2, we only need to make sure that the function only returns False if it is guaranteed that RA n RB = 0.
As such, we are able to simplify the complex problem of generalized cross-polytope intersection to the much simpler one of ellipsoid over-approximation intersection. We do this by considering the over-approximation i.e. superset, ellipsoids Ra = {a e R" : AA - a)ll2 < 1} and RB = fa R" |B(r - 6)ll < 1}, and perform the cllipsoid intersection chock presented in Appendix D.2. If n Rg 0, then this implics that RA n RB / and we can safely return False. Otherwise, we conservatively assume the generalized cross-polytopes intersect, and return True, triggering the reduction procedure detailed in Appendix D.5.
22

---

Published in Transactions on Machine Learning Research (08/2022)
D.4 Implementing Largest RB) in the Ellipsoid Case
((x=) Given two ellipsoids RA { E R.: ax A(x - a) S 1 and Rn {s E ER: (x - b) B(z -x b) S }} that do intersect where A and B are positive defimite diagonal matrices, the task is to find the largest possible ellipsoid Rg centered at b such that RB _ RB where RA n Rg =
B
Finding a maximum ellipsoid that satisfies those conditions not trivial, so instead we consider maximum enclosing fz-ball of RB, RB {a E R" || bll2 S r), that does not intersect RA. To obtain this ball, we project the center of RB, b, to the ellipsoid Ra. Particularly, we formulate the problem the projection of vector y b onto ellipsoid with the same shape as RA centered at O, This is equivalent to solving the following optimization problem for a symmetric positive definite matrix A:
min 2
1
211
s.t. Ar
Note that the objective function is convex, and the constraint forms convex set. Forming the Lagrangian to this problem, we obtain:
1 111 1122- A 1x Ax- 1))
((x, A)
where À > 0. Therefore, the global optimal solution must satisfy the KKT conditions below:
dc
0 -+ (2XA + +1)
dr
OL
(2XA + 1) y = 0. +yy T A
= 0X
S(A)
Thus, to project the vector on our region the ellipsoid characterized by A, one needs to solve the scalar optimization f())= = then substitule back in the formula of x². Further, given = (Alig(A11............ Ann), we can simplify the problem to:
A
f()) 2AA
=.
Once x" obtained, we can define the maximum radius of the fe-ball centered at that does not intersect RA as:
||xx + bll2 e,
for an arbitrarily small Finally, we obtain Rg as the maximum ball contained within RB that has a radius smaller than r", that is:
RB = (ir E R" | b1l2 S mainrr",ijn Ba)).
Note that while choosing the radius of RB be r' guarantees that RB RR this does not guarantee that Rg C RB- To guarantee both properties, we take the minimum of both r* and min; Ba- This approach finds the solution to the projection of the point to the ellipsoid {x E R" : Ax < 1); it does not work for the case in which b E RA, since the problem would be trivially solved by setting xt y. Thus, our classifier must abstain in that situation.
D.5 Implementing LargesttDuttSussttRRR. RB) in the Generalized Cross Pooysopo Case
Let RA and RB be two generalized cross-polytopes RA far E R |A(x a)]lı s 1} and RB = fx e R": |[[x - b)]l < 1}, where A and B are positive definite diagonal matrices with elements {A,),, and {B respectively. The task is to find the largest possible generalized cross-polytope Rg centered at such that RB S RB where RA n RB =
As with the ellipsoid case, solving this problem for a generalized cross-polytope is not trivial, so instead we consider maximum enclosing cross-polytope (i.e., l-bblll) of RB far E R. || - b//2 S r) that does not.
23

---

Published in Transactions on Machine Learning Research (08/2022)
intersect RA and is subset of Rg. To obtain this fI-ball, project the center of RB, b, to the generalized cross-polytope RA in similar fashion to the ellipsoid case in Appendix D.4. We formulate the problem the projection of the vector
b - to the O centered generalized cross-polytope {ir E 1 ||Ax||1 S 1}.
Lemma 4. Consider the hyperplane H = {a ER : TTx x = 0} and a point y E IR". The f2 projection of y on the hyperplane is the point x² = y - (10 ToTTyr " w
Proof. We define the projection problem in a similar fashion to the ellipsoid case:
1 min 2 || 2112
s.t. w J k 0.
and obtain the Lagrangian as (xx, A) = 1/2 | - 21l2 + s(w x - k), from where we get (using the KKT conditions): x² = y - A and X = w k thus obtaining: x²' = (w g y-k)
While this formulation does not yield the closest point from hyperplane when measured with the l norm, [|1 2 ||
1|z=== 211|2 implies the certification set obtained in the & norm via this method is subset of the fz-ball of the minimum projection point. Crucially, this l2 projection has the advantage of having a closed- form solution, while an l one would require solving the problem using an iterative linear programming solver. As such, for the sake of computational complexity, we decided to use this projection, despite the sub-optimality of the result from the l perspective. Empirically, we have found this does not affect our results.
the fact that ||æ =0||
Since the set of vertices of the generalized cross-polyten pross-polytope {a E R" ||Aæ|| S 13 is given by (e//A., )/A.)/ and considering the distance between the projections and the original y. the hyperplane that minimizes it is By writing it as system of equations, we obtain the defined by the set of vertices (sign()))//AAa)) -sign(yn)) Ann] and k = 1. Finally, after computing x' as per hyperplane defined by w = [-sign(y)) Lemma 4, we can define the maximum radius of the ball centered at b that does not intersect RA as:
r² = [|x + aa bll1 c,
for an arbitrarily small c. Finally, and similar to the cllipsoids case, we obtain RB as the maximum generalizod cross-polytope contained within RB that has a radius smaller than r", that is:
RB (x E R"; ||e blli S min(r" min B,])
Similar to before, guarantee that the & ball Rg is still a subset to RB, we take the minimum between r* and min; B; to be the radius of RB. As with the ellipsoid case, this approach does not work for the case in which b E RA, since the assumption of the closest plane to y would not hold. Thus, our classifier must abstain in that situation.
E Experimental Setup
The experiments reported in the paper used the CIFAR-10 Krizhevsky (2009)3 and ImageNet Deng et al. (2009)* datasets, and trained ResNet18, WedeRessNet40 and ResNet50 networks He et al. (2016). Experiments used the typical data split for these datasets found in the PyTorch implementation Paszke et al. (2019). The procedures to obtain the baseline networks used in the experiments are detailed in Appendix E.1 and E.2 for ellipsoids and generalized cross-polytopes, respectively. Source code to reproduce the ANCeR optimization and certification results of this paper is available as supplementary material.
Isotropic DD Optimization. We used the available code of Alfarra et al. (2022)5 to obtain the isotropic data dependent smoothing parameters. To train our models from scratch, we used an adapted version of the code provided in the same repository.
3 Available here (url), under MIT license.
4 Available here (url), terms of access detailed in the Download page. 5 Data Dependent Randomized Smoothing source code available here
24

---

Published in Transactions on Machine Learning Research (08/2022)
Certification. Following Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019); Yang et al (2020);
Alfarra et al. (2022), all results were certified with No = 100 Monte Carlo samples for selection and N = 100, 000 estimation samples, with failure a probability of a = 0.001.
E.1 Ellipsoid certification baseline networks
In terms of ellipsoid certification, the baselines we considered were COHEN Cohen et al. (2019)), SMOOTHADY Salman al. (2019a)² and MACER Zhai et al. (2019)
In the CIFAR-10 experiments, used ResNet architecture, instead of the ResNet 10 used in Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019) due to constraints the level of computation power. As such, we had to train each of the networks from scratch following the procedures available in the source code of each of the baselines. We did so under our own framework, and the training scripts are available in the supplementary material. For the ImageNet experiments we used the ResNet50 networks provided by each of the baselines in their respective open source repositories.
We trained the ResNet18 networks for 120 epochs, with batch size of 256 and stochastic gradient descent. with learning rate of 10-2, and momentum of 0.9.
E.2 Generalized Cross-Polytope certification baseline networks
For the certification of generalized cross-polytopes we considered RS4A Yang et al. (2020) As described in RS4A Yang et al. (2020), we take >= 5/v3 and report results as a function of a for case of comparison.
As with the baseline, we ran experiments on CIFAR-10 on WideResNet40 architecture, and Ima- geNet on a ResNet50 Yang al. (2020). However, due to limited computational power, we were not able to run experiments on the wide range of distributional parameters the original work consid- ers, i.e. σ {0.15, 0.25, 0.5, 0.75, 1.0, 1.125, 1.5, 1.75, 2.0, 2.25, 2,5, 3.25, 3.5} on CIFAR-10 and a = (0.25, 0.5, 0.75, 1.0, 1.125, 1.5, 1.75, 2.0, 2.25, 2.75, 3.0, 3.25, 3.5} on ImageNet. Instead, and matching the requirements from the ellipsoid section, we choose a subset of a = {0.25, 0.5, 1.0) and performed our analysis at that level.
While the trained models are available in the source code of RS4A, we ran into several issucs when we altempted to use them, the most problematic of which being the fact that the clean accuracy of such models very low in both the WideResNet400 and ResNet50 ones. To avoid these issues we trained the models from scratch, but using the stability training loss as presented in the source code of RS4A. All of these models achieved clean accuracy of over 70%.
Following the procedures described in the original work, we trained the WedeRosNet400 models with the stability loss used in Yang al. (2020) for 120 epochs, with a batch size of 128 and stochastic gradient descent with a learning rate of 10 2, and momentum of 0.9, along with a step learning rate scheduler with a y of 0.1. For the ResNet50 networks ImageNet, we trained them from scratch with stability loss for 90 epochs with learning rate of 0.1 that drops by a factor of 0.1 after cach 30 epochs and batch size of 256.
F Superset argument
The results we present in Section 7 support the argument that ANCER achieves, in general, a certificate that is a superset of the Fixed a and Isotropic DD ones. To confirm this at an individual test set sample level, we compare the l2, L,, Ey and f certification results across the different methods, and obtain the percentage of the test set which ANCER performs at least as well as all other methods in each certificates of the samples. Results of this analysis are presented in Tables 4 and 5.
"CoHEn source code available here. SMOOTHADY
code available here. MACER source code available here. PRS4A source code available here.
25

---

Published in Transactions on Machine Learning Research (08/2022)
For most networks and datasets, observe that ANCER achieves larger lp certificate than the baselines in significant portion of the dataset, showcasing the fact that it obtains superset of the isotropic region per sample. This is further confirmed by the comparison with the anisotropic certificates, in which, for all trained networks except MACER in CIEAR-10, ANCER's certificate is superior in over 90% of the test set samples.
Table 4: Superset in top-1 lg and E (rounded to nearest percent)
% ANCER l2 is the best % ANCER E is the best
CIFAR-10: COHEN
83
93
CIFAR-10: SMOOTHADV
73
90
CIFAR-10: MACER
50
69
ImageNet: COHEN
96
ImageNet: SMOOTHADV
90
93
Table 5: Superset in top-1 l and e (rounded to nearest percent)
% ANCER & the best
% ANCER 4 is the best
CIFAR-10: RS4A
100
100
ImageNet: RS4A
97
G Experimental Results per o
G.1 Certifying Ellipsoids - la and fg certification results per o
In this section we report certified accuracy at various & radii and 6y proxy radii, following the metrics defined in Section 7, for each training method (COHEN Cohen et al. (2019), SMoOTHADV Salman al. (2019a) and MACER Zhai et al. (2019)), dataset (CIFAR-10 and ImageNet) and (a E (0.12, 0.25, 0.5, 1.0)). Figures 7 and 8 shows certified accuracy at different & radii for CIFAR-10 and ImlgeNet, respectively, whereas Figures 9 and 10 plot certified accuracy and different by proxy radii for CIFAR-10 and ImageNet, respectively.
G.2 Certifying Ellipsoids é and e certification results per
In this scction we report cortified accuracy at various & radii and E proxy radii, following the metrics defined in Section 7, for RS4A, dataset (CIFAR-10 10 and ImageNet) and o (a E (0.25, 0.5, 1.0)). Figures 11 and 12 shows certified accuracy at different & radii for CIFAR-10 and ImageNet, respectively, whereas Figures 13 and 14 plot certified accuracy and different f proxy radii for CIFAR-10 and ImageNet, respectively.
Visual Comparison of Parameters in Ellipsoid Certificates
Anisotropic certification allows for a better characterization the decision boundaries the base classifier f. For example, the directions aligned with the major axes of the ellipsoids ||,]|,,2 = r, i.e. locations where Σ, is large, are, by definition, expected be less scnsitive perturbations compared the minor axes directions. To visualize this concept, Figure 15 shows CIFAR-10 R-10 images along with their corresponding optimized & isotropic parameters obtained by Isotropic DD, and Ey anisotropic parameters obtained by ANCER. First, we note the richness of information provided by the anisotropic parameters when compared to the & worst-case, isotropic one. Interestingly, pixel locations where the intensity of Σ is large (higher intensity in Figure 15) are generally the ones corresponding least with the underlying true class and overlapping more with background pixels.
A particular insight one can get from ANCER certification that the decision boundaries are not distributed isotropically around each input. To quantify this in higher dimensions, plot in Figure 16 histogram
26

---

Published in Transactions on Machine Learning Research (08/2022)
Cohen [d - 0.12)
Cohen (a- 2.25)
Cohen (d 0.5)
Cohen (a 1.0)
0.6
Floed (A6R-0.283)
Fieed (ACR-04002)
0..6
Fixdd (ACR- 4.22)
Finual (AGRuO, 407)
Certed eccumyy
0.5
ANCER (ACR-0.447)
Isooopic 2.9
Cortfed acuuaay
0.6
NNER (ACR+0
(ACR=00.4)
Controd acquuttyy
ANCER (ACR=O 814)
Isotrosic (ACR
Corifedd accurccy
ANCER (ACR-10025)
IACR=0 824)
0.4
0.3
04
0.2
02
0.2
0.1
0.0
0.0
0.0
0.0
0.00
0.25
0.90
0.75
1.00
1.25
0.0
0.5
1,0
1.5
0.0
0.5
1.0
1.5
2.0
255
6g midus
modius
6g radius
12 roduus
SmootisAdv (ar= 0.12)
SmoothAdv (ar= 0 0.25)
SmoothAdv (ar 0.5)
SmoothAdv (or = 1.0)
0.8
Gortted 105.n8y
0.8
0.5
lestroic: (ACR-005811)
Fixed (ACR=00454)
Go 300 socuuoity
0.8
Floud (ACR=0.568)
lactrasic (ACRR= K15)
Cwrtte a00.u00c
0.4
bestopp:: (ACR+0 894) ANDER (ACR-0.871)
Fixed (ACRRHO, 985)
ANCER (ACR-O. 665)
0.4
ANCER (AC
0.3
0.4
0.2
0.2
Fioed (ACR) 2.291
02
0.2
Isstroplc (AGR-0. 465)
ANCER (ACR=00508))
0.0
0.0
0.0
0.0
0.00
0.28
0.50
0.75
1.00
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
2.0
2.5
22 mndis
1 mddia
4 Fadiu
1 radius
MACER (o- 0.12)
MACER (a = 0 0.25
MACER (a - D.5)
MACER (a - 1.00
Floed (AGR== 272)
Flond (4
0.6
Flord (ACR+-0.7)
0.4
Frove (AGIR=O B86)
Corteed scoureg
Isotrpicc (ACR-0,345)
ANGER (AGR-0 203)
Cantffed acoursoy
0.6
ANCER (ACRR+) 424)
lootrpic (ACR-0.401)
Conteed scqurss
ANCER (ACR-00
Isotropic (AC 641)
Cuntffud acourasy
0.3
kottropic INGR 383)
ANGER (AGR+0.50) 561)
30.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
2 rodus
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
2.0
2.5
5
1,
radlus
4, roddus
1, roduus
Figure 7: CIFAR-10 certified accuracy as a function of Ea radius, per model and a (used as initialization in the isotropic data-dependent case and ANCER).
Cohen (ar 0.25)
Cohen (0 0.5)
Cohen (ar 1.0)
0.6
Coettedd Caettedd sreumicy
crcurra accursyy
0.4
0.4
0.4
0.9
0.2
0.2
Floed (ACR=0477
02
Floed (ACR:00721)
Fioad (ACR:0..84) 884)
Isctropic (WCR-0 627)
Isotrapio (AGRR-0,78))
kottapic c |AGR-0 996)
ANCER (ACR-0055)
ANCER (AGR+11119)
ANDER (ACR-14438)
0.0
0.00
0.25
1,25
0.5
1.0
fa
SmoothAdv (g - 0255)
SmoothAdv (a 0.5)
SmoothAdy (o - 1.D)
0.6
0.4
Conteed meturery
0.4
Centeedaccuu
0.4
0.9
0.2
0.2
(ACR==3.515
Food 816))
lestopic (ACR-081)
lectrpicc (AGR=00.00 .21)
0.1
baklopic (ACR-1.13
ANGER (ACR-0
ANCER (AGR-11.00) (.33)
ANDER (ACR-1 458)
0.0
0.00
0.25
0.50
0.75
1.00
0.5
2.0
radia
mndux
Figure& 8: ImageNet certified accuracy as function of la radius, per model and a (used as initialization in the isotropic data-dependent case and ANCer).
of the ratio between the maximum and minimum elements of our optimized smoothing parameters for the experiments on SmoothAdv (with an initial a = 1.0) on CIFAR-10. We note that this ratio can be as high as 5 for some of the input points, meaning the decision boundaries in that case could be times closer to a given input for some directions than others.
27

---

Published in Transactions on Machine Learning Research (08/2022)
Cohen [d - 0.12)
Cohen (a- 2,2
Cohen (a - 0.5)
Cohen (a- 1.0)
0.6
Fixed (ACIÉ= 263)
(AC/H0,,002)
0.6
Food (ACK-O 487)
Cortfed eecurayy
0.5
Inotropic (999
Coddtedd acourary
0.8
tnotropic (ACA-0044)
Confood accuroty
Inotropic (ACA400,503)
Isotmpic (ACii- 824)
NNCER (477-00670))
ANCER (ACK--0.87)
ANCER (4C66-0.99)
0.3
ANCER (ACGF-1.163)
04
0.2
0.2
22
2
0.1
0.0
0.0
0.0
0.0
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
2.0
2.5
0
12 prony volume
2 prany volume
f2 pracy volume
< prapy vdlume
Smoothsdd (ar= 0.12)
SmoothAdv (ar= 0 0.25)
SmoothAdy (a= 0.5)
SmoothAdv (ar = 1.0)
0.8
Carthed scorrgg
0.6
Flood (ACK-00289))
Isatropic (4C8-00488)
Cantiied acqursayy
0.5
Fooe (AC5400
lactropii (ACR-0.581)
Confect aocuessy
0.8
Floed (ACRR-0,698)
laoeopic (ACR-0.835)
Curtifud accuraoy
0.4
betroppl (ACF-00
Fooed (ACR-0,685 6)
ANGER (ACK-00821)
ANCER (ACA-0.886)
0..4
ANCER (ACR-0.990)
0.3
ANCER (XCC 90.92
0.4
0.
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
0.0
0.5
1.0
1.5
2.0
255
0
1] pmocy volume
4) preay-vatmm volmme
1 pracy volume
4) prnny volume
MACER (o- 0.12)
MACER (a = O 25)
MACER (o = D.5)
MACER (ar - 1.0)
Floed (AC)--0222))
Fowd (AC2-00429)
0.6
Fixed (AC1-00.5))
0.4
Fixel (AC 886)
Centeed sesurey
Cesteed sxcuraay
0.6
lestroi (4C)6-0.481)
scqurssy mar
Inotrpii (417600.41)
Cardfeed sccuessy
bestmpir (ACIf-0.390)
ANCER (ACA-
ANCER (ACR-0.581
94
0.4
ANCER (4 (ACF-00708)
0.3
ANCER 80
0.4
Certedd
0.4
0.2
0.2
0.2
0.1
0.0
0.5
1.0
0.0
0.5
1.0
1.5
provy volume
4 vooky
1 pracy volume
4g provy volumo
Figure 9: CIFAR-10 certified accuracy as a function of 63 proxy radius, per model and a (used as initialization in the isotropic data-dependent case and ANCEr).
Cohon (a = 0.25)
Cohan (a = 0.5)
Cohon (a = 1.0)
0.6
Cenifed woturnyy
0.6
lecimpic VAC160 1977
Food (ACf-004)
Cortfedd accuazy
0.4
Indirapic (Anf- 985)
Flodd (6C4-0.884)
ANCER (ACR-00.99) 9899)
0.4
0.5
ANCER (AC1-11531)
0.2
Fived (ACK--0,72
0.2
Isotrapic (ACK--0.700 785)
0.1
ANCER (22))
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
0.0
0.5
1.0
1.6
2.0
2.5
2
1 prosy volume
praxy volume
4f proxy volume
Smoothddv (o m 0.25)
SmoothAdy (a - 0.5)
SmoolhAdv (a no 1.D)
Cortled scruewy
0.8
Floed (1
Isotropic (ACK--0.6)
Corfiid scorray St
0.4
0.4
ANGER (ACIENG 977)
0.4
0.3
02
0.2
Floud (ACR-00816)
Flood (ACR-110113
lastrpiic (ACR--0.00 921)
0.1
bok bo (ACf--113))
ANCER (AC4-11283)
ANCER (ACR-1 (557
0.0
0.0
0.0
2 1f praay volum
3
3
é prazy volumee
1 prady volume
Figure 10: ImageNet certified accuracy as a function of E proxy radius, per model and a (used as initializatioo in the isotropic data-dependent case and ANCER).
Non data-dependent Anisotropic Certification
As mentioned briefly in Section 6, it is our intuition that anisotropic certification requires data-dependent approach, as different points will have fairly different decision boundaries and the certified regions will extend in different directions (as exemplified in Figure 1).
To validate this claim, we perform cortification of SmoothAdy Salman et al. (2019a) with an initial o a= on CIFAR-10 using a E which is the average of all the optimized Σg. The results of the certified accuracy, ACR and ACR are presented in Table 6, along with the same results for the methods reported in the main paper.
28

---

Published in Transactions on Machine Learning Research (08/2022)
RS4A (o- 0.25)
RS4A (o - 0.5)
RS4A (c 1.0)
0.3
Foodd (ACR 212!
0.8
Fiead (ACR=1.507)
0.8
(ACR-0,475) 475)
(1C
0.8
ANCER (4CR+00488)
9.6
ANCER (ACR #20)
0.6
Fined (ACiite 757,
0.4
0.4
ANCIR (ACR)4 81)
0.2
02
0.0
0.0
0.0
0.00
0.26
0.50
0.75
1.00
1,25
0.0
0.5
1.0
1.5
0.0
0.5
1.0
2.0
radiue
Ft midddus
moduu
Figure 11: CIFAR-10 certified accuracy a function of & radius per (used as initialization in the isotropic data-dependent case and ANCER).
(S = 0.25)
RS4A (c 0.5)
RS4A 1.0)
0.6
0.6
Cortfed
Cartfed NOS
0.4
9.4
0.4
0.2
Floed (ACIEt0 175)
0.2
Flovd (ACRR=0.339)
Floed (AGIlt+
Isatrpic (ACR-00
Isotrapto (ACR-00.37))
Isotrppic (NCR=0
ANGER (33))
ANCER (AGR-00377)
ANGER (KGR- (8)
0.0
0.0
0.0
0.0
0.5
0.2
03
0.4
025
0,50
0.75
1.00
radius
tt mdus
madus
Figure 12: ImageNet certified accuracy as function of & radius per (used as initialization in the isotropic data-dependent case and ANCER).
As can be obsorved, moving away from the data-dependent cortification in the anisotropic sccnario leads to a significant performance drop in terms of robustness.
J Theoretical and Empirical Comparison with Mohapatra et al. (2020)
In regards to the theoretical results, unfortunately the certified regions of Mohapatra et al. (2020) do not exhibit a closed form solution similarly to ours. Thus, a direct theoretical volume bound comparison is not possible.
As for the empirical comparison, ANCER'S performance both &2 and & certificates far out-does that of Mohapatra et al. (2020). For example, with & certificates at radius of 0.5, Cohen certified with AnCer achieves 77% certified accuracy (see Table 1) while Mohapatra et al. (2020) achieves under 60% certified accuracy. Note that Mohapatra et al. (2020) has only a marginal improvement over Cohen et al. As for the & certificates, Mohapatra et al. (2020) uses the Gaussian distribution of Cohen et al, resulting in worse performance than existing state-of-art in & Yang et al. (2020) that uses a uniform distribution. Our approach improves further upon the performance of Yang et al. (2020). For example, as per Table 2, RS4A with ANCER certification achieves 84% certified accuracy at an & radius of 0.5, Yang et al. (2020) achieves 75% certified accuracy while Mohapatra et al. (2020) achieves below 60%. However, we believe that the combination of both approaches, ANCER and Mohapatra et al. (2020) can further boost the performance as also hinted on in the abstract of Mohapatra et al. (2020) on the use of dete-denn smoothing.
29

---

Published in Transactions on Machine Learning Research (08/2022)
RS4A (o- 0.25)
RS4A (g- 0.5)
RS4A (ar 1.0)
(ACR-0212
Flxed (ACR-0.387)
0.8
Inotopic jAciio 478)
Corsited accursay
leotope (ACN-o #14)
accunnoy
0.6
ANCER (ACA 005)
ANGER (AC1F-0.701)
(AC4-00757)
0.4
R.4
bntropic (AC1i-0
ANGER (AC8+
0.2
0.2
1,0
47 prody volume
prozy volume
4 pracy volume
Figure 13: CIFAR-10 certified accuracy as function of e proxy radius per (used as initialization in the isotropic data-dependent case and ANCER).
(o== 0.25)
RS4A (a= 0.5)
RS4A (a= 1.0)
Ceetfedd RECuRME
Cortfedd accursey
0.6
Cartfed aecuwayy
0.6
Foed (ACA-0 178)
Fleed (ACIR- 309)
84
Fieed (ACN--0 642)
Isotropi: (ACR-00,23)
Isotrpic (1C3-00.77))
lsotrapic (ACk-0.681)
ANCER (ACR-1.411)
(ACR-11063)
ANCER (ACR-1.075)
0.0
0.0
0.
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
2.5
E. proxy volume
volume
praxy volume
Figure 14: ImageNct certified accuracy function of es proxy radius per (used as initialization in the isotropic data-dependent case and ANCER).
Figure 15: Visualization of an imput CIFAR-10 image a (top), and the optimized parameters a (middle) and (bottom) higher intensity corresponds to higher o; in that pixel and channel of the smoothing distributions in the isotropic and anisotropic case, respectively.
0.6
0.4
Figure 16: Distribution of the maximum over the minimum ANCER T" at cach dataset point for AdoothAdy Salman et al. (2019a) CIFAR-10 (for initial a 1.0)
30

---

Published in Transactions on Machine Learning Research (08/2022)
Table Comparison of different certification methods on SmoothAdy with an initial a 1.0 on CIFAR-10.
Accuracy la radius (%)
CIFAR-10
SmoothAdv
Ea ACR
& ACR
0.0
0.25
0.5
1.0
1.5
2.0
2.5
Fixed
45
40
35
25
16
5
0.565
0.565
Tsotropic DD
41
39
36
29
21
14
7
0.694
0.694
ANCER
43
35
8
0.871
0.992
Average
25
21
14
2
0.329
0.379
31


Reviews:
[{"review_id": "4GVgHG3C0h", "reviewer": "Reviewer_kc78", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n+ The paper is very well written and easy to follow. It was a nice read for me.\n+ The proposed approach is well-motivated and supported with intuitive diagrams that helps grasping the idea. Specifically, S3 motivates why anisotropic certification is important and would be better than isotropic certifications (though I have some concerns, see below), with proper connections to previous works.\n+ The authors do a good job evaluating their method and comparing it with previous methods on proper benchmarks.\n+ The authors explicitly discuss the limitations of their method in S6 highlighting the memory-based and data-dependent requirements for their anisotropic certification.\n\n### Weaknesses\n+ The contribution of the paper is minor and the results are not very significant ( though I understand that TMLR does not focus on these aspects).\n+ It is unclear why anisotropic certification matters in practice to guarantee more robustness. Relatedly, I think the proxy radius \\tilde{R} might be misleading and does not really reflect the robustness of the model. Larger \\tilde{R} reflects a larger stable (irregular/anisotropic) region of the smoothed model around a given datapoint, but does not mean that the model is more robust there. In fact, an adversary does not care about how large that stable region is, all it cares about is finding the closest decision boundary; this closest decision boundary won't change if we make the certified region more flexible/anisotropic. Thus it is not clear why larger *irregular* stable regions implies higher adversarial robustness. I would appreciate if the authors can clarify/comment on this.\n\nOverall, I like this paper, and I believe it will be useful for the community as an extension of isotropic certification.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a modification of randomized smoothing to support certifying anisotropic regions around each datapoint as compared to previous methods which does it only for isotropic regions (lp-balls). Specifically, the paper utilizes the idea of data-dependent certification in previous work, and maximizes the certified volume per datapoint to get anisotropic certified regions. The authors evaluate their method on CIFAR-10 and ImageNet, properly comparing with previous isotropic randomized smoothing methods.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "+ **A discussion on why anisotropic certification means more robustness:** This is regarding my second point in weaknesses. I understand that the proposed method can certify larger volumes by relaxing the isotropy of the certified regions, thus we can have larger stable neighborhoods around each given data-points. But does this mean more robustness? As I mentioned above, the closest decision region will be the same for an isotropic vs anisotropic region. Nevertheless I still believe the anisotropy can be of advantage, but I believe that such a discussion would be useful in the paper.\n+ **Memory requirement of data-dependent certification:** I appreciate that the authors include certification runtime in section 7.4, but I also think a similar discussion on the memory requirement of data-dependent certification would be useful for the reader. I understand that this might be already discussed in Alfarra et al., but I think it would be useful in this paper too.\n", "broader_impact_concerns": "No concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IttwxSIo7w", "reviewer": "Reviewer_UHCa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The paper's idea of an anisotropic certification region sounds novel and potentially useful.\n\nWeaknesses:\n\n1) The paper's motivation for developing ANCER needs to be further clarified. What kind of applications may require anisotropic certification regions with bounded volumes? The introduction only mentions that it is possible to find a larger anisotropic certification region that is a superset of the maximal isotropic region (Figure 1). However, ANCER is only a certification tool that applies to an already trained classifier. Therefore, as long as the anisotropic region in ANCER is found through extending the maximal isotropic certification region such that the output label does not change for an input $x$, ANCER does not make any changes to the original classification rule coming from the isotropic randomized smoothing certification method. In other words, ANCER may find a larger anisotropic certification region, but it essentially uses the same classification rule as (Alfarra et al 2022)'s method.\n\n2) The optimization task in Equation (1) is vaguely explained. I could not find the mathematical definition of $r^p(x,\\Theta^x)$ which is vaguely referred to as \"the gap value under the anisotropic smoothing distribution\". Is $r^p(x,\\Theta^x)$ a function of model $f$? I am wondering how the authors take the gradient of this function w.r.t. $\\Theta^x$, which is not explained in the text. Since these key details are missing in section 6, I could not see whether ANCER results in a different classification rule from the smoothed classifier with fixed variance parameter $r^*_{iso}$. It seems Equation (1) tries to expand the $r^*_{iso}$-radius isotropic region until the classifier's prediction remains unchanged. If this statement is true, the classification rule remains essentially the same.  \n\n3) The numerical discussion in section 7 needs further clarification. The paper mainly uses $\\ell_p$ certified accuracy as the evaluation metric for the proposed ANCER and the baseline methods. However, a higher certified accuracy only implies that the certification method could guarantee the prediction in a larger radius and does not mean the classifier enjoys higher adversarial robustness. This point needs to be clarified in the text. \n\n4) As another comment on numerical results, the results in Figures 3,4 and Table 1 show ANCER improves the certified accuracy over isotropic DD (Alfarra et al 2022), while the certified accuracy is in terms of the isotropic $\\ell_p$ accuracy. At first, this claim sound rather unexpected to me, since ANCER is the anisotropic version of (Alfarra et al 2022)'s method. However, the paper uses the optimized variables of (Alfarra et al 2022)'s method as the ANCER initialization. Therefore, the better numerical performance is only a consequence of the suboptimality of (Alfarra et al 2022)'s method in finding the optimal isotropic radius, and it seems they do not imply that an anisotropic method could improve the maximal isotropic radius over the optimal isotropic method. This point needs to be discussed clearly in the paper, and the claim that an anisotropic method like ANCER improves the isotopic certified accuracy should be revised and moderated accordingly.\n\n5) I think the comparison vs. isotropic DD is to some extent unfair, since the current implementation initializes ANCER's optimization variables using the baseline isotropic DD's solution. What happens if ANCER's initialization becomes independent of the baseline method's solution, e.g. random or zero initialization? How much does the performance deteriorate as the initialization changes? \n\n6) As a comment on the writing style, the paper delays several key details to the Appendix. For example, the discussion in Appendix C, or at least a significant part of it should be moved back to the main text. Especially, a clean pseudocode version of the Python code in Listing 1 should be added to the main text. Currently, the main text does not have any algorithm descriptions, while ANCER is a new algorithm for computing anisotropic certification regions. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes ANCER as a robustness certification tool based on randomized smoothing through anisotropic noise. The approach is built upon existing randomized smoothing tools that use isotropic Gaussian and uniform noise to certify the prediction against $\\ell_2,\\ell_\\infty$ norm-bounded adversarial noise. The ANCER optimization problem is defined in Equation (1) and Appendix C suggests relaxing the optimization problem and applying projected gradient ascent to solve the task. Numerical results are presented in section 7, claiming that ANCER outperforms the fixed-variance smoothing and Isotropic DD baselines in terms of certified accuracy for CIFAR10 and ImageNet datasets.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "As already mentioned in my comments on the paper's weaknesses, the paper needs to be revised to address the followings:\n\n1) The introduction should better explain the motivation for an anisotropic certification region. What types of machine learning applications can use anisotropic certification regions?\n\n2) Equation (1) needs to be explained clearly. What is the mathematical definition of $r^p(x,\\Theta^x)$, and how can one compute the gradient of this function for solving the optimization problem? Also, an algorithmic block for ANCER needs to be added to Section 6.\n\n3) The numerical results in section 7 should be further clarified, and the paper needs to investigate the suboptimality of (Alfarra et al 2022)'s method in finding the maximal isotropic certification region. Also, ANCER's numerical results without the baseline-based initialization should be included for a fair comparison.", "broader_impact_concerns": "I have no specific ethical concerns regarding this submission. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NwnAOv4BNa", "reviewer": "Reviewer_MBuZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper is well-written and easy to follow. I found the idea of generalizing smoothed distribution to be anisotropic insightful and interesting.\n+ The paper presents extensive experiments to demonstrate the effectiveness of the proposed anisotropic certification methods. Compared with state-of-the-art, it achieves improved certified accuracy and a larger certified radius.\n+ The authors spent a decent amount of effort discussing the limitations of the proposed method (Section 6), allowing readers to clearly understand the trade-offs between improved performance and limitations on memory and computational costs.\n\nWeaknesses:\n- The proposed method is heavily based on the memory-based data-dependent certification approach (Alfarra et al, 2022). As the authors mentioned in Section 6, one limitation caused by this is that the overall certified statistics depend on ordering the test inputs. This raises the question of whether the presented comparisons with non-data-dependent approaches are fair. While the authors seem to propose a fix for this by showing “the worst-case results for AnCer in which we abstain from deciding whenever an intersection of two certified regions occurs”, it is still unclear to me how their inference phase is implemented and what the run time complexity of this phase is.\n\n- No standard deviation results are presented for the reported statistics (i.e., certified accuracy and certified radius). Given the probabilistic nature of randomized smoothing (i.e., sampling from the smoothed distribution) and the optimization procedure with respect to Equation (1), I am not confident in the consistency of the claimed improvement. This is particularly the case for l1-norm, as the l1-certified accuracies of ANCER and Isotropic DD are quite close to each other.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an anisotropic certification method for l1-norm and/or l2-norm by adapting (isotropic) randomized smoothing. It performs sample-wise region volume maximization, generalizing the data-dependent, memory-based solution from Alfarra et al. (2022). Experiments demonstrate that the proposed method achieves larger certified region compared with existing state-of-the-art isotropic certification methods.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I hope the authors provide more detailed discussions and more experiments on the effect of ordering test inputs on the certification results. In my perspective, the soundness of a certification method is of top priority. In the worst-case scenario, if an adversary is capable of varying the test input ordering, how much improvement of the proposed method can achieve. What about the average-case scenario? Clarifications on this will largely strengthen the work.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were satisfied with the author responses, and have reached a consensus that the paper meets the TMLR acceptance criteria. I therefore recommend accepting the paper.
Decision: Accept (poster)