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: ICLR 2022 Submitted (2022)
Keywords: randomized smoothing
anisotropic certification
deep neural network certification
certified defenses

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, while certifying larger regions in terms of volume, highlighting the benefits of moving away from isotropic analysis.

Under review as a conference paper at ICLR 2022
ANCER: ANISOTROPIC CERTIFICATION VIA SAMPLE- WISE VOLUME MAXIMIZATION
An Anonymous authors Paper under double-blind review
ABSTRACT
Randomized smoothing has recently emerged as an effective tool that enables certification of deep neural network classifiers at scale. All prior on randomized smoothing has focused on isotropic lp certification, which has the advantage of yielding certificates that can be easily compared among isotropic methods via f--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 & and & certificates 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 another if it certifies supersel 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-deeendent classifiers. Our empirical results demonstrate that ANCER achieves state-of-the-ard & 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.
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 et al., 2014). A recent promising approach to achieve state-of-the-arr provable robustness (i.e. a theoretical 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 and network f, randomized smoothing constructs g(x) = E [f + c)] such that g(x) g(x + 5) 4g E R. where the certification region R is characterized by x, f. and the smoothing distribution D. For instance, Cohen al. (2019) showed that if D N/00, o² I) then R is balball whose radius is determined by x, ff and σ. Since then, there has been significant progress towards the design of D leading the largest R. for all inputs x. The interplay between R characterized by 4, lg and balls, and a notion of optimal distribution 2 has been previously studied Yang et al. (2020).
Despite this progress, current randomized smoothing approaches provide certification regions that are isotropic 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 R in prior art is due the common assumption that the smoothing distribution D is identically distributed (Yang et al., 2020; Kumar et al., 2020; Levine & Feizi, 2021). Moreover, comparisons between various randomized smoothing approaches were limited to methods that produce the same ép certificate, with clear metrics for comparing with other certificates. In this paper, we address both concerns and present new oftt--of-theaare art certified accuracy results on both CIFAR-10 and ImageNet datasets.
Our contributions are threefold. (i) We provide 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 positive definite A, ellipsoids, i.e. |Aol2 c, and generalized pross-poyyoopes,

---

Under review as a conference paper at ICLR 2022
Anacctropic
Anastmppk: tectnapic
sctropt:
An actrapi:
Inctropi:
Inctrapi:
huctrozic
(a)
(h)
(c)
(d)
Figure 1: Illustaation of the landscape of f (blue corresponds to higher confidence in y, the true label) for a region around an input in toy, 2-dimensional radially separable dataset. For two dataset examples, in (a) and (b) we show the boundaries of the optimal l isotropic and anisotropic certificates, while (c) and (d) are the boundaries of the optimal l2 isotropic and anisotropic certificates. A thorough discussion of this figure is presented in Section 3.
i.e. ||A8|| S C, generalizing both &2 (Cohen et al., 2019) and 4 (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 R2 is superior to another certifying R2, if R2 is strict superset to R2. Further, we define standalone quantitative metric the volume of the certified region, and specialize it for the cases of ellipsoids and generalized pross-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. (2020). Through experiments on CIFAR- 10 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009), we show that restricting ANCER's 's certification region to ε and é-- balballs outperforms state-of-the tfttt---ttttet&tte f and f2 results from previous works (Yang et al., 2020; Alfarra et al., 2020). Further, we show that the volume of the certified regions are significantly larger than all existing methods, thus setting a new state-of-the-an in certified accuracy. We highlight that while we effectively achieve state-of-the- tftt--rr-t---tttt-- performance, it comes at high cost given the data- dependepy requirements. A discussion of the limitations of the solution is presented in Section 6.
Notation. We consider base classifier f R + P(K), where P(K) is a probability simplex over K classes, i.e. f 2 0 and f = for J. Further, we use (x, y) to be a sample input x 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 lp to be the typically defined l|p norm (p 2 1), and eo or IlA.p for [1,2] to be composite norm defined with respect to a positive definite matrix A as A AA1/PPllpp
2 RELATED WORK
Verified Defenses. Since the discovery that DNNs are vulnerable against input perturbations (Good- fellow 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 (Tjeng et al., 2019; Weng et al., 2018).
Randomized Smoothing. The first works on randomized smoothing used Laplacian (Lecuyer et al., 2019; Li et al., 2019) and Gaussian Cohen et al. (2019) distributions to obtain & and ball certificates, respectively. Several subsequent works improved the performance of smooth classifiers by training the base classifier using adversarial augmentation (Salman et al., 2019a), regularization (Zhai et al., 2019), or general adjustments to training routines (Jeong & Shin, 2020). Recent work derived & -o-m certificates for other isotropic smoothing distributions (Yang et al., 2020; Levine & Feizi, 2020; Zhang et al., 2019). Concurrently, Dvijotham et al. (2020) developed a framework to handle arbitrary smoothing measures in any f,-norm; however, the certification process requires significant hyperparameter tuning. Similarly, Mohapatra et al. (2020) introduces larger certificates that require oidder-order information, yet do not provide closed-fome solution. This was followed by a complementary Mata-dependen smoothing approach, where the parameters of the smoothing distribution were optimized per test set sample maximize the certified radius at individual
2

---

Under review as a conference paper at ICLR 2022
imput (Alfarra et al., 2020). All prior works considered smoothing with isotropic distributions and hence certified isotropic e--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 et al., 2020) 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()) = arg max; f' + 5) vo E R. Recent randomized smoothing techniques perform this certification by explicitly optimizing the isotropic lp certified region around each input (Alfarra et al., 2020), obtaining state-of- the-art performance worst-case from the perspective of that norm, as it avoids adversary regions by limiting its certificate to the ep-closest adversary. This means that it can only enjoy a radius that is most equal to the distance to the closest decision boundary. However, decision boundaries of general classifiers are complex, non-linean and non-radially distributed with respect to a generic input sample (Karimi et al., 2019). This is evidenced by the fact that, within a reasonably small Ep-ball around an input, there are often only a small set of adversary directions (Tramèr al., 2017: 2018) (e.g. see the decision boundaries in Figure 1). As such, while Ep np-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.
result. Despite this l optimality, we note that any f--norm certificate is
To visualize these concepts, illustrate the decision boundaries of base classifier f trained toy 2-dimensional, radially separable (with respect to the origin) binary classification dataset, and consider two different input test samples (see Figure 1). We compare the optimal isotropic and anisotropic certified regions of different shapes at these points. In Figures 1a and 1b, we compare an isotropic cross-polytope (of the form [|ō][ S r) with anisotropic generalized cross- cross-polyton polytope (of the form || < r), while in Figures Ic and ld we compare an isotropic lz ball (of the form ||ö]|2 S r) with an anisotropic ellipsoid (of the form ||A8||2 r). Notice that in Figures 1a and Ic, due to the curvature of the classification boundary (shown in white), the optimal certification region isotropic nature, which is evidenced by the similarities of the optimal isotropic and anisotropic certificates. On the other hand, in Figures 1 and I,, the location of the decision boundary allows for the anisotropic certified regions to considerably larger than their isotropic counterparts, as they are not as constrained by the closest decision boundary, i.e. the worsf-case performance. We note that these differences are further highlighted in higher dimensions, and we study them for a single CIFAR-10 10 test set sample in Appendix A. Further, we also showcase how anisotropic certification allows for further insights into constant prediction (safe) directions in Appendix A.2.
4 ANISOTROPIC CERTIFICATION
One of the main obstacles in enabling anisotropic certification is the complexity of the analysis required. To alleviate this, we follow 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 in Appendix B.
Proposition 1. Consider differentiable function IR" + R. (l S L where || . -1.. has a dual norm ||>||| = max, = x s.f. ||-]| & 1, then is L-Lipschitz under norm ||. ||,,, that is 19(x)) .(v)l < L||0 yll-
Given the previous proposition, we formalize ||- certification as follows:
Theorem 1. Let g T - RRKK g² be L--lipschitz continuous under norm 11- Vi E (1....,K) K). and CΛ arg max; gf (z). Then, we have arg max, (x + 5) CA for all 8 satisfying:
1
||l|| < 2L ax)
max g ofen (x))
Theorem provides || norm robustness certificate for any L-Lipschitz classifier g under || ||.. The certificate only informative when one can attain a tight non-trivial estimate of L, ideally sup,, [Vg<)) which is generally difficult when g is arbitrary neural network.
3

---

Under review as a conference paper at ICLR 2022
Framework Recipe. In light of Theorem 1, randomized smoothing can be viewed differently an instance of Theorem with the favorable property that the constructed smooth classifier enjoys an analytical form for L sup,. g2)2))l by design. As such, to obtain informative || certificate, one must, for an arbitrary choice of a smoothing distribution, compute the analytic Lipschitz constant L under || ||. for the smooth g. While there can exist notion of "optimal" smoothing distribution for a given choice of || certificate, as in part addressed earlier for the isotropic f1, l2 and &oo 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 Neyman- Peannon lemma (Cohen et al., 2019) or the Level-Set and Differential Method (Yang et al., 2020).
We will deploy this framework recipe show two specializations for anisotropic certification, namely ellipsoids (Section 4.1) and generalized cross-polytopes (Section 4.2).'.
4.1 CERTIFYING ELLIPSOIDS
In this section, we consider the certification under E norm, or |0]| V-T that has a dual norm [|6||x--12 2- Note that both ||0]| I r and || I r define an ellipsoid. Despite that the following results hold for any positive definite Σ, we assume for efficiency reasons that Σ is diagonal throughout. First, we consider the anisotropic Gaussian smoothing distribution (O, Σ) with the smooth classifier defined as 9=(xr) = Be~N((,E)) [f (x + c)). Considering the classifier 4- (gx(2)) where T is the standard Gaussian CDF, and following Theorem
grant Ey certificate for (gx (x)), we derive the Lipschitz constant under ||x.-,,2, in the following proposition.
Proposition 2. 4 (gg(x)) is L-Lipschitz (i.e. L 1) under the ||x-,,, norm.
Since + 1 is strictly increasing function, by combining Proposition 2 with Theorem 1, we have: Corollary 1. Let Ca arg max, (x). then arg max, (x + 6) for all ō satisfying:
| 2 S 2 ( (
CGft (x))
--1 max gs. ofC (x))
Corollary holds the & certification from Zhai et al. (2019) as a special case for when Σ = 021.2
4.2 CERTIFYING GENERALIZED CROSS- POLYTPPS
Here we consider certification under the e norm defining a generalized cross-polytope, iee. the set {8 | ||A- < r), opposed to the fi-bounded set that defines a cross-polytope. iee. (6: : |8|1 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 U4 which defines the smooth classifier (z) E-- [f (x + Ac)]. Following Theorem I and to certify under the A norm, we compute the Lipschitz constant of ga under the ||Az]| norm, which the dual norm of Ila.1 (see Appendix B), in the next proposition.
Proposition 3. The classifier gA is 1/2-Lipschitz (i.e. L 1/2) under the ||Ax]|oo 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, g (x + 8) = for all satisfying:
|| ||A -811 (9 max gΛ (x))
Corollary 2 holds the & certification from Yang et al. (2020) as special case for when A = AI.
1 Our analysis also grants certificate mixture Gaussians smoothing distribution (see Appendix B. A similar result was derived in the appendix of Fischer et al. (2020); Li et al. (2020) with more involved analysis by extending Neyman- Pearson's lemma.
4

---

Under review as a conference paper at ICLR 2022
5 EVALUATING ANISOTROPIC CERTIFICATES
With the anisotropic certification framework presented in the previous section, the question arises: "Given two general (isotropic or anisotropic) certification regions R. and R2, how can one effectively compare them?". We propose the following definition to address this issue.
Definition 1. For a given inpul point I, consider the Iwo certification regions R1 and R22 obtained for two classifiers fi and fz. i.e. A = {Ō arg max, ff) arg max, ff(r + 6), Vō E R1}
and A2 {ō : arg max. f2(x) arg max, fi + 8), v8 R2} where arg max, fi (z) arg max, (z). We say A1 is a "superior certificate" to A (i.e. A1 A2), if and only if. A C Az.
This definition is a natural extension from the radius-based comparison of Cp-ball certificates, provid- ing 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 is a superset to the isotropic region, and (ii) if were superset, how 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.
5.1 EVALUATING ELLIPSOID CERTIFICATES
Comparing & Balls to e Ellipsoids (Specialization of Definition 1). Recall that if = I²I, ellipsoid certification in Corollary recovers as special case the isotropic balball certification of Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019). Consider the certified regions RR = {5 ||ō]|2 S 3r1} and R2 = {ō || x,2 = VōTΣ-15 S r2) for given 71, r2 > 0. Since we take Σ diag(1 biag((o?))) }²]]))) ) the maximum enclosed b-lball for the ellipsoid R₂ is given by the R3 (6 ||0||2 S min; 3, and thus R2 Rg. Therefore, it suffices that R3 Ri (i.e.
min; r2 1r1), to say that Rg is superior certificate to the isotropic R₁ as per Definition 1.
Quantifying E Certificates. The aforementioned specialization is only concerned with whether our ellipsoid certified region R2 is "superior" to the isotropic E2-ball without quantifying it. natural solution is to directly compare the volumes of the certified regions. Since the volume of an ellipsoid given by R2 is (RR2 = r V/ /T(-/+++) I of (Kendall, 2004), we directly compare the proxy radius R defined for R2 as R T2 VII og 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 as a generalization to the certified radius the case when 0; = a Vi.
5.2 EVALUATING GENERALIZED CROSS-POLYTOPE CERTIFICATES
Comparing Balls to e/ e Generalized Cross Cross-Polytopes (Specialization of Definition 1). Consider the certificates S = {ō ||ō|| < År... : S2 {ō | = ||A-1 S r2). and (0: ||6|| S min; Air2], where we take A = diag( { ) Note that since S2 2 Sg. then as per Definition 1, it suffices that S3 2 S, (iee. min; Xrro 2 Ar,) to say that the anisotropic generalized
cross-polytope S2 superior to the isotropic l St.
Quantifying e Certificates. Following the approach proposed in the Eye case, we quantitatively compare the generalized cross-polytope certification of Corollary 2 to the & certificate through the volumes the two regions. We first present the volume of the generalized cross-polytope.
Proposition 4. V ((5: ||A-16|| -11 S r])
[2r]" II, A4.
Following this definition, we define the proxy radius for S2 in this case to be π = r2 VIl dr. As with the & case, larger Ai correspond certified regions with larger volumes. As in the ellipsoid case, R can be seen generalization the certified radius when X; = X Vi.
5

---

Under review as a conference paper at ICLR 2022
6 ANCER: SAMPLE-WISE VOLUME MAXIMIZATION FOR ANISOTROPIC CERTIFICATION
Given the results from the previous sections, particular ellipsoids and generalized cross- proyytoooy As mentioned in Section 4, these regions are generally defined R {ō : [,6|le.p e.p I r²) for given parameter of the smoothing distribution @ = diag ((0)]==) ) an - ---norm (p E (1,2)), and a gap value of r2 E R At this point, one could simply take an anisotropic distribution with arbitrarily chosen parameters O and certify trained network at any input point æ, in the style of what was done in the previous randomized smoothing literature with isotropic distributions. However, the choice of θ is more complex in the anisotropic case. A fixed choice of anisotropic θ could severely underperform the isotropic case take, for example, the anisotropic distribution of Figure ld applied the input of Figure 1c.
now equipped to certify anisotropic regions, in
Instead of taking a fixed θ we generalize the framework introduced in Alfarra et al. (2020), where parameters of the smoothing distribution are optimized per input test point (i.e. in sample-wise fashion) so as to maximize the resulting certificate. The goal of the optimization in Alfarra et al. (2020) is, at a point z, to maximize the isotropic lg region described in Section 4.1 (i.e. {ō: [88|2 I " of }),, where r is the gap and a function of x and ot E ERt.
. In the isotropic lp case, this generalizes to maximizing the region {ō ||6|pp S r (1r, )²)), which can be achieved by maximizing radius 0"''" (z. 0%) through 0 E R obtaining riso (Alfarra et al., 2020).
For the general anisotropic case, we propose ANCER, whose objective is to maximize the volume of the certified region through the proxy radius, while satisfying the superser condition with respect to the maximum isotropic &g radius, riso In the case of the ellipsoids and generalized cross-poly cross-polytopes as presented in Sections 5.1 and 5.2, respectively, ANCER's optimization problem be written as:
arg max rp 0%) 6
III OF
s.t. min r (x, θt) 2 ris
where rd (z, θz) is the gap value under the anisotropic smoothing distribution. We iteratively solve a relaxed version of Equation (1), with further details presented in Appendix C.
Memory-based Anisotropic Certification. While each of the classifiers induced by the parameter O i.e. ge-. is robust by definition as presented in Section 4, the certification of the overall data- dependent classifier is not necessarily sound due to the optimization procedure for each x. This is known issue in certifying data-dependent classifiers, and is addressed by Alfarra et al. (2020) through the use of a memory-baser procedure. In Appendix D, we present an 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 Alfara et al. (2020), it incurs limitations on memory and runtime complexity. The main limitations of the memory-basee certification are outlined in Appendix E of Alfarra et al. (2020). The anisotropic case increases the complexity of the isotropic framework by the increased runtime of specific functions presented in Appendix D. Certification runtime comparisons are in Section 7.3.
Further, note that in memory-based data-dependent certification there is single procedure for both certification and inference in contrast with the fixed a setting from Cohen et al. (2019). While the linear runtime dependency on memory size might appear daunting for the deployment of such system, there are a 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- cost-certification stage, 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 offline scenarios, where improved robustness is desired and inference time 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 statistics obtained. Within a memory-based framework, certifying T2 with Ii in memory can be different from certifying Ii 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 faimess of comparison with non- memmorrr based methods, we report "worst-case" results for ANCER in which we abstain from deciding whenever an intersection of two certified regions occurs.

---

Under review as a conference paper at ICLR 2022
CIFAR-10 Cahen
CFAR-11 Smoothilly
CIAAR-O MAGER
Iraagehiet- Cahen
Imaeghhat: -mmott Ady
Fiod Io
Reee Inteae
Fiod
Fone beaop
Inavor n0
04
3
0.5
Food Co
hiee butkep DO
Foodd ho
Food buttopr 30
butiape DO ANCEH
ANCEN
12 prory volans
4 pror volum
prop radia
prayy rudus
Figure 2: Distribution of top-1 I certified accuracy as a function of le radius (top) and fy -nomm proxy radius (bottom) obtained by different certification methods on CIFAR-10 and ImageNet.
EXPERIMENTS
We now study the empirical performance of ANCER to obtain Ez. e/. Ez and E certificates on networks 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 lz and l certification when compared to certification baselines that smooth using fixed isotropic o (Fixed σ) (Cohen et al., 2019; Yang et al., 2020; Salman et al., 2019a; Zhai et al., 2019) or data-dependent and memory-based isotropic one (Isotropic DD) (Alfarra et al., 2020); and (ii) a significant improvement in terms of the &g and ff-norm certified region obtained by the same methods - compared by computing the proxy 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 a trade-off given the limitations of the method described in Section 6.
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 et al., 2009), certifying the entire CIFAR-10 test set and subset of 500 examples from the ImageNet test set. For the implementation of ANCER, we solve Equation (1) with Adam for 100 iterations, where the certification gap r r3 +²) is estimated at each iteration using 100 noise samples per test point (see Appendix C) and @ in Equation (1) is initialized with the Isorroicc DD solution from Alfarra et al. (2020). Further details of the setup can be found in Appendix E.
As in previous works, Ep 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 e5 certified accuracy at proxy radius of R (as defined in Section 5) to be the portion of D, in which the smooth classifier classifies correctly with an ee norm certificate of an n root volume of at least R. We also report average certified radius (ACR) defined as Fz,gy,, [R, 1 (g(x)) = v)] (Alfarra et al., 2020; Zhai et al., 2019) as well as average certified proxy radius (ACR) defined as Eg,yy>,, [R₂ (g(()) = y)]. where R2 and R₂ denote the radius and proxy radius at x with a true label y for smooth classifier g. Recall that in the isotropic case, the proxy radius is, by definition, the same as the radius for a given fy-norm. For each classifier, we ran experiments on the 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 1 certified accuracy plots, ACR and ACR per radius across a, as in Salman et al. (2019a); Zhai et al. (2019); Alfarra et al. (2020). The performance of each method per is presented in Appendix G.
7.1 ELLIPSOID CERTIFICATION (62 AND & -NORM CERTIFICATES)
We perform the comparison of Ey- ball vs. Ey -elipssoid certificates via Gaussian smoothing using net- works trained following the procedures defined in Cohen et al. (2019), Salman et al. (2019a), and Zhai et al. (2019). For each of these, we report results on ResNet18 trained using a 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
7

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison of top-1 certified accuracy at different & radii, l average certified radius (ACR) and Eh average certified proxy radius (ACR) obtained by using the isotropic used for training the networks (Fixed σ); the isotropic data-depent dependent (Isotropic DD) optimization scheme from Alfarra et al. (2020); and ANCER's data-dependent anisotropic optimization.
Accuracy @ & radius (%)
CIFAR-10
Certification
E2 ACR
& ACR
0.0
0.25
0.5
1.0
1.5
2.0
2.5
Fixed a
86
71
51
27
2
0.722
0.722
COHEN Cohen et al. (2019)
Isotropic DD
82
76
62
39
24
14
1.117
1.117
ANCER
86
855
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 Ø
87
76
59
37
24
14
9
0.970
0.970
MACER Zhai (2019)
Isotropic DD
88
80
66
40
17
9
6
1.007
1.007
ANCER
84
80
67
34
15
11
1.136
1.481
Accuracy @ E radius (%)
ImageNet
Certification
I2 ACR
E AC'
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Fixed
70
56
41
31
19
14
12
1.098
1.098
COHEN Cohen et al. (2019)
Isotropic DD
71
59
46
36
24
19
15
1.234
1.234
ANCER
70
70
62
42
36
29
1.810
1.981
Fixed a
65
59
38
26
20
1.287
1.287
SMOOTHADY 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
procedures, see Appendix E. Figure 2 plots top-1 certified accuracy as function of the & radius (top) and of the -nomm proxy radius (bottom) per trained network and dataset, while Table 1 presents an overview of the certified accuracy at various & radii, as well as lg ACR and & -nom ACR. Recall that, following the considerations in Section 5.1, the & certificate obtained through ANCER is the maximum enclosed isotropic b--ball in the Ey ellipsoid.
First, we note that sample-war wise certification (Isotropic DD and ANCEr) achieves higher certified accuracy than fixed across the board. This mirrors the findings in Alfarra al. (2020), since certi- fying with a fixed a for all samples struggles with the robustness/accuracy trade-off first mentioned in Cohen al. (2019), whereas the data-dependent solutions explicitly optimize per sample to avoid it. More importantly, ANCER achieves new state-of-the-a & certified accuracy at most radii in Table 1, e.g. at radius 0.5 ANCER brings certified accuracy 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 larger maximum enclosed ball certificate in &y ellipsoid when compared optimizing the balball with Isotropic DD. We explore this phenomenon in Appendix G.3.
As expected, ANCER substantially improves E ACR compared to Isotropic DD in all cases with relative improvements in ACR between 38% and 63% over both datasets. The joint results, certification with lg and Ey establish that ANCER certifies the b region obtained by previous approaches, addition to a much larger region captured by the ty certified accuracy and AC R, and therefore is, according Definition generally superior to the Isotropic DD one.
7.2 GENERALIZED
CERTIFICATION (&1 AND E -NORM CERTIFICATES)
To investigate -all eA Ee-generalized cross-polytope certification via Uniform smooth- ing, 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 (WideResNer40) and Ima- geNet (ResNet50) and due to limited computational resources, we perform the analysis on subset of those networks with = (0.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 E.2.
8

---

Under review as a conference paper at ICLR 2022
Table 2: Comparison of top-1 certified accuracy at different & radii, & average certified radius (ACR) and & average certified proxy radius (ACR) obtained by using the isotropic used for training the networks (Fixed σ); the isotropic cuta-dependen (Isotropic DD) optimization scheme from Alfarra et al. (2020); and ANCER's 's data-dependent anisotropic optimization.
Accuracy @ & radius (%)
CIEAR-10
Certification
&1 ACR
E ACR
0.0
0.25
0.5
0.75
1.0
1.5
2.0
Fixed
92
83
71
46
0
0.775
0.775
RS4A Yang et al. (2020)
Isotropic DD
92
89
76
58
2
0.946
0.946
ANCER
92
90
84
80
63
2
0.980
1.104
ImageNet
Fixed
78
73
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
Figure shows the top-1 certified accuracy as a function of the & radius (top) and of the -ormo proxy radius (bottom) for RS4A, and Table 2 shows an overview of the certified accuracy at various l radii, as well as l ACR and E ACR.
DIBAR-10 RB4A
Imagehet RS4A
Flosd
Iurraiic DD
Fass ANCED
0.3
0.5
1.0
1.5
20
0.90
0.25
0,00
1.90
As with the ellipsoid case, we notice that ANCER out- performs both Fixed a and Istropic DD for most & radii, establishing new state-of-the-art art results in CIFAR-10 at radii 0.5 and 1.0, and ImageNet radii 0.5 (compared to previous results reported in Yang et al. (2020)). Once more and as expected, ANCER significantly improves the A ACR for all radii, pointing to substantially larger cerfi- cates than the isotropic case. These results also establish that ANCER certifies the b-alll region obtained by previ- work, in addition to the larger region obtained by the E certificate, and thus we can consider it superior (with respect to Definition 1) to Isotropic DD.
Fladt
Food 1o
kuraii Dhh
procy
Figure 3: Distribution of top-1 certified accuracy as a function of & radius (top) and e -nomm proxy radius (bottom) ob- tained by different certification methods on CIFAR-10 and ImageNet.
7.3 CERTIFICATION RUNTIME
Table 3:
Average certification time for each sample per architecture used: (a) ResNet18 (f2, E on CIFAR-10), (b) WedeResNet40 (41, es on CIFAR-10), and (c) ResNet50 (ImageNet).
The certification procedures of Isotropic DD and ANCER tradeoff 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-based step per Alfarra et al. (2020). The runtime of the optimization and certification procedures is roughly equal for f,, l2, fy and l certification, and mostly depends on network architecture. As such, we report the average certification runtime for test set sample on an NVIDIA Quadro RTX 6000 GPU for Fixed a,, Isotropic DD and ANCER (including the isotropic initialization step) in Table 3. We observe that the overall run time overhead for ANCER is not significant as compared to its certification gains.
Fixed
Isotropic DD
ANCER
(a)
1.6s
1.8s
2.7s
(b)
7.4s
9.5s
11.5s
(c)
109.5s
136.0s
147.0s
8 CONCLUSION
In this work, 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 the parameters of the anisotropic smoothing distribution to maximize the certificate. Our experiments show that ANCER achieves state-of- thf-thh-rt l and & certified accuracy on CIFAR-10 and ImageNet. Our anisotropic analysis enables further insights about the boundary of the safe region around input sample, as compared to its isotropic counterpart.

---

Under review as a conference paper at ICLR 2022
9 REPRODUCIBILITY STATEMENT
We provide complete proofs for each of the theoretical results presented in Section 4 in Appendix B. Details on the practical implementation of the ANCER optimization algorithm presented in Appendix C, while the memory- based procedure is detailed in Appendix D. An overview of the experimental setup used to obtain the results in Section 7 can be found at the top of that section, while details on the hyperparameters and network training are presented in Appendix E. We include source code Python and instructions to reproduce our results as part of the supplementary material.
10 ETHICS STATEMENT
We confirm that no results in this paper involved studies on human subjects, and all experiments used open-source datasets.
REFERENCES
Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem. Data dependent randomized smoothing. arXiv preprint arXiv:2012.0433.. 2020. 2, 6, 7, 8, 9, 13, 17, 18, 19, 23, 25
Rudy Bunel, llker Turkaslan, Philip HS Torr, Pushmeet Kohli, and Pawan Kumar. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICML), 2019. 1, 2, 3, 4, 5, 6, 7, 9. 23, 24
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009, 1, 22
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 Learning Reprexentations (ICLR), 2020. 2
Mare Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transformations via randomized smoothing. Advances in Neural Information Processing Systems (NeurIPS), 2020.
4
Igor Gilitschenski and Uwe Hanebeck. robust computational test for overlap of two arbitrary- dimensional ellipsoids in fault-detection of kalman filters. In 2012 15th International Conference on Information Fusion, 2012. 19, 20
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015. 1,2
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.
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. 22
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference on Computer Aided Verification (CAV), 2017.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. In Advances in Neural Information Processing Systems (NeurIPS). 2020. 2
10

---

Under review as a conference paper at ICLR 2022
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 3
Hamid Karimi, Tyler Derr, and Jiliang Tang. Characterizing the decision boundary of deep neural networks. arXiv preprint 1ef.:1991..116600 2019.
Maurice G Kendall. A Course in the Geometry of Dimensions. Courier Corporation, 2004. 5, 15
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. 2, 7, 13, 22
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. 1
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy (SP), 2019. 1,2
Guang- He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. arXiv preprint arXiv: 190,04490,,4448, 2019. 3
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by ran- domized ablation. In Association for the Advancement of Artificial Intelligence (AAAI), 2020.
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for certified robustness. arXiv preprint Stt::22003.108344 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.
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Tao Xie, Ce Zhang, and Bo Li. Provable robust learning based on transformation-speeife smoothing. arXiv preprint arXiv:2002. /23998 2020. 4
Jeet Mohapatra, Ching- Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. Advances in Neural Information Processing Systems (NeurIPS), 2020. 2, 27, 28
Seyed-Mohsen Moosavi -ezzooll,,,,, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- via curvature regularization, and vice versa. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2019. 13
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 Detito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS). 2019. 18, 23
Lluís 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. 19, 20
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems (NeurIPS), 2019a. 2, 3, 5, 7, 8, 14, 23, 24, 27, 29
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification of neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 2019b. 2
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations (ICI.), 2014. 1,
11

---

Under review as a conference paper at ICLR 2022
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations (ICLR), 2019.
Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint (rXXiv:704.034555 2017. 3
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations (ICLR), 2018.
Tsui-Was Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks, In International Conference on Machine Learning (ICML), 2018.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning (ICML), 2020. 1, 2, 3, 4, 7, 8, 9, 23, 28
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations (ICLR), 2019. 2, 4. 5, 7, 8, 23, 24
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: //openrevis ew net net.torum? forum? d= 2019. 2
12

---

Under review as a conference paper at ICLR 2022
A QUALITATIVE MOTIVATION OF ANISOTROPIC CERTIRICATION
A.1 VISUALIZING CIFAR-10 OPTIMIZED ISOTROPIC vs. ANISOTROPIC CERTIFICATES
To extend the illustration in Figure 1 to higher dimensional input, we now analyze an exam- ple of the isotropic & certification of random- ized smoothing with N (0, I),, where is op- timized per imput Alfarra et al. (2020), against ANCER, certifying an anisotropic region char- acterized by a diagonal Ez norm. To do so, we consider CIFAR-IO Krizhevsky (2009) dataset point x, where the input is of size (32x32x3). We perform the 2D analysis by considering the regions closest to a decision boundary. To do so, and following Moosavi- -oossvi-Dezzoooli et al. (2019), we compute the Hessian of (z) with respect to x where y is the true label for with / clas- sifying correctly, i.e. = arg max; (z). In addition to the Hessian, we also compute eigenvector decomposition, yielding the eigen- vectors { (1...., 3072) ordered in de- scending order of the absolute value of the re- spective eigenvalues. In Figure 4a, we show the projection of the landscape of S in the highest curvature directions, i.e. ii and v2. Note that the isotropic certification, much as in Figure Ie, in these 2 dimensions is nearly optimal when compared to the anisotropic region. However, if we take the same projection with respect the eigenvectors with the lowest and highest eigenvalues, i.e. 111 and 13072, the advantages of the anisotropic certification become clear shown in Figure 4b.
Ansempp batrosic
Asiempp Isotroic
m
(a)
(b)
Figure 4: Illustration of the landscape of f for points around an input point and two pro- jections of an isotropic & certified region and an anisotropic 2- region dataset example to a subset of two eigenvectors of the Hessian of f" (blue regions correspond higher confidence in y).
CIFAR-10
A.2 VISUALIZING SAFE IMAGES OPTIMIZED ANISOTROPIC CERTIFICATES
Figure 5: Visualization of a CIFAR-10 image and an example + 5 of an imperceptible change that is not inside the optimal isotropic certified region, but is covered by the anisotropic certificate.
As observed from the examples in Section 3 and Appendix A.1, anisotropic certification reasons more closely about the shape of the decision boundaries. allowing for further insights into constant prediction (safe) directions. In Figure 5, we present series of test set images xr well as practically indistinguishable x + 5 images which are not inside the optimal certified isotropic falballs for each input sample, yet are within the anisotropic certified regions. This showcases the merits of using anisotropic certification for characterizing larger safe regions.
B ANISOTROPIC CERTIFICATION AND EVALUATION PROOFS
Proposition 1 (restatement). Consider a differentiable,furaae g RR + R. If sup, VV((2) < L where || |]. has a dual norm ||æ||| max, 2T x s.t. || I 1, then g is L-Lipschitz under norm
|| Il., that is (g(x) g(v)l El|e yll-
13

---

Under review as a conference paper at ICLR 2022
Proof. Consider some z; y I² and parameterization in 7(t) (1 t)x + ty Vt [0, 1].
Note that 7(0) = x and 7(1) = y. By the Fundamental Theorem of Calculus we have:
L." dg(r(t)) dt
% Vg Vydt
/ V>>V> dt
(g(v) ]x)] = (1() 9(>(0)))
dt
- ! [Vg(z)
L - x||
Theorem 1 (restatement). Let g R RKK 96 be I-Lipschitz continuous under norm |- Vi E (l,...,K K}. and сΛ = arg max; (x).. Then, we have arg max; 9 + 6) ca for all satisfying:
1 |+|| S 2T. (xx - max g tee (x))
Proof. Take cg = arg max, * By Proposition 1, we get:
l (x - 6) 9x)] < L|| = (x 2 (x) - |
Ig (x + (x (<) - L|,5|| = gx S gd + I. |
By subtracting the inequalities and re-arranging terms, we have that as long as go - L. > (x) + L|] ie. the bound in the Theorem, then gea + 6) > ge + 8), completing the proof.
Proposition 2 (restatement). Consider gn((x) Beo (s e)}. (gx((())) is 1-Lipschitz (i.e. L- 1) under the || 1,2 norm.
Proof. To prove Proposition one needs to show that + (g)((1)) Vi is I-Lipschitz under the || l> 1,2 norm. For ease of notation, we drop the superscript 9'. and use only g. We want to 1. Following the argument presented in Salman et al. (2019a), it suffices to show that, for any unit norm direction u and p = (2(x), we have:
show that (gz- (x))]xx== = (gyx)))
u TVtVa=( S 2t
1 (-2(0-1)))
exp
(2)
We start by noticing that:
u (
/
f(1)u Tr x)) exp exp (- (x 1) (x 1) d
1
(V2m)² VI Rm
(E,N((, [f + s) = EEn + v)u Σ buj.
We now need to find the optimal f 12n + [0, 1] that satisfies gz(x) E [f + v)] =p
while maximizing the left hand size E.- [z + v)u Σ ro). We argue that the maximizer is the following function:
(" { I (0)
To prove that f is indeed the optimal maximizer, we first show fcasibility. (i): is clear that f" IR" + [0, 1). (ii) Note that:
E ( [ [1( T 2e - (w) P. Pan (x x (p)) = -1- = p.
To show the optimality of fe, we show that it attains the right upper bound:
Eu-N(0 u T E à vl { E 2 क - = Ez-N1O.1)
r1l {o - -
1 (-1²²) dr
=
xexp
V2T (
- (
1
25 exp
obtaining the bound from Equation (2), and thus completing the proof.
14

---

Under review as a conference paper at ICLR 2022
Proposition 3 (restatement), Consider ga(x) = 11,, + Ac)]. The classifier gk Vi is 1/2-Lipschizz (i.e. I, = 1/2) under the || norm.
Proof. We begin by observing that the dual norm of | || - is ||]|| ||Ac since:
max I'y 1el S1
max 11
As ||ylloc.
a|
Without loss of generality, we analyze 0g /an.. Let i [x2,.... [n] E R then:
\ggg
(2X)a dr 1-1,1]--1 [ fl + 21 2 + Ac)dead"
A1
a
dz1
1
(f 1, Ae) f( 1, + Ae))d
2n
|-1.1]"
Thus,
A Og Or
/ [-11]1
Man + +1, Aσ) - f2( 1, x + Aε) d 1 2
2 1T,==2
The second and last steps follow by the change of variable = 21 + 116 and Leibniz rule. Following symmetric argument, 2,000/0z, S 1/2 Vi resulting in having || V (z)] max; X |006 /am. 1/2 vi concluding the proof.
Proposition 4 (restatement). V ((0: | S 5r))
(2r) = ml II, Aj.
Proof. Take A = rA diag( 3/r2.) diag (a,
We can re-write the region as fxr E; |r| < 1). from which it is clear to see that this region is an origin centered, axis-aligned simplex with the of vertices (= where e, the standard basis vector i.
Define the sets of vertices V V (-)/a,, and yo = v (//.,x)) Given the symmetry around the origin, each of these sets defines n-dimensional hyperpyramid with a shared base B,-1 given by the 1-dimensional hyperplane defined by all vertices where zn 0, and an apex at the vertex 1/a.c,, (or -1/a,.,, in the case of V*) The volume of each of these n - 1- dimensional hyperpyramids is given by V(Bn-1)fna, (Kendall (2004)), yielding total volume of V, -1). The same argument can be applied to compute ) y(Bn-1) which is union of two n 1-dimensional hyperpyramids. This forms recursion that completes the proof.
L
Proof. (Alternative Proof.) We consider the case that A-1 is general positive definite matrix that is not necessarily diagonal. Note that V ({5: ||A - < <}) = ((ő: [I(AA)-18]] S 1})
r"I [MA (15 ||ó]] < 1)) where |rA] denotes the determinant. The last equality follows by the volume of set under a linear map and noting that {8 [|(rA)] - 1
{rAo ||ō]] r). At last, {5 : [|8]] & 1} can be expressed as the disjoint union of 2 simplexes. Thus, we have
V ({6 : | I r}) /nt/ since the volume of a simplex 1/nl completing the proof. O
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 |nxnn we have the following:
2r
v (Z(A)) S /0 ||~ | sr)) < (Z(A)
where (2(A)) / [ATA| which is the volume of the zonotope with generator matrix A.
15

---

Under review as a conference paper at ICLR 2022
Proof. Let S1 {8 |A~ Sr.. = f6:
0|10c ||A-
r) and 5 = 1 I
r}. Since ||A ||-16 6llec < 811 $
2 S Therefore, we have v(Sx) 2 V(S)) V(S%). last note that, S (5A6 ||0|| S 1] and that with the change of variables 6 2u In where I is a vector of all ones, we have S
then Sx 2 S
2 - where is
Minkowski sum and noting that AA is single point R". Therefore,
2 = A = { -
(2*/n)" (V The upper bound follows with a similar argument completing the proof.
B.1 CERTIFICATION UNDER GAUSSIAN MIXTURE SMOOTHING DISTRIBUTION
We consider a general, K-component, zero-mean Gaussian mixture smoothing distribution such that:
K
G(ta,, )i
a,N(0,
s.t. Σa= = 1,0 3
Given f and as per the recipe described in Section 4, we are interested in the Lipschitz constant of the smooth classifier (x)x)= (f * (x) Σx agge, >x ai(s (0 2.)) E. o:gr, (4)
where gm, 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. gE / under ||-||=-1.2 norm.
Proof. Following similar argument to the proof of Proposition 2, we get:
exp (-) 1
u TEA (gx(t) & (2 [Σ] 12" |u I 1 - x¹) exp
1x - dr
= =Ep-N(10D)
[lu" T s|] = (Bm.)o, = 22/x.
With Proposition 6, we obtain Lipschitz constant for Gaussian mixture smoothing distribution as:
Proposition 7. gg is ///2-iipshhitz under [|0]| norm, where B Σx o
Proof.
l0 + +8))+8000 -gg(x)) S Σ as (x (x 92. (x)
S Σ 0oll/||be, S
8T Σ Ea.
8
Obtained by first applying the triangle inequality, then Proposition followed by Jensen's 's inequality.
Thus yielding the following certificate by combining Proposition 7 and Theorem 1. Corollary 3. Let CA arg max, go (x). then arg max, d' (x 5) CA CA for all 8 satisfying:
||1|8.22 S
1
666 (x) max 96 cfc (x)
22
where B- EK 5-1
16

---

Under review as a conference paper at ICLR 2022
C ANCER OPTIMIZATION
In this section we detail the implementation choices required to solving Equation (1). For ease of presentation, restate the ANCER optimization problem (with O diag (0f) ) )==1)):
arg pp (ar, Ot) 6"
II OH
min 0. (2r, θ²)) 2 1s0
where r" (z, θ") is the gap value under the anisotropic smoothing distribution, and r is the optimal isotropic radius, i.c. ("r 0*) for lt RR. This is a nonlinear constrained optimization problem that is challenging to solve. As such, relax and solve instead:
arg max r (I, 6=
II Og Kamin 0 0*)
2 0z
given a hyperparameter Rt. While the constraint 0 frr is not explicitly required enforce the superser condition over the isotropic case, proved itself beneficial from an empirical perspective. To sample from the distribution parameterized by @a (in our case, either Gaussian or Uniform), make use of the reparameterization trick, as in Alfarra et al. (2020). The solution of this optimization problem can be found iteratively by performing projected gradient ascent.
standalone implementation for the ANCER optimization stage is presented in Listing 1, whereas the full code integrated in code base available as supplementary material. To perform certification, we simply feed the output of this optimization to the certification procedure from Cohen et al. (2019).
import
from torch, autograd import variable import hormal
Frem dis.rbbbisssssiooon......
class (estificate():
def parppue__poxyy__e (self, logi:s: torch. Tensor):
def naise (self, batch: Tensor, repeated_ torch. iensor) ralse Not ementedfrror
def compute_ges gap (self,,,, påBaz: float): raise Not
class :2Certi ficate (Cartli
def
(self, bator_aize: devices "ouda:0"): self.m itorch zeros (batch_ tolteeice)) torch. (batch_sizee size)) (device))
self.deviee device self.norm "12*
def compute self.m. iodf (logitels, ollalapp_ C01, (.999)) zelf.m m. iede (logits(;, 11.ciamp_ 0.399))
_ecpuuteepoo______ee proxy_ooooooo gep (self, logits: torch. Tensor)
def sample_nates saillennaieeeeee (self, batch: forch,Tenson repeated_theta: theta: torch, Tensor) teroor return
(batch, cevioe=se... repeated_thes
def compute_gap (self, PABar: Float): zeturn norm.opS
ass "1Carti fttrtifionn ficate (Certifictee:
def Liiit _nni__ (self, "eviie="cuda:0") self.device device self.nora "11"
def compute_proxx_sset (self, logits: tensor) return logital:, logital;, 1]
def
betch: forch.fensor. aipeated_thetd forch.Jenson return rand (bstch, fniisesell..evisoe 0.51 theta
def Saapuute_aappeeee páBaz: float): return (pAsar 0.5]
17

---

Under review as a conference paper at ICLR 2022
def ancer_opt pote_oopppiiiaiion
model: forch.nn.Kodillee batch: Terch, certificate: Certificate, lea:ning_rate: Fleatr
isotropic_thetar torch. Iensor, iterations: int,
samples: int, koppa: fleat, device: "cuda:0"1: "nOptiniee batch using ANCE3, sasuming isotropic initialization point.
Angg:
model: Lrained network
batch: inputs certify around
certificates instance of desized certification object learning_rate: optimi zation learning rate for ANCER taotropio_theta: initialisation laotropic value per input in batch iterations: number icerations to run optimization samplea: number of samples pez input and iteration kappa: relexation hypesperameter ...
batch_ size shape[[] img_size np.prod (batch (1:])
define variable, eptinizes, theia (isotrop
initial sigma values graad-rr ldevice) optimizer torch.optin.Adami Athm((theta), te=lesrning_eatel initial_theta (e
"samples"" per input bateh nev_shape - (bstch_size samples] new_shape.extent exteee shaape)
reshape
new_batch betchhrepeat ( (1, samples, vilev (tek__happ))
solve iteratively projected gradient ascend
for in range (iterstions) thela_repested repeali, samples, 1, wiewinew_ssaape
# Reparaneterization noise out model
theta_repes:ed)
new_hatch noise
) rerehhpee (batchaaiea samplea, -1). (dim=1)
vals, torch.topkieus, 2)
gap certificate wtwpiaatts.cccrreeppooo.ooooooee
prod torch.prod(
(theta. reahape (batch_aize, -1)) (1/'mg_siee) dim=1)
proxy_radius prod x gap
andius_maxinizes =
proxy_ moxyyraddus.sum/
keppa
(torch.min (theta. view viewibstchhssann -11, dimel) valluaseapp..om ()
optimizer.step()
project to the initial theca with (erch.no_grad()) corch.max (theta, initial tt_tta, out=theta!
return theta
Listing I: Python implementation of the ANCER optimization routine using PyTorch Paszke et al. (2019)
D MEMORY-BASED CERTIFICATION FOR ANCER
To guarantee the soundness of the ANCER classifier, memory-basee solution presented in Alfarra et al. (2020). The modified algorithm involves post-processing certification step that obtains adjusted certification statistics based the memory
adapted version of the data-dependent
18

---

Under review as a conference paper at ICLR 2022
procedure from Alfarra et al. (2020) (see the original paper for more details). We present adapted version to ANCER this post post-procsssing memory-based step in Algorithm
Algorithm 1: Memory-Baaa -Baed Certification
Input: input point 2N++1 certified region RN+1, prediction CN+1, and memory M Result: Prediction for 21++ and certified region at #N+1 that does not intersect with any certified region in M.
for (Ii, Ca, Ri) E M do
if CN+++ * C, then if 2I++1 E R. then return ABSTAIN. 0 else if Ma..Interreectt/wwa R2) and Intersect(Rx+i) then
R'v+1 Largestout Rx+1);
RN+1 t R'v+1i
end
add (IN-1. CN+1, RN+1) to M;
return Cx+1, RN+1;
Note that the proposed certified region Rx+1 emerges from our certification bounds presented in Sections 4.1 and 4.2. There are few differences between our proposed Algorithm I with respect to the original variant presented in Alfarra et al. (2020). The first is that we remove the computation of the largest certifiable subset of a certified region RN+1 when there exists an such that #N+1 R; with a different class prediction, i.e. (Largest InSubset in Alfarra et al. (2020)) due to the complexity the operation in the anisotropic case. As an example, it 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 a certificate in this situation within our experiments. Further, to the computational burden of the Intersect function, we introduce and instantiate the function whether the by-ball over-approximation of the region RN+1 intersects with a b, over-approximation of R,, This follows since when the Ep balls over- vee-approxximation to the anisotropic regions R and R; do not intersect, then RN+1 and R, do not intersect either. Only in cases in which those overaapproximation regions intersect, we run the more expensive Intersect procedure. We present practical implementations for MaxIntersect, Intersect and ellipsoids and generalized cross-polytopes considered in this paper.
Insect first which checks
for the
D.1 IMPLEMENTING MAXINTERSECT (RAi RB) IN THE ELLIPSOID AND GENERALIZED CROSS-POLYTOPE CASES
Given the two regions RA and RB, consider ba-ball approximations of those regions, R3 {Ir R" || allp S ra and RB = {x E R" ||æ bll, S ro} such that Rr C RÁ and RB C RB.
Lemma 1. If |a bllp ra Tb, then Rr n RB = 0.
Proof. For the sake of contradiction, let la - b11p ra + Tb and æ E R nRg. Then, we have that
| - all S ra and || bll S rb. However:
ra tr |a b/l S || allp + || b|اp S ra + Tb.
forming contradiction. Thus, R2 RB 0. which in turn implies RA n RB 0 since RA and RB are subsets of Rí and RB. respectively.
This forms fast, maximum intersection check for ellipsoids, i.e. p = 2, and generalized cross- polytopes, i.e. p 1. The MaxIntersee function returns Fa 1 se if I|a bllp > Fa + Tb, and True otherwise.
D.2 IMPLEMENTING INTERSECT RB) IN THE ELLIPSOID CASE
The problem of efficiently checking if two ellipsoids intersect is not trivial. We rely the work of Ros et al. (2002); Gilitschenski Hanebeck (2012) with missing proofs from Gilitschenski & Hanebeck (2012) for completeness.
19

---

Under review as a conference paper at ICLR 2022
Lemma 2. Let RA {x ER: (x (2-a))(((xaa))) 1 define two ellipsoids centered at a and b, respectively. We have that R {a : t(x - a) A(x
1) RB f f
R" b) B (z)
a) + (1 (1-t)(x b) T B b) v 1 for any E [0, 1] satisfies RA n RB C R S RA RB.
Proof. By considering the convex combination of the left-hand side of the inequalities defining the regions RA and Rg. becomes obvious that I E RA RB = x E R, concluding the left side of the property. As for the right side, it suffices to show that if x & RA and a E R then z E Rg and, similarly, that if x & RB and follows by symmetry. Without loss of generality, we assume that = b On. Now, let be such that x Ar and Lx: A + (1 f)x Bx S since x & RA and x E R. Then, since E R, we
R then z E RA. We show the first case since the second
have that (1 t)x Bx S 1 fx Az < since Az > 1 which implies that E 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 is equivalent to the following ellipsoid R for (x-m) E1 (= m) S (())) where E, +A + t)B, E, (tAa (1 +)Bb), and K(t) 1-ta Aa (1 (1-th) t)6 Bb
m E.m.
Proof.
1x - a) T A(x - 0) + (1 () - B)x bb) S
<x T (IA + (1 - (i]]) x - 2x (IAa + (1 - -()Bb) S - La Aa -(1 ()bTBB
E
F,m
(x - -m) T E2
m) 1 ta T Aa - (1 - 1)6 T Bb + m E,m
The last equality follows by adding and subtracting m E,m and concluding the proof.
Proposition 8. The set of points satisfying R. t (0, either an empty set, 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 (0. 1) such that (t) 0, the set R. is empty set, and since R 2 RA O RB, the two sets do not intersect. If K(t) = O. then the only point satisfying R the center m. Following similar argument, then the two ellipsoids intersect at a point. At last for
choice of t such that K ((t) > O, then R defines an ellipsoid.
As per Theorem 8, it suffices find some t E 00, 1] under which (tt 0 to guarantee that the ellipsoids do not intersect. To that end, we solve the following convex optimization problem: argmin (tt and check the condition if k(r)) < 0. Moreover, as shown by Ros al. (2002); Gilitschenski & Hanebeck (2012) K(t) is convex in the domain E (0, 1). With several algebraic manipulations, one show that K (t) has the following equivalent forms:
K(1) la T Aa - (1 1)b Bh m TEm
((t)- = 1 - 1(1 - t)(b a) "BE, A( 10-00 a)
K(t)= = (b- (b- ( 1-t B-1
1 A-1
-1
(b-a)
Observe that for ANCER, have that both A and B to be diagonals with diagonal elements {A and {B respectively, resulting in the following simple form for K(t):
t(1 BB
Ktt) = 1 Σ (b. 0,) tA + (1 - BB
The Intersect function in the ellipsoid case returns False if there exists a E (0, 1) such that (()) < Lee. ellipsoids do not intersect, and True otherwise.
20

---

Under review as a conference paper at ICLR 2022
D.3 IMPLEMENTING INTERSECI RB) IN THE GENERALIZED CROSS-POLYTONE CASE
Let RA and Ra be two generalized cross-polytopes RA = { E II || - -]لl S 1 and RB {ar R [B b]]l 1}. where A and B are positive definite diagonal matrices with elements {= and [ respectively. We are interested in deciding whether RA and RB intersect. However, given the conservative context in which Intersect is used Algorithm we
only need to make sure that the function only returns False if it is guaranteed that RA n RB =
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 R {or E R ||A(z a)llı s 1] and RB { E IR" [B b)ll2 S 1]. and perform the ellipsoid intersection check presented in Appendix D.2. R n R 0, then this implies that R.A n RB = 0 and we can safely return False. Otherwise, conservatively assume the generalized cross- poss-pooyyoses intersect, and return True, triggering the reduction procedure detailed in Appendix D.5.
D.4 IMPLEMENTING LARGESTOUTSUB::
RB) IN THE ELLIPSOID CASE
A(xx a) S 1) and RB {x E R" (x b) B(z - 6) S 1} that do intersect where A and B are positive definite diagonal matrices, the task to find the largest possible ellipsoid Rg centered b such that RB S RR where RA RB 0.
Given two ellipsoids RA {I E R" (x (x-a)
Finding a maximum ellipsoid that satisfies those conditions is not trivial, so instead we consider a maximum enclosing ba-ball of Rg, RB {I E I || bll2 S rr. that does not intersect RA. To obtain this ball, we project the center of Ra. b, to the ellipsoid RA Particularly, we formulate the problem the projection of vector y = b onto ellipsoid with the same shape as R centered at O,, This is equivalent to solving the following optimization problem for a symmetric positive definite matrix A:
- 211
s.t.
Ar 1.
Note that the objective function is convex, and the constraint forms a convex set. Forming the Lagrangian to this problem, we obtain:
C(x,
Ar || v1l + X Ax -1
where A > 0. Therefore, the global optimal solution must satisfy the KKT conditions below:
dc = 0 + + = (22A 1
dz
dL = 0 + 1(2A + 1) A2AA + 1) 8- 1--1-00 y
0X
f(A)
Thus, to project the vector y on our region the ellipsoid characterized by A, one needs to solve the scalar optimization f() = 0 then substitute back in the formula of x". Further, given A = diag( , Ann), we can simplify the problem to:
ve Au f(A) Σ (1 )
= 0.
Once x² obtained, we can define the maximum radius of the ball centered at b that does not intersect RA as:
= [xxx + a) bll2 -,
for an arbitrarily small e. Finally, we obtain R3 as the maximum ball contained within RB that has radius smaller than r", that is:
RB = (xe || bll2 S min(r", min B.)).
Note that while choosing the radius of RB to be r* guarantees that R3 R - 0. this does not guarantee that RB S RB. To guarantee both properties, we take the minimum of both r" and min; Bg. This approach finds the solution to the projection of the point to the ellipsoid {z E R" x A & ; does not work for the case in which E RA since the problem would be trivially solved by setting x² y. Thus, classifier must abstain in that situation.
21

---

Under review as a conference paper at ICLR 2022
D.5 IMPLEMENTING LARGESTOUSSSSIIIR RB) IN THE GENERALIZED PROSSPPOLYTOPE CASE
Let RA and RB be two generalized cross-polytopes RA {a E R" || a)ll S 1 and RB = {z E R= [B 6)]l1 S 1}, where A and B are positive defimite diagonal matrices with 1 {A and (B f respectively. The task is to find the largest possible generalized cross-polytope RB centered at such that RB S RB where RA n R 0.
elements
As with the ellipsoid case, solving this problem for generalized cross-polytope not trivial, so instead we consider maximum enclosing cross-poly poosttoo (i.e., b--bll of Rū {i E R" || -bll S } that does not intersect R.A and a subset of RB. To obtain this bball,, we project the center of RB, b, to the generalized cross-polytope RA in a similar fashion to the ellipsoid case in Appendix D.4, We formulate the problem as the projection of the vector y = a to the O,, centered generalized cross cross-polytope {I R" ||Az||ı 1}.
Lemma 4. Consider the hyperplane H {ir E IR" w xx h: 0} and point y E IR". The l projection of on the hyperplane is the point x² = (w" y 1
Proof. We define the projection problem in a similar fashion to the ellipsoid case:
min x 2112
s.t. w x k 0,
and obtain the Lagrangian as Cxx, >) = 1 || 212 + N(w kc), from where we get (using the
2
KKT conditions): x² = X w and X = w v v- wl 3: thus obtaining: x =
(wr g k)xc
10
While this formulation does not yield the closest point from a hyperplane when measured with the E
norm, the fact that ||æ-~>*]| ||x [xx==*]] x=122 implies the certification set obtained in the & norm via this method is a subset of the E2-ball of the minimum projection point. Crucially, this & projection has the advantage of having closed-form solution, while an l one would require solving the problem using an iterative linear programming solver. As such, for the sake computational complexity, decided use this projection, despite the sub-optimality of the result from the & perspective. Empirically, we have found this does not affect our results.
Since the set of vertices of the generalized cross-polytope {x E R" E ||Az|1 S 1} is given by (e+/Au, ei/An) and considering the distance between the projections and the original y, the hyperplane that minimizes is defined by the set of vertices {sign(y: )../., A. By writing it system of n equations, we obtain the hyperplane defined by w = [-sign(y1) (11())))11................... sign(yn)) Amm] and k Finally, after computing x¹ as per Lemma 4, we can define the maximum radius of the ball centered at b that does not intersect RA as:
r" [< aa b111 -,
for an arbitrarily small c. Finally, and similar to the ellipsoids case, we obtain Rg as the maximum generalized cross-polytope contained within Ry that has radius smaller than r", that is:
RB { R" ||= bll2 min(r", min Ba))
Similar to before, to guarantee that the e, ball RB is still subset to RB, 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 RA, since the assumption of the closest plane 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)² and ImageNet Deng et al. (2009)* datasets, and trained ResNet18, WideResNet40 and ResNet50 networks He et al. (2016).
"Available here (url), under an MIT license. Availlbbe here (url), terms of access detailed in the Download page.
22

---

Under review as a conference paper at ICLR 2022
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-pi 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. (2020)² to obtain the isotropic data dependent smoothing parameters. To train our models from scratch, we used adapted version of the code provided in the same repository.
Certification. Following Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019); Yang et al. (2020); Alfarra et al. (2020), 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. ELLIPSOID CERTIFICATION BASELINE NETWORKS
In terms of ellipsoid certification, the baselines we considered were COHEN Cohen et al. (2019) SMOOTHADV Salman et al. (2019a)² and MACER Zhai et al. (2019)*.
In the CIFAR-10 experiments, we used a ResNet18 architecture, instead of the ResNet110 used in Cohen et al. (2019); Salman 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 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 a learning rate of 10 and momentum of 0.9.
E.2 GENERALIZED CROSS-POLYTOPH 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 À v/v3 and report results as a function of a for ease of comparison.
As with the baseline, we ran experiments on CIFAR-10 10 on a WideResNer40 architecture, and ImageNet on a ResNet50 Yang et 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 considers, í.e. σ = (0.15, 0.25, 0.5, 0.75..7. 1.0, 1.125, 1.5, 1.75, 2.25, 2.5, 2.75, 3.0, 3.25, 3.5) on CIFAR-10 and a (0.25, 0.5, 0.75. 1.0, 1.125, 1.5, 1.75, 2.25, 2.5, 2.75, 3.0, 3.25, 3.5} on ImageNet. Instead, and matching the requirements from the ellipsoid section, we choose subset of (0.25, 0.5, 1.0} and performed our analysis that level.
While the trained models are available in the source code of RS4A, we ran into several issues when we attempted to use them, the most problematic of which being the fact that the clean accuracy of such models was very low in both the WedeResNet40 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 Wede models with the stability loss used in Yang et al. (2020) for 120 epochs, with a batch size of 128 and stochastic gradient descent with learning rate of 1 and momentum of 0.9, along with a step learning rate scheduler with of 0.1. For the ResNet50 networks on ImageNet, we trained them from scratch
'Data Dependent Randomized Smoothing source code available here "CoHen source code available here.
7 MOOTTAADY souree code available here.
M ACER source code available here.
PRS4A source code available here.
23

---

Under review as a conference paper at ICLR 2022
with stability loss for 90 epochs with a learning rate of 0.1 that drops by factor of 0.1 after each 30 epochs and a batch size of 256.
F SUPERSET ARGUMENT
The results we present in Section 7 support the argument that ANCER achieves, in general, certificate that is supersel of the Fixed a and Isotropic DD ones. To confirm this at an individual test set sample level, we compare the 22 &1, E and E certification results across the different methods, and obtain the percentage of the test set in which ANCER performs at least well as all other methods in each certificates of the samples. Results of this analysis are presented in Tables 4 and 5.
For most networks and datasets, observe that ANCER achieves a larger lp certificate than the baselines in a significant portion of the dataset, showcasing the fact that it obtains a 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 CIFAR-10, ANCER ' certificate is superior in over 90% of the test set samples.
Table 4: Superset in top-1 1 &g and Eg (rounded nearest percent)
ANCER & is the hest ANCER E the hest
CIFAR- 10: COHEN
CIFAR-I0: SMOOTHADV
73
90
CIFAR-10: MACER
50
69
ImageNet: COHEN
94
96
ImageNet: SMOOTHADV
90
93
Table 5: Superset in top-1 E and et (rounded to nearest percent)
% ANCER & is the best
% ANCER &f is the best
CIFAR-10: 10: RS4A
100
100
ImageNet: RS4A
97
99
G EXPERIMENTAL RESULTS PER
G.1 CERTIFYING ELLIPSOIDS fg AND & CERTIFICATION RESULTS PER
In this section we report certified accuracy at various &g radii and Ey proxy radii, following the metrics defined in Section 7, for each training method (COIEN Cohen et al. (2019), SMOOTHAAY Salman et al. (2019a) and MACER Zhai et al. (2019)), dataset (CIFAR-10 10 and ImageNet) and a (a e {0.12, 0.25, 0.3, 1.0)). Figures 6 and 7 shows certified accuracy at different & radii for CIFAR-10 10 and ImageNet, respectively, whereas Figures 8 and 9 plot certified accuracy and different Ey proxy radii for CIFAR-10 and ImageNet, respectively.
G.2 CERTIPYING ELLIPSOIDS e, AND & CERTIFICATION RESULTS PER o
In this section we report certified accuracy at various & radii and e proxy radii, following the metrics defined in Section 7, for RS4A, dataset (CIFAR- 10 and ImageNet) and (a E f0.25, 0.5, 1.0)). Figures 10 and 11 shows certified accuracy at different & radii for CIFAR-10 10 and ImageNet, respec- tively, whereas Figures 12 and 13 plot certified accuracy and different & proxy radii for CIFAR-10 and ImageNet, respectively.
G.3 WHY DOES ANCER IMPROVE UPON ISOTROPIC DD's fp CERTIFICATES?
As observed Sections 7.1 and 7.2, ANCER'S l and é certificates outperform the corresponding certificates obtained by Isotropic DD. To explain this, compare the & certified region obtained
24

---

Under review as a conference paper at ICLR 2022
Cohen (ora 12)
Cohen (aro 0:25)
Cohen 0.5)
Cohen (or 1.
(622-04221 ANDOR (AGRed (56)
0.6
Poud
JACR--
ANCER (A3RH0A47)
HVGER (00.11
AVGER (AC 8251
Cottfoc 4-4
0.4
Coffiee
62
0.8
0.
4 reddua
radua
6 red
Smoolliddy (a- 0.12)
SmootbAdy (o 0.25)
Smoolbbddy 0.5)
0.5
tocknpir (ACANS 5i1)
Fioss (ACRes 464)
0.6
locanpes jAcles 606)
Fixnt (eGRnd F0M
044
loatniic JACRn (84)
Foost (ASAnO sei)
aNcER (A20--01)))))
ANGER (AC74-2.77))
0.4
Flovt (AGRed 260)
looessi (A2R-0043))
02
0.1
ANCEM (ACN-4
08
00
0/02
25
8.25
1.00
8.
055
10
1.5
6.0
0.5
10
15
2.0
25
3
MACER (a-- 0.12!
MAGER (or- 0.25)
MAGER (cr- 0.51
MAGER (ar 1.01
Fhad (AC 277)
Food (ACI-E 428)
0.6
Fladt (AC ST;
044
Food JACB-O 868)
lookoiis (ACIe22 345)
0.5
bnokoiic (ACIN 401)
ludropic (AGHte 541)
laatraicc JACBH 300)
4.4
0.4
0.4
0.2
0.5
0.0
0.0
00
18
0.0
0.5
1.0
1.5
2.0
2.5
radiu
Figure 6: CIFAR- 10 certified accuracy as function of E2 radius, per model and a (used as initializa- tion in the isotropic data-dependent case and ANCER).
Cohen (arm 0.25)
Cohen (crm 0.5)
(tr
0.5
Cont Bet SEOUENE
(AGH-
Ieatops (ACBt+ 127)
laahaps JACBI+ 785)
0.1
leatrgg (4CBi- a05)
ANCZEt (A0
ANCZR (AC/tw1 122)
ANCCT (ACIt 438)
0:83
0.25
0.53
0.75
10
0.0
20
Fanediu
fareluu
(moothAdv 0.25)
SmoohAdv 0.5)
SmoothAdv 1.0)
Fowd (ACR
Food (ACR-BAA))
Food (AGRH1 Di1))
Indropi (41
badiape (AGN- 121)
ladiario (ACH- 1.0 ANGSR (AGHe-1 458)
00
ANGER (46-62255)
03
ANOER (AG-H) 188)
0.2
0.80
3.2
0.75
3.0
0.5
24
Figure 7: ImageNet certified certffffe accuracy as function of lg radius, per model and a (used as initialization in the isotropic data-dependent case and ANCER).
by ANCER, defined in Section 6 as {6= : |01||2 S min; ofr(z, ))), to the one by Isotropic DD defined as {6 1001l2 < r"r(zz o²) )²)}. We observe that the radius of both of these certificates can be separated into a o-factor (a" vs. ohin = min; of) ) and gap-factor (r(x:, a²) vs. r(r, E²)). We posit the seemingly surprising result can be attributed to the computation of the gap-factor 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 oiin than the isotropic ot when given further optimization iterations.
To investigate this, we take the optimized parameters from the Isotropic DD experiments on SMOOTHADV for an initial o = 0.25 on 10, and run the optimization step of Isotropic DD for 100 iterations more than its default number of iterations from Alfarra et al. (2020), so as to match the total number of optimization steps between Isotropic DD and AnCER. The histograms of ot tion results, are presented in Figure 14. While ot for Isotropic DD is similar in distribution to ANCER'S of min- the distribution of the two gaps, r(x, and r(æ, E²), are quite different.
oh and the gap-factor r, L.e. the two factors from the & certifica-
25

---

Under review as a conference paper at ICLR 2022
Cohen (ora 0. 12)
Cohen (arm 0:25)
Cohen (ari 0.55
Cohen (cr 1.
loteacis (MCRs 201)
Fladd 243y
Floud puGled 402)
watape (KOk1044)
0.6
Food (ACi-o 482)
loarose (ACRi 568)
04
lotropo (ACRH1
Fase JACiio 497)
10.4
0.4
(
00
ANZOR (ACE
022
0.2
0.
0.0
1.3
1.5
1.2
1.5
2.
6 avey sdiun
6 poey nduume
o prea volune
4 prop vours
SmoollAdly 0.12)
SmoolhAdy (o- 0.25)
Smoolbbdd 0.5)
50.
Inokmoti (iC8-2 468)
Food (ACif-
0.5
(ACRf 2011
(ACff-
Pood (ACif-o
lndrope (ACi- coe)
044
Inarrpp JACtf- cau)
(ACii-o ses)
ANCER (ACK)0A22))
ANCER (AC4m0a9))
ANCER (1C6
ANDER (ACk- 992)
0.4
0.2
022
02
0.8
0.6
0.6
0.
0.0
0.5
1.0
1.5
2.6
8.0
1.0
1.5
smay
( aray
pray
MACER (ar- 0.12!
MACER (or- 0.25)
MAGER (dr- 0.51
MAGER (dr 1.0)
(f 272)
Fiodd (ACRes 424
Fond (AC6no R2)
Fine (ACRn s48 (4C1--3335) ANGERLACE-O..O
hoteusi (CC 340)
(AC--8841) ANCER AACER-0
0.4
ANDER (4Cf-003)
014
ANGER (CCf-0.00
0.4
0.0
pray
Figure 8: CIFAR-10 certified accuracy function of E proxy radius, per model and a (used as initialization in the isotropic deta-depnndnnt case and ANCER).
Ochan (c - 0.25)
Ochan (c - 0.5)
Cahan (c 1.0)
0.5
Fooel (ACR-u 671
0.4
Foood (ACR-2 864)
lastagic (Acil-o 5om)
fustragte (ACil- 505; (4CE-1
0.4
(Acffo
Food (act-- 12ly lestap pall-am
(aCE:
6.0
0.5
15
20
0.0
05
15
2.
proyyoliue
paay vduue
SmoothAid (p= 0.55)
Smoothidd 0.5)
Smooth/dd (cr 1.0)
Iscres (ackieat)
ANDER (4C)-2
02
Food (Aclln pri)
Food (ACS D11)
lnthopo (AC600922)
ANC 2001
ANGEN 5471
02
2 ( volure
( solum
prosy sdume
Figure 9: ImageNet certified accuracy as a function of Eg proxy radius, per model and a (used as initialization in the isotropic data-dependent case and ANCER).
In particular, the ANCER certification gap is significantly larger when compared to Isotropic DD, and is the main contributor the improvement in the balb certificate of ANCER. That is to say, AnCeR generates n that is better aligned with the decision boundaries, and hence increases the confidence of the smooth classifier.
100- ledmpreDD DO
ANCER
0.6
0.4
2
02
0.0
0
0.2
H VISUAL COMPARISON OF PARAMETERS IN ELLIPSOID CERTIFICATES
of ope
Figure 14: Histograms of the values of the o- (left) and gap r (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.
Anisotropic certification allows for a better characteriza- tion of the decision boundaries of the base classifier f. For example, the directions aligned with the major axes of the ellipsoids ||ā||,, = r, i.e. locations where Σ is large, are, by definition, expected to be less sensitive perturbations
26

---

To validate this claim, we perform certification of AdoothAdy Salman et al. (2019a) with initial a = 1 on CIFAR-10 10 using a Σ 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 Under review as a conference paper at ICLR 2022
RS4A (ar 25)
HS4A (g 0.5)
RS4A (.00
ANCER (1CR-6 481)
(ADN-O
Cettiic accureo
ANDER (KCH-6 629)
(ADR-)
0.4
0.
0.
Figure 10: CIFAR-10 10 certified accuracy as a function of & radius per a (used as initialization in the isotropic data-dependent case and ANCER).
R84A (o 0225)
RB4A (o - 0.5)
R84A (o 1.0)
0.
04
Food (AGB-8176)
Food (ACP-6333))
Food (AGR-0642
Ieabasic JACRted
lnarap: JAGB+8
Figure/ 11: ImageNet certified accuracy as a function of & radius per a (used as initialization in the isotropic data-dependent case and ANCER).
compared to the minor axes directions. To visualize this concept, Figure 15 shows CIFAR-10 images along with their corresponding optimized &g isotropic parameters obtained by Isotropic DD, and & 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 D 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 is that the decision boundaries are not distributed isotropically around each input. To quantify this in higher dimensions, we plot in Figure 16 histogram of the ratio between the maximum and minimum elements of our optimized smoothing parameters for the experiments on SmoothAdv (with an initial o = 1.0) on CIFAR-10. We note that this ratio can be high 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.
1 NON DATA-DEPENDENT ANISOTROPIC CERTIFICATION
As mentioned briefly Section 6, it is our intuition that anisotropic certification requires a data- dependent approach, different points will have fairly different decision boundaries and the certified regions will extend in different directions (as exemplified in Figure 1).
methods reported in the main paper. As can be observed, moving away from the data-dependent certification in the anisotropic scenario 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 on both & and l 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 marginal improvement
27

---

Under review as a conference paper at ICLR 2022
RS4A (ari 25)
HS4A (gr 0.5)
RS4A (c 1.0)
Frod (Acfmo 203;
Foosd jic 287;
netipp (ACHn 4MM
tscrggo (ACKio 886
Poud JAcil-errr,
ANDER (CC
02
0:03
6.2
0.50
0.75
1.25
0.5
1.5
pron volrww
prana volurm
pr000 solumw
Figure 12: CIFAR-10 10 certified accuracy as function of e proxy radius per a (used as initialization in the isotropic data-dependent case and ANCER).
RE54A m 0.25)
( 0.5)
RSSA 1.0)
0.5
Fove (AC4-0
(CC 500)
Froee (AC 942)
lapeopic (ACil-o 2015
Isbegpic (4201-0 2ng
Isooiaaic (Aciloo.88) 2011
ANCER (orffet
AMCOR (ACH-1 8C3)
ANOOR (ACÉ-
0.3
0.5
Figure 13:
ImageNet certified accuracy as function of e proxy radius per a (used as initialization in the isotropic data-dependent case and ANCER).
over Cohen et al. As for the & certificates, Mohapatra al. (2020) uses the Gaussian distribution of Cohen et al, resulting in worse performance than existing state-of-art in l Yang al. (2020) that uses a uniform distribution. Our approach improves further upon the performance of Yang 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 al. (2020) the use of data-dependent smoothing.
28

---

Under review as a conference paper at ICLR 2022
Figure 15: Visualization of an input CIFAR-10 image æ (top), and the optimized parameters (middle) and y (bottom) higher intensity corresponds to higher ø, in that pixel and channel of the smoothing distributions in the isotropic and anisotropic case, respectively.
08
Figure 16: Distribution of the maximum over the minimum ANCER o at each dataset point for SmoothAdy Salman al. (2019a) on CIFAR- 10 (for initial 1.0)
Table 6: Comparison different certification methods on SmoothAdy with an initial = 1.0 on CIFAR-10.
Accuracy @ & radius (%)
CIFAR-10
SmoothAdy
E ACR
E 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
Isotropic DD
41
39
36
29
21
14
7
0.694
0.694
1.0
ANCeR
43
41
26
8
0.871
0.992
Average
29
25
21
14
0.329
0.379
29


Reviews:
[{"review_id": "d8HMqSY6qfR", "reviewer": "Reviewer_fXE9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and easy to follow.\nAt the high-level the idea of anisotropic certificates is mathematical simple, yet interesting and, as shown in the evaluation, effective.\n\nThe mathematical ideas introduced in sections 4 and 5 mostly follow directly from prior work (as is acknowledged in footnote 2).\nANCER, presented in sections 6 and C, also seems straight forward and correct. However, I have concerns about the data dependent nature of the algorithm (see below).\n\nThe evaluation section is quite thorough and obtains SOTA results.\nHowever, what is completely missing is a discussion of the inference/prediction procedure.\n\nBased on this my main concerns are:\n- The usefulness of data-dependence approach (see below) and whether comparison with non-data-dependent approaches is fair.\n- The novelty of the approach: Many of the contributions are direct consequences or applications of other approaches.\n  While normally, in the light of good results, I would not mind this, in the case of this publication I am unsure, due to my first concern, how good the results really are.\n\nFurthermore, I am wondering whether ACR gains can be realized in the anisotropic setting without per-datapoint optimization (e.g. finding a anisotropic smoothing parameters offline on the training set, and subsequently using them in certification)?\n\nData Dependence:\nData-dependent randomized smoothing (DDRS) [1] has been shown to be unsound in its original form and was then patched by the addition of memory-based certification in the latest draft of [1] as well as in this paper.\nWhile the memory-based approach seems to fix the unsoundness of DDRS when applied to perturbed versions of previously certified samples, I have a few questions regarding its suitability as a practical certified defense:\n- Neither this paper nor [1] discuss inference/prediction (e.g., PREDICT in [2]). Can you elaborate on how a prediction procedure would look like, that (i) is consistent with the result of the memory-based certification and (ii) is efficient (i.e. does not need to compute the certification radius at inference time)?\n- Can you clarify whether the order in which inputs are presented can influence the output of the model? If so, would the model have to include a history of all samples, predictions, and certified radii previously seen? Consequently, would any obtained guarantees only be valid for a model with the exact same history, hence preventing parallel application?\n- Can you discuss the possibility of an attacker deliberately presenting inputs (e.g. in small pockets of one class in the decision landscape) that influence the model’s predictions on future inputs?\n\nDepending on these questions, data-dependent and non-data-dependent approaches (e.g. [2]) seem to target very different settings. If this is the case, I believe a direct comparison and the claim to be SOTA to be unfair.  To avoid confusion in the field, this difference in setting and all its implications should be made abundantly clear.\n\nFurther, while I am very open to discuss these points and, depending on the answers, raise my score, I am unsure whether this is the right place to discuss these issues as they mostly concern the key contributions of [1], which has not yet been published in a peer reviewed format, potentially due to these very questions.\n\n[1] Data Dependent Randomized Smoothing, Alfarra et al.; arXiv 2020/2021\n\n[2] Certified Adversarial Robustness via Randomized Smoothing, Cohen et al.; ICML 2019\n\n", "summary_of_the_paper": "In this paper, the authors discuss the extension of $\\ell_{p}$-randomized smoothing to anisotropic counterparts.\nIn particular, they consider the extension of $\\ell_{2}$-certificates from (hyper)spheres to (hyper)ellipsoids\nby sampling anisotropic rather than isotropic Gaussian noise, as well as the extension of $\\ell_{1}$-certificates to cross-polytopes by sampling scaled Uniform noise rather than unscaled noise.\nFurther, the authors discuss how these extended certificates can be compared to their base-counter parts to establish superiority (inclusion).\nThe introduced certification algorithm, ANCER, utilizes the idea of data-dependent randomized smoothing to find the anisotropic shape with maximal certification volume.\nIn experimental evaluation on Cifar-10 and Imagenet the authors show that the obtained certificates permit higher isotropic certificating radii than other methods in the per-sample optimization setting.", "summary_of_the_review": "The paper presents anisotropic robustness certificates, which seems to be technically correct and conceptually interesting.\nWhile not stellar I believe the novelty and motivation are sufficient, given the results.\nHowever, my reception of the results, and thereby the overall paper hinges on the data-dependent optimization procedure considered in the paper, of which I am currently not convinced.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PDQLTOMKK8n", "reviewer": "Reviewer_xapX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n\nThis paper is fairly interesting and insightful as it sufficiently demonstrates the advantage of introducing anisotropic robustness certificates. Although section 4.2 and 4.3, the main derivations of the non-isometric certification, are directly based on Salman et al. 2019(a), it is useful and allows less restrictive certification geometry. The discussion and adoption of Alfarra et al. 2020 in maximizing the volume through proxy radius are also interesting. Section 7.3 is especially helpful as it delves into the root keys of the better performance over isotropic DD.\n\n\nWeakness\n\nThe paper mentioned all prior works considered smoothing with isotropic distributions and hence certified isotropic ell_p-ball regions, but [*] admits non-isotropic certified radius bound via first-order certification. It will be helpful if the authors can include comparisons theoretically and empirically with this prior work, allowing a more fair evaluation of the significance of the paper.\n\nMohapatra, Jeet, Ching-Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. \"Higher-Order Certification for Randomized Smoothing.\" Advances in Neural Information Processing Systems 33 (2020).\n\n\nMinor error: There is a redundant 'the' in the first sentence of section 7.3.", "summary_of_the_paper": "The paper proposes the anisotropic version of randomized smoothing. Evaluation metrics based on the volume of the certified region are proposed, allowing comparisons with the certified regions provided from isotropic randomized smoothing. Experimental results show the usefulness of introducing anisotropic randomized smoothing as it certifies larger regions.", "summary_of_the_review": "The paper contributes adequately to the community and provides enough details regarding the problem formulation and empirical performance-cost tradeoff. Including a more complete comparison with the literature will make it a stronger submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IY8-Z0T0hGh", "reviewer": "Reviewer_Fomp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n\nRandomized smoothing, being the most scalable of robustness certification techniques, is an important research direction, and this work significantly advances the state of the art, even in the isotropic setting. The proposed technique is clearly explained and the analysis to justify this approach is simpler than that of Cohen or Yang. While the problem setting is slightly different than prior arts (anisotropic vs isotropic), a natural and fair quantitative comparison approach is described. The most significant and surprising result of this work: that these isotropic certificates outperform even Alfarra's approach is given ample discussion, and empirically-supported justification. The experiments are thorough and fairly compare against prior work.\n\n**Weaknesses:**\n\nA primary pitfall of this work is that anisotropic certificates are not particularly well-motivated. The community-accepted threat model for adversarial attackers is typically isotropic, and probing the shape of the decision boundary is of dubious utility. If this were a primary goal, more efforts would be paid to considering anisotropic certificates that are not axis-aligned (i.e. Sigma and Lambda are not diagonal). Another downside to this work is that it relies heavily upon the approach of Alfarra. Importantly, this also means AnCer inherits the main inelegance of Alfarra's approach: the memory-based classifier. This raises serious concerns in that the certificates provided are dependent upon the order in which the model is queried. While this is perhaps borderline not-kosher, it has not been a concern in practice in prior works, but it would be nice to see some evidence of this claim here.\n\n**Questions:**\n\n- How does Ancer perform for non axis-aligned anisotropic regions? Searching over orthogonal matrices (for the rotation) in addition to the diagonal anisotropic components could drastically increase the number of optimization variables as well as complicate the optimization landscape. How does this affect performance in terms of both runtime and reported certificates?\n- Are there examples for which the memory bank of the memory-based classifier is leveraged? In particular, how does the minimum distance between a pair of cross-class test data points compare to the bounds provided? \n- What insights does AnCer tell us about the shape of the decision boundary? ", "summary_of_the_paper": "The authors provide a technique for a data-dependent randomized smoothing that provides anisotropic certificates of robustness. This may be viewed as an extension of the work of Alfarra et al, where the certificates provided are axis-aligned cross-polytopes or ellipsoids; however surprisingly the proposed approach provides even tighter bounds than Alfarra's in the isotropic setting.", "summary_of_the_review": "This approach advances the state of the art in an important line of work. A slightly nonstandard problem setting is considered, but even when comparing to the standard problem, AnCer improves upon prior works. The analysis is clean, the results surprising, and the experiments are thorough. I have no qualms recommending acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7YCKLcuu1Dl", "reviewer": "Reviewer_xsin", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, polished, and easy to follow. The anistropic part of the proposed approach is well-motivated, however the sample-wise part has several issues (see below) making it unsuitable to use in practice. Moreover, some of the theoretical results are not novel (see below).\n\nComments:\n- The derivation of the certificate in term of the Lipschitz constant under the dual norm (Proposition 1, Theorem 1) is insightful. However, this result is already known in the literature in greater generality and should be properly cited. Specifically, Theorem 1 in [1] derives the local (\\alpha,\\beta)-Lipschitz constant over an open set. The special case of a scalar function is also discussed (see Eq. 3 in [1]) and it coincides with the result in Proposition 1 (if we are in the special case where the open set is R). The discussion of how to use such a Lipschitz constant for certification is also discussed in [1] (see section E.2).\n- The authors already discuss a know issue of data-dependent classifiers which when not tackled can lead to certificates that are not sound. To address the issue they adapt the memory-based procedure introduced in Alfarra et al. While this procedure does make the certificate sound it has other problems.\n  - First, by introducing memory the proposed anisotropic certificate (or in fact any method to compute a certified region) becomes completely irrelevant. Namely, for sample i construct any region R_i and define that the prediction in that region is some arbitrary C_i. Then run the post-processing certification step in Algorithm 1 (or similarly the procedure from Alfarra et al.). Since the obtained regions will not intersect with any certified regions in the memory M the procedure is still sound. This is true regardless of how the region R_i was constructed.\n  - A second, and more important, issue is that the memory makes the certificate dependent on the order of the incoming test samples. This provides a new avenue for attack, i.e. the adversary can optimize the order of the test samples to decrease the utility of the final obtained smoothed classifier.\n  - Finally, the success of this memory approach also somewhat depends on the \"sparsity\" of the test samples. Namely, by using a small test set since the samples are in a high-dimensional space the distance between them tends to be bigger than the (proxy) radii of the certified regions. However, in a real-world application we are likely to have many more test samples which would increase the number of intersections when running Algorithm 1.\n  - Note, all of these issue also apply to Alfarra et al. and are simply inherited in this approach.\n- Another issue with the proposed approach is the optimization procedure described in section C. The optimization suffers from issues such as: inconsistent estimation due to clamping and not using confidence bounds, sensitivity to initialization, high gradient variance, etc. These and other issues have been described in great detail in section C.2 in [2], focusing on Alfarra et al., although, given the similarity, the same issues are inherited in this approach.\n- Relatedly, in [2] the authors show that input-dependent randomized smoothing suffers from the curse of dimensionality. A discussion of this issue and how it applies to the proposed certificate should be included.\n- The derivations for the special cases of certifying ellipsoids and generalized cross polytopes are useful. Note that similar results are derived in [3] (see Theorem 5 for a weighted l_2 metric equivalent to a diagonal \\Sigma, and also Theorem 3) albeit in a slightly different context. A discussion on how these two relate should be included.  \n- The discussion of how to evaluate the anisotropic certificates and the formal definition of a \"superior certificate\" is appreciated. \n- The experiments are executed well.\n\nQuestions:\n- Assuming that estimate of the Lipschitz constant L is tight is the certificate provided by Theorem 1 also tight? For the special case of l_2 certification with \"\\Sigma = \\sigma^2 I\" tightness is shown in previous work. Does it hold in general?\n- Are there any benefits to training with anisotropic noise?\n\nReferences:\n1. Jordan and Dimakis. \"Exactly Computing the Local Lipschitz Constant of ReLU networks\"\n2. Sukenik et al. \"Intriguing Properties of Input-dependent Randomized Smoothing\"\n3. Yeom and Fredrikson. \"Individual Fairness Revisited: Transferring Techniques from Adversarial Robustness\"", "summary_of_the_paper": "The authors extend the standard (isotropic) l_1/l_2 randomized smoothing certificate to anisotropic smoothing distributions (and anisotropic regions). They propose to maximize the volume of the certified region for each sample independently, using a memory procedure to preserve soundness.", "summary_of_the_review": "The paper is well written, polished, and easy to follow. The anistropic part of the proposed approach is well-motivated, however the sample-wise part has several issues (see main review) making it unsuitable to use in practice. Moreover, some of the theoretical results are not novel (see main review).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes the anisotropic version of randomized smoothing. Evaluation metrics based on the volume of the certified region are proposed, allowing comparisons with the certified regions provided from isotropic randomized smoothing. Experimental results show the usefulness of introducing anisotropic randomized smoothing as it certifies larger regions.

Strengths:
+ The paper is well written, polished, and easy to follow.
+ The anisotropic part of the proposed approach is well-motivated.
+ The evaluation section is quite thorough and obtains SOTA results.

Weaknesses:
- The sample-wise (data dependent) part has several issues making it unsuitable to use in practice. The authors already discuss a know issue of data-dependent classifiers which when not tackled can lead to certificates that are not sound. To address the issue they adapt the memory-based procedure introduced in Alfarra et al. While this procedure does make the certificate sound it has other problems. For example, an issue is that the memory makes the certificate dependent on the order of the incoming test samples. This provides a new avenue for attack, i.e. the adversary can optimize the order of the test samples to decrease the utility of the final obtained smoothed classifier. In addition, the success of this memory approach also somewhat depends on the "sparsity" of the test samples. Namely, by using a small test set since the samples are in a high-dimensional space the distance between them tends to be bigger than the (proxy) radii of the certified regions. However, in a real-world application we are likely to have many more test samples which would increase the number of intersections when running Algorithm 1. Although the authors provide opposite empirical evidence on a specific dataset, it is not very clear how general it is for other datasets.

- Some of the theoretical results are not novel as they follow directly from prior work (as acknowledged in the paper). 

- Another issue with the proposed approach is the optimization procedure described in section C. The optimization suffers from issues such as: inconsistent estimation due to clamping and not using confidence bounds, sensitivity to initialization, high gradient variance, etc.
Decision: Reject