Year: 2019

Abstract:
We present a novel statistical certification method that generalizes prior work based on smoothing to handle richer perturbations. Concretely, our method produces a provable classifier which can establish statistical robustness against geometric perturbations (e.g., rotations, translations) as well as volume changes and pitch shifts on audio data. The generalization is non-trivial and requires careful handling of operations such as interpolation. Our method is agnostic to the choice of classifier and scales to modern architectures such as ResNet-50 on ImageNet.

text: We present a novel statistical certification method that generalizes prior work based on smoothing to handle richer perturbations. Concretely, our method produces a provable classifier which can establish statistical robustness against geometric perturbations (e.g., rotations, translations) as well as volume changes and pitch shifts on audio data. The generalization is non-trivial and requires careful handling of operations such as interpolation. Our method is agnostic to the choice of classifier and scales to modern architectures such as ResNet-50 on ImageNet.

heading: 1 INTRODUCTION
text: The success of deep neural networks (Krizhevsky et al., 2012; Silver et al., 2017) and their use in various application domains has triggered a concern to the sensitivity of these models to small, imperceptible perturbations, known as adversarial examples (Szegedy et al., 2014). Over the last few years there has been substantial interest in finding adversarial examples (Carlini & Wagner, 2017), empirically (Madry et al., 2018) and provably (Wong & Kolter, 2018; Mirman et al., 2018) defending against them as well as proving the neural network is robust to these (Gehr et al., 2018). Much of the focus so far has been on restricted, norm-based perturbations and while these cover important attacker models, it has been shown that natural perturbations, e.g., image rotation, can trigger adversarial behaviors not covered by norm-based attacks (Engstrom et al., 2017).
In this work we focus on certifying a neural network against a wider class of perturbations, by generalizing a recently presented statistical technique (Lecuyer et al., 2018; Cohen et al., 2019), called smoothing, for creating classifiers that are provably robust against certain norm-based attacks. The basic idea behind smoothing is to sample many possible perturbations of the input, classify each of them, and use the aggregate information to make a final robust classification. Overall, the method provides statistical guarantees for l2-norm robustness around a given input (e.g., an image). In our work, we generalize this method to also handle perturbations of the parameters of a given transformation (e.g., the angle of a rotation). This generalization means that we can now apply and study the effectiveness of smoothing across a wider range of interesting perturbations (e.g., image rotation and translation), not previously possible. The generalization is non-trivial and requires careful handling of operations such as interpolation.
Our main contributions are:
• A generalization of the Gaussian smoothing framework to a richer class of perturbations, with a local robustness guarantee on the parameters of the perturbation.
• The first statistical verifier able to certify rotations and translations of images. The system scales to large input sizes and networks such as ImageNet classification. Concretely – among other results – we are the first to create and certify a provable ImageNet classifier (with high confidence) for image translation and rotation.
• An evaluation showing the strengths and limitations of the smoothing approach across a richer class of perturbations than previously possible.

heading: 2 RELATED WORK
text: We now survey the most closely related work in exact and statistical certification as well as richer perturbations beyond norm-based attacks.
Exact Certification: complete and incomplete methods To defend against lp norm bound adversarial examples, many techniques have been developed to verify that a classification is stable in the presence of an attacker. These techniques include complete methods which guarantee a proof of robustness or provide a counter example, such as SMT solvers (Ehlers, 2017; Katz et al., 2017; Bunel et al., 2018), as well as incomplete methods which are sound but may suffer from false positives due to too much approximation error. Examples of these include abstract interpretation based methods (Gehr et al., 2018; Gowal et al., 2018; Singh et al., 2019), linear relaxations (Zhang et al., 2018; Weng et al., 2018) and semi definite programming (Raghunathan et al., 2018). Kurakin et al. (2017); Madry et al. (2018) train empirically robust networks by including adversarial examples in the training set. Wang et al. (2018a;b) replace the softmax layer to increase adversarial robustness. While both methods improve empirical robustness, the method does not provide a formal certificate. Provable defenses (which use incomplete methods) aim to address the issue to some degree by training networks in a way where they are more provable (Mirman et al., 2018; Wong & Kolter, 2018). However, because complete methods are not scalable and incomplete methods lose precision (by design), exact formal certification and training of large-scale networks with good absolute guarantees is a challenging task and remains an active area of research.
Statistical Certification via Smoothing One can trade the absolute (exact) guarantees for probabilistic ones by using smoothed classifiers that scale to much larger networks (Lecuyer et al., 2018; Li et al., 2018; Cohen et al., 2019; Salman et al., 2019). A smoothed classifier g can be built out of an ordinary classifier f by taking the majority vote among perturbed inputs x, i.e., f(x+ δ) where δ is drawn from a probability distribution. Smoothing has the advantage that it scales to large models, however, it can suffer from an added overhead during inference time, and currently only provides l2 robustness statistical certification on limited input perturbations (e.g., pixels of an image). In this space, Lecuyer et al. (2018) presented the first certified robustness method based on randomized smoothing. Later, Li et al. (2018) improved these bounds, which where further improved by Cohen et al. (2019). Salman et al. (2019) improved the results of Cohen et al. (2019) by performing adversarial training on the smoothed classifier. Wang et al. (2019) similarly inject Gaussian noise into ResNet architectures to increase adversarial robustness.
Certification of geometric transformations Beyond lp norm bound attacks, a more realistic attacker model includes perturbations such as geometric attacks, i.e., rotations, translations and shearing (Engstrom et al., 2017; Kanbak et al., 2018). Work on certification against geometric attacks was performed by (Pei et al., 2017) using enumeration and (Singh et al., 2019) using abstract interpretation. Neither work scales to large networks and images. Thus, an interesting question is whether we can handle more complex perturbations (e.g., rotations) on larger networks. Towards this, in the rest of the paper, we show a generalization of the smoothing method to this richer class of transformations.

heading: 3 SMOOTHED CLASSIFIER
text: In this work we consider parameterized transformations of data points x ∈ Rn. We denote the smoothing transformation with parameter s ∈ Rd by ψs : Rn → Rn. Further we denote the attacker transformation φδ : Rn → Rn with δ ∈ Rd as the perturbation that the adversary can apply. We require that ψ and φ compose as ψs ◦ φδ = ψs+δ . Examples of attacker transformations are image rotations and translations as discussed in Section 4.
Using this notion of transformation we now define a smoothed classifier: Definition 3.1 (Smoothed Classifier). Given a base classifier f : Rn → {1, . . . , k} and a transformation ψs : Rn → Rn with s ∈ Rd we define a smoothed classifier gfψ : Rn → {1, . . . , k}:
gfψ(x) = arg max c Ps (f(ψs(x)) = c) , s ∼ N (0,Σ)
for a covariance matrix Σ (symmetric positive definite matrix).
Algorithm 1 for prediction # evaluate g at x function PREDICT(f , Σ, x, n, α, ψ) counts← SAMPLE(f , x, n, Σ, ψ) ĉA, ĉB ← top two indices in counts nA, nB ← counts[ĉA], counts[ĉB] if PVALUETEST(nA, nA + nB , 0.5) ≤ α
return ĉA else return ABSTAIN
Algorithm 2 for certification # certify the robustness of g around x function CERTIFY(f , Σ, x, n0, n, α, ψ) counts0← SAMPLE(f, x, n0,Σ, ψ) ĉA ← top index in counts0 counts← SAMPLE(f, x, n,Σ, ψ) pA ← LBOUND(counts[ĉA], n, 1− α) if pA > 12 return ĉA and R else return ABSTAIN
As it is usually clear from the context, we drop sub- and super- script and just write g.
Given this definition we state our main theorem on the robustness of the smoothed classifier w.r.t attacks φ. This is an adapted version of the main theorem presented in Cohen et al. (2019):
Theorem 3.2. We assume a fixed but arbitrary data point x ∈ Rn, base classifier f : Rn → {1, . . . , k} and transformation ψs : Rn → Rn. Further we allow an attacker to choose δ and apply φδ(x), s.t. ψs ◦ φδ = ψs+δ . Then: If P(f(φs(x) = cA) = pA ≥ pA ≥ pB = pB = maxcB 6=cA P(f(φs(x) = cB) then g(ψδ(x)) = cA for all δ such that √ δTΣ−1δ < Φ−1(pA)−Φ−1(pB) 2 .
Proof. The proof is similar to the one given by Cohen et al. (2019) and is stated in Appendix A.
Throughout the paper we refer to Φ−1(pA)−Φ−1(pB)
2 as the certification radius R.
The key differences to Cohen et al. (2019) are: (i) we allow general transformations ψ rather than only additive noise, and (ii) we consider a full covariance matrix Σ rather than an isotropic one. Specifically for ψs(x) = x + s and Σ = σ2In, our theorem exactly recovers the statement from Cohen et al. (2019). These two additions enable us to tackle many interesting transformations. Due to the similarity of Theorem 3.2 to their main theorem we can also use very similar versions of their algorithms, shown in Algorithms 1 and 2. Theorem 3.2 is a deterministic statement, as the only involved random variable s is integrated out. However in practice, the theorem only holds with a certain probability as we have finite amount of samples to estimate pA (or pA) and pB (or pB). The function SAMPLE(f , x, n, Σ, ψ) returns n samples of f(ψs(x)), s ∼ N (0,Σ). These samples are then used in a statistical test to determine pA or test if it is > 12 with certainty 1− α for a given α. In both algorithms pB = 1−pA. The probability that Algorithm 1 returns a class other than g(x) is at most α and with probability of at least 1− α Algorithm 2 does not abstain.

heading: 4 EXAMPLE PERTURBATIONS
text: We now discuss several practical perturbations ψ which are important and can be handled by our generalization. Specifically, we will consider low parameter image transformations such as changes in contrast and brightening as well as geometric transformations such as rotation and translation, which require special attention to deal with interpolation. Further, we describe low parameter audio transformations such as changes in volume or pitch.

heading: 4.1 IMAGE PERTURBATIONS & INTERPOLATIONS
text: Interpolation A major issue with image transformations such as rotation and translation (for noninteger offsets) is interpolation. A pixel in the transformed image maps to a location in the original image (not necessarily on the pixel grid) where the pixel value is taken from. To obtain the value, we need to interpolate it. Typical interpolations for images are nearest-neighbor interpolation, bilinear
interpolation and bicubic interpolation. Further, if the transformation moves a coordinate outside of the original image, the pixel value is commonly set to (0, 0, 0)T (black).
We explore the issues created by interpolation using the example of rotation, the same method applies to other geometric transformations. We denote the rotation and subsequent interpolation of an image x ∈ Rn by an an angle β as rotateβ(x). In general rotateβ ◦ rotateγ 6= rotateβ+γ due to interpolation. Thus, if we choose ψβ := rotateβ , this does not compose with an angle γ chosen by an attacker φγ . To formalize this problem we write (rotateβ ◦ rotateγ)(x) = rotateβ+γ(x) + β,γ(x) where β,γ(x) denotes the interpolation error.
Modeling Interpolation We address this by modeling the composition of two rotations as a single rotation together with addition of l2 noise. The smoothing operation against an attacker utilizing rotation is ψs(x) = ψ( β
η )(x) := rotateβ(x) + η. For ease of notation we write ψβ,η . We will let the attacker choose δ = ( γ0 ) but in truth apply δ̂ = ( γ ω ) for a ω yet to be determined to offset the interpolation error. Thus we can model the overall attacking and smoothing process as:
(ψβ,η ◦ φγ,ω)(x) = ψβ+γ,η+ω(x) = rotateβ+γ(x) + η + ω = rotateβ ◦ rotateγ(x)− β,γ(x) + η + ω. (1)
Now choosing ω = β,γ(x) we can get rid of the introduced interpolation errors. Thus, our overall transformation ψβ,η ◦ φγ,ω recovers the semantic of ψβ,η ◦ φγ,0 without interpolation. Instantiating Theorem 3.2 with this transformation and Σ = ( σ2r 0
0 σ2i In
) , where In denotes the n × n Identity
matrix, we obtain the bound:√ δ̂TΣ−1δ̂ < R R>0 ===⇒ δ̂TΣ−1δ̂ < R2
=⇒ σ−2r γ2 + σ−2i ω̂ Tω < R2 =⇒ γ2 < σ2r ( R2 − σ−2i ‖ β,γ(x)‖ 2 2 ) =⇒ |γ| < σr √ R2 − σ−2i E2 (2)
with E upper bounding ‖ β,γ(x)‖2 ≤ E. In the first step we also need to assume that R > 0. When R is negative (or term under the root is negative) we take the bound |γ| = 0.
Approach Using Eq. (2), we can derive an algorithm that certifies a range of rotation angles and extend CERTIFY to return |γ| rather than R. There are four ways one can proceed here: Per-Input Global Optimization: If we are given a fixed image x and a range [γmin, γmax] we can calculate the worst case interpolation error by performing global optimization over γ ∈ [γmin, γmax] and β ∈ [−180, 180]. In CERTIFY we would first calculate E before proceeding with the rest of the procedure. This procedure can be improved by only considering β ∈ [−3σr, 3σr], which likely simplifies the optimization problem and still covers 99.7% of possible angles.
Per-Input Sampling: Similar to the global optimization approach, we can, for a given x and a range [γmin, γmax] sample different interpolation errors and obtain a probabilistic guarantee on E.
Training Set Global Optimization: If we assume that our x will come from the data distribution we can already pre-compute the maximal E over the training set.
Training Set Sampling: Again assuming that x follows the data distribution we can sample different E over the training set and rotation angles and take the maximum.
There are two major downsides here: (i) the global maximum of the error norm might be quite large even though the majority of values is actually quite small and (ii) approaches based on the training set or sampling might not find the correct maxima and only provide probabilistic guarantees.
In practice (see Fig. 2; discussed later) most error norms are small under certain assumptions. However, some are vast outliers. This effectively rules out taking the maximum of E (either for specific x or over the whole dataset) as it becomes essentially impossible to obtain a bound in Eq. (2). This rules out taking the global maxima of the error as E.
Further, we need to consider that sampling many interpolation errors for a specific image can be done but is expensive. Rotating an m × l color image with bilinear interpolation requires around
74 · l · m floating point operations which quickly becomes a bottleneck. This rules out creating a new set of samples for every image.
For these two reasons we see computing a probabilistic bound P(E ≤ t) ≤ ε over the training set offline as the only viable way. We treat each sample as a boolean random variable and obtain the Clopper-Pearson upperbound (Clopper & Pearson, 1934) ε with confidence 1− ρ.
Probabilistic Guarantees Assume that in CERTIFY or PREDICT we observe ñA and ñB examples of classes cA and cB when taking n = ñA+ ñB samples. As in Cohen et al. (2019), we can estimate p̃A, the probability that we observe cA, and lower bound it by p̃A with confidence 1− α. Due to our probabilistic guarantee on E, there are samples that can not be trusted as Eq. (2) and subsequently the bound on δ in Theorem 3.2 is not satisfied. When estimating pA and pB we must account for these bad samples. Specifically we can assume that in the worst case all of these samples would have counted towards class cA and construct a conservative lower bound. We can model the real chance of observing clean samples from cA, denoted pA by using the union bound:
p̃A = P(sample from cA ∨ sample is bad) ≤ P(sample from cA) + P(sample is bad) =⇒ p̃A ≤ pA + ε =⇒ pA ≥ p̃A − ε (3)
Since we had confidence 1−α and 1−ρ for p̃A and ε the confidence pA for 1−α−ρ. In Cohen et al. (2019) the authors note that the probability that PREDICT returns a wrong class and that CERTIFY abstains are both at most α, when pA was estimated with confidence 1−α. The same applies to our probabilistic approach, but the failure rate becomes α+ ρ. Fig. 1 shows the overall bound on |γ|. Finally, as we obtained our probabilistic guarantee on E with sampling from γ ∈ U([−γmin, γmax]), we need – in order to be sound – mention that we do not guarantee robustness for all γ covered by Theorem 3.2, but only those intersecting with [−γmin, γmax].

heading: 4.2 INTERPOLATION-FREE PIXEL TRANSFORMATION
text: While we mainly focus on dealing with image perturbations that introduce interpolation error, there are many that do not. A simple class here are perturbations that are additive operations in some color space (RGB, HSV, HSL, etc.). For example, to model brightness we consider the perturbation ψβ(x) = x + β · 1 in RGB space where 1 is the vector of ones with the same dimensions as the image x. The equation can easily be adapted to have different β per color channel or even per region of the image. We can also model multiplicative changes, by bounding them in the exp domain. As an example, we consider changes in contrast, ψβ(x) = 128 + eβ(x− 128)
ψβ ◦ φγ(x) = 128 + eβ · eγ · (x− 128) = 128 + eβ+γ · (x− 128) = ψβ+γ(x) However we can not combine additive and multiplicative perturbations into linear transformations without additional assumptions about the order in which perturbations are applied.
The perturbation of the attacker is likely applied to the image in integer space (i.e., each pixel intensity value is an integer in {0, . . . , 255}). Thus after applying additive or multiplicative scaling the value might be rounded. Hence, to show that perturbations with value |β| are safe, we have to verify that in fact |β + 1| is safe (depending on the exact rounding behavior adding 12 might be sufficient). For multiplicative changes, a corresponding safety margin can be calculated.

heading: 4.3 AUDIO PERTURBATIONS
text: The domain of audio data has similar challenges as the one for image processing. As before, we handle low parameter attacks like shifts in pitch or changes in volume:
Volume The volume of an audio signal can be changed by multiplying the signal with a constant. The smoothing operation is ψβ(x) := eβ ·x and similarly the adversary operation is φγ(x) := eγ ·x. We see that the composition is additive in the parameter space:
ψβ ◦ φγ(x) = eβ · eγ · x = eβ+γ · x = ψβ+γ(x), where we clip values exceeding the range of the values of x back when needed.
Pitch shifts We let DFT denote the discrete Fourier transform and IDFT is its inverse. The transformation that shifts an audio signal by β is ψβ(x) := IDFT(β + DFT(x)). Further, for an attacker φγ := IDFT(γ + DFT(x)) the composition of these two is again additive in the parameter space: ψβ ◦ φγ(x) = IDFT(β + DFT(IDFT(γ + DFT(x)))) = IDFT(β + γ + DFT(x)) = ψβ+γ(x),
where we again neglected the frequencies exceeding the frequency range of the applied DFT. Further, β and γ are rounded to the frequency steps of the DFT, requiring bound similar to Section 4.2.

heading: 5 EVALUATION
text: Setup We evaluated our algorithm on a machine with 16 CPU cores running at 3.5GHz and a GeForce RTX 2080 Ti. We run the perturbation on the images in parallel on CPU and evaluate the network on the GPU with a batch size of 64 in PyTorch (Paszke et al., 2017).
ImageNet Pipeline and Interpolation Error In our evaluation we use the ImageNet classification dataset (Russakovsky et al., 2015). While our algorithm works for general image datasets (with a few restrictions, discussed later in this section) we will specifically discuss this dataset as we require the specifics of the image classification pipleline to precisely model and discuss perturbations. The images in the ImageNet training dataset range in size from 20×17 to 7056×4488. Some classifiers are adaptive in the input size, but most neural network based methods are fixed to take images of size 224 × 224 (Krizhevsky et al., 2012; He et al., 2016). Thus the standard procedure is to first resize the image such that the shorter side has length 256 and then take the 224× 224 center of the image and run the classifier on this image. We denote all of this preprocessing as preprocess(x). A side effect of this preprocessing is that rotation of less than |γ| ≤ 8.13 degrees is applied to an image, then the preprocessed image will not have black corners, as tan−1 ( 256−224
224
) = 8.13 gives
the largest angle for which this holds based on the resizing and cropping size.
Further, many image pipeline implementations can perform these perturbations on floating point images or 8-bit-integer-based images. In the integer case the result of the interpolation is rounded to the closest value in {0, . . . , 255}. In this work we assume the transformations are performed in integer space as this models a more realistic attacker. We let τ denote the function that maps images from the integer domain to the [0, 1] floating point domain, by dividing by 255. When adding noise, the pixel values might exceed their bounds, thus they are clamped to 0 and 255 or to 0 and 1 respectively, by the clamping function clamp. To facilitate faster training (Simonyan & Zisserman, 2015) the pixel intensities have their mean subtracted and are scaled to have a standard deviation of 1. This is known as normalization (normalize).
In general we can ignore all preprocessing and replace the base classifier f with f ′ = f ◦ normalize ◦ clamp ◦ τ ◦ preprocess, but in this section we need to specifically look at the interactions between this and the smoothing procedure.
While one would, based on everyday experience assume that interpolation errors are small, the l2 norm can be surprisingly large. For a large sample of images x from the training and pairs of angles β, γ we measure the norm of the interpolation error ‖ β,γ(x)‖. We observed a mean error of 3.9 with a standard deviation of 3.3 and a maximum of 60.1 A key observation is, that larger images have lower errors. For example, taking a random 250× 250 image x from the ImageNet training set and calculating ‖(τ ◦preprocess)(x)−(τ ◦preprocess ◦ rotate−8 ◦ rotate8)(x)‖2 yields a value of 5.5, but still a very similar image. For comparison the largest l2 perturbations considered in provable robustness are around 3.8 (Cohen et al., 2019; Salman et al., 2019).
Scaling the image up by a factor of 4 before performing this routine reduces the error norm already to 1.49. This is not merely an artifact of scaling up the images, but that larger images in general have a quite low error, as can be seen for example in Fig. 2 which shows interpolation errors ‖̂‖ for images such that the shorter side is at least 2000 pixels long.
Rotation & Translation To apply rotation and translation we use the framework developed in Section 4. However, in practice we apply the rotation before any preprocessing (as this is where the real attacker would do), and the error-offsetting l2 noise after, as preprocessing operations such as down-scaling and cropping tend to reduce it. This does not weaken the attacker, but is only a technical detail of the implementation. So specifically we consider a classifier f ′′ = f ◦normalize ◦ clamp and a perturbation ψ̂β+γ,η+ω(x) = (τ ◦ preprocess ◦ rotateβ ◦ rotateγ(x)) − ̂ + η + ω̂. where ̂ = (τ ◦ preprocess ◦ rotateβ ◦ rotateγ)(x)− (τ ◦ preprocess ◦ rotateβ+γ)(x).
Replacing the perturbation and in Eq. (1) with these ultimately yields to a smaller bound on E in Eq. (2). Due to the size issues outlined before, we consider only images from ImageNet where the shorter side has at least 2000 pixels. Fig. 2 shows the distribution over ‖̂‖ over a sample of these images and different angles β ∼ N (0, 52), γ ∈ U([−8, 8]). We chose these distributions to model the errors, actually observed during the smoothing procedure: Here we assume an attacker to choose γ ∈ [−8, 8] and σr = 5. Based on these samples we derive P(E ≤ t) listed in Table 1. More details, including histograms for translations are given in Fig. 3 in the Appendix.
We now evaluate our algorithm on the images of the ImageNet test set, where the shorter side is at least 2000 pixels, of which there are 65. Since we are largely bound by the l2 robustness of the classifier we use two classifiers from Salman et al. (2019), which were trained to be robust base classifiers for l2 Gaussian smoothing: S0.5 denotes a ResNet-50 (He et al., 2016) trained with SMOOTHADVPGD, σ = 0.5, = 1.0, which had the best approximate certified test accuracy for a noise levels of 1.0 and 1.5 and S1.0 denotes the same model trained with σ = 1.0. While this has slightly worse performance it was trained with a higher σ (robustness to l2 noise, allowing us to use a larger σn. On our data the base classifier S0.5 was correct on 36 samples and S1.0 on 19. Further, we are using E = 1.25, σn = 0.75, σr = 5, α = 0.001, ρ = 0.001, n0 = 100, n = 10000, and bilinear interpolation.
The results are shown in Table 2 where we consider the following evaluation metrics: (i) Abstained shows how often the classifier did not return a certified classification, (ii) Verified is how often a radius larger than 0 was proven to be correct for a class (note that the verification is approximate with the stated confidence), (iii) Accurately Verified shows how many samples could be verified for the same class as the base classifier predicted, and (iv) Correctly Verified shows how many samples were verified and also had the correct label to the dataset.
The biggest trade-off in these experiments is choosing σn as large as possible, to obtain a good bound in Eq. (2). However, at the same time this lowers the accuracy and thus decreases the bound. Interestingly more samples don’t necessarily help us as much as they do in Cohen et al. (2019) as our estimate of pA is fundamentally limited by Eq. (3).
For rotation with S0.5 the mean±standard deviation is 3.24±0.77 degrees for the verified examples and 3.56± 0.50 degrees for S1.0. For transformation on S0.5, ‖ ( dx dy ) ‖2 ≤ 10.70± 3.60, where dx and dy denotes the offset in x and y direction respectively. To be sound we would need to limit dx and dy to at most ±2 as this was our assumption when obtaining E, but the distribution for larger changes is similar to the one obtained for ±2 so an argument for the full range can be made. The average run time to certify rotations with n = 10000 is 256.27s and for translations 250.02s.
We conclude that the main bottlenecks are the inequality Eq. (3), the accuracy of the base classifier and its robustness to l2 allowing us to choose larger σn.
Brightness and Contrast In contrast to the perturbations that perform interpolation we do not need to use Eq. (2) but can directly use Theorem 3.2. So for brightness changes and contrast changes we use Σ = σ (a scalar), and since for this task we don’t specifically need an l2 robust network, we use a standard ResNet-50 (He et al., 2016) from PyTorch Torchvsion (Paszke et al., 2017), denoted as R, as well as S0.5 from before. The results are shown in Tables 3 and 4. For brightness we use σ = 12 and for contrast σ = 0.2 as well as σ = 0.4. For both we use n0 = 100, n = 10000 and α = 0.001 and observe an average evaluation time for n = 10000 of 24.01 s. To be sound w.r.t. integer rounding we need to subtract 1 and 0.0008 from the β in Table 3 and Table 4 respectively. The results highlight how much the accuracy and robustness of the base classifier aid verification. R is much more accurate than S0.5 allowing us to certify large ranges of brightness changes.

heading: 6 CONCLUSION
text: We presented a way to extend the Gaussian Smoothing framework (Cohen et al., 2019) to interesting perturbations in application domains such as image and audio classification. In our evaluation we showed that the approach is applicable to complex tasks such as ImageNet classification, although we believe that improvements to classifiers and application domain specific insights can strongly improve the results. We believe that this work makes Gaussian Smoothing applicable outside the often considered lp-ball and will trigger further work in this direction.

heading: A PROOF OF THEOREM 3.2
text: The assumption is
P ((f ◦ ψs) (x) = c) = pc ≥ pc ≥ p′c ≥ p′c = P ((f ◦ ψs) (x) = c′) .
By the definition of g we need to show that
P ((f ◦ ψs ◦ φδ) (x) = c) ≥ P ((f ◦ ψs ◦ φδ) (x) = c′) .
Using ψs ◦ φδ = ψs+δ , we get
P ((f ◦ ψs+δ) (x) = c) ≥ P ((f ◦ ψs+δ) (x) = c′) .
We define the set A := {z | δTΣ−1z ≤ √ δTΣ−1δΦ(pc)}. We claim that
P(f ◦ ψs(x) = c) ≥ P(s ∈ A) (4) P(f ◦ ψs+δ(x) = c) ≥ P(s + δ ∈ A) (5)
holds. First, we show that Eq. (4) holds.
P(s ∈ A) = P(δTΣ−1s ≤ √ δTΣ−1δΦ(pc))
= P(δTΣ−1N (0,Σ) ≤ √ δTΣ−1δΦ(pc)) = P(δT √ Σ−1N (0,1) ≤ √ δTΣ−1δΦ(pc)) = P(N (0, δTΣ−1δ) ≤ √ δTΣ−1δΦ(pc)) = P( √ δTΣ−1δN (0,1) ≤ √ δTΣ−1δΦ(pc))
= P(N (0,1) ≤ Φ(pc)) = Φ(Φ−1(pc))
= pc
Thus Eq. (4) holds. Next we show that Eq. (5) holds
∫ Rd [f ◦ ψz = c]ps+δ(z)dz − ∫ A ps+δ(z)dz
= ∫ Rd\A [f ◦ ψz(x) = c]ps+δ(z)dz + ∫ A ([f ◦ ψz(x) = c]− 1)ps+δ(z)dz
= ∫ Rd\A [f ◦ ψz(x) = c]ps+δ(z)dz
+ ∫ A ([f ◦ ψz(x) = c]− [f ◦ ψz(x) = c]− [f ◦ ψz(x) 6= c])ps+δ(z)dz
= ∫ Rd\A [f ◦ ψz(x) = c]ps+δ(z)dz − ∫ A [f ◦ ψz(x) 6= c]ps+δ(z)dz
Lemma A.1 ≥ ∫ Rd\A [f ◦ ψz(x) = c]ps(z)dz − ∫ A [f ◦ ψz(x) 6= c]ps(z)dz
= ∫ Rd [f ◦ ψz(x) = c]ps(z)dz − ∫ A ps(z)dz
Eq. (4) ≥ 0.
Thus also Eq. (5) holds.
Lemma A.1. There exists t > 0 such that ps+δ(z) ≤ ps(z) · t for all z ∈ A.
Proof.
ps+δ(z)
ps(z) = exp
( − 12 (z − δ) TΣ−1(z − δ) + 12z TΣ−1z ) = exp ( − 12z TΣ−1z + zTΣ−1δ − 12δ TΣ−1δ + 12z TΣ−1z )
= exp ( zTΣ−1δ − 12δ TΣ−1δ )
What is the lowest t if it exists such that ps+δ(z)ps(z) ≤ t?
ps+δ(z)
ps(z) ≤ t ⇔ exp ( zTΣ−1δ − 12δ TΣ−1δ ) ≤ t ⇔ zTΣ−1δ − 12δ TΣ−1δ ≤ log t ⇔ zTΣ−1δ ≤ log t+ 12δ TΣ−1δ
Because z ∈ A, we know that
zTΣ−1δ ≤ √ δTΣ−1δΦ−1(pc).
Does there exist a t such that both upper bound coincide? Yes, namely t = exp (√
δTΣ−1δΦ−1(pc)− 12δ TΣ−1δ
) .
Next, we claim that for B := {z | δTΣ−1z ≥ √ δTΣ−1δΦ−1(1− p′c)} holds that
P(f ◦ ψs(x) = c′) ≤ P(s ∈ B) (6) P(f ◦ ψs+δ(x) = c′) ≤ P(s + δ ∈ B) (7)
The proof for Eq. (6) and Eq. (7) are analogous to the proofs for Eq. (4) and Eq. (5).
Now we derive the conditions that lead to P(s + δ ∈ A) > P(s + δ ∈ B):
P(s + δ ∈ A) = P ( δTΣ−1(s + δ) ≤ √ δTΣ−1δΦ−1(pc) ) = P ( δTΣ−1( √ ΣN (0,1) + δ) ≤ √ δTΣ−1δΦ−1(pc)
) = P ( δT √ Σ−1N (0,1) + δTΣ−1δ ≤ √ δTΣ−1δΦ−1(pc)
) = P (√ δTΣ−1δN (0,1) + δTΣ−1δ ≤ √ δTΣ−1δΦ−1(pc)
) = P ( N (0,1) + √ δTΣ−1δ ≤ Φ−1(pc)
) = P ( N (0,1) ≤ Φ−1(pc)− √ δTΣ−1δ
) = Φ(Φ−1(pc)− √ δTΣ−1δ)
Similarly, we have P(s + δ ∈ B) = P ( N (0,1) ≥ Φ−1(1− pc′)− √ δTΣ−1δ ) = Φ( √ δTΣ−1δ − Φ−1(1− pc′))
Thus, we get
P(s + δ ∈ A) > P(s + δ ∈ B)
⇔ Φ(Φ−1(pc)− √ δTΣ−1δ) > Φ( √ δTΣ−1δ − Φ−1(1− pc′)) ⇔ Φ−1(pc)− √ δTΣ−1δ > √ δTΣ−1δ − Φ−1(1− pc′) ⇔ Φ−1(pc) + Φ−1(1− pc′) > 2 √ δTΣ−1δ
⇔ 12 (Φ −1(pc)− Φ−1(pc′)) >
√ δTΣ−1δ.
B FURTHER FIGURES

Review summaries:
This paper introduces a new smoothing algorithm which produces classifiers with certified robustness against adversarial perturbations. In particular, the authors are interested in settings where the input vectors need not be robust simply to \ell_2 perturbations, for which previous authors (e.g., Cohen et al.) have already introduced a "randomized smoothing" classifier which possesses the desired properties. Instead, motivated by the desire to certify robustness to other families of transformations, the authors propose to introduce a smoothing transform that operates in an additive way on the underlying parameter space (rather than on the raw input vectors, as in the case of \ell_2 randomized smoothing). The authors provide details for a few examples from image and audio data processing, and then show experimental results on ImageNet data.