Year: 2021

Abstract:
The vulnerability of deep learning models to adversarial examples and semantic transformations has limited the applications in risk-sensitive areas. The recent development of certified defense approaches like randomized smoothing provides a promising direction towards building reliable machine learning systems. However, current certified defenses cannot handle complex semantic transformations like rotational blur and defocus blur which are common in practical applications. In this paper, we propose a generalized randomized smoothing framework (GSmooth) for certified robustness against semantic transformations. We provide both a unified and rigorous theoretical framework and scalable algorithms for certified robustness on complex semantic transformations. Specifically, our key idea is to use a surrogate image-to-image neural network to approximate a transformation which provides a powerful tool for studying the properties of semantic transformations and certify the transformation based on this neural network. Experiments on multiple types of semantic perturbations and corruptions using multiple datasets demonstrate the effectiveness of our approach.

heading: 1 INTRODUCTION
text: Although deep learning models have achieved remarkable success on various applications (LeCun et al., 2015), they are vulnerable to adversarial examples (Biggio et al., 2013; Szegedy et al., 2013; Goodfellow et al., 2014) and semantic transformations (Hendrycks & Dietterich, 2019). The vulnerability of deep learning models can limit their applications on many important tasks. For example, the autonomous driving system can be misled even by a small adversarial patch on the road mark (Jing et al., 2021). Compared with the maliciously crafted adversarial examples, semantic transformations are more practical in real-world scenarios, such as rotation, translation, blur, bad weather, and so on. Such transformations do not damage the semantic features of images and can be easily recognized by humans, but they also degrade the performance of deep learning models. Therefore, it is imperative to improve model robustness against semantic transformations.
To develop more reliable machine learning systems, many efforts have been made to design defense techniques against adversarial attacks or semantic transformations. The existing defense methods can be categorized into empirical defenses and certified defenses. Adversarial training (AT) (Madry et al., 2017; Zhang et al., 2019a) is one of the most effective empirical defenses against `p-norm bounded adversarial examples. Moreover, methods based on data augmentation (Hendrycks et al., 2019; Wang et al., 2019; Calian et al., 2021) have been proposed to empirically improve the performance under semantic transformations. However, the performance of empirical defenses is difficult to be fully justified and these defenses can be further broken by new adaptive attacks (Athalye et al., 2018; Tramer et al., 2020). In contrast, the certified defenses aim to theoretically provide a certified region where the model is theoretically safe under any attack or perturbation (Wong & Kolter, 2018; Cohen et al., 2019; Gowal et al., 2018; Zhang et al., 2019b). Along this line, developing certified defense methods is a crucial step towards reliable machine learning systems.
Although certified defenses have achieved great success, most of them are limited to defend against `p-norm bounded attacks. However, the `p distance between the original image and its corrupted counterpart by a semantic transformation (e.g., translation, rotation) would be large even when the
corruption is slight. Therefore, the current methods are incapable of certifying robustness against such semantic perturbations. To solve this problem, several recent works (Fischer et al., 2020; Mohapatra et al., 2020; Li et al., 2021) attempt to extend the certified defenses to several simple semantic corruptions, including translation, rotation, and Gaussian blur. However, these works are not scalable to certify robustness against complex and general semantic perturbations. First, deterministic certified defenses (Mohapatra et al., 2020) based on convex relaxation for the activation function require solving a complex optimization problem for computing bound which is computationally expensive. Second, probabilistic approaches based on randomized smoothing also demand a handcrafted Lipschitz bound (Li et al., 2021), which is intractable for complicated semantic transformations. For example, many semantic transformations such as glass blur and pixelate do not have a closed form expression or they are black boxes and hard to be analyzed theoretically, but they are common in real-world scenarios. Therefore, it is still highly challenging to certify robustness against these complex and realistic semantic transformations.
To address the aforementioned challenges, we propose a generalized randomized smoothing framework (GSmooth). First, we provide a unified framework of GSmooth for certifying general semantic transformations. Then we categorize the transformations into resolvable transformations (e.g., translation) and non-resolvable transformations (e.g., rotational blur) similar with Li et al. (2021). As mentioned above, most non-resolvable transformations are complex and the existing methods cannot provide their certified radius. To handle the challenge, we propose to use an image-to-image translation neural network to approximate all these transformations. Due to the strong capacity of neural networks, our method is flexible and scalable to model these complex semantic transformations. By introducing an augmented noise in the layers of the surrogate model, we can theoretically provide the certified radius for the proxy neural networks which can be used for certifying the original transformations. Next, we provide theoretical analysis and error bounding for the approximation. Finally, we validate the effectiveness of our methods on several publicly available datasets. Extensive experimental results demonstrate that our methods are effective for certifying complex semantic transformations including different types of blur or image quality corruptions.

heading: 2 RELATED WORK

heading: 2.1 ATTACKS AND DEFENSES FOR SEMANTIC TRANSFORMATIONS
text: Unlike `p perturbation which adds small noise to every pixel of an image, semantic attacks or physical attacks are usually unrestricted. Brown et al. (2017); Song et al. (2018) use a small patch added to the image to mislead the classifier or the object detector. Engstrom et al. (2019; 2018); Xiao et al. (2018) construct adversarial examples using spatial transformations like rotation or translation. Hendrycks & Dietterich (2019) show that a wide variety of semantic perturbations degrade the performance for many deep learning models. Many works (Cubuk et al., 2019; Hendrycks et al., 2019; 2020; Robey et al., 2020) propose diverse data augmentation techniques to enhance robustness under semantic perturbations. Calian et al. (2021) propose adversarial data augmentation that can be viewed as adversarial training for defending semantic perturbations. Beyond empirical defenses, several works (Mohapatra et al., 2020; Madry et al., 2017; Singh et al., 2019; Balunović et al., 2019) attempt to certify some simple geometric transformations. However, all of them belong to deterministic certification approaches and their performance on realistic datasets are unsatisfactory.

heading: 2.2 RANDOMIZED SMOOTHING
text: Randomized smoothing is a novel certification method originated from differential privacy (Lecuyer et al., 2019). Cohen et al. (2019) then improve the certified bound and apply it to large scale deep neural networks and datasets. Yang et al. (2020) exhaustively analyze the robust radius by using different noise distribution and norms. Hayes (2020); Yang et al. (2020) point out that randomized smoothing suffers from curse of dimensionality for the l∞ norm. Salman et al. (2019) adopt adversarial training to train smoothed classifiers to obtain better robustness guarantees. Li et al. (2021); Fischer et al. (2020) extend randomized smoothing to certify some simple semantic transformations, e.g., image translation and rotation. It shows that randomized smoothing could be generalized to certify more diverse attacks or corruptions. However, their methods are limited to simple semantic transformations, which are easy to analyze their mathematical properties.

heading: 3 PROPOSED METHOD
text: In this section, we present the framework and theoretical analyses of our Generalized Randomized Smoothing (GSmooth). We first introduce the basic notations. Then we divide the semantic transformations into resolvable transformations and non-resolvable transformations similar with Li et al. (2021). Next we introduce the details of our GSmooth for these two types of semantic transformations, respectively. Finally, we show the theoretical insight and proof sketch of our main results.

heading: 3.1 NOTATIONS
text: We first introduce the notations and formulation of the task. Given the input of x ∈ Rn and the labels of Y = {1, 2, . . . p}, we denote the classifier as f(x) : Rn → [0, 1]p, which outputs predicted probabilities over all p classes. The prediction of f is arg maxi∈Y f(x)i, where f(·)i denotes the i-th element of f(·). Let τ(θ, x) : Rm×Rn → Rn be a semantic transformation of raw input x with parameter θ ∈ Rm. We define the smoothed classifier as
G(x) = Eθ∼g[f(τ(θ, x))], (1) which is the average prediction for the samples under a smoothing distribution g(θ) where g(θ) = exp(−ψ(θ)) and ψ(θ) is a smooth function from Rm → R. Let ||u|| = 1 be any vector with unit norm and a random variable γu = 〈u,∇ψ(δ)〉 where δ ∼ g and ∇ is the gradient operator of a function. The complementary CDF is ϕu(c) = P[γu > c] and the inverse complementary CDF is ϕ−1u (p) = inf{c|P(γu > c) 6 p}. Following Yang et al. (2020), we define a function Φ as Φ(p) = max||u||=1 E[γuI{γu > ϕ−1u (p)}], (2) which will be used to represent the certified radius. Let yA= arg maxi∈YG(x)i be the predicted label by the smoothed classifier G(x) and yB = arg maxi∈Y\yA G(x)i is the runner-up class. Without causing confusion, we use G(x)A to denote the probability of the top class G(x)yA ; likewise for G(x)B .

heading: 3.2 CERTIFIED BOUND FOR RESOLVABLE SEMANTIC TRANSFORMATIONS
text: We first discuss a class of transformations that are resolvable — the composition of two transformations with parameters belonging to a perturbation set θ, ξ ∈ P ⊂ Rm is still a transformation with a new parameter γ(θ, ξ) ∈ P ⊂ Rm, where γ(·, ·) : P × P → P is a function depending on these parameters. For resolvable semantic transformations, we have the following theorem. Theorem 1. Let f(x) be any classifier and G(x) be the smoothed classifier defined in Eq. (1). If there exists a function M(·, ·) : P × P → R, the transformation τ(·, ·) satisfies
∂γ(θ, ξ) ∂ξ = ∂γ(θ, ξ) ∂θ M(θ, ξ),
and there exist two constants pA , pB satisfying
G(x)A > pA > pB > G(x)B ,
then yA = arg maxi∈Y G(τ(ξ, x))i holds for any ‖ξ‖ 6 R where
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp, (3)
and M∗ = maxξ,θ∈P ||M(ξ, θ)||.
Remark. The settings of Theorem 1 are similar with Li et al. (2021) for resolvable semantic transformations. But here we adopt a different presentation and proof for the theorem which could be easier to extend to our GSmooth framework for general semantic transformations. Specifically, we show two examples of the theorem which are additive transformations and commutable transformations. A transformation is additive if τ(θ, τ(ξ, x)) = τ(ξ + θ, x) for any θ, ξ ∈ P ; or it is commutable if τ(θ, τ(ξ, x)) = τ(ξ, τ(θ, x)) for any θ, ξ ∈ P . For these two types of transformations, it is straightforward to verify that they satisfy the property proposed in Theorem 1. As an example, we simply apply Theorem 1 for isotropic Gaussian distribution g(θ) = N (0, σ2I) and get the certified radius
R = σ
2
( Ψ ( pA ) −Ψ (pB) ) , (4)
where Ψ is the inverse CDF of the standard Gaussian distribution. These two kinds of transformations include image translation and Gaussian blur, which are basic semantic transformations and widely discussed in previous works (Li et al., 2021; Fischer et al., 2020). The certification of these simple transformations only requires applying translation or Gaussian blur to the sample and gets the average classification score under the noise distribution.

heading: 3.3 CERTIFIED BOUND FOR GENERAL SEMANTIC TRANSFORMATIONS
text: Translation and Gaussian blur are two specific cases of semantic transformations. In practice, most semantic transformations are not commutable or even not resolvable. Therefore, we need to develop better methods for certifying more types of semantic transformations. However, the existing methods like Semanify-NN (Mohapatra et al., 2020) based on convex relaxation and TSS (Li et al., 2021) based on randomized smoothing require to develop a specific algorithm or bound for each individual semantic transformation. This is not scalable and might be infeasible for more complicated transformations without explicit mathematical forms.
To address the challenge, we draw inspiration from the fact that neural networks are able to approximate functions including a complex and unknown semantic transformation (Zhu et al., 2017). First, we propose to use a surrogate image-to-image translation model to accurately fit the semantic transformation. Then we theorectially show that by introducing an augmented noise in the layers of the surrogate model, as shown in Fig 1, randomized smoothing can be extended to handle these transformations. Specifically, we define the surrogate model as the following form that will lead to a simple certification bound as we shall see:
τ(θ, x) = H(F1(θ) + F2(x)), (5)
where F1(·) : Rm → Rd, F2(·) : Rn → Rd, and H(·) : Rd → Rn are three individual neural networks. F1(·) and F2(·) are the encoders for transformation parameters and images respectively, and their encodings are added together in the semantic space which is critical for its theoretical certification. We find that the surrogate neural network is much easier to analyze and can be certified by introducing a dimensional augmentation strategy for both noise parameters and input images.
As illustrated in Fig. 1, an augmented noise is added to the semantic layers H(·) in the surrogate model. Our key insight is that the transformation could be viewed as the superposition of a resolvable part and a non-resolvable residual part in the augmented semantic space. Then we could use the augmented noise to control the non-resolvable residual part if the augmented dimension d > m+n. This dimension augmentation is the key step of our technique. The augmentation for noise is from Rm to Rd. To keep the dimension consistent, we also augment data x to Rd by padding 0 entries.
By certifying the transformation based on the surrogate model, we are able to certify the original transformation if the approximation error is within an acceptable region (detailed analysis is in Theorem 3). Our method is flexible and scalable since the surrogate neural network has a uniform mathematical form for theoretical analysis and they are trained automatically. Next, we discuss the details of GSmooth.
Specifically, we introduce the augmented data x̃ ∈ Rd and the augmented parameter θ̃ ∈ Rd as
x̃ =
( x′
x
) , θ̃ = ( θ θ′ ) , (6)
where the additional parameters θ′ ∈ Rn are sampled from g′(θ′), and the joint distribution of θ′ and θ is θ̃ ∼ g̃ where g̃(θ̃) = g′(θ′)g(θ). Moreover, the augmented data x′ ∈ Rm. We define the generalized smoothed classifier as
G̃(x̃) = Eθ̃∼g̃(θ̃) [ f̃(τ̃(θ̃, x̃)) ] , (7)
where f̃ is the “augmented target classifier” that equals the original classifier when constrained on the original input x, which means f̃(x̃) = f(x). This can be achieved by setting the weights of additional dimensions to 0. Note that now all the functions are augmented for a d dimensional input. We further augment our surrogate neural network to represent the augmented transformation τ̃ : Rd → Rd,
τ̃(θ̃, x̃) = H̃(F̃1(θ̃) + F̃2(x̃)), (8)
where H̃(·), F̃1(·), F̃2(·) : Rd → Rd are parts of the augmented surrogate model. By carefully designing the interaction between the augmented parameters and the original parameters, we could turn the transformation to a resolvable one and it does not change the original surrogate model when constraining to the original input x and θ. Specifically, we design the function F̃1 and F̃2 as follows:
F̃1(θ̃) =
( θ
F1(θ) + θ ′
) , F̃2(x̃) = ( x′
F2(x)
) , H̃(x̃) = [ Id−n
H(x)
] . (9)
Before stating our main theorem, we introduce several notations z̃ξ = F̃1(ξ̃)+ F̃2(x̃), z̃θ = F̃1(θ̃)+ F̃2(x̃), ỹξ = (y′ξ, yξ) T = H̃(F̃1(ξ̃)+F̃2(x̃)) and ỹθ = (y′θ, yθ) T = H̃(F̃1(θ̃)+F̃2(x̃)) for simplicity. Then we theoretically prove that the GSmooth classifier is certifiably robust within a given range:
Theorem 2. Suppose f(x) is a classifier and G̃(x̃) is the smoothed classifier defined in Eq. (7), if there exist pA and pB satisfying
G̃(x̃)A > pA > pB > G̃(x̃)B ,
then yA = arg maxi∈Y G̃(τ̃(ξ̃, x̃))i for any ‖ξ‖2 6 R, where
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp, (10)
and the coefficient M∗ is defined as
M∗ = max ξ,θ∈P
√ 1 + ∥∥∥∥∂F2(yξ)∂ξ − ∂F1(θ)∂θ ∥∥∥∥2
2
. (11)
As the main result of our GSmooth, we have several observations about it. First, we see that the certified radius is similar to the result in Theorem 1. Second, compared with resolvable transformations, we need to add a new type of noise when constructing the GSmooth classifier. This isotropic noise has the same dimension as the data and is added to the intermediate layers of surrogate neural networks. The theoretical explanation behind this is that this isotropic noise makes the Jacobian matrix of the semantic transformation to be invertible which is crucial for the proof. Third, we observe that the coefficient M∗ depends on the norm of the difference of two Jacobian matrices and is independent with the target classifier, later we will discuss the meaning of this term in detail.
Before diving into our theoretical insight and proof of the theorem, we introduce a specific case of Theorem 2 which is more convenient for practical usage. We empirically found that taking a
linear transformation as F1(θ) = A1θ + b1 where A1 ∈ Rn×m, b1 ∈ Rn does not sacrifice the precision of the surrogate network and we have ∂F1(θ)∂θ = A1. After substituting the term in Eq. (44) we only need to optimize ξ for calculating M∗ and we make the bound tighter. Additionally, we use two gaussian distributions for the noise distribution and the augmented noise distribution, i.e. g(θ) = N (0, σ21I) and g′(θ′) = N (0, σ22I). Formally, we have the following corollary, Corollary 1. Suppose f(x) is a classifier and G̃(x̃) is the smoothed classifier defined in Eq. (7), if the layer F1(θ) in the surrogate neural network has the following form:
F1(θ) = A1θ + b1 (12)
where A1∈ Rn×m, b1 ∈ Rn are the parameters; and if there exists pA and pB satisfying
G̃(x̃)A > pA > pB > G̃(x̃)B ,
then yA = arg maxi∈Y G̃(τ̃(ξ̃, x̃))i for any ‖ξ‖2 6 R where
R = 1 2M∗ ( Ψ ( pA ) −Ψ (pB) ) , (13)
where Ψ(·) is the inverse CDF of standard Gaussian distribution, and the coefficient M∗ is defined as,
M∗ = max ξ∈P
√ 1
σ21 +
1
σ22
∥∥∥∥∂F2(yξ)∂ξ −A1 ∥∥∥∥2
2
. (14)

heading: 4 PROOF SKETCH AND THEORETICAL ANALYSIS

heading: 4.1 PROOF SKETCH OF OUR MAIN THEOREM
text: In this section, we briefly summarize the main idea for proving the Theorem 2 and the theoretical insight of our GSmooth. The key idea is to prove that the gradient of the smoothed classifier can be bounded by a function of the classification confidence and the parameters of the noise distribution. Formally, we calculate the gradient to the perturbation parameter ξ for our augmented smoothed classifier as ∇ξ̃G̃(τ̃(ξ̃, x̃)) = ∇ξ̃Eθ̃∼g̃(θ̃)[f̃(τ̃(θ̃, τ̃(ξ̃, x̃)))]. (15) We expand the expectation into integral and see that
∇ξ̃G̃(τ̃(ξ̃, x̃)) = ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂ξ̃ g̃(θ̃)dθ̃. (16)
The key step is to eliminate the gradient of ∂F̃ (τ̃(θ̃,ỹξ)) ∂ξ̃ and replace it with ∂f̃(τ̃(θ̃,ỹξ)) ∂θ̃ . Then we integrate it by parts to get the following obejective,
∇ξ̃G̃(τ̃(ξ̃, x̃)) = − ∫ Rn+d F̃ (τ̃(θ̃, ỹξ)) ∂ ∂θ̃ (M̃(ξ̃, θ̃)g̃(θ̃))dθ̃. (17)
After that, we could bound the gradient of the GSmooth classifier using the technique similar to randomized smoothing (Yang et al., 2020). More details of the proof can be found in Appendix A.

heading: 4.2 THEORETICAL INSIGHT
text: Next, we provide the theoretical insight for our augmentation scheme on transformation parameters and data. First, the key is to expand the transformation space by adding additional dimensions to form a closed space. In the augmented space, the Jacobian matrix of the semantic transformation became invertible which is crucial for our proof. Second, as we can see in Eq. (14) that M∗ is influenced by two factors. One is the standard deviation of two noise distributions. The other is the norm of the Jacobian matrix ∂F2(yξ)∂ξ − A1. It can be viewed as the residual of the non-resolvable part of the transformation. Along this line, our method decomposes the unknown semantic transformation into a resolvable part and a residual part. The non-resolvable residual part could be handled by introducing additional noise with standard deviation σ2.

heading: 4.3 ERROR ANALYSIS FOR SURROGATE MODEL APPROXIMATION
text: In this subsection, we theoretically analyze the effectiveness of certifying real semantic transformation due to the existence of approximation error of surrogate neural networks. Theorem 3. Suppose the simulation of the semantic transformation has an small enough error
‖τ̃(ξ̃, x̃)− τ(ξ̃, x̃)‖2 < ε,
Then there exists a constant ratio A = A(‖F ′1(ξ̃)‖2, ‖F ′2(ỹξ)‖2, ‖F ′2(z̃ξ)‖2) > 0 does not depend on the target classifier, we have the certified radius for the real semantic transformation satisfies that Rr > R(1−Aε) where R is the certified radius for surrogate the neural network in Theorem 2 and
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp,
We find that the reduction of the certified radius is influenced by two factors. The first one is the approximation error between the surrogate transformation and the real semantic transformation. The second one the ratio A is about the norm of the Jacobian matrix for some layers of the surrogate model which is also an inherent property of the semantic transformation itself and does not depend on the target classifier.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP AND EVALUATION METRICS
text: In this section, we conduct extensive experiments to show the effectiveness of our GSmooth on various types of semantic transformations. We use MNIST, CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009) datasets to verify our methods. We train a resnet with 110 layers (He et al., 2016a) from scratch. Similar to prior works, we apply moderate data augmentation (Cohen et al., 2019) to improve the generalization of the classifier. For the surrogate image-to-image translation model for simulating semantic transformations, we adopt the U-Net architecture (Ronneberger et al., 2015) for H̃(·) layers and several simple convolutional or linear layers for F̃1(·) and F̃2(·). All models are trained using Adam optimizer with an initial learning rate of 0.001 that decays every 50 epochs until convergence. The algorithms for calculating M∗ and other details in our experiments are listed in Appendix B due to limited space. The evaluation metric is the certified accuracy, which is the percentage of samples that are correctly classified and has a larger certified radius than the given range. We use ‖α‖ to indicate the preset certified radius.

heading: 5.2 MAIN RESULTS
text: To demonstrate the effectiveness of our GSmooth on certifying complex semantic transformations, we measure the certified correct accuracy for different semantic transformations on different datasets in Table 1. We compare the results of our GSmooth with several baselines, including randomized smoothing for some simple semantic transformation of TSS (Li et al., 2021) and IndivSPT/distSPT (Fischer et al., 2020), and our GSmooth is a natural and powerful extension of their methods. We also compare our method with the deterministic certification approaches, including DeepG (Balunović et al., 2019) that uses linear relaxations similar to Wong & Kolter (2018), Interval (Singh et al., 2019) that is based on interval bound propagation, VeriVis (Pei et al., 2017) that enumerates all possible outcomes for semantic transformations with finite values of parameters, and Semanify-NN (Mohapatra et al., 2020) which uses a new preprocessing layer to turn the problem into a `p norm certification.
We have the following observations for the experimental results. First, only our method achieves non-zero accuracy on certifying some complex semantic transformations and the results verify our Theorem 2. This is a breakthrough that greatly extends the boundary of randomized smoothing based methods. Second, we see the performance of GSmooth is similar to the state-of-the-art randomized smoothing approaches like TSS on several simple semantic transformations like Gaussian
blur, translation. This is a natural result since our method works similarly for resolvable transformations. For two specific non-resolvable transformations, i.e. rotation and scaling, our accuracy is slightly lower. The possible reason is that in TSS (Li et al., 2021) they derive more elaborate Lipschitz bound for rotation which is better than us. Third, those inherently non-resolvable transformations like image blurring (except Gaussian blur) and pixelate are more difficult than resolvable or approximately resolvable (rotation) transformations. Thus their certified accuracy is also lower.

heading: 5.3 ABLATION STUDY
text: Ablation study on the influence of noise distribution. The choice of noise distribution is important for randomized smoothing based methods. Since our GSmooth could certify different types of semantic transformations that exhibit different properties. Understanding the influence of different smoothing distributions for different semantic transformations is necessary. We choose (folded) Gaussian, uniform, and exponential distribution and compare the certified accuracy on zoom blur transformation for both CIFAR-10 and CIFAR-100 datasets. As shown in Fig. 2, We found that
the impact of smoothing distributions depends on datasets. Uniform distribution is better for small radius certification while exponential distribution is more suitable for certifying large radius on average.
Ablation study on the influence of noise variance for certification. Since our GSmooth contains two different variances for controlling the resolvable part and the residual part for a non-resolvable semantic transformation. Here we investigate the effect of different noise variance on the certified accuracy. The results are shown in Table 2. We found that using medium transformation noise and augmented noise achieves the best certified accuracy. The fact is consistent with results in (Cohen et al., 2019). An explanation is that there is a trade-off since higher the noise variance decreases the coefficient M∗ but it might also degrade the clean accuracy.
Visulization experiments: comparsion between augmented semantic noise and image noise. Our GSmooth needs to add a new noise in the semantic layers of the surrogate model. Here we compare the difference between these two types of noise and visualize them. We random sample images from CIFAR-10 and add gaussian noise with σ = 0.2 to both the semantic layer of the surrogate model simulating zoomed blur transformation and raw images. Results are shown in Fig. 3. Both two types of noise severely blur the images. But we found that the augmented semantic noise is more placid which can therefore keep the holistic semantic features better, e.g., shapes.

heading: 6 CONCLUSIONS
text: In this paper, we proposed a generalized randomized smoothing framework (GSmooth) for certifying robustness against general semantic transformations. We proposed a novel idea that using a surrogate neural network to fit semantic transformations. Then we prove tight certified robustness bound for the surrogate model and use it for certifying semantic transformations. Extensive experiments verify the effectiveness of our method and we achieved state-of-the-art performance on various types of semantic transformations. In the future, we plan to extend our method to real-world scenarios on more diverse semantic transformations.

heading: 7 REPRODUCIBILITY STATEMENT
text: We ensure the reproducibility of our paper from three aspects. (1) Experiment: The implementation of our experiment is described in Sec. 5.1. Ablation study for our experiments is in Sec. 5.3. Further details are in Appendix B. (2) Code: Our code is included in supplementary materials. (3) Theory and Method: A complete proof of the theoretical results described is provided in Appendix A.

heading: 8 ETHICS STATEMENT
text: Machine learning models are easily attacked by adversarial examples and semantic transformations. Thus it is fundamental problem to develop certified robust machine learning methods. This paper proposed GSmooth to certify against semantic transformations. It may promote the development of safe and reliable machine learning models in the future.

heading: A PROOF OF THEOREMS
text: In this section, we will provide detailed proofs of theorems in our paper.
First, we restate the theorem of randomized smoothing for additive noise and binary classifiers f(·) : Rn → [0, 1], G(x) = Eθ∼g[f(x+ θ)] (18) Theorem 4. Let f(x) be any classifier and G(x) be the smoothed classifier defined in Eq. (18), if G(x) < 12 , then G(x+ δ) < 1 2 for any
‖δ‖ < ∫ 1 2
G(x)
1
Φ(p) dp (19)
where Φ(·) is a function about smoothing distribution defined in Eq. (2).
Proof. We first calculate the gradient of the smoothed classifier
∇G(x) = ∂ ∂x ∫ Rn f(x+ θ)g(θ)dθ
= ∫ Rn ∂ ∂x f(x+ θ)g(θ)dθ
= ∫ Rn ∂ ∂θ f(x+ θ)g(θ)dθ
Then we multiple any vector with unit norm u ∈ Bn(1) = {u : ‖u‖= 1, u ∈ Rn}, |〈∇G(x), u〉| = ∣∣∣∣〈∫
Rn
∂
∂θ f(x+ θ)g(θ)dθ, u 〉∣∣∣∣ =
∣∣∣∣∫ Rn 〈 ∂ ∂θ f(x+ θ), u 〉 g(θ)dθ ∣∣∣∣ =
∣∣∣∣∣∑ i ∫ Rn ∂f(x+ θ) ∂θi uig(θ)dθ ∣∣∣∣∣ =
∣∣∣∣∣∣ ∑ i ∫ Rn−1 (∫ +∞ −∞ ∂f(x+ θ) ∂θi uig(θ)dθi )∏ j 6=i dθj ∣∣∣∣∣∣ =
∣∣∣∣∣∣− ∑ i ∫ Rn−1 (∫ +∞ −∞ f(x+ θ)ui ∂g(θ) ∂θi dθi )∏ j 6=i dθj ∣∣∣∣∣∣ =
∣∣∣∣∣∑ i ∫ Rn f(x+ θ) ∂g(θ) ∂θi uidθ ∣∣∣∣∣ =
∣∣∣∣∫ Rn f(x+ θ)〈∇g(θ), u〉dθ ∣∣∣∣ =
∣∣∣∣∫ Rn f(x+ θ)g(θ)〈∇ψ(θ), u〉dθ ∣∣∣∣ = |Eθ∼g[f(x+ θ)〈∇ψ(θ), u〉]| (20)
To bound the gradient of the smoothed classifier, we use the following inequality,
|〈∇G(x), u〉| 6 sup f̂ :Ĝ(x)=G(x)
Eθ∼g [ f̂(x+ θ)〈ψ(θ), u〉 ] (21)
As shown in Yang et al. (2020), the optimal f̂(x) achieves at,
f̂(x+ θ) = { 1, if〈u, ψ(θ)〉 > ϕ−1u (G(x)) 0, else
(22)
Then,
Eθ∼g [ f̂(x+ θ)〈u, ψ(θ)〉 ] = E [ γuI{γu > ϕ−1u (G(x))} ] 6 Φ(G(x)) (23)
which means that, |〈∇G(x), u〉| 6 Φ(G(x)) (24)
and this is true for all u ∈ Bn(1), so we have,
max u∈Bn(1)
〈∇G(x), u〉 6 Φ(G(x)) (25)
Consider a path from ξt : [0, ‖δ‖]→ Rd with ξ0 = x and ξ‖δ‖ = x+ δ and ξ′t = δ‖δ‖ , we have
dG(ξt)
dt = 〈∇G(ξt), u〉 6 Φ(G(ξt)). (26)
If the norm of δ satisfies that,
‖δ‖ < ∫ 1 2
G(x)
1
Φ(p) dp, (27)
if right hand side exists, we name it ‖δ0‖ = ∫ 1 2
G(x) 1/Φ(p)dp. Without loss of generality, we assume that G(ξt) is increasing in t, then we cound calculate the minimal twhen G(ξt) increase to 12 ,
T =
∫ 1 2
G(ξ0)
1
Φ(p) dp = ‖δ0‖. (28)
By the generality of δ we have,
G(x+ δ) < 1
2 (29)
for any δ < ‖δ0‖.
This theorem is naturally extended to problems with p > 2 classes by considering the two top classes which are G(x)A and G(x)B . This turns the problem into a binary classification problem.
A.1 THE PROOF OF THEOREM 1
Theorem 1. Let f(x) be any classifier and G(x) be the smoothed classifier defined in Eq. (1), if there exists a function M(·) , and the transformation τ(·, ·) satisfies that
∂γ(θ, ξ) ∂ξ = ∂γ(θ, ξ) ∂θ M(θ, ξ),
and there exists two constants pA , pB that satisfies that
G(x)A > pA > pB > G(x)B ,
then yA = arg maxi∈Y G(τ(ξ, x))i holds for any ‖ξ‖ 6 R where
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp, (30)
here M∗ = maxξ,θ||M(ξ, θ)||.
Proof. WLOG, we only prove it for binary cases that f(·) : Rn → [0, 1].
∇ξG(τ(γ(θ, ξ), x))
=
∫ ∂f(τ(γ(θ, ξ), x))
∂τ(γ(θ, ξ), x) · ∂τ(γ(θ, ξ), x) ∂ξ g(θ)dθ
=
∫ ∂f(τ(γ(θ, ξ), x))
∂τ(γ(θ, ξ), x) · ∂τ(γ(θ, ξ), x) ∂γ(θ, ξ) ∂γ(θ, ξ) ∂ξ g(θ)dθ
=
∫ ∂f(τ(γ(θ, ξ), x))
∂τ(γ(θ, ξ), x) · ∂τ(γ(θ, ξ), x) ∂γ(θ, ξ) ∂γ(θ, ξ) ∂θ M(θ, ξ)g(θ)dθ
=
∫ ∂f(τ(γ(θ, ξ), x))
∂θ M(θ, ξ)g(θ)dθ
(31)
For u ∈ Rd and ‖u‖ = 1, we have:
|〈∇ξG(γ(ξ, x)), u〉| = ∣∣∣∣∫ ∂f(τ(γ(θ, ξ), x))∂θ M(θ, ξ)ug(θ)dθ ∣∣∣∣ (32) 6 M∗ max
‖v‖=1 ∣∣∣∣∫ ∂f(τ(γ(θ, ξ), x))∂θ vg(θ)dθ ∣∣∣∣ (33)
6 M∗ max ‖v‖=1 ∣∣∣∣∫ f(τ(γ(θ, ξ), x))∂g(θ)∂θ vdθ ∣∣∣∣ (34)
(35)
here M∗ = maxθ,ξ ‖M(θ, ξ)‖ and we assume that g(θ) = exp(−ψ(θ)):
|〈∇ξG(γ(ξ, x)), u〉| 6 M∗ max ‖v‖=1 ∣∣∣∣∫ f(τ(γ(θ, ξ), x))∂g(θ)∂θ vdθ ∣∣∣∣ (36)
= M∗ max ‖v‖=1 ∣∣∣∣∫ f(τ(γ(θ, ξ), x))g(θ)∇ψ(θ)vdθ∣∣∣∣ (37) = M∗ max
‖v‖=1 |Eθ∼g [f(τ(γ(θ, ξ), x))〈∇ψ(θ), v〉]| (38)
6 M∗ max ‖v‖=1
sup f̂ :Ĝ(τ(ξ,x))=G(τ(ξ,x))
Eθ∼g[f̂(τ(γ(θ, ξ), x))〈ψ(θ), u〉] (39)
Similar with Theorem 4, the optimal f̂ achieves at
f̂(τ(γ(θ, ξ), x)) = { 1, if〈ψ(θ), u〉 > ϕ−1u (G(τ(ξ, x)))) 0, else
(40)
Then we have |〈∇ξG(τ(ξ, x)), u〉| 6 Φ(G(τ(ξ, x))). (41)
Consider a path from ζt : [0, ‖δ‖]→ Rd with ζ0 = x and ζ‖δ‖ = τ(ξ, x) and ζ ′t = δ‖δ‖ , we have
dG(ξt)
dt = 〈∇G(ξt), u〉 6 Φ(G(ξt)). (42)
The last part of proof is the same with Theorem 4.
A.2 THE PROOF OF THEOREM 2
Theorem 2. Suppose f(x) is any classifier and G̃(x̃) is the smoothed classifier defined in Eq. (7), if there exists pA , pB that satisfies that
G̃(x̃)A > pA > pB > G̃(x̃)B ,
then yA = arg maxi∈Y G̃(τ̃(ξ̃, x̃))i for any ‖ξ‖2 6 R where
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp, (43)
and the coefficient M∗ is defined as
M∗ = max ξ,θ∈P
√ 1 + ∥∥∥∥∂F2(yξ)∂ξ − ∂F1(θ)∂θ ∥∥∥∥2
2
. (44)
Proof. In this part, we will prove Theorem 2, which is the main result in this paper. WLOG, we prove it for binary cases where f(·) : Rn → [0, 1]. First, we will calculate the gradient of G̃(τ̃(ξ̃, x̃)) to ξ̃:
∇ξ̃G̃(τ̃(ξ̃, x̃)) = ∇ξ̃Eθ̃∼g̃(θ̃)[f̃(τ̃(θ̃, τ̃(ξ̃, x̃)))]. (45) We expand the expectation into integral and use chain rule to see that
∇ξ̃G̃(τ̃(ξ̃, x̃)) = ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂τ̃(θ̃, ỹξ) · ∂τ̃(θ̃, ỹξ) ∂ỹξ · ∂ỹξ ∂ξ̃ g̃(θ̃)dθ̃. (46)
The key step is to eliminate the gradient of ∂f̃(τ̃(θ̃,ỹξ)) ∂τ̃(θ̃,ỹξ) and replace it with ∂f̃(τ̃(θ̃,ỹξ)) ∂θ̃ . Since:
∂τ̃(θ̃, ỹξ)
∂ỹξ =
[ σ′1(z ′ θ)
σ′2(zθ)
] [ F ′21(y ′ ξ)
F ′22(yξ)
] , (47)
∂ỹξ
∂ξ̃ =
[ H ′1(z ′ ξ)
H ′2(zξ)
] [ Id
F ′1(ξ) In
] . (48)
We have:
∇ξ̃G̃(τ̃(ξ̃, x̃)) = ∫ Rn+d ∂F̃ (τ̃(θ̃, ỹξ)) ∂τ̃(θ̃, ỹξ) · [ H ′1(z ′ θ) H ′2(zθ) ] [ F ′21(y ′ ξ) F ′22(yξ) ] [ H ′1(z ′ ξ)
H ′2(zξ)
] [ Id
F ′1(ξ) In
] g̃(θ̃)dθ̃ (49)
= ∫ Rn+d ∂F̃ (τ̃(θ̃, ỹξ)) ∂τ̃(θ̃, ỹξ) · [ H ′1(z ′ θ) H ′2(zθ) ] [ Id F ′1(θ) In ] [ Id −F ′1(θ) In ] [ F ′21(y ′ ξ)
F ′22(yξ)
] [ H ′1(z ′ ξ)
H ′2(zξ)
] [ Id
F ′1(ξ) In
] g̃(θ̃)dθ̃ (50)
= ∫ Rn+d ∂F̃ (τ̃(θ̃, ỹξ)) ∂θ̃ [ Id −F ′1(θ) In ] [ F ′21(y ′ ξ) F ′22(yξ) ] [ H ′1(z ′ ξ)
H ′2(zξ)
] [ Id
F ′1(ξ) In
] g̃(θ̃)dθ̃ (51)
= ∫ Rn+d ∂F̃ (τ̃(θ̃, ỹξ)) ∂θ̃ M̃(ξ̃, θ̃)g(θ̃)dθ̃, (52)
here we define
M̃(ξ̃, θ̃) ,
[ Id
−F ′1(θ) In
] [ F ′21(y ′ ξ)
F ′22(yξ)
] [ H ′1(z ′ ξ)
H ′2(zξ)
] [ Id
F ′1(ξ) In
] (53)
We consider the Unit enlargement, which means:
H1(z ′) = z′, F21(x ′) = x′ (54)
thus:
M̃(ξ̃, θ̃) =
[ Id Od×n
F ′21(yξ)− F ′1(θ) F ′22(yξ)H ′2(zξ)
] (55)
Since θ′ is the virtual parameter introduced, which can be taken as 0 in case of actual disturbance. Thus we only need to consider the projection of∇ξ̃G̃(ỹξ) in the space of ξ. Thus we set
ũ =
( u
On×1
) , (56)
here u ∈ Rd and ‖u‖ = 1. Assume
g̃(θ̃) = exp(−ψ̃(θ̃)) (57)
∂g̃(θ̃)
∂θ̃ = −g̃(θ̃) · ∇ψ̃(θ̃). (58)
And we have
∣∣∣〈∇ξ̃G̃(ỹξ), ũ〉∣∣∣ = ∣∣∣∣∣ ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂θ̃ M̃(ξ̃, θ̃)ũg̃(θ̃)dθ̃ ∣∣∣∣∣ (59) =
∣∣∣∣∣ ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂θ̃ [ Id, Od×n F ′22(yξ)− F ′1(θ), On×n ] ũg̃(θ̃)dθ̃ ∣∣∣∣∣ (60) =
∣∣∣∣∣ ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂θ̃ M(ξ, θ)ũg̃(θ̃)dθ̃ ∣∣∣∣∣ (61) 6 M∗ max
‖ṽ‖2=1 ∣∣∣∣∣ ∫ Rn+d ∂f̃(τ̃(θ̃, ỹξ)) ∂θ̃ ṽg̃(θ̃)dθ̃ ∣∣∣∣∣ (62) = M∗ max
‖ṽ‖2=1 ∣∣∣∣∣ ∫ Rn+d f̃(τ̃(θ̃, ỹξ)) ∂g̃(θ̃) ∂θ̃ ṽdθ̃ ∣∣∣∣∣ (63) = M∗ max
‖ṽ‖2=1 ∣∣∣∣∫ Rn+d f̃(τ̃(θ̃, ỹξ))g̃(θ̃)∇ψ̃(θ̃)ṽdθ̃ ∣∣∣∣ (64)
= M∗ max ‖ṽ‖2=1 ∣∣∣Eθ∼g [f̃(τ̃(θ̃, τ̃(ξ̃, x)))〈∇ψ̃(θ̃), ṽ〉]∣∣∣ (65) We bound the right hand side by∣∣∣〈∇ξ̃G̃(ỹξ), ũ〉∣∣∣ 6 sup
f̂ :Ĝ(τ(ξ,x))=G(τ(ξ,x))
M∗ max ‖ṽ‖2=1 ∣∣∣Eθ∼g [f̂(τ̃(θ̃, τ̃(ξ̃, x)))〈∇ψ̃(θ̃), ṽ〉]∣∣∣ (66) and the optimal f̂ is as follows,
f̂(τ̃(θ̃, τ̃(ξ̃, x̃)) = { 1, if〈ψ̃(θ̃), ũ〉 > ϕ−1u (G̃(τ̃(ξ̃, x̃)))) 0, else
(67)
here
M(ξ, θ) =
[ Id, Od×n
F ′22(yξ)− F ′1(θ), On×n
] (68)
and M∗ is
M∗ = max ξ,θ∈P ∥∥∥∥[ Id, Od×nF ′22(yξ)− F ′1(θ), On×n ]∥∥∥∥
2
= max ξ,θ∈P ∥∥∥∥[ Id∂F22(yξ) ∂ξ − ∂F1(θ) ∂θ ]∥∥∥∥ 2
= max ξ,θ∈P
√ 1 + ∥∥∥∥(∂F22(yξ)∂ξ − ∂F1(θ)∂θ )∥∥∥∥2
2
.
(69)
Notice that here F22(·) is the same as F2(·) the notations in the main text. Then we could apply the techniques used in Theorem 1 and Theorem 4, we have:
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp, (70)
Thus we have proven this Theorem.
A.3 THE PROOF OF THEOREM 3
Theorem 3. Suppose the simulation of the semantic transformation has an small enough error
‖τ̃(ξ̃, x̃)− τ(ξ̃, x̃)‖ < ε,
Then there exists a constant ratio A = A(‖F ′1(ξ̃)‖, ‖F ′2(ỹξ)‖, ‖F ′2(z̃ξ)‖) > 0 does not depend on the target classifier, we have the certified radius for the real semantic transformation satisfies that
Rr > R(1−Aε)
where R is the certified radius for surrogate the neural network in Theorem 2 and
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp.
Proof. We set
ũ =
( u
On×1
) , (71)
here u ∈ Rd and ‖u‖ = 1. Then we have
〈 ∇ξ̃G̃(τ̃(ξ̃, x̃))−∇ξ̃G̃(τ̄(ξ̃, x̃)), ũ 〉 =
∫ ( ∂f̃(τ̃(θ̃, τ̃(ξ̃, x̃)))
∂ξ̃ − ∂f̃(τ̃(θ̃, τ̄(ξ̃, x̃))) ∂ξ̃
) ũg̃(θ̃)dθ̃
= ∫ ( τ̃(ξ̃, x̃)− τ̄(ξ̃, x̃) ) ∂2f̃(τ̃(θ̃, τ̂(ξ̃, x̃))) ∂ξ̃∂τ̂ ũg̃(θ̃)dθ̃
(72)
Set L = ∂ 2f̃(τ̃(θ̃,τ̄(ξ̃,x̃)))
∂ξ̃∂τ̂ , we have
L = ∂
∂ξ̃
( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))
∂τ̂
) = ∂
∂ξ̃
( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂τ̂
) . (73)
Set yξ̃ = τ̃(θ̃, τ̂(ξ̃, x̃)), we have:
∂τ̃(θ̃, τ̂(ξ̃, x̃)) ∂τ̂ = ∂H̃(F̃1(θ̃) + F̃2(τ̂(ξ̃, x̃))) ∂τ̂
= H̃ ′ ( F̃1(θ̃) + F̃2(τ̂(ξ̃, x̃)) ) ∂F̃2(τ̂(ξ̃, x̃)) ∂τ̂
= H̃ ′ ( F̃1(θ̃) + F̃2(τ̂(ξ̃, x̃)) )[ Id
F ′1(θ) In
] [ Id
−F ′1(θ) In
] ∂F̃2(τ̂(ξ̃, x̃))
∂τ̂
= ∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂θ̃
[ Id
−F ′1(θ) In
] F̃2 ′ (τ̂(ξ̃, x̃))
= ∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂θ̃ A1
(74)
here A1 = [
Id −F ′1(θ) In
] F̃2 ′ (τ̂(ξ̃, x̃)). By the proof above, we have ∂
∂ξ̃ = ∂ ∂θ̃ A2, thus we have:
L = ∂
∂ξ̃
( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂τ̂
)
= ∂
∂θ̃
( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂τ̃(θ̃, τ̂(ξ̃, x̃))
∂θ̃ A1
) A2
= ∂
∂θ̃
( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))
∂θ̃ A1
) A2.
(75)
〈 ∇ξ̃G̃(τ̃(ξ̃, x̃))−∇ξ̃G̃(τ̄(ξ̃, x̃)), ũ 〉 = ∫ ( τ̃(ξ̃, x̃)− τ̄(ξ̃, x̃)
) ∂2f̃(τ̃(θ̃, τ̂(ξ̃, x̃))) ∂ξ̃∂τ̂ ũg̃(θ̃)dθ̃
= ∫ ( τ̃(ξ̃, x̃)− τ̄(ξ̃, x̃) ) ∂ ∂θ̃ ( ∂f̃(τ̃(θ̃, τ̂(ξ̃, x̃))) ∂θ̃ A1 ) A2ũg̃(θ̃)dθ̃
6Ã · | ∫ f̃(τ̃(θ̃, τ̂(ξ̃, x̃)))g̃(θ̃)〈∇ψ̃(θ̃), ũ〉d θ̃|,
(76)
where Ã is a constant depending on ‖F ′1(ξ̃)‖, ‖F ′2(ỹξ)‖, ‖F ′2(z̃ξ)‖. Then there exists A and we have Rr > R(1− A), (77)
where
R = 1
2M∗ ∫ pA pB 1 Φ(p) dp
B IMPLEMENTATION DETAILS AND EXPERIMENTAL SETTINGS
B.1 PRACTICAL ALGORITHMS FOR CALCULATING M∗
For resolvable transformations in Theorem 1, the M∗ is defined as
M∗ = max ξ,θ∈P ‖M(ξ, θ)‖. (78)
Since if we have verified that the semantic transformation is resolvable, most of time we have a closed form ofM∗ like contrast/brightness transformation and we are able to calculate it analytically as shown in Li et al. (2021).
For non-resolvable transformations in Corollary 1, M∗ is defined as
M∗ = max ξ∈P
√ 1
σ21 +
1
σ22
∥∥∥∥∂F2(yξ)∂ξ −A1 ∥∥∥∥2
2
. (79)
This ratio is similar with the Lipschitz bound for a semantic transformation in Li et al. (2021).For low dimensional semantic transformations, we are able to interpolate the domain to find a maximumM∗ and corresponding ξ. But this remains a challenge for high dimensional semantic transformations. Specifically, for a given ξ, we need to compute the norm of ∂F2(yξ)∂ξ − A1. The Jacobian matrix is n×n. Caculating it requires n times of backpropagation. Thus it is inefficient to store the matrix or directly compute its norm. To solve the problem, we noitice that∥∥∥∥∂F2(yξ)∂ξ −A1 ∥∥∥∥2 2 = max ‖u‖2=1 ∥∥∥∥(∂F2(yξ)∂ξ −A1 ) u ∥∥∥∥2 2 . (80) And then we have ( ∂F2(yξ)
∂ξ −A1
)T u = ∂
∂ξ 〈F2(yξ)−A1, u〉 (81)
Since tranposing a matrix does not change its norm, we could calculate its norm by optimizing u that,
max ‖u‖2=1 ∥∥∥∥ ∂∂ξ 〈F2(yξ)−A1, u〉 ∥∥∥∥2
2
. (82)
Using this formulation, we only need to multiply the output with an unit vector and perform one backpropagation. This is a simple convex optimization problem. Then we could use any iterative algorithm to find its solution which is very fast to compute. This trick is crucial and it makes the matrix norm computation to be scalable in practice.
B.2 OTHER DETAILS FOR EXPERIMENTS.
Our GSmooth requires to train two neural networks. First we randomly generate corrupted images to train a image-to-image neural network. The training process of classifiers and certification for semantic transformations are done on 2080Ti GPUs. We use a U-Net (Ronneberger et al., 2015) for the surrogate model and replace all BatchNorm layers with GroupNorm (Wu & He, 2018) since we might use the model in low bacthsize settings. The U-Net could be replace by other networks used in image segmentation or superresolution like Res-UNet (Diakogiannis et al., 2020) or EDSR (Lim et al., 2017). We use L1-loss to train the surrogate model which achieves better accuracy than others which is also reported (Lim et al., 2017).
After train a surrogate model to simulate the semantic transformation. Then we train the base classifier for certification with a moderate data augmentation like (Li et al., 2021; Cohen et al., 2019) to ensure that training and testing of the classifier is performed on the same distribution. There are two types of data augmentation, one is the semantic transformation and the other is the augmented noise introduced only in our work. Data augmentation based semantic transformation could be done using both the surrogate model or the raw semantic transformation. We can only use the surrogate model to add the augmented noise because this noise is a type of semantic noise in the layers of surrogate model. In our experiments the standard deviation of the augmented noise is chosen from 0.1 ∼ 0.4 depending on the performance. The basic network architectures for these datasets are kept the same with (Li et al., 2021). On CIFAR-100 daatsets, we use a PreResNet (He et al., 2016b) re-implement the method by Li et al. (2021). We also adopt the progressive sampling trick mentioned in TSS (Li et al., 2021) which is useful to reduce computational cost and certify larger radius. The details could also be found in Li et al. (2021).

heading: C SUPPLEMENTARY EXPERIMENTS
text: In this section, we report the results of our GSmooth under adaptive attacks to verify the tightness of our certified bound. The experiments are conducted on CIFAR-10 dataset. We use expectation of transformation to calculate the gradient of the model. Then we apply projected gradient descent
to find adversarial examples until it converged. Then we report the accuracy of our model on the corrupted dataset. The result is listed in the following table. We found that the empirical attack is no less than the certified accuracy. This shows that the bound for our model is effective. Additional, some empirical results are much higher than the certified accuracy, which might indicate the bound still has space for improvement.
We have conducted some experiments under the common benchmark CIFAR-10-C to show the empirical robustness under these corruptions. We conducted the experiments on some subsets of CIFAR-10-C. The corruption types of these subsets are related to the experiments in our paper. The settings of these experiments and the results of baselines are from TSS(Li et al 2021).

Review summaries:
This paper proposes a more generalized form of certified robustness and attempts to provide new results on applying randomized smoothing to semantic transformations such as different types of blurs or distortions. The main idea is to use an image-to-image neural network to approximate semantic transformations, and then certify robustness based on bounds on that neural network. The authors provide empirical results on standard datasets like MNIST and CIFAR showing that their method can achieve improved results on some transformations compared to prior work.

The authors propose a randomized smoothing based certification algorithm  for general semantic transformations. The key idea of the work is to use a neural surrogate for the semantic transformations, and add noise in the latent space of the surrogate for randomized smoothing. The neural surrogate appears to convert the non-linear, multiplicative transformation into an additive operation in the latent space, thus allowing for randomized smoothing methods to be applied. Their approach proposes to decompose the resolvable and unresolvable parts of the semantic transformation by lifting the data+transformation parameters into a larger augmented latent space defined by an image-to-image network. The resolvable parts of the transform can then be certified similar to previous works (Yang'2021, Salman'2019) using the Lipschitzness of the smoothed transforms. The non-resolvable part of the transform however are assumed to be Lipschitz in the latent space. The authors provide theoretical and empirical evidence for GSmooth and show improvement on contemporary methods.

This paper proposed GSmooth, a generalized randomized smoothing method for semantic transformations.   The main technical contributions are: (1) Introduce the use of an image-to-image translation network to provide a unified framework for the analysis of non-resolvable semantic transformations.  (2) Theoretical proof on the certified radius and the approximation error from the image-to-image translation network.   (3) The empirical performance is superior to existing methods on most transformations. More importantly, the method can certify many new transformations that are hard to analyze based on existing methods.