Year: 2021

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 `p certification, which has the advantage of yielding certificates that can be easily compared among isotropic methods via `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 `1 and `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 `1 and `2 certified accuracy on CIFAR-10 and ImageNet in the data-dependence setting, while certifying larger regions in terms of volume, highlighting the benefits of moving away from isotropic analysis.

heading: 1 INTRODUCTION
text: 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-art 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 x and a network f , randomized smoothing constructs g(x) = E ∼D[f(x + )] such that g(x) = g(x + δ) ∀δ ∈ R, where the certification region R is characterized by x, f , and the smoothing distribution D. For instance, Cohen et al. (2019) showed that if D = N (0, σ2I), thenR is an `2-ball whose radius is determined by x, f and σ. Since then, there has been significant progress towards the design of D leading to the largestR for all inputs x. The interplay betweenR characterized by `1, `2 and `∞-balls, and a notion of optimal distribution D has been previously studied Yang et al. (2020). Despite this progress, current randomized smoothing approaches provide certification regions that are isotropic in nature, limiting their capacity to certifying smaller and worst-case regions. We provide an intuitive example of this behavior in Figure 1. The isotropic nature ofR in prior art is due to 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 no clear metrics for comparing with other certificates. In this paper, we address both concerns and present new state-of-the-art certified accuracy results on both CIFAR-10 and ImageNet datasets.
Our contributions are threefold. (i) We provide a general and simpler analysis compared to prior art (Cohen et al., 2019; Yang et al., 2020) that paves the way for the certification of anisotropic regions characterized by any norm, holding prior art as special cases. We then specialize our result to regions that, for a positive definite A, are ellipsoids, i.e. ‖Aδ‖2 ≤ c, and generalized cross-polytopes,
i.e. ‖Aδ‖1 ≤ c, generalizing both `2 (Cohen et al., 2019) and `1 (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 certifyingR1 is superior to another certifyingR2, ifR1 is a strict superset to R2. Further, we define a standalone quantitative metric as the volume of the certified region, and specialize it for the cases of ellipsoids and generalized cross-polytopes (Section 5). (iii) We propose ANCER, an anisotropic certification method that performs sample-wise (i.e. per sample in the test set) region volume maximization (Section 6), generalizing the data-dependent, memory-based solution from Alfarra et al. (2020). Through experiments on CIFAR-10 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009), we show that restricting ANCER’s certification region to `1 and `2-balls outperforms state-of-the-art `1 and `2 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-art in certified accuracy. We highlight that while we effectively achieve state-of-the-art performance, it comes at a high cost given the data-dependency requirements. A discussion of the limitations of the solution is presented in Section 6.
Notation. We consider a base classifier f : Rn → P(K), where P(K) is a probability simplex over K classes, i.e. f i ≥ 0 and 1>f = 1, for i ∈ {1, . . . ,K}. Further, we use (x, y) to be a sample input x and its corresponding true label y drawn from a test set Dt, and fy to be the output of f at the correct class. We use `p to be the typically defined ‖ · ‖p norm (p ≥ 1), and `Ap or ‖ · ‖A,p for p = {1, 2} to be a composite norm defined with respect to a positive definite matrix A as ‖A−1/pv‖p.

heading: 2 RELATED WORK
text: Verified Defenses. Since the discovery that DNNs are vulnerable against input perturbations (Goodfellow et al., 2015; Szegedy et al., 2014), a 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 `1 and `2-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 `p-norm 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 `p-norm; however, the certification process requires significant hyperparameter tuning. Similarly, Mohapatra et al. (2020) introduces larger certificates that require higher-order information, yet do not provide a closed-form solution. This was followed by a complementary data-dependent smoothing approach, where the parameters of the smoothing distribution were optimized per test set sample to maximize the certified radius at an individual
input (Alfarra et al., 2020). All prior works considered smoothing with isotropic distributions and hence certified isotropic `p-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.

heading: 3 MOTIVATING ANISOTROPIC CERTIFICATES
text: Certification approaches aim to find the safe region R, where arg maxi f i(x) = arg maxi f i(x + δ) ∀δ ∈ R. Recent randomized smoothing techniques perform this certification by explicitly optimizing the isotropic `p certified region around each input (Alfarra et al., 2020), obtaining state-ofthe-art performance as a result. Despite this `p optimality, we note that any `p-norm certificate is worst-case from the perspective of that norm, as it avoids adversary regions by limiting its certificate to the `p-closest adversary. This means that it can only enjoy a radius that is at most equal to the distance to the closest decision boundary. However, decision boundaries of general classifiers are complex, non-linear, 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 `p-ball around an input, there are often only a small set of adversary directions (Tramèr et al., 2017; 2018) (e.g. see the decision boundaries in Figure 1). As such, while `p-norm certificates are useful to reason about worst-case performance and are simple to obtain given previous works (Cohen et al., 2019; Yang et al., 2020; Lee et al., 2019), they are otherwise uninformative in terms of the shape of decision boundaries, i.e. which regions around the input are safe.
To visualize these concepts, we illustrate the decision boundaries of a base classifier f trained on a 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 ‖δ‖1 ≤ r) with an anisotropic generalized cross-polytope (of the form ‖Aδ‖1 ≤ r), while in Figures 1c and 1d we compare an isotropic `2 ball (of the form ‖δ‖2 ≤ r) with an anisotropic ellipsoid (of the form ‖Aδ‖2 ≤ r). Notice that in Figures 1a and 1c, due to the curvature of the classification boundary (shown in white), the optimal certification region is isotropic in nature, which is evidenced by the similarities of the optimal isotropic and anisotropic certificates. On the other hand, in Figures 1b and 1d, the location of the decision boundary allows for the anisotropic certified regions to be considerably larger than their isotropic counterparts, as they are not as constrained by the closest decision boundary, i.e. the worst-case performance. We note that these differences are further highlighted in higher dimensions, and we study them for a single CIFAR-10 test set sample in Appendix A.1. Further, we also showcase how anisotropic certification allows for further insights into constant prediction (safe) directions in Appendix A.2.

heading: 4 ANISOTROPIC CERTIFICATION
text: One of the main obstacles in enabling anisotropic certification is the complexity of the analysis required. To alleviate this, we follow a Lipschitz argument first observed by Salman et al. (2019a) and Jordan & Dimakis (2020) and propose a simple and general certification analysis. We start with the following two observations. All proofs are in Appendix B. Proposition 1. Consider a differentiable function g : Rn → R. If supx‖∇g(x)‖∗ ≤ L where ‖ · ‖∗ has a dual norm ‖z‖ = maxx z>x s.t. ‖x‖∗ ≤ 1, then g is L-Lipschitz under norm ‖ · ‖∗, that is |g(x)− g(y)| ≤ L‖x− y‖.
Given the previous proposition, we formalize ‖ · ‖ certification as follows: Theorem 1. Let g : Rn → RK , gi be L-Lipschitz continuous under norm ‖ · ‖∗ ∀i ∈ {1, . . . ,K}, and cA = arg maxi gi(x). Then, we have arg maxi gi(x+ δ) = cA for all δ satisfying:
‖δ‖ ≤ 1 2L
( gcA(x)−max
c gc 6=cA(x)
) .
Theorem 1 provides an ‖ · ‖ norm robustness certificate for any L-Lipschitz classifier g under ‖ · ‖∗. The certificate is only informative when one can attain a tight non-trivial estimate of L, ideally supx‖∇g(x)‖∗, which is generally difficult when g is an arbitrary neural network.
Framework Recipe. In light of Theorem 1, randomized smoothing can be viewed differently as an instance of Theorem 1 with the favorable property that the constructed smooth classifier g enjoys an analytical form for L = supx‖∇g(x)‖∗ by design. As such, to obtain an 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 a notion of “optimal” smoothing distribution for a given choice of ‖ · ‖ certificate, as in part addressed earlier for the isotropic `1, `2 and `∞ 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-Pearson’s lemma (Cohen et al., 2019) or the Level-Set and Differential Method (Yang et al., 2020).
We will deploy this framework recipe to show two specializations for anisotropic certification, namely ellipsoids (Section 4.1) and generalized cross-polytopes (Section 4.2).1.

heading: 4.1 CERTIFYING ELLIPSOIDS
text: In this section, we consider the certification under `Σ2 norm, or ‖δ‖Σ,2 = √ δ>Σ−1δ, that has a dual norm ‖δ‖Σ−1,2. Note that both ‖δ‖Σ,2 ≤ r and ‖δ‖Σ−1,2 ≤ 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 N (0,Σ) with the smooth classifier defined as gΣ(x) = E ∼N (0,Σ) [f(x+ )]. Considering the classifier Φ−1(gΣ(x)), where Φ is the standard Gaussian CDF, and following Theorem 1 to grant an `Σ2 certificate for Φ−1(gΣ(x)), we derive the Lipschitz constant L under ‖ · ‖Σ−1,2, in the following proposition.
Proposition 2. Φ−1(gΣ(x)) is 1-Lipschitz (i.e. L = 1) under the ‖ · ‖Σ−1,2 norm.
Since Φ−1 is a strictly increasing function, by combining Proposition 2 with Theorem 1, we have:
Corollary 1. Let cA = arg maxi giΣ(x) , then arg maxi giΣ(x+ δ) = cA for all δ satisfying:
‖δ‖Σ,2 ≤ 1
2
( Φ−1 (gcAΣ (x))− Φ −1 ( max c gc6=cAΣ (x) )) .
Corollary 1 holds the `2 certification from Zhai et al. (2019) as a special case for when Σ = σ2I .2

heading: 4.2 CERTIFYING GENERALIZED CROSS-POLYTOPES
text: Here we consider certification under the `Λ1 norm defining a generalized cross-polytope, i.e. the set {δ : ‖δ‖Λ,1 = ‖Λ−1δ‖1 ≤ r}, as opposed to the `1-bounded set that defines a cross-polytope, i.e. {δ : ‖δ‖1 ≤ r}. As with the ellipsoid case and despite that the following results hold for any positive definite Λ, for the sake of efficiency, we assume Λ to be diagonal throughout. For generalized cross-polytope certification, we consider an anisotropic Uniform smoothing distribution U , which defines the smooth classifier gΛ(x) = E ∼U [−1,1]n [f(x+ Λ )]. Following Theorem 1 and to certify under the `Λ1 norm, we compute the Lipschitz constant of gΛ under the ‖Λx‖∞ norm, which is the dual norm of ‖ · ‖Λ,1 (see Appendix B), in the next proposition. Proposition 3. The classifier gΛ is 1/2-Lipschitz (i.e. L = 1/2) under the ‖Λx‖∞ norm.
Similar to Corollary 1, by combining Proposition 3 with Theorem 1, we have that:
Corollary 2. Let cA = arg maxi giΛ(x) , then arg maxi giΛ(x+ δ) = cA for all δ satisfying: ‖δ‖Λ,1 = ‖Λ−1δ‖1 ≤ ( gcAΛ (x)−maxc g c6=cA Λ (x) ) .
Corollary 2 holds the `1 certification from Yang et al. (2020) as a special case for when Λ = λI .
1Our analysis also grants a certificate for a mixture of Gaussians smoothing distribution (see Appendix B.1). 2A similar result was derived in the appendix of Fischer et al. (2020); Li et al. (2020) with a more involved
analysis by extending Neyman-Pearson’s lemma.

heading: 5 EVALUATING ANISOTROPIC CERTIFICATES
text: With the anisotropic certification framework presented in the previous section, the question arises: “Given two general (isotropic or anisotropic) certification regionsR1 andR2, how can one effectively compare them?”. We propose the following definition to address this issue.
Definition 1. For a given input point x, consider the two certification regionsR1 andR2 obtained for two classifiers f1 and f2, i.e. A1 = {δ : arg maxc f c1(x) = arg maxc f c1(x + δ),∀δ ∈ R1} and A2 = {δ : arg maxc f c2(x) = arg maxc f c2(x + δ),∀δ ∈ R2} where arg maxc f c1(x) = arg maxc f c 2(x). We sayA1 is a "superior certificate" toA2 (i.e. A1 A2), if and only if,A1 ⊃ A2.
This definition is a natural extension from the radius-based comparison of `p-ball certificates, providing a basis for evaluating anisotropic certification. To compare an anisotropic to an isotropic region of certification, it is not immediately clear how to (i) check that an anisotropic region is a superset to the isotropic region, and (ii) if it were a superset, how to quantify the improvement of the anisotropic region over the isotropic counterpart. In Sections 5.1 and 5.2, we tackle these issues for the particular cases of ellipsoid and generalized cross-polytope certificates.

heading: 5.1 EVALUATING ELLIPSOID CERTIFICATES
text: Comparing `2−Balls to `Σ2−Ellipsoids (Specialization of Definition 1). Recall that if Σ = σ2I , our ellipsoid certification in Corollary 1 recovers as a special case the isotropic `2-ball certification of Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019). Consider the certified regions R1 = {δ : ‖δ‖2 ≤ σ̃r1} and R2 = {δ : ‖δ‖Σ,2 = √ δ>Σ−1δ ≤ r2} for given r1, r2 > 0. Since we take Σ = diag({σ2i }ni=1), the maximum enclosed `2-ball for the ellipsoid R2 is given by the set R3 = {δ : ‖δ‖2 ≤ mini σir2}, and thus R2 ⊇ R3. Therefore, it suffices that R3 ⊇ R1 (i.e. mini σir2 ≥ σ̃r1), to say thatR2 is a superior certificate to the isotropicR1 as per Definition 1.
Quantifying `Σ2 Certificates. The aforementioned specialization is only concerned with whether our ellipsoid certified regionR2 is “superior” to the isotropic `2-ball without quantifying it. A natural solution is to directly compare the volumes of the certified regions. Since the volume of an ellipsoid given by R2 is V(R2) = rn2 √ πn/Γ(n/2+1) ∏n i=1 σi (Kendall, 2004), we directly compare the proxy
radius R̃ defined for R2 as R̃ = r2 n √∏n
i σi, since larger R̃ correspond to certified regions with larger volumes. Note that R̃, which is the nth root of the volume up to a constant factor, can be seen as a generalization to the certified radius in the case when σi = σ ∀i.

heading: 5.2 EVALUATING GENERALIZED CROSS-POLYTOPE CERTIFICATES
text: Comparing `1−Balls to `Λ1−Generalized Cross-Polytopes (Specialization of Definition 1). Consider the certificates S1 = {δ : ‖δ‖1 ≤ λ̃r1}, S2 = {δ : ‖δ‖Λ,1 = ‖Λ−1δ‖1 ≤ r2}, and S3 = {δ : ‖δ‖1 ≤ mini λir2}, where we take Λ = diag({λi}ni=1). Note that since S2 ⊇ S3, then as per Definition 1, it suffices that S3 ⊇ S1 (i.e. mini λir2 ≥ λ̃r1) to say that the anisotropic generalized cross-polytope S2 is superior to the isotropic `1-ball S1.
Quantifying `Λ1 Certificates. Following the approach proposed in the `Σ2 case, we quantitatively compare the generalized cross-polytope certification of Corollary 2 to the `1 certificate through the volumes of the two regions. We first present the volume of the generalized cross-polytope.
Proposition 4. V ( {δ : ‖Λ−1δ‖1 ≤ r} ) = (2r) n
n! ∏ i λi.
Following this definition, we define the proxy radius for S2 in this case to be R̃ = r2 n √∏n
i=1 λi. As with the `2 case, larger R̃ correspond certified regions with larger volumes. As in the ellipsoid case, R̃ can be seen as a generalization to the certified radius when λi = λ ∀i.

heading: 6 ANCER: SAMPLE-WISE VOLUME MAXIMIZATION FOR ANISOTROPIC CERTIFICATION
text: Given the results from the previous sections, we are now equipped to certify anisotropic regions, in particular ellipsoids and generalized cross-polytopes. As mentioned in Section 4, these regions are generally defined as R = {δ : ‖δ‖Θ,p ≤ rp} for a given parameter of the smoothing distribution Θ = diag ({θi}ni=1), an `p-norm (p ∈ {1, 2}), and a gap value of rp ∈ R+. At this point, one could simply take an anisotropic distribution with arbitrarily chosen parameters Θ and certify a trained network at any input point x, in the style of what was done in the previous randomized smoothing literature with isotropic distributions. However, the choice of Θ is more complex in the anisotropic case. A fixed choice of anisotropic Θ could severely underperform the isotropic case – take, for example, the anisotropic distribution of Figure 1d applied to the input of Figure 1c.
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 a sample-wise fashion) so as to maximize the resulting certificate. The goal of the optimization in Alfarra et al. (2020) is, at a point x, to maximize the isotropic `2 region described in Section 4.1 (i.e. {δ : ‖δ‖2 ≤ σxrp(x, σx))}), where rp is the gap and a function of x and σx ∈ R+. In the isotropic `p case, this generalizes to maximizing the region {δ : ‖δ‖p ≤ θxrp (x, θx)}, which can be achieved by maximizing radius θxrp (x, θx) through θx ∈ R+, obtaining r∗iso (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 superset condition with respect to the maximum isotropic `2 radius, r∗iso. In the case of the ellipsoids and generalized cross-polytopes as presented in Sections 5.1 and 5.2, respectively, ANCER’s optimization problem can be written as:
arg max Θx
rp (x,Θx) n √∏ i θxi s.t. min i θxi r p (x,Θx) ≥ r∗iso (1)
where rp (x,Θx) 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 Θx, i.e. gΘx , is robust by definition as presented in Section 4, the certification of the overall datadependent classifier is not necessarily sound due to the optimization procedure for each x. This is a known issue in certifying data-dependent classifiers, and is addressed by Alfarra et al. (2020) through the use of a memory-based 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 Alfarra et al. (2020), it incurs limitations on memory and runtime complexity. The main limitations of the memory-based certification are outlined in Appendix E of Alfarra et al. (2020). The anisotropic case increases on 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 a single procedure for both certification and inference in contrast with the fixed σ setting from Cohen et al. (2019). While the linear runtime dependency on memory size might appear daunting for the deployment of such a 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-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 is not a critical issue.
A further limitation of the memorization procedure has to do with the impact of the order in which inputs are certified on the overall statistics obtained. Within a memory-based framework, certifying x2 with x1 in memory can be different from certifying x1 with x2 in memory if they intersect. In practice, given the low number of intersections observed with the original certified regions, this effect was almost negligible in the results presented in Section 7. For fairness of comparison with non-memory based methods, we report "worst-case" results for ANCER in which we abstain from deciding whenever an intersection of two certified regions occurs.

heading: 7 EXPERIMENTS
text: We now study the empirical performance of ANCER to obtain `Σ2 , ` Λ 1 , `2 and `1 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 `2 and `1 certification when compared to certification baselines that smooth using a fixed isotropic σ (Fixed σ) (Cohen et al., 2019; Yang et al., 2020; Salman et al., 2019a; Zhai et al., 2019) or a data-dependent and memory-based isotropic one (Isotropic DD) (Alfarra et al., 2020); and (ii) a significant improvement in terms of the `Σ2 and ` Λ 1 -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 a 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 rp(x,Θx) is estimated at each iteration using 100 noise samples per test point (see Appendix C) and Θx in Equation (1) is initialized with the Isotropic DD solution from Alfarra et al. (2020). Further details of the setup can be found in Appendix E.
As in previous works, `p certified accuracy at radius R is defined as the portion of the test set Dt for which the smooth classifier correctly classifies with an `p certification radius of at least R. In a similar fashion, we define the anisotropic `Σ2 /` Λ 1 certified accuracy at a proxy radius of R̃ (as defined in Section 5) to be the portion of Dt in which the smooth classifier classifies correctly with an `Σ2 /` Λ 1 -norm certificate of an n
th root volume of at least R̃. We also report average certified radius (ACR) defined as Ex,y∼Dt [Rx1(g(x) = y)] (Alfarra et al., 2020; Zhai et al., 2019) as well as average certified proxy radius (ACR̃) defined as Ex,y∼Dt [R̃x1(g(x) = y)], where Rx and R̃x denote the radius and proxy radius at x with a true label y for a smooth classifier g. Recall that in the isotropic case, the proxy radius is, by definition, the same as the radius for a given `p-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 certified accuracy plots, ACR and ACR̃ per radius across σ, 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 (`2 AND `Σ2 -NORM CERTIFICATES)
We perform the comparison of `2-ball vs. `Σ2 -ellipsoid certificates via Gaussian smoothing using networks 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 σ ∈ {0.12, 0.25, 0.5, 1.0} for CIFAR-10, and ResNet50 using σ ∈ {0.25, 0.5, 1.0} for ImageNet. For details of the training
procedures, see Appendix E.1. Figure 2 plots top-1 certified accuracy as a function of the `2 radius (top) and of the `Σ2 -norm proxy radius (bottom) per trained network and dataset, while Table 1 presents an overview of the certified accuracy at various `2 radii, as well as `2 ACR and `Σ2 -norm ACR̃. Recall that, following the considerations in Section 5.1, the `2 certificate obtained through ANCER is the maximum enclosed isotropic `2-ball in the `Σ2 ellipsoid.
First, we note that sample-wise certification (Isotropic DD and ANCER) achieves higher certified accuracy than fixed σ across the board. This mirrors the findings in Alfarra et al. (2020), since certifying with a fixed σ for all samples struggles with the robustness/accuracy trade-off first mentioned in Cohen et al. (2019), whereas the data-dependent solutions explicitly optimize σ per sample to avoid it. More importantly, ANCER achieves new state-of-the-art `2 certified accuracy at most radii in Table 1, e.g. at radius 0.5 ANCER brings certified accuracy to 77% (from 66%) and 70% (from 62%) on CIFAR-10 and ImageNet, respectively, yielding relative percentage improvements in ACR between 13% and 47% when compared to Isotropic DD. While the results are significant, it might not be immediately clear why maximizing the volume of an ellipsoid with ANCER results in a larger maximum enclosed `2-ball certificate in `Σ2 ellipsoid when compared to optimizing the `2-ball with Isotropic DD. We explore this phenomenon in Appendix G.3.
As expected, ANCER substantially improves `Σ2 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 `2 and `Σ2 , establish that ANCER certifies the `2-ball region obtained by previous approaches, in addition to a much larger region captured by the `Σ2 certified accuracy and ACR̃, and therefore is, according to Definition 1, generally superior to the Isotropic DD one.
7.2 GENERALIZED CROSS-POLYTOPE CERTIFICATION (`1 AND `Λ1 -NORM CERTIFICATES)
To investigate `1-ball vs. `Λ1 -generalized cross-polytope certification via Uniform smoothing, we compare ANCER to the `1 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 σ levels between 0.15 and 3.5 on CIFAR-10 (WideResNet40) and ImageNet (ResNet50) and due to limited computational resources, we perform the analysis on a 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.
Table 2: Comparison of top-1 certified accuracy at different `1 radii, `1 average certified radius (ACR) and `Λ1 average certified proxy radius (ACR̃) obtained by using the isotropic σ used for training the networks (Fixed σ); the isotropic data-dependent (Isotropic DD) optimization scheme from Alfarra et al. (2020); and ANCER’s data-dependent anisotropic optimization.
CIFAR-10 Certification Accuracy @ `1 radius (%) `1 ACR `Λ1 ACR̃0.0 0.25 0.5 0.75 1.0 1.5 2.0
RS4A Yang et al. (2020) Fixed σ 92 83 75 71 46 0 0 0.775 0.775 Isotropic DD 92 89 82 76 58 6 2 0.946 0.946 ANCER 92 90 84 80 63 6 2 0.980 1.104
ImageNet
RS4A Yang et al. (2020) Fixed σ 78 73 67 63 0 0 0 0.683 0.683 Isotropic DD 79 76 70 65 46 0 0 0.729 0.729 ANCER 78 76 70 66 48 0 0 0.730 1.513
0.0 0.5 1.0 1.5 2.0 1 radius
0.0
0.2
0.4
0.6
0.8
C er
tif ie
d ac
cu ra
cy
CIFAR-10 - RS4A Fixed Isotropic DD ANCER
0.00 0.25 0.50 0.75 1.00 1 radius
0.0
0.2
0.4
0.6
0.8
C er
tif ie
d ac
cu ra
cy
ImageNet - RS4A
Fixed Isotropic DD ANCER
0 1 2 1 proxy radius
0.0
0.2
0.4
0.6
0.8
C er
tif ie
d ac
cu ra
cy
Fixed Isotropic DD ANCER
0 1 2 3 1 proxy volume
0.0
0.2
0.4
0.6
0.8
C er
tif ie
d ac
cu ra
cy
Fixed Isotropic DD ANCER
Figure 3: Distribution of top-1 certified accuracy as a function of `1 radius (top) and `Λ1 -norm proxy radius (bottom) obtained by different certification methods on CIFAR-10 and ImageNet.
Figure 3 shows the top-1 certified accuracy as a function of the `1 radius (top) and of the `Λ1 -norm proxy radius (bottom) for RS4A, and Table 2 shows an overview of the certified accuracy at various `1 radii, as well as `1 ACR and `Λ1 ACR̃.
As with the ellipsoid case, we notice that ANCER outperforms both Fixed σ and Istropic DD for most `1 radii, establishing new state-of-the-art results in CIFAR-10 at radii 0.5 and 1.0, and ImageNet at radii 0.5 (compared to previous results reported in Yang et al. (2020)). Once more and as expected, ANCER significantly improves the `Λ1 ACR̃ for all radii, pointing to substantially larger cerficates than the isotropic case. These results also establish that ANCER certifies the `1-ball region obtained by previous work, in addition to the larger region obtained by the `Λ1 certificate, and thus we can consider it superior (with respect to Definition 1) to Isotropic DD.
7.3 CERTIFICATION RUNTIME Table 3: Average certification time for each sample per architecture used: (a) ResNet18 (`2, `Σ2 on CIFAR-10), (b) WideResNet40 (`1, `Λ1 on CIFAR-10), and (c) ResNet50 (ImageNet).
Fixed σ Isotropic DD ANCER
(a) 1.6s 1.8s 2.7s (b) 7.4s 9.5s 11.5s (c) 109.5s 136.0s 147.0s
The certification procedures of Isotropic DD and ANCER tradeoff improved certified accuracy for runtime, since they require a sample-wise optimization to be run prior to the CERTIFY step described in Cohen et al. (2019), and a memory-based step as per Alfarra et al. (2020). The runtime of the optimization and certification procedures is roughly equal for `1, `2, `Σ2 and ` Λ 1 certification, and mostly depends on network architecture. As such, we report the average certification runtime for a test set sample on an NVIDIA Quadro RTX 6000 GPU for Fixed σ, 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.

heading: 8 CONCLUSION
text: In this work, we lay the theoretical foundations for anisotropic certification through a simple analysis, propose a metric for comparing general robustness certificates, and introduce ANCER, a certification procedure that estimates the parameters of the anisotropic smoothing distribution to maximize the certificate. Our experiments show that ANCER achieves state-of-the-art `1 and `2 certified accuracy on CIFAR-10 and ImageNet. Our anisotropic analysis enables further insights about the boundary of the safe region around an input sample, as compared to its isotropic counterpart.

heading: 9 REPRODUCIBILITY STATEMENT
text: 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 is 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 in Python and instructions to reproduce our results as part of the supplementary material.

heading: 10 ETHICS STATEMENT
text: We confirm that no results in this paper involved studies on human subjects, and all experiments used open-source datasets.

heading: A QUALITATIVE MOTIVATION OF ANISOTROPIC CERTIFICATION
text: A.1 VISUALIZING CIFAR-10 OPTIMIZED ISOTROPIC VS. ANISOTROPIC CERTIFICATES
To extend the illustration in Figure 1 to a higher dimensional input, we now analyze an example of the isotropic `2 certification of randomized smoothing with N (0, σ2I), where σ is optimized per input Alfarra et al. (2020), against ANCER, certifying an anisotropic region characterized by a diagonal `Σ2 -norm. To do so, we consider a CIFAR-10 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-Dezfooli et al. (2019), we compute the Hessian of fy(x) with respect to x where y is the true label for x with f classifying x correctly, i.e. y = arg maxi f
i(x). In addition to the Hessian, we also compute its eigenvector decomposition, yielding the eigenvectors {νi}, i ∈ {1, . . . , 3072} ordered in descending order of the absolute value of the respective eigenvalues. In Figure 4a, we show the
projection of the landscape of fy in the highest curvature directions, i.e. ν1 and ν2. Note that the isotropic certification, much as in Figure 1c, in these 2 dimensions is nearly optimal when compared to the anisotropic region. However, if we take the same projection with respect to the eigenvectors with the lowest and highest eigenvalues, i.e. ν1 and ν3072, the advantages of the anisotropic certification become clear as shown in Figure 4b.
A.2 VISUALIZING SAFE IMAGES IN OPTIMIZED ANISOTROPIC CERTIFICATES
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 a series of test set images x, as well as practically indistinguishable x+ δ images which are not inside the optimal certified isotropic `2-balls for each input sample, yet are within the anisotropic certified regions. This showcases the merits of using anisotropic certification for characterizing larger safe regions.

heading: B ANISOTROPIC CERTIFICATION AND EVALUATION PROOFS
text: Proposition 1 (restatement). Consider a differentiable function g : Rn → R. If supx‖∇g(x)‖∗ ≤ L where ‖ · ‖∗ has a dual norm ‖z‖ = maxx z>x s.t. ‖x‖∗ ≤ 1, then g is L-Lipschitz under norm ‖ · ‖∗, that is |g(x)− g(y)| ≤ L‖x− y‖.
Proof. Consider some x, y ∈ Rn and a parameterization in t as γ(t) = (1 − t)x + ty ∀t ∈ [0, 1]. Note that γ(0) = x and γ(1) = y. By the Fundamental Theorem of Calculus we have:
|g(y)− g(x)| = |g(γ(1))− g(γ(0))| = ∣∣∣∣∫ 1
0
dg(γ(t))
dt dt ∣∣∣∣ = ∣∣∣∣∫ 1 0 ∇g>∇γdt ∣∣∣∣ ≤ ∫ 1 0 ∣∣∇g>∇γ∣∣ dt ≤ ∫ 1
0
‖∇g(x)‖∗‖∇γ(t)‖dt ≤ L‖y − x‖
Theorem 1 (restatement). Let g : Rn → RK , gi be L-Lipschitz continuous under norm ‖ · ‖∗ ∀i ∈ {1, . . . ,K}, and cA = arg maxi gi(x). Then, we have arg maxi gi(x + δ) = cA for all δ satisfying:
‖δ‖ ≤ 1 2L
( gcA(x)−max
c gc 6=cA(x)
) .
Proof. Take cB = arg maxc g c6=cA(x). By Proposition 1, we get:
|gcA(x+ δ)− gcA(x)| ≤ L‖δ‖ =⇒ gcA(x+ δ) ≥ gcA(x)− L‖δ‖ |gcB (x+ δ)− gcB (x)| ≤ L‖δ‖ =⇒ gcB (x+ δ) ≤ gcB (x) + L‖δ‖
By subtracting the inequalities and re-arranging terms, we have that as long as gcA(x) − L‖δ‖ > gcB (x) + L‖δ‖, i.e. the bound in the Theorem, then gcA(x + δ) > gcB (x + δ), completing the proof.
Proposition 2 (restatement). Consider gΣ(x) = E ∼N (0,Σ) [f(x+ )]. Φ−1(gΣ(x)) is 1-Lipschitz (i.e. L = 1) under the ‖ · ‖Σ−1,2 norm.
Proof. To prove Proposition 2, one needs to show that Φ−1(giΣ(x)) ∀i is 1-Lipschitz under the ‖ · ‖Σ−1,2 norm. For ease of notation, we drop the superscript giΣ and use only g. We want to show that ‖∇Φ−1(gΣ(x))‖Σ−1,2 = ‖Σ
1/2∇Φ−1(gΣ(x))‖2 ≤ 1. Following the argument presented in Salman et al. (2019a), it suffices to show that, for any unit norm direction u and p = gΣ(x), we have:
u>Σ 1 2∇gΣ(x) ≤ 1√ 2π exp
( −1
2 (Φ−1(p))2
) . (2)
We start by noticing that:
u>Σ 1 2∇gΣ(x) =
1
( √ 2π)n √ |Σ| ∫ Rn f(t)u>Σ 1 2 Σ−1(t− x) exp ( −1 2 (x− t)Σ−1(x− t) ) dnt
= Es∼N (0,I)[f(x+ Σ 1 2 s)u>s] = Ev∼N (0,Σ)[f(x+ v)u>Σ− 1 2 v].
We now need to find the optimal f∗ : Rn → [0, 1] that satisfies gΣ(x) = Ev∼N (0,Σ)[f(x+ v)] = p while maximizing the left hand size Ev∼N (0,Σ)[f(x+ v)u>Σ− 1 2 v]. We argue that the maximizer is the following function: f∗(x+ v) = 1 { u>Σ− 1 2 v ≥ −Φ−1(p) } .
To prove that f∗ is indeed the optimal maximizer, we first show feasibility. (i): It is clear that f∗ : Rn → [0, 1]. (ii) Note that:
Ev∼N (0,Σ)) [ 1 { u>Σ− 1 2 v ≥ −Φ−1(p) }] = Px∼N (0,1)(x ≥ −Φ−1(p)) = 1− Φ(−Φ−1(p)) = p.
To show the optimality of f∗, we show that it attains the right upper bound: Ev∼N (0,Σ)) [ u>Σ− 1 2 v1 { u>Σ− 1 2 v ≥ −Φ−1(p) }] = Ex∼N (0,1) [ x1 { x ≥ −Φ−1(p) } ] =
1√ 2π ∫ ∞ −Φ−1(p) x exp ( −1 2 x2 ) dx
= 1√ 2π exp
( −1
2 (Φ−1(p))2 ) obtaining the bound from Equation (2), and thus completing the proof.
Proposition 3 (restatement). Consider gΛ(x) = E ∼U [−1,1]n [f(x + Λ )]. The classifier giΛ ∀i is 1/2-Lipschitz (i.e. L = 1/2) under the ‖Λx‖∞ norm.
Proof. We begin by observing that the dual norm of ‖x‖Λ,1 = ‖Λ−1x‖1 is ‖x‖∗ = ‖Λx‖∞, since:
max ‖Λ−1x‖1≤1 x>y = max ‖z‖1≤1 y>Λz = ‖Λy‖∞.
Without loss of generality, we analyze ∂gi/∂x1. Let x̂ = [x2, . . . , xn] ∈ Rn−1, then:
λ1∂g i
∂x1 = λ1 (2λ)n ∂ ∂x1 ∫ [−1,1]n−1 ∫ 1 −1 f i(x1 + λ1 1, x̂+ Λ̂̂)d 1d n−1̂
= 1
2n ∫ [−1,1]n−1 (f i(x1 + 1, x̂+ Λ̂̂)− f i(x1 − 1, x̂+ Λ̂̂))dn−1̂
Thus,∣∣∣∣λ1∂gi∂x1 ∣∣∣∣ ≤ 12n∏nj=2 λj ∫ [−1,1]n−1 ∣∣∣f i(x1 + 1, x̂+ Λ̂̂)− f i(x1 − 1, x̂+ Λ̂̂)∣∣∣ dn−1̂ ≤ 1 2 .
The second and last steps follow by the change of variable t = x1+λ1 1 and Leibniz rule. Following a symmetric argument, ∣∣λj∂gi/∂xj∣∣ ≤ 1/2 ∀i resulting in having ‖Λ∇gi(x)‖∞ = maxi λi ∣∣∂gi/∂xi∣∣ ≤ 1/2 ∀i concluding the proof. Proposition 4 (restatement). V ( {δ : ‖Λ−1δ‖1 ≤ r} ) = (2r) n
n! ∏ i λi.
Proof. Take A = rΛ−1 = diag(1/rλ1, . . . , 1/rλn) = diag(a1, . . . , an). We can re-write the region as {x : ∑ i ai|xi| ≤ 1}, from which it is clear to see that this region is an origin centered, axis-aligned simplex with the set of vertices V = {±1/aiei}ni=1, where ei is the standard basis vector i.
Define the sets of vertices Vt = V \ {−1/anen} and Vb = V \ {1/anen}. Given the symmetry around the origin, each of these sets defines an n-dimensional hyperpyramid with a shared base Bn−1 given by the n − 1-dimensional hyperplane defined by all vertices where xn = 0, and an apex at the vertex 1/anen (or −1/anen in the case of Vb). The volume of each of these n − 1- dimensional hyperpyramids is given by V(Bn−1)/nan (Kendall (2004)), yielding a total volume of Vn = 2 n 1 an V(Bn−1). The same argument can be applied to compute V(Bn−1) which is a union of two n− 1-dimensional hyperpyramids. This forms a recursion that completes the proof.
Proof. (Alternative Proof.) We consider the case that Λ−1 is a general positive definite matrix that is not necessarily diagonal. Note that V ( {δ : ‖Λ−1δ‖1 ≤ r} ) = V ( {δ : ‖(rΛ)−1δ‖1 ≤ 1} ) = rn|Λ|V ({δ : ‖δ‖1 ≤ 1}) where |rΛ| denotes the determinant. The last equality follows by the volume of a set under a linear map and noting that {δ : ‖(rΛ)−1δ‖1 ≤ 1} = {rΛδ : ‖δ‖1 ≤ r}. At last, {δ : ‖δ‖1 ≤ 1} can be expressed as the disjoint union of 2n simplexes. Thus, we have V ( {δ : ‖Λ−1δ‖1 ≤ r} ) = (2r) n /n!|Λ| since the volume of a simplex is 1/n! completing the proof.
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 Λ−1 ∈ Rn×n, we have the following:( 2r
n
)n V ( Z(Λ) ) ≤ V ( {δ : ‖Λ−1δ‖1 ≤ r} ) ≤ (2r)nV (Z(Λ))
where V (Z(Λ)) = √ |Λ>Λ| which is the volume of the zonotope with a generator matrix Λ.
Proof. Let S1 = {δ : ‖Λ−1δ‖1 ≤ r}, S∞ = {δ : ‖Λ−1δ‖∞ ≤ r} and Sn∞ = {δ : n‖Λ−1δ‖∞ ≤ r}. Since ‖Λ−1δ‖∞ ≤ ‖Λ−1δ‖1 ≤ n‖Λ−1δ‖∞, then S∞ ⊇ S1 ⊇ Sn∞. Therefore, we have V(S∞) ≥ V(S1) ≥ V(Sn∞). At last note that, Sn∞ = { rnΛδ : ‖δ‖∞ ≤ 1} and that with the change of variables δ = 2u−1n where 1n is a vector of all ones, we have Sn∞ = Z ( 2r n Λ ) ⊕−rn Λ1n where⊕ is a Minkowski sum and noting that rnΛ1n is a single point in R n. Therefore, V ( Z ( 2r n Λ ) ⊕ −rn Λ1n ) = (2r/n) n V (Z(Λ)). 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 G such that:
G({αi,Σi}Ki=1) := K∑ i=1 αiN (0,Σi), s.t. ∑ i αi = 1, 0 < αi ≤ 1 (3)
Given f and as per the recipe described in Section 4, we are interested in the Lipschitz constant of the smooth classifier gG(x) = (f ∗ G)(x) = ∑K i αigΣi = ∑K i αi(f ∗ N (0,Σi)) = ∑ i αigΣi(x) where gΣi is defined as in the Gaussian case.
Note the weaker bound when compared to Proposition 2, for each of the Gaussian components presented in the following proposition.
Proposition 6. gΣ is √ 2/π-Lipschitz under ‖.‖Σ−1,2 norm.
Proof. Following a similar argument to the proof of Proposition 2, we get:
u>Σ 1 2∇gΣ(x) ≤
1 (2π)n/2 √ |Σ| ∫ Rn |u>Σ− 12 (t− x)| exp ( −1 2 (x− t)>Σ−1(x− t) ) dnt
= Es∼N (0,I) [ |u>s| ] = Ev∼N (0,1) [|v|] = √ 2/π.
With Proposition 6, we obtain a Lipschitz constant for a Gaussian mixture smoothing distribution as: Proposition 7. gG is √ π/2-Lipschitz under ‖δ‖B−1,2 norm, where B−1 = ∑K i αiΣ −1 i .
Proof. |gG(x+ δ)− gG(x)| ≤ ∑ i αi|gΣi(x+ δ)− gΣi(x)|
≤ √ π
2 ∑ i αi‖δ‖Σi,2 ≤ √ π 2 √√√√δ>(∑ i αiΣ −1 i ) δ = √ π 2 ‖δ‖B,2,
Obtained by first applying the triangle inequality, then Proposition 2 followed by Jensen’s inequality.
Thus yielding the following certificate by combining Proposition 7 and Theorem 1.
Corollary 3. Let cA = arg maxi gG(x) , then arg maxi giG(x+ δ) = cA for all δ satisfying:
‖δ‖B,2 ≤ 1√ 2π ( gcAG (x)−maxc g c6=cA G (x) ) .
where B−1 = ∑K i αiΣ −1 i .

heading: C ANCER OPTIMIZATION
text: In this section we detail the implementation choices required to solving Equation (1). For ease of presentation, we restate the ANCER optimization problem (with Θx = diag({θxi }ni=1)):
arg max Θx
rp (x,Θx) n √∏ i θxi s.t. min i θxi r p (x,Θx) ≥ r∗iso,
where rp (x,Θx) is the gap value under the anisotropic smoothing distribution, and r∗iso is the optimal isotropic radius, i.e. θ̄xrp(x, θ̄x) for θ̄x ∈ R+. This is a nonlinear constrained optimization problem that is challenging to solve. As such, we relax it, and solve instead:
arg max Θx
rp (x,Θx) n √∏ i θxi + κmin i θxi r p (x,Θx) s.t. θxi ≥ θ̄x
given a hyperparameter κ ∈ R+. While the constraint θxi ≥ θ̄x is not explicitly required to enforce the superset condition over the isotropic case, it proved itself beneficial from an empirical perspective. To sample from the distribution parameterized by Θx (in our case, either a Gaussian or Uniform), we 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.
A standalone implementation for the ANCER optimization stage is presented in Listing 1, whereas the full code integrated in our code base is 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 torch from torch.autograd import Variable from torch.distributions.normal import Normal
class Certificate(): def compute_proxy_gap(self, logits: torch.Tensor):
raise NotImplementedError
def sample_noise(self, batch: torch.Tensor, repeated_theta: torch.Tensor): raise NotImplementedError
def compute_gap(self, pABar: float): raise NotImplementedError
class L2Certificate(Certificate): def __init__(self, batch_size: int, device: str = "cuda:0"):
self.m = Normal(torch.zeros(batch_size).to(device), torch.ones(batch_size).to(device)) self.device = device self.norm = "l2"
def compute_proxy_gap(self, logits: torch.Tensor): return self.m.icdf(logits[:, 0].clamp_(0.001, 0.999)) - \
self.m.icdf(logits[:, 1].clamp_(0.001, 0.999))
def sample_noise(self, batch: torch.Tensor, repeated_theta: torch.Tensor): return torch.randn_like(batch, device=self.device) * repeated_theta
def compute_gap(self, pABar: float): return norm.ppf(pABar)
class L1Certificate(Certificate): def __init__(self, device="cuda:0"):
self.device = device self.norm = "l1"
def compute_proxy_gap(self, logits: torch.Tensor): return logits[:, 0] - logits[:, 1]
def sample_noise(self, batch: torch.Tensor, repeated_theta: torch.Tensor): return 2 * (torch.rand_like(batch, device=self.device) - 0.5) * repeated_theta
def compute_gap(self, pABar: float): return 2 * (pABar - 0.5)
def ancer_optimization( model: torch.nn.Module, batch: torch.Tensor, certificate: Certificate, learning_rate: float, isotropic_theta: torch.Tensor, iterations: int, samples: int, kappa: float, device: str = "cuda:0"):
"""Optimize batch using ANCER, assuming isotropic initialization point.
Args: model: trained network batch: inputs to certify around certificate: instance of desired certification object learning_rate: optimization learning rate for ANCER isotropic_theta: initialization isotropic value per input in batch iterations: number of iterations to run the optimization samples: number of samples per input and iteration kappa: relaxation hyperparameter """ batch_size = batch.shape[0] img_size = np.prod(batch.shape[1:])
# define a variable, the optimizer, and the initial sigma values theta = Variable(isotropic_theta, requires_grad=True).to(device) optimizer = torch.optim.Adam([theta], lr=learning_rate) initial_theta = theta.detach().clone()
# reshape vectors to have ‘‘samples‘‘ per input in batch new_shape = [batch_size * samples] new_shape.extend(batch[0].shape) new_batch = batch.repeat((1, samples, 1, 1)).view(new_shape)
# solve iteratively by projected gradient ascend for _ in range(iterations):
theta_repeated = theta.repeat(1, samples, 1, 1).view(new_shape)
# Reparameterization trick noise = certificate.sample_noise(new_batch, theta_repeated) out = model(
new_batch + noise ).reshape(batch_size, samples, -1).mean(dim=1)
vals, _ = torch.topk(out, 2) gap = certificate.compute_proxy_gap(vals)
prod = torch.prod( (theta.reshape(batch_size, -1))**(1/img_size), dim=1) proxy_radius = prod * gap
radius_maximizer = - ( proxy_radius.sum() + kappa * (torch.min(theta.view(batch_size, -1), dim=1).values*gap).sum() ) radius_maximizer.backward() optimizer.step()
# project to the initial theta with torch.no_grad():
torch.max(theta, initial_theta, out=theta)
return theta
Listing 1: Python implementation of the ANCER optimization routine using PyTorch Paszke et al. (2019)

heading: D MEMORY-BASED CERTIFICATION FOR ANCER
text: To guarantee the soundness of the ANCER classifier, we use an adapted version of the data-dependent memory-based solution presented in Alfarra et al. (2020). The modified algorithm involves a post-processing certification step that obtains adjusted certification statistics based on the memory
procedure from Alfarra et al. (2020) (see the original paper for more details). We present an adapted version to ANCER of this post-processing memory-based step in Algorithm 1.
Algorithm 1: Memory-Based Certification Input: input point xN+1, certified regionRN+1, prediction CN+1, and memoryM Result: Prediction for xN+1 and certified region at xN+1 that does not intersect with any certified region inM. for (xi, Ci,Ri) ∈M do
if CN+1 6= Ci then if xN+1 ∈ Ri then
return ABSTAIN, 0 else if MaxIntersect(RN+1,Ri) and Intersect(RN+1,Ri) then R′N+1 = LargestOutSubset(Ri,RN+1); RN+1 ← R′N+1;
end add (xN+1, CN+1,RN+1) toM; return CN+1,RN+1;
Note that the proposed certified region RN+1 emerges from our certification bounds presented in Sections 4.1 and 4.2. There are a few differences between our proposed Algorithm 1 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 regionRN+1 when there exists an i such that xN+1 ∈ Ri with a different class prediction, i.e. (LargestInSubset in Alfarra et al. (2020)) due to the complexity of 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 ease the computational burden of the Intersect function, we introduce and instantiate the function MaxIntersect first which checks whether the `p-ball over-approximation of the regionRN+1 intersects with a `p over-approximation of Ri. This follows since when the `p balls over-approximation to the anisotropic regions RN+1 and Ri do not intersect, then RN+1 and Ri do not intersect either. Only in cases in which those over-approximation regions intersect, we run the more expensive Intersect procedure. We present practical implementations for MaxIntersect, Intersect and LargestOutSubset for the ellipsoids and generalized cross-polytopes considered in this paper.
D.1 IMPLEMENTING MAXINTERSECT(RA, RB) IN THE ELLIPSOID AND GENERALIZED CROSS-POLYTOPE CASES
Given the two regionsRA andRB, consider `p-ball approximations of those regions,RB̃ = {x ∈ Rn : ‖x− a‖p ≤ ra} andRB̃ = {x ∈ Rn : ‖x− b‖p ≤ rb} such thatRA ⊆ RÃ andRB ⊆ RB̃. Lemma 1. If ‖a− b‖p > ra + rb, thenRA ∩RB = ∅.
Proof. For the sake of contradiction, let ‖a− b‖p > ra + rb and x ∈ RÃ ∩RB̃. Then, we have that ‖x− a‖ ≤ ra and ‖x− b‖ ≤ rb. However:
ra + rb < ‖a− b‖p ≤ ‖x− a‖p + ‖x− b‖p ≤ ra + rb, forming a contradiction. Thus,RÃ ∩RB̃ = ∅, which in turn impliesRA ∩RB = ∅ sinceRA and RB are subsets ofRÃ andRB̃, respectively.
This forms a fast, maximum intersection check for ellipsoids, i.e. p = 2, and generalized crosspolytopes, i.e. p = 1. The MaxIntersect function returns False if ‖a − b‖p > ra + rb, and True otherwise.
D.2 IMPLEMENTING INTERSECT(RA, RB) IN THE ELLIPSOID CASE
The problem of efficiently checking if two ellipsoids intersect is not trivial. We rely on the work of Ros et al. (2002); Gilitschenski & Hanebeck (2012) with missing proofs from Gilitschenski & Hanebeck (2012) for completeness.
Lemma 2. LetRA = {x ∈ Rn : (x−a)>A(x−a) ≤ 1} andRB = {x ∈ Rn : (x−b)>B(x−b) ≤ 1} define two ellipsoids centered at a and b, respectively. We have thatR = {x : t(x− a)>A(x− a) + (1− t)(x− b)>B(x− b) ≤ 1} for any t ∈ [0, 1] satisfiesRA ∩RB ⊆ R ⊆ RA ∪RB.
Proof. By considering the convex combination of the left-hand side of the inequalities defining the regionsRA andRB, it becomes obvious that x ∈ RA ∩RB =⇒ x ∈ R, concluding the left side of the property. As for the right side, it suffices to show that if x /∈ RA and x ∈ R then x ∈ RB and, similarly, that if x /∈ RB and x ∈ R then x ∈ RA. We show the first case since the second follows by symmetry. Without loss of generality, we assume that a = b = 0n. Now, let x be such that x>Ax > 1 and tx>Ax+ (1− t)x>Bx ≤ 1 since x /∈ RA and x ∈ R. Then, since x ∈ R, we have that (1− t)x>Bx ≤ 1− tx>Ax ≤ 1 since x>Ax > 1 which implies that x ∈ RB.
Note that the previous result holds without loss of generality when for the radius 1 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 setR is equivalent to the following ellipsoidR = {x : (x−m)>Et(x−m) ≤ K(t)} where Et = tA+(1−t)B,m = E−1t (tAa+ (1− t)Bb), andK(t) = 1−ta>Aa−(1−t)b>Bb+ m>Etm.
Proof.
t(x− a)>A(x− a) + (1− t)(x− b)>B(x− b) ≤ 1 ⇔x> (tA + (1− t)B)︸ ︷︷ ︸
Et
x− 2x> (tAa+ (1− t)Bb)︸ ︷︷ ︸ Etm ≤ 1− ta>Aa− (1− t)b>Bb
⇔(x−m)>Et(x−m) ≤ 1− ta>Aa− (1− t)b>Bb+m>Etm
The last equality follows by adding and subtracting m>Etm and concluding the proof.
Proposition 8. The set of points satisfyingR for t ∈ (0, 1) is either an empty set, a single point, or the ellipsoidR.
Proof. We first observe that since A and B are positive definite, then Et is positive definite. Then observe that for a choice of t ∈ (0, 1) such that K(t) < 0, the set R is an empty set, and since R ⊇ RA ∩ RB, the two sets do not intersect. If K(t) = 0, then the only point satisfying R is the center at m. Following a similar argument, then the two ellipsoids intersect at a point. At last for a choice of t such that K(t) > 0, thenR defines an ellipsoid.
As per Theorem 8, it suffices to find some t ∈ [0, 1] under which K(t) < 0 to guarantee that the ellipsoids do not intersect. To that end, we solve the following convex optimization problem: t∗ = argmint∈[0,1]K(t) and check the condition if K(t
∗) < 0. Moreover, as shown by Ros et al. (2002); Gilitschenski & Hanebeck (2012) K(t) is convex in the domain t ∈ (0, 1). With several algebraic manipulations, one can show that K(t) has the following equivalent forms:
K(t) = 1− ta>Aa− (1− t)b>Bb+m>Etm K(t) = 1− t(1− t)(b− a)>BE−1t A(b− a)
K(t) = 1− (b− a)> ( 1
1− t B−1 +
1 t A−1
)−1 (b− a)
Observe that for ANCER, we have that both A and B to be diagonals with diagonal elements {Aii}ni=1 and {Bii}ni=1, respectively, resulting in the following simple form for K(t):
K(t) = 1− n∑ i=1 (bi − ai)2 t(1− t)AiiBii tAii + (1− t)Bii .
The Intersect function in the ellipsoid case returns False if there exists a t ∈ (0, 1) such that K(t) < 0, i.e. ellipsoids do not intersect, and True otherwise.
D.3 IMPLEMENTING INTERSECT(RA, RB) IN THE GENERALIZED CROSS-POLYTOPE CASE
Let RA and RB be two generalized cross-polytopes RA = {x ∈ Rn : ‖A(x − a)‖1 ≤ 1} and RB = {x ∈ Rn : ‖B(x− b)‖1 ≤ 1}, where A and B are positive definite diagonal matrices with elements {Aii}ni=1 and {Bii}ni=1, respectively. We are interested in deciding whetherRA andRB intersect. However, given the conservative context in which Intersect is used in Algorithm 1, we only need to make sure that the function only returns False if it is guaranteed thatRA ∩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 RÃ = {x ∈ Rn : ‖A(x − a)‖2 ≤ 1} and RB̃ = {x ∈ Rn : ‖B(x − b)‖2 ≤ 1}, and perform the ellipsoid intersection check presented in Appendix D.2. If RÃ ∩ RB̃ = ∅, then this implies that RA ∩ RB = ∅ and we can safely return False. Otherwise, we conservatively assume the generalized cross-polytopes intersect, and return True, triggering the reduction procedure detailed in Appendix D.5.
D.4 IMPLEMENTING LARGESTOUTSUBSET(RA, RB) IN THE ELLIPSOID CASE
Given two ellipsoids RA = {x ∈ Rn : (x − a)>A(x − a) ≤ 1} and RB = {x ∈ Rn : (x − b)>B(x− b) ≤ 1} that do intersect where A and B are positive definite diagonal matrices, the task is to find the largest possible ellipsoidRB̃ centered at b such thatRB̃ ⊆ RB whereRA ∩RB̃ = ∅. Finding a maximum ellipsoid that satisfies those conditions is not trivial, so instead we consider a maximum enclosing `2-ball of RB, RB̃ = {x ∈ Rn : ‖x − b‖2 ≤ r}, that does not intersect RA. To obtain this ball, we project the center ofRB, b, to the ellipsoidRA. Particularly, we formulate the problem as the projection of a vector y = b − a onto an ellipsoid with the same shape as RA centered at 0n. This is equivalent to solving the following optimization problem for a symmetric positive definite matrix A:
min x
1 2 ‖x− y‖22 s.t. x >Ax ≤ 1. Note that the objective function is convex, and the constraint forms a convex set. Forming the Lagrangian to this problem, we obtain:
L(x, λ) = 1 2 ‖x− y‖22 + λ
( x>Ax− 1 ) ,
where λ > 0. Therefore, the global optimal solution must satisfy the KKT conditions below: ∂L ∂x = 0→ x∗ = (2λA + I)−1 y,
∂L ∂λ = 0→ y> (2λA + I)−>A (2λA + I)−1 y − 1︸ ︷︷ ︸ f(λ) = 0.
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(A11, . . . ,Ann), we can simplify the problem to:
f(λ) = n∑ i=1 y2iAii (1 + 2λAii)2 − 1 = 0.
Once x∗ is obtained, we can define the maximum radius of the `2-ball centered at b that does not intersectRA as: r∗ = ‖(x∗ + a)− b‖2 − , for an arbitrarily small . Finally, we obtainRB̃ as the maximum ball contained withinRB that has a radius smaller than r∗, that is:
RB̃ = {x ∈ R n : ‖x− b‖2 ≤ min{r∗,min i Bii}}.
Note that while choosing the radius of RB̃ to be r∗ guarantees that RB̃ ∩ RA = ∅, this does not guarantee that RB̃ ⊆ RB. To guarantee both properties, we take the minimum of both r∗ and mini Bii. This approach finds the solution to the projection of the point to the ellipsoid {x ∈ Rn : x>Ax ≤ 1}; it does not work for the case in which b ∈ RA, since the problem would be trivially solved by setting x∗ = y. Thus, our classifier must abstain in that situation.
D.5 IMPLEMENTING LARGESTOUTSUBSET(RA, RB) IN THE GENERALIZED CROSS-POLYTOPE CASE
Let RA and RB be two generalized cross-polytopes RA = {x ∈ Rn : ‖A(x − a)‖1 ≤ 1} and RB = {x ∈ Rn : ‖B(x− b)‖1 ≤ 1}, where A and B are positive definite diagonal matrices with elements {Aii}ni=1 and {Bii}ni=1, respectively. The task is to find the largest possible generalized cross-polytopeRB̃ centered at b such thatRB̃ ⊆ RB whereRA ∩RB̃ = ∅. As with the ellipsoid case, solving this problem for a generalized cross-polytope is not trivial, so instead we consider a maximum enclosing cross-polytope (i.e., `1-ball) of RB̃ = {x ∈ Rn : ‖x− b‖1 ≤ r} that does not intersectRA and is a subset ofRB. To obtain this `1-ball, we project the center ofRB, b, to the generalized cross-polytopeRA in a similar fashion to the ellipsoid case in Appendix D.4. We formulate the problem as the projection of the vector y = b− a to the 0n centered generalized cross-polytope {x ∈ Rn : ‖Ax‖1 ≤ 1}. Lemma 4. Consider the hyperplane H = {x ∈ Rn : w>x − k = 0} and a point y ∈ Rn. The `2 projection of y on the hyperplane is the point x∗ = y − (w>y−k)w/‖w‖22.
Proof. We define the projection problem in a similar fashion to the ellipsoid case:
min x
1 2 ‖x− y‖22 s.t. w >x− k = 0,
and obtain the Lagrangian as L(x, λ) = 12 ‖x− y‖ 2 2 + λ(w >x− k), from where we get (using the KKT conditions): x∗ = y − λ∗w and λ∗ = w>y−k/‖w‖22; thus obtaining: x∗ = y −
(w>y−k)w ‖w‖22 .
While this formulation does not yield the closest point from a hyperplane when measured with the `1 norm, the fact that ‖x−x∗‖1 ≥ ‖x−x∗‖2 implies the certification set obtained in the `1 norm via this method is a subset of the `2-ball of the minimum projection point. Crucially, this `2 projection has the advantage of having a closed-form solution, while an `1 one would require solving the problem using an iterative linear programming solver. As such, for the sake of computational complexity, we decided to use this projection, despite the sub-optimality of the result from the `1 perspective. Empirically, we have found this does not affect our results.
Since the set of vertices of the generalized cross-polytope {x ∈ Rn : ‖Ax‖1 ≤ 1} is given by {ei/Aii,−ei/Aii}ni=1, and considering the distance between the projections and the original y, the hyperplane that minimizes it is defined by the set of vertices {sign(yi)ei/Aii}ni=1. By writing it as a system of n equations, we obtain the hyperplane defined by w = [−sign(y1)A11, ...,−sign(yn)Ann] and k = 1. Finally, after computing x∗ as per Lemma 4, we can define the maximum radius of the `1-ball centered at b that does not intersectRA as:
r∗ = ‖(x∗ + a)− b‖1 − ,
for an arbitrarily small . Finally, and similar to the ellipsoids case, we obtainRB̃ as the maximum generalized cross-polytope contained withinRB that has a radius smaller than r∗, that is:
RB̃ = {x ∈ R n : ‖x− b‖1 ≤ min{r∗,min i Bii}}
Similar to before, to guarantee that the `1 ball RB̃ is still a subset to RB, we take the minimum between r∗ and mini Bii to be the radius ofRB̃. As with the ellipsoid case, this approach does not work for the case in which b ∈ RA, since the assumption of the closest plane to y would not hold. Thus, our classifier must abstain in that situation.

heading: E EXPERIMENTAL SETUP
text: The experiments reported in the paper used the CIFAR-10 Krizhevsky (2009)3 and ImageNet Deng et al. (2009)4 datasets, and trained ResNet18, WideResNet40 and ResNet50 networks He et al. (2016).
3Available here (url), under an MIT license. 4Available here (url), terms of access detailed in the Download page.
Experiments used the typical data split for these datasets found in the PyTorch implementation Paszke et al. (2019). The procedures to obtain the baseline networks used in the experiments are detailed in Appendix E.1 and E.2 for ellipsoids and generalized cross-polytopes, respectively. Source code to reproduce the ANCER optimization and certification results of this paper is available as supplementary material.
Isotropic DD Optimization. We used the available code of Alfarra et al. (2020)5 to obtain the isotropic data dependent smoothing parameters. To train our models from scratch, we used an adapted version of the code provided in the same repository.
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 N0 = 100 Monte Carlo samples for selection and N = 100, 000 estimation samples, with failure a probability of α = 0.001.
E.1 ELLIPSOID CERTIFICATION BASELINE NETWORKS
In terms of ellipsoid certification, the baselines we considered were COHEN Cohen et al. (2019)6, SMOOTHADV Salman et al. (2019a)7 and MACER Zhai et al. (2019)8.
In the CIFAR-10 experiments, we used a ResNet18 architecture, instead of the ResNet110 used in Cohen et al. (2019); Salman et al. (2019a); Zhai et al. (2019) due to constraints at the level of computation power. As such, we had to train each of the networks from scratch following the procedures available in the source code of each of the baselines. We did so under our own framework, and the training scripts are available in the supplementary material. For the ImageNet experiments we used the ResNet50 networks provided by each of the baselines in their respective open source repositories.
We trained the ResNet18 networks for 120 epochs, with a batch size of 256 and stochastic gradient descent with a learning rate of 10−2, and momentum of 0.9.
E.2 GENERALIZED CROSS-POLYTOPE CERTIFICATION BASELINE NETWORKS
For the certification of generalized cross-polytopes we considered RS4A Yang et al. (2020)9. As described in RS4A Yang et al. (2020), we take λ = σ/√3 and report results as a function of σ for ease of comparison.
As with the baseline, we ran experiments on CIFAR-10 on a WideResNet40 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, i.e. σ = {0.15, 0.25, 0.5, 0.75, 1.0, 1.125, 1.5, 1.75, 2.0, 2.25, 2.5, 2.75, 3.0, 3.25, 3.5} on CIFAR-10 and σ = {0.25, 0.5, 0.75, 1.0, 1.125, 1.5, 1.75, 2.0, 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 a subset of σ = {0.25, 0.5, 1.0} and performed our analysis at that level. While the trained models are available in the source code of RS4A, we ran into several 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 WideResNet40 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 WideResNet40 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 a learning rate of 10−2, and momentum of 0.9, along with a step learning rate scheduler with a γ of 0.1. For the ResNet50 networks on ImageNet, we trained them from scratch
5Data Dependent Randomized Smoothing source code available here 6COHEN source code available here. 7SMOOTHADV source code available here. 8MACER source code available here. 9RS4A source code available here.
with stability loss for 90 epochs with a learning rate of 0.1 that drops by a factor of 0.1 after each 30 epochs and a batch size of 256.

heading: F SUPERSET ARGUMENT
text: The results we present in Section 7 support the argument that ANCER achieves, in general, a certificate that is a superset of the Fixed σ and Isotropic DD ones. To confirm this at an individual test set sample level, we compare the `2, `1, `Σ2 and ` Λ 1 certification results across the different methods, and obtain the percentage of the test set in which ANCER performs at least as well as all other methods in each certificates of the samples. Results of this analysis are presented in Tables 4 and 5.
For most networks and datasets, we observe that ANCER achieves a larger `p 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’s certificate is superior in over 90% of the test set samples.
G EXPERIMENTAL RESULTS PER σ
G.1 CERTIFYING ELLIPSOIDS - `2 AND `Σ2 CERTIFICATION RESULTS PER σ
In this section we report certified accuracy at various `2 radii and `Σ2 proxy radii, following the metrics defined in Section 7, for each training method (COHEN Cohen et al. (2019), SMOOTHADV Salman et al. (2019a) and MACER Zhai et al. (2019)), dataset (CIFAR-10 and ImageNet) and σ (σ ∈ {0.12, 0.25, 0.5, 1.0}). Figures 6 and 7 shows certified accuracy at different `2 radii for CIFAR-10 and ImageNet, respectively, whereas Figures 8 and 9 plot certified accuracy and different `Σ2 proxy radii for CIFAR-10 and ImageNet, respectively.
G.2 CERTIFYING ELLIPSOIDS - `1 AND `Λ1 CERTIFICATION RESULTS PER σ
In this section we report certified accuracy at various `1 radii and `Λ1 proxy radii, following the metrics defined in Section 7, for RS4A, dataset (CIFAR-10 and ImageNet) and σ (σ ∈ {0.25, 0.5, 1.0}). Figures 10 and 11 shows certified accuracy at different `1 radii for CIFAR-10 and ImageNet, respectively, whereas Figures 12 and 13 plot certified accuracy and different `Λ1 proxy radii for CIFAR-10 and ImageNet, respectively.
G.3 WHY DOES ANCER IMPROVE UPON ISOTROPIC DD’S `p CERTIFICATES?
As observed in Sections 7.1 and 7.2, ANCER’s `2 and `1 certificates outperform the corresponding certificates obtained by Isotropic DD. To explain this, we compare the `2 certified region obtained
by ANCER, defined in Section 6 as {δ : ‖δ‖2 ≤ mini σxi r(x,Σx)}, to the one by Isotropic DD defined as {δ : ‖δ‖2 ≤ σxr(x, σx)}. We observe that the radius of both of these certificates can be separated into a σ-factor (σx vs. σxmin = mini σ x i ) and a gap-factor (r(x, σ
x) vs. r(x,Σx)). 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 a better σxmin than the isotropic σ x when given further optimization iterations.
To investigate this, we take the optimized parameters from the Isotropic DD experiments on SMOOTHADV for an initial σ = 0.25 on CIFAR-10, and run the optimization step of Isotropic DD for 100 iterations more than its default number of iterations from Alfarra et al. (2020), so as to match the total number of optimization steps between Isotropic DD and ANCER. The histograms of σx or σxmin and the gap-factor r, i.e. the two factors from the `2 certification results, are presented in Figure 14. While σx for Isotropic DD is similar in distribution to ANCER’s σxmin, the distribution of the two gaps, r(x, σ x) and r(x,Σx), are quite different.
In particular, the ANCER certification gap is significantly larger when compared to Isotropic DD, and is the main contributor to the improvement in the `2-ball certificate of ANCER. That is to say, ANCER generates Σx that is better aligned with the decision boundaries, and hence increases the confidence of the smooth classifier.
H VISUAL COMPARISON OF PARAMETERS IN ELLIPSOID CERTIFICATES
Anisotropic certification allows for a better characterization of the decision boundaries of the base classifier f . For example, the directions aligned with the major axes of the ellipsoids ‖δ‖Σ,2 = r, i.e. locations where Σ is large, are, by definition, expected to be less sensitive to perturbations
compared to the minor axes directions. To visualize this concept, Figure 15 shows CIFAR-10 images along with their corresponding optimized `2 isotropic parameters obtained by Isotropic DD, and `Σ2 anisotropic parameters obtained by ANCER. First, we note the richness of information provided by the anisotropic parameters when compared to the `2 worst-case, isotropic one. Interestingly, pixel locations where the intensity of Σ is large (higher intensity in Figure 15) are generally the ones corresponding least with the underlying true class and overlapping more with background pixels.
A particular insight one can get from ANCER certification is that the decision boundaries are not distributed isotropically around each input. To quantify this in higher dimensions, we plot in Figure 16 a histogram of the ratio between the maximum and minimum elements of our optimized smoothing parameters for the experiments on SmoothAdv (with an initial σ = 1.0) on CIFAR-10. We note that this ratio can be as high as 5 for some of the input points, meaning the decision boundaries in that case could be 5 times closer to a given input for some directions than others.

heading: I NON DATA-DEPENDENT ANISOTROPIC CERTIFICATION
text: As mentioned briefly in Section 6, it is our intuition that anisotropic certification requires a datadependent approach, as different points will have fairly different decision boundaries and the certified regions will extend in different directions (as exemplified in Figure 1).
To validate this claim, we perform certification of SmoothAdv Salman et al. (2019a) with an initial σ = 1 on CIFAR-10 using a Σ which is the average of all the optimized Σx. The results of the certified accuracy, ACR and ACR̃ are presented in Table 6, along with the same results for the methods reported in the main paper. 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 `2 and `1 certificates far out-does that of Mohapatra et al. (2020). For example, with `2 certificates at a radius of 0.5, Cohen certified with ANCER achieves 77% certified accuracy (see Table 1) while Mohapatra et al. (2020) achieves under 60% certified accuracy. Note that Mohapatra et al. (2020) has only a marginal improvement
over Cohen et al. As for the `1 certificates, Mohapatra et al. (2020) uses the Gaussian distribution of Cohen et al, resulting in worse performance than existing state-of-art in `1 Yang et al. (2020) that uses a uniform distribution. Our approach improves further upon the performance of Yang et al. (2020). For example, as per Table 2, RS4A with ANCER certification achieves 84% certified accuracy at an `1 radius of 0.5, Yang et al. (2020) achieves 75% certified accuracy while Mohapatra et al. (2020) achieves below 60%. However, we believe that the combination of both approaches, ANCER and Mohapatra et al. (2020) can further boost the performance as also hinted on in the abstract of Mohapatra et al. (2020) on the use of data-dependent smoothing.

Review summaries:
In this paper, the authors discuss the extension of $\ell_{p}$-randomized smoothing to anisotropic counterparts. In particular, they consider the extension of $\ell_{2}$-certificates from (hyper)spheres to (hyper)ellipsoids by 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. Further, the authors discuss how these extended certificates can be compared to their base-counter parts to establish superiority (inclusion). The introduced certification algorithm, ANCER, utilizes the idea of data-dependent randomized smoothing to find the anisotropic shape with maximal certification volume. In 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.

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.