Despite the widespread success of deep neural networks (DNNs), they remain surprisingly susceptible to misclassification when small adversarial changes are applied to correctly classified inputs (Goodfellow et al., 2015;Kurakin et al., 2018). This phenomenon is especially concerning as DNNs are increasingly being deployed in many safety-critical domains, such as autonomous driving (Bojarski et al., 2016;Sitawarin et al., 2018) and medical imaging (Finlayson et al., 2019).
As a result, there have been widespread efforts aimed at formally verifying the robustness of DNNs against norm-based adversarial perturbations (Gehr et al., 2018;Singh et al., 2019;Weng et al., 2018;Zhang et al., 2018) and designing novel mechanisms for incorporating feedback from the verifier to train provably robust networks with deterministic guarantees (Gowal et al., 2019;Mirman et al., 2018;Xu et al., 2020;Zhang et al., 2020). However, recent works (Dreossi et al., 2018;Engstrom et al., 2019;Hendrycks & Dietterich, 2019;Kanbak et al., 2018;Liu et al., 2019) have shown that geometric transformations ± which capture real-world artifacts like scaling and changes in contrast ± can also easily deceive DNNs. No prior work has formulated the construction of a deterministic provable defense needed to ensure DNN safety against geometric transformations. Further, existing deterministic verifiers for geometric perturbations (Balunovic et al., 2019;Mohapatra et al., 2020) are severely limited by their scalability and cannot be used during training for building provable defenses. Probabilistic geometric robustness verifiers (Fischer et al., 2020;Hao et al., 2022;Li et al., 2021) are more scalable but may be inadequate for safety-critical applications like autonomous driving, since they may falsely label an adversarial region as robust. These limitations have prevented the development of deterministic provable defenses against geometric transformations thus far.
Challenges. Training networks to be certifiably robust against geometric transformations carries multiple challenges that do not arise with norm-based perturbations. First, geometric transformations are much more difficult to formally reason about than ℓ p perturbations, as unlike an ℓ p -ball, the adversarial region of a geometric transformation is highly nonuniform and cannot be directly represented as a symbolic formula encoding a convex shape. Computing this adversarial input region for geometric perturbations is indeed the main computational bottleneck faced by existing geometric robustness verifiers (Balunovic et al., 2019;Mohapatra et al., 2020), thus making the overall verification too expensive for use during training. Hence, training DNNs for deterministic certified robustness against geometric perturbations requires not only formulating the construction of a provable defense, but also completely redesigning geometric robustness verifiers for scalability. This Work. To address the outlined challenges, we propose Certified Geometric Training (CGT), a framework for training neural networks that are deterministically certified robust to geometric transformations. The framework consists of (1) the Fast Geometric Verifier (FGV), a novel method to perform geometric robustness certification that is orders of magnitude faster than the state-of-theart and (2) computationally efficient loss functions that embed FGV into the training procedure.
We empirically evaluate our method on the MNIST (LeCun et al., 1998), CIFAR10 (Krizhevsky, 2009), Tiny ImageNet (Le & Yang, 2015), and Udacity self-driving car (Udacity, 2016) datasets to demonstrate CGT's effectiveness. Our results show that CGT-trained networks consistently achieve state-of-the-art clean accuracy and certified robustness; furthermore, FGV is between 60× to 42,600× faster than the state-of-the-art verifier for certifying each image. We also achieve several breakthroughs: (1) FGV enables us to certify deterministic robustness against geometric transformations on entire test sets of 10,000 images, which is more than 50× the number of images over existing works (100 in Balunovic et al. (2019) and 200 in Mohapatra et al. (2020)); (2) we are the first to scale deterministic geometric verification beyond CIFAR10; and (3) we are the first to verify a neural network for autonomous driving under realistic geometric perturbations. Our code is publicly available at https://github.com/uiuc-arc/CGT.
Geometric Robustness Certification. Certification of geometric perturbations (such as image rotations or scaling) going beyond ℓ p -norm attacks have recently begun to be studied in the literature. There are two main approaches to formally verifying the geometric robustness of neural networks: deterministic and probabilistic. Most recent works on geometric robustness verification use randomized smoothing-based techniques to obtain probabilistic guarantees of robustness (Fischer et al., 2020;Hao et al., 2022;Li et al., 2021). While these approaches can scale to larger datasets, their analyses are inherently unsound, i.e., they may falsely label an adversarial region as robust. For safety-critical domains, this uncertainty may be undesirable. Furthermore, such guarantees are obtained over a smoothed version of a base network, which at inference time requires sampling (i.e., repeatedly evaluating) the network up to 10,000 times per image, thereby introducing significant runtime or memory overhead (Fischer et al., 2020). Our work focuses on deterministic verification, whose analysis is always guaranteed to be correct and whose certified network incurs no overhead during inference. In particular, this type of certificate always holds against any adaptive attacker. However, the existing deterministic geometric robustness verifiers (Balunovic et al., 2019;Mohapatra et al., 2020) are exceedingly slow and thus unsuitable for training, due to the high cost of abstracting the geometric input region (even before propagating it through the network). Singh et al. (2019) study deterministic robustness against rotations, but their results are subsumed by Balunovic et al. (2019). While some works have focused on scaling verifiers (MÈ uller et al., 2021;Xu et al., 2020), they have not targeted geometric robustness as we do.
Provable Defenses Against Norm-based Perturbations. Prior works (Gowal et al., 2019;Mirman et al., 2018;Xu et al., 2020;Zhang et al., 2020) incorporate verification explicitly into the training loop so that the trained networks become easier to verify. Typically, this task is accomplished by formulating a loss function that strikes a balance between the desired formal guarantees (i.e., high certified robustness) and clean accuracy (i.e., the network's accuracy on the original dataset). To ensure quick loss computation over a large set of training images, interval bound propagation (IBP) (Gowal et al., 2019;Mirman et al., 2018) is the most popular technique. However, previous IBP works mainly consider norm-based perturbations, which do not capture the highly nonuniform adversarial input regions that characterize geometric transformations.
We denote a neural network as a function f : R C×H×W → R no from an H × W image with C channels to n o real values. We focus on feedforward networks, but our approach is general and equally applicable to other architectures. Let x ∈ R C×H×W denote an input image and y denote its corresponding label. For the remainder of the paper, we write interval variables with a tilde: e.g., x = [x, x] = {x : x ≤ x ≤ x} is an interval with x and x as lower and upper bounds, respectively. First, we detail the geometric transformations that our work considers.
A geometric image perturbation is a function P : R C×H×W × R |θ| → R C×H×W , which takes an input image x and parameters θ (e.g., angle of rotation, amount of brightness), then produces the geometrically perturbed image x ′ . We consider interpolated transformations ± rotation, translation, scaling, and shearing ± and pixelwise transformations ± contrast and brightness. For ease of expression, since these transformations (Eqs. 2 and 3 below) apply independently to each image channel, we write x i,j to denote x's pixel in the i th row and j th column of an arbitrary channel.
Interpolated Transformations. Interpolated transformations involve an affine transformation on each pixel's row and column indices, followed by an interpolation operation. As these operations are performed in the 2D plane, we first interpret the row and column indices (i, j) as points (u, v) ∈ R 2 , where the u-axis is the horizontal axis and the v-axis is the vertical axis. Here, we define functions ϕ u (j) = j -(W -1)/2 and ϕ v (i) = (H -1)/2 -i, which convert zero-indexed i, j indices to u, v coordinates with respect to the center of an H × W image. Let T θ : R 2 → R 2 be an invertible affine transformation (e.g., rotation, translation) parameterized by θ (e.g., rotation angle, amount of horizontal shift). The equations for each affine transformation are given in Eqs. 10-13 in Appendix A. To compose multiple perturbations, we compose their respective affine transformations; for example, scaling by λ, rotating by φ, then shearing by γ results in the transformation v) where θ = (λ, φ, γ). Having converted row-column indices to R 2 , we compute for each location (ϕ u (j), ϕ v (i)) the (real-valued) coordinate that maps to this location under T θ ; we can obtain this coordinate as
, where T -1 θ is the inverse transformation. Since these transformed coordinates may not align exactly with integer-valued pixel indices, we must interpolate. We consider the bilinear interpolation kernel of Jaderberg et al. (2015), given as:
The value of each pixel in the interpolated image x ′ is then:
Pixelwise Transformations. The cumulative effects of contrast and brightness acting on the pixel x i,j are given by the respective contrast and brightness perturbation parameters α, β ∈ R, as described in Balunovic et al. (2019); Mohapatra et al. (2020):
For each pixel in the input and each neuron in the DNN, verification with interval bound propagation (IBP) (Gowal et al., 2019) associates an interval bounding its minimum and maximum values.
A sound verifier propagates intervals through the network from the input to the output layer by evaluating the network's layers using interval arithmetic; we detail these operations in Appendix B.
We now show how to certify the geometric robustness of classification and regression networks.
Certified Classification Robustness Against Geometric Transformations. Given an interval x enclosing the set of possible perturbations on the input and a classifier f , we denote the worst-case output vector as f (x), where (interpreting all operations via interval arithmetic) the correct class's entry is the lower bound and all other entries are the upper bounds of the network's output:
We say that f is certifiably robust for x if, even in the worst case, we can still guarantee that the network classification is correct: y = arg max i fi (x). To certify geometric robustness on an image x requires computing its bounds as x = P (x, θ), where θ = [θ, θ] is an interval vector bounding the range of geometric perturbation parameters, and the geometric perturbation P is interpreted over interval arithmetic. However, for a given range of perturbation parameters θ for which we wish to verify robustness, the interval width θ -θ may be too large for the direct evaluation of f (P (x, θ)) to yield bounds that are precise enough for successful certification. Hence, like other geometric robustness verifiers (Balunovic et al., 2019;Mohapatra et al., 2020), we employ parameter splitting.
We subdivide the entire range of parameters θ into K smaller disjoint intervals { θ1 , θ2 , . . . , θK } where θ = K k=1 θk , and certify each split θk independently. If verifying all splits succeeds, then certification holds on the entire parameter range θ. As interval bounds are constants and do not symbolically depend on the input parameters (unlike DeepG (Balunovic et al., 2019)), propagating these bounds is highly efficient and can be done on a large number of parameter splits for improved precision. Accounting for splitting, we say that f is certifiably robust for P (x, θ) if:
Certified Regression Bound Against Geometric Transformations. Distinct from classifiers, as regression tasks do not have a strict notion of correctness, our goal is to verify whether a network's outputs are within a range close to the ground truth. Hence, our certification problem is to directly bound the network outputs. For a regression network f (interpreted over interval arithmetic), the certified output range over the input P (x, θ) is the smallest interval containing the union of all splits' output bounds:
We now describe the formulation of our provable defense and fast geometric verifier (FGV) that comprise our training framework for certified geometric robustness.
Training Classification DNNs. The key to incorporating geometric robustness guarantees into training lies in formulating certification as part of the loss function. Since f represents the worstcase classification output under a range of perturbed inputs, we can use it in the training loss to guide the parameter updates toward obtaining provably robust DNNs. To account for parameter splitting during certification (which is unique to our geometric setting), we formulate our training loss to enforce local robustness at the level of individual input splits. To certify the network across the entire desired range θ = [θ, θ], we enforce this local property across all splits. Furthermore, similar to other works on certified training, we also need to enforce high clean accuracy. This yields the following formulation for the ideal robust classification loss:
where ℓ can be any classification loss function (we use the cross-entropy loss) and κ ∈ [0, 1] governs the relative weighting between the clean accuracy and geometric robustness terms (with higher κ prioritizing clean accuracy).
In practice, the loss in Eq. 7 is too computationally expensive, since the runtime scales linearly with the number of splits, which often needs to be large to ensure precise certification. As a remedy, we instead enforce the robustness property stochastically using data augmentation in conjunction with a randomized sampling of interval splits. We uniformly sample a scalar perturbation amount θ ∼ U(θ, θ) and compute a local interval split θl = [θ -ν, θ + ν], where ν is a hyperparameter vector governing the interval size of each perturbation parameter. We then compute the tractable robust classification loss as:
Since we sample a different θ for each mini-batch of training samples, this approach will, on average, effectively enforce local robustness over the entire parameter range (hence leading to global robustness). As in prior works (Gowal et al., 2019;Xu et al., 2020;Zhang et al., 2020), we can vary κ with the training iteration, temporally changing the weighting between clean accuracy and robustness. The hyperparameter vector ν is akin to ϵ in the ℓ ∞ -norm case, but it governs the size of a geometric ball P (x, θl ) rather than an ϵ-ball; note that ν is a vector, since the interval size corresponding to each geometric transformation may be different. We show that this hyperparameter is easy to determine. Finally, while this loss function incorporates only IBP to propagate the geometric region through the network, it can be easily adapted to other provable training methods like CROWN-IBP (Zhang et al., 2020) by substituting the ϵ-balls in their loss functions with our formulation of local geometric balls.
Training Regression DNNs. Since our goal is to minimize both the width of the certified output bound as well as its distance to the ground truth, the ideal scenario would be when the certified lower and upper bounds coincide at the ground truth. Hence, we can essentially treat the certified bounds as worst-case network outputs and minimize both the lower and upper bounds' distances to the label. With similar insights gleaned from the classification loss function, we thus formulate the robust regression loss as:
where ℓ can be any regression loss function (we use the mean squared error).
While we experimentally focus on the more common interpolated transformations, our loss formulations can also be used for other parameterized semantic perturbations on which interval overapproximations for each pixel can be computed, such as Gaussian blur or color space perturbations.
A key technical challenge arises during the computation of the loss functions in Eqs. 8 and 9: we need to perform geometric robustness certification on images at every iteration of training. Certification against geometric transformations requires two key steps: (1) obtaining bounds on the set of perturbed images obtainable after applying geometric perturbation P and (2) propagating these bounds through a neural network. The key bottleneck of existing geometric verifiers, which renders them unusable for training, lies in the first step (which we show in Section 5.3). This bottleneck stems from the fact that when computing the interpolation, the sequence of arithmetic computations performed at each pixel can be drastically different depending on the pixel location, which has precluded existing approaches from leveraging parallelism. Thus, a core part of our contribution is designing a novel and efficient GPU-parallelizable method for computing interpolated transformations over interval bounds: serving the dual purpose of speeding up verification and being able to utilize these bounds during training. Algorithm 1 presents the pseudocode. Additionally, we also show a running example in Appendix C.1. By default, areas of an interpolated image with no corresponding source pixel will be padded with zero, as in Balunovic et al. (2019). However, our algorithm is agnostic to the particular padding mode: we discuss how to handle other padding strategies (e.g., replicating the border pixel values) in Appendix C.2.
We mathematically decompose the interpolated transformations (Eqs. 1 and 2) into three parts which are all GPU-parallelizable: computing the coordinates of each pixel location under inverse transformation
, and finally obtaining the resulting interpolated images. Our key insight is that the first two steps are solely dependent on the transformation T θ and the height and width of the images, but not the image pixel values themselves. Hence, these computations need only be done once for a given transformation range, amortizing the cost for any number of images in a batch. We now detail each part.
Inverse Coordinates 1 . We first determine the inverse coordinates (ũ ′ , ṽ′ ) = T -1 θ (ϕ u (j), ϕ v (i)) for each (i, j) pixel index, where 0 ≤ i < H and 0 ≤ j < W for images with height H and Algorithm 1 Fast interval interpolated transformation.
Tθ, an interpolated transformation with interval parameters θ
g ← flatten( G) 10:
q ← get nonzero indices(g) 11:
w ← g[q] 12:
(r, c) ← (⌊(q mod HW )/W ⌋, (q mod HW ) mod W ) 13:
return Gs ← (r, c, w, z) 14: end procedure 15: 16: procedure INTERPOLATE(X, Gs) 17:
(r, c, w, z) ← Gs 18:
width W . The inverse transformations (shown in Appendix A Eqs. 10-13) are pixelwise, hence this step can immediately be parallelized by defining the matrices U, V ∈ R H×W where U (i, j) = ϕ u (j) and V (i, j) = ϕ v (i), then applying T -1 θ over this whole grid of coordinates. Since T -1 θ is parameterized by an interval range of parameters θ, this inverse transformation and all subsequent arithmetic operations are interpreted via interval arithmetic.
Interpolation Grid 2 and Exploiting Sparsity 3 . For each (ũ ′ , ṽ′ ), we next calculate the terms max(0, 1 -|ṽ
Eq. 1; we call these terms interpolation distances and denote them dũ ′ ,ṽ ′ n,m . Here lies a key difference between our interpolation formulation and that of sequential implementations. In the sequential case, one need only compute dũ ′ ,ṽ ′ n,m for n where ṽ′ ≤ ϕ v (n) ≤ ṽ′ and m where ũ′ ≤ ϕ u (m) ≤ ũ′ ; this is because all other values of n, m will evaluate to a distance of 0. Yet since these ranges of n, m can be vastly different for each (ũ ′ , ṽ′ ), the only way to parallelize the simultaneous computation of these distances for all inverse coordinates is to, for each (ũ ′ , ṽ′ ), compute dũ ′ ,ṽ ′ n,m for all 0 ≤ n < H, 0 ≤ m < W . We term these computed distances the interpolation grid G. However, since most of the entries in G will be 0 (i.e., the degenerate interval [0, 0]) ± typically more than 99% of them ± we design a custom sparse tensor representation of G so that when interpolating, only the nonzero entries will be multiplied with image pixel values (i.e., computing x n,m • dũ ′ ,ṽ ′ n,m only when the distance is nonzero). First, for each nonzero dũ ′ ,ṽ ′ n,m , we must know its location (i.e., n, m) so that we can multiply its value with the corresponding image pixels in the same location. To do so, we convert G to COO (coordinate) format, a 3-tuple of vectors: w which stores the nonzero values of G, and r, c which store the nonzero values' row and column indices n, m. However, once we actually interpolate across images and obtain the summands sũ ′ ,ṽ ′ n,m = x n,m • dũ ′ ,ṽ ′ n,m , we need to know which summands contribute to the same pixel (i.e., have the same ũ′ and ṽ′ ) and should thus be added together; this is challenging since the grid values have been flattened. To solve this issue, we store an additional vector z that records the number of nonzero interpolation distances for each (ũ ′ , ṽ′ ).
Obtaining Interpolated Images 4 . After calling MAKEINTERPGRID (which only needs to be done once for a given set of transformations) and obtaining Gs = (r, c, w, z), we can now efficiently interpolate across any batch of images X. For all batch and channel dimensions, we obtain the pixel values at locations corresponding to the interpolation distances in w (by indexing the last two dimensions of X with r, c) and elementwise multiply with w to obtain S, which contains the values of all summands across all pixels. To recover the final pixel values, we sum the terms belonging to the same pixel (i.e., the sũ ′ ,ṽ ′ n,m that have the same ũ′ , ṽ′ ) together. To do so, we split the last dimension of S into HW chunks {h i } HW i=1 , where each h i has length z i ; then, each chunk's sum is exactly the final pixel value. Since this last dimension has been flattened to take advantage of sparsity, we reshape it back to dimension H × W to obtain the final interpolated images.
Finally, we use IBP (during both training and certification) to propagate the computed geometric bounds through the neural network.
We evaluate the effectiveness of CGT over multiple datasets, network architectures, and transformations. We implemented CGT atop PyTorch (Paszke et al., 2019) and use auto_LiRPA (Xu et al., 2020) to propagate our computed geometric perturbation bounds through neural networks.
Datasets and Architectures. We evaluate our approach on the MNIST, CIFAR10, Tiny ImageNet, and Udacity self-driving car datasets. The first three are image classification tasks, while the last is a regression task that predicts a steering angle given a driving scene image. On MNIST and CIFAR10, we use the same architectures from DeepG (Balunovic et al., 2019) as to compare directly with their results. On Tiny ImageNet, we use the 7-layer convolutional network (CNN7) and WideResNet architectures from Xu et al. (2020). On Udacity, we use the classic Nvidia architecture from Bojarski et al. (2016). Details are in Appendix D.1.
Metrics. Our primary metrics for a classifier are (1) its clean accuracy, (2) its certified robustness under geometric transformations, and (3) the certification time on the test set. For a regression network, we utilize the analogous metrics of (1) mean absolute error (MAE), (2) certified MAE, i.e., the larger of the certified lower and upper bounds' MAEs, as well as (3) certification time. We also measure per-epoch runtime and GPU memory usage during training (shown in Appendix E.4).
Baselines. To the best of our knowledge, training a DNN via PGD (Madry et al., 2018) combined with data augmentation (denoted PGD/A) and certifying it with DeepG produces the current stateof-the-art deterministic geometric robustness and accuracy. However, the DeepG verifier does not scale beyond CIFAR10; hence, we compare our approach to theirs on just the MNIST and CI-FAR10 datasets, using the sets of transformations from their work. Notably, DeepG only certifies 100 images (due to long runtimes), while we certify full test sets of 10,000 images. The work of Semantify-NN (Mohapatra et al., 2020) is strictly less precise than DeepG and also only handles a single interpolated transformation (rotation); thus, we only compare certification with DeepG. However, they propose an algorithm to compute the interval over-approximation of images under rotation, and we provide an ablation study comparing the speed of Algorithm 1 to theirs.
Hyperparameters. We show the training and certification hyperparameters in Appendices D.2 and D.3 and explain how to tune these hyperparameters in Appendix D.4.
Hardware. We trained and certified all networks (except WideResNet) on a machine with a 2.40GHz 24-core Intel Xeon Silver 4214R CPU with 192GB of main memory and one Nvidia A100 GPU with 40GB of memory. All baseline results were also run on the same hardware for fair comparisons. For WideResNet, we used the same CPU with four A100 GPUs.
Table 1 presents the comparison of our approach with DeepG; asterisks denote DeepG certification results over a subset of 100 images (since their approach takes too long to run on the full test set). Over a variety of challenging transformations on MNIST and CIFAR10, our approach consistently achieves state-of-the-art performance. On all MNIST experiments, our certified robustness is substantially higher than DeepG, while attaining comparable clean accuracy. Furthermore, our verifier Table 1: Comparison of network certification time and accuracy with the prior state-of-the-art on MNIST and CIFAR10. We denote R(φ) a rotation of ±φ degrees; T u (∆u) and T v (∆v) a translation of ±∆u pixels horizontally and ±∆v pixels vertically, respectively; Sc(λ) a scaling of ±λ%; Sh(γ) a shearing of ±γ%; C(α) a contrast change of ±α%; and B(β) a brightness change of ±β. Asterisk denotes that certification was measured on a subset of 100 test images. is several orders of magnitude faster. On CIFAR10, we achieve significantly better tradeoff between certified robustness and accuracy than the baseline for the first two cases, while obtaining similar results on the third transformation set; our certification time is considerably lower than DeepG. For the first and third CIFAR10 experiments, we attain 65% and 49% on the subset of 100 images used by DeepG (which are equal or better than their results), while the certifiability evaluated over the whole test set (presented in the table) is slightly lower. These results show that rather than using more precise abstractions on the input set to certify networks not trained to be provably robust, it is more effective to explicitly train networks to be certifiably robust and verify them with a less precise but faster verifier (with a large number of parameter splits). Using our custom loss formulation in Eq. 8 yields the best results on our verifier; Table 6 in Appendix E.1 shows that other existing ℓ ∞ -based training methods (which cannot incorporate geometric bounds) do not perform as well. Our work can scale to larger datasets like Tiny ImageNet and a real-world autonomous driving dataset where previous approaches do not.
Table 2 presents our results on Tiny-ImageNet networks trained for the shear, scale, and rotation transformations. For both networks, we observe that our approach preserves a relatively high clean accuracy while obtaining substantial robustness guarantees. For context, in Xu et al. (2020) for ℓ ∞ -robustness with ϵ = 1/255, they attain 21.6% accuracy and 12.7% certified robustness on CNN7 and 27.8% accuracy and 15.9% certified robustness on WideResNet. Certification time is still fast, even though the images are much higher-definition than MNIST and CIFAR10, showcasing FGV's scalability. We also see that our approach scales well to large state-of-the-art models like WideResNet. While there is an inherent tradeoff between certified robustness and network performance on the previous datasets, we find that, surprisingly, here we can scale our approach to obtain both high certifiability and improve network performance at the same time. To demonstrate this phenomenon, we train a network with (1) just the regular mean-squared error loss and input data augmentation of ±2 • rotation (Regular), (2) the first method with the addition of dropout on linear layers (Dropout), and (3) our CGT formulation in Eq. 9.
Table 3 presents our results for the standard and certified errors of these training methods (lower is better). An interesting observation is that this task is prone to overfitting: we can observe that adding dropout significantly improves the standard error of the network. In this case, training with CGT's interval bounds actually acts as an effective regularizer that serves the dual purpose of combatting overfitting and enforcing certifiability. Training without CGT leads to trivial certification bounds (i.e., the certified steering angle can be anywhere in ±90 • ); conversely, training with CGT yields very tight certified bounds. Fig. 1 shows visualizations of the CGT-trained network's predictions and certified bounds.
Algorithm for Interval Interpolated Transformation. In Appendix E.3, we compare Algorithm 1 to Semantify-NN's algorithm for computing interval rotation bounds. We show that our algorithm is orders of magnitude faster, hence enabling our scalable training and verification approaches.
Effect of Parameter Split Size. We train a CIFAR10 and Tiny ImageNet network with various sizes of the hyperparameter ν and discuss how it affects certified and clean accuracy in Appendix E.2.
We proposed Certified Geometric Training (CGT), a provable defense that leverages a novel fast geometric verifier to improve the deterministic certified robustness of neural networks with respect to geometric transformations. Our experiments across multiple datasets and perturbation sets showed that CGT consistently attains state-of-the-art certified deterministic geometric robustness and clean accuracy, while being highly scalable.
We detail the network architecture(s) used for each dataset below. We express a convolutional layer as a 4-tuple of (number of filters, kernel size, stride, padding).
• MNIST: 2 conv layers {(32, 4, 2, 1), (64, 4, 2, 1)} followed by 2 linear layers with {200, 10} neurons. All layers are followed by a ReLU activation, except for the final output layer. • CIFAR10: 3 conv layers {(32, 3, 1, 1), (32, 4, 2, 1), (64, 4, 2, 1)} followed by 2 linear layers with {150, 10} neurons. All layers are followed by a ReLU activation, except for the final output layer. • Tiny ImageNet: ± CNN7: 5 conv layers {(64, 3, 1, 1), (64, 3, 1, 1), (128, 3, 2, 1), (128, 3, 1, 1), (128, 3, 2, 1)} followed by 2 linear layers with {512, 200} neurons. Each conv layer is followed by a batch norm layer then a ReLU activation. The first linear layer is followed by a ReLU activation. ± WideResNet: Let Q x (p i , p o , s) denote the output after feeding x through this sequence of layers: batch norm with p i features, ReLU, conv(p o , 3, 1, 1), batch norm with p o features, ReLU, conv(p o , 3, s, 1); let S x (p i , p o , s) denote the output after feeding x into a conv(p o , 1, s, 0). Then, we define a wide basic block as the function
The architecture of the network is then: a conv layer (16, 3, 1, 1), W x (16, 160, 1), W x (160, 320, 2), W x (320, 640, 2), batch norm, ReLU, average pooling with a 7 × 7 kernel, then finally a linear layer with 200 neurons. • Driving: 5 conv layers {(24, 5, 2, 0), (36, 5, 2, 0), (48, 5, 2, 0), (64, 3, 1, 0), (64, 3, 1, 0)} followed by 4 linear layers with {100, 50, 10, 1} neurons. All layers are followed by a ReLU activation, except for the final output layer. For the Dropout network, we add a dropout layer with p = 0.5 after the first 3 linear layers.
Training Schedule. We train the MNIST networks for 100 epochs with batch size 256, CIFAR10 networks for 120 epochs with batch size 128, Tiny ImageNet networks for 160 epochs with batch size 128 (CNN7) or 400 (WideResNet), and the self-driving network for 50 epochs with batch size 128. For the classifiers, we first train with only the cross-entropy loss during a warm-up period; we warm up for 15 epochs on MNIST and 30 epochs on CIFAR10 and Tiny ImageNet. For the selfdriving network, we directly use Eq. 9 from the start. In order to ensure convergence for the loss, we linearly decay κ from 1 to κ f = 0.5 and employ a linear ramp-up schedule to slowly increase the value of ν from 0 up to a final parameter size of ν f ; we ramp up across 50, 60, 80, and 50 epochs for MNIST, CIFAR10, Tiny ImageNet, and self-driving, respectively. We explain how to tune the hyperparameter ν f and provide the values of ν f for each experiment in Section D.4.
Data Preprocessing and Augmentation. For all networks, we augment the input images during training according to the set of transformations to which we want to be robust. In addition, for CIFAR10 and Tiny ImageNet, we also perform random horizontal flips and select random crops of 32 × 32 with padding 4 (for CIFAR10) and random crops of 56 × 56 (for Tiny ImageNet). At test time, we use a central crop of 56 × 56 for Tiny ImageNet. For the self-driving dataset, we first crop the top of the 480 × 640 input images to 280 × 640, then resize them with bilinear interpolation to 66 × 200; we also perform random horizontal flips. For all datasets, we normalize input images according to the channel statistics from the train set immediately before the first network layer.
Optimizer. We use the Adam optimizer (Kingma & Ba, 2015) across all networks. For MNIST and CIFAR10, we use an initial learning rate of 10 -3 , which we decay by 0.1 at the 80th and 100th epoch, respectively. For Tiny ImageNet, we use an initial learning rate of 5 × 10 -4 , which we decay by 0.1 after 120 and 150 epochs. For self-driving, we use an initial learning rate of 10 -3 , which we decay by 0.1 after 20 and 40 epochs. For all networks, we clip gradients at an ℓ 2 -norm of 8. 8.94 × 10 -3 2.82 × 10 -2 4.52 × 10 -3 1.42 × 10 -2 Sc(1), R(1), C(1), B(0.001) 6.37 × 10 -3 1.26 × 10 -2 6.37 × 10 -3 1.26 × 10 -2 Tiny ImageNet Sh(2) 1.21 × 10 -3 4.90 × 10 -3 2.44 × 10 -4 9.82 × 10 -4 Sc(2)
2.39 × 10 -3 8.76 × 10 -3 4.81 × 10 -4 1.76 × 10 -3 R(5)
2.15 × 10 -3 7.88 × 10 -3 8.63 × 10 -4 3.17 × 10 -3
Driving R(2) 2.82 × 10 -3 1.51 × 10 -2 7.71 × 10 -4 4.00 × 10 -3
Batch Size. We use a batch size of 10,000, 10,000, 2,000, 400, and 3,000 during the certification of MNIST, CIFAR10, Tiny ImageNet CNN7, Tiny ImageNet WideResNet, and self-driving networks, respectively.
Parameter Splits. To ensure precise certification, we select parameter splits that are 1-5× smaller in width than those used during training. The certification configurations for each experiment can be found in Section D.4.
In Table 4, we show the interval sizes of the geometric perturbation parameters that we use during training and certification for all experiments. In the Training column, we present the final (i.e., after ramp-up) interval size of each perturbation parameter used during training. Since we enforce a local geometric ball of up to ±ν f in Eqs. 8 and 9, the interval size of this ball is 2ν f (where ν f is the final parameter interval size after ramp-up, as discussed in Section D.2). In the Certification column, we present the interval size of each split used during robustness certification. For experiments with multiple perturbations, the ordering of the sizes corresponds with the ordering of the transformations in the Perturbations column.
We describe below the procedure to obtain the values of ν f shown in Table 4: 1. For a given set of n perturbations P with interval parameter ranges θ = [θ, θ], we first start with an arbitrary ν f such that ν f i < θ i -θ i for all 1 ≤ i ≤ n.
2. Then, we uniformly sample 10 random scalar parameter values {θ k } 10 k=1 (where each θ k ∼ U (θ, θ) as in Eqs. 8 and 9) and compute, over all train set images X ∈ [0, 1] N ×C×H×W , the maximum pixel interval width of each image under perturbation of P with parameters
given X ′ i denotes the i th perturbed image in the train set. Essentially, in this step we are converting interval sizes in parameter space to pixel space to gauge the amount of overapproximation in the computed bounds (as it is the pixel's intervals that are ultimately propagated through the network). Now, we calculate the average maximum pixel interval width over all images and parameter samples, obtaining µ = mean{mean M k } 10 k=1 . We find that selecting ν f such that µ is close to typical values of ϵ used in the ℓ ∞ -norm setting (e.g., 0.2 and 0.4 for MNIST, 4/255 and 8/255 for CIFAR10) yields both accurate and certifiable networks. If µ > ϵ, then we reduce ν f (hence reducing the amount of over-approximation) and recompute this step until µ ≈ ϵ. Note that this tuning requires no training, and µ can be computed in under a minute for all the datasets that we consider.
3. Once appropriate values of ν f have been determined from step (2), we can proceed to use them in training. We perform a 80-20 train-validation split of the train set, and use CGT to train a network to completion. If the validation accuracy and robustness are sufficiently high, then no further tuning is required. Else, we reduce ν f and repeat this step. We only had to do this step a few times, as the calculation of the pixel widths already provided a good heuristic for network performance.
After determining the appropriate parameter sizes during training time, selecting the certification split sizes is straightforward. We empirically find that selecting parameter sizes that are 2× smaller than those used during training yields a good balance between certification rate and runtime. If faster certification time is desired, one can use the same parameter sizes at both training and certification time (as we do in the CIFAR10 experiment with scaling, rotation, contrast, and brightness). If higher certification rate is desired, one can use parameter sizes that are even smaller, at the cost of higher runtime (e.g., we find 5× to be effective for Tiny ImageNet, while using parameter sizes that are even smaller has diminishing returns and does not appreciably increase certification rate).
Table 5 shows the maximum pixel interval width during training and certification for each experiment. Additionally, we also show the average pixel interval width (i.e., Eq. 16 with the max operation replaced by mean) to demonstrate that geometric transformations produce highly nonuniform bounds, further motivating why supplying precise geometric bounds during training is crucial to achieving networks that are both accurate and certifiable.
To demonstrate the benefit of our loss function, we compare CGT with three baseline training methods: (1) data augmentation, denoted Augment.;
(2) augmentation with PGD (Madry et al., 2018), denoted PGD+A; and (3) augmentation with IBP (Gowal et al., 2019), denoted IBP+A. We select these baselines because, to the best of our knowledge, they are the only training methods utilized in existing works on deterministic geometric robustness (as no work incorporates precise geometric regions into training as we do). For (1), the loss function is simply the cross-entropy loss, with input images augmented according to the perturbations we are trying to certify. For (2), we use PGD to generate adversarial examples of the augmented images. For (3), we employ the IBP loss, with interval ϵ-balls placed around the augmented images. Table 6 shows these comparisons on the MNIST translation and CIFAR10 rotation benchmarks. For the PGD and IBP-based baselines, we select ϵ = 0.1 and ϵ = 2/255 for MNIST and CIFAR10, respectively, which are commonly used in the literature (Balunovic et al., 2019;Gowal et al., 2019;Zhang et al., 2020). For PGD, we use a step size of 0.005 and 40 steps for MNIST and a step size of 0.002 and 7 steps for CIFAR10. When calculating the time and memory statistics for CGT and IBP+A, we only consider the epochs after warm-up (i.e., when we start computing the interval robustness loss term). We can observe that our approach, which can supply precise bounds that correspond to the geometric perturbations we are trying to certify, is able to attain the best certified accuracy while maintaining high clean accuracy and only using slightly more time and memory compared to the other approaches.
Table 7: Variation of clean and certified accuracy as a function of ν f . c is the certification interval size, ν o is the value of ν f used in our main results, and g = ν o -c.
Accuracy Type As the size of the local geometric ball (controlled by ν) is a key training hyperparameter of our loss function in Eq. 8, we conduct an ablation study on a CIFAR10 network and Tiny ImageNet CNN7 on how varying ν f (i.e., the final parameter interval size after ramp-up, as discussed in Section D.2) affects the certified and clean accuracies of CGT-trained networks. Table 7 presents these results.
In addition to the original value of ν f used in our benchmarks in Sections 5.1 and 5.2 (denoted ν o ), we select four additional settings for ν f and train with CGT for each of these values. We choose the smallest ν f to be equal to the interval size at certification time, c, and the largest ν f to be equal to c plus two times the difference between ν o and c. We certify all networks with the original size of c.
We can observe that generally, larger values of ν f lead to increased certified accuracy, at the cost of decreased clean accuracy. CGT thus allows one to explicitly tune the tradeoff between these metrics by varying ν f . The notable exception to this trend is the CIFAR10 network with the largest ν f ; in this case, using a ν f that is excessively large actually decreases certified robustness (since the clean accuracy drops considerably). There are diminishing returns to using larger intervals during training: while the certified accuracy increases significantly when using ν f = ν o compared to ν f = c, further increasing the size to ν f = ν o + g/2 or above only slightly increases certifiability.
We demonstrate why FGV is a necessary component of our framework. Table 8 presents the comparison of Algorithm 1 to the state-of-the-art algorithm for computing interval geometric bounds in Semantify-NN (Mohapatra et al., 2020), which is sequential and CPU-only. To compute interval rotation bounds for a batch of training images (256 for MNIST and 128 for CIFAR10 and Tiny ImageNet), we are 8,000-20,000× faster. Our end-to-end speedup when combining both the input geometric perturbation bound computation and the propagation of these bounds through the network is 3,000-5,000×. For Tiny ImageNet, we use the CNN7 network in this experiment. These results show that without Algorithm 1, the overhead during training is too high to use our proposed loss functions in Eqs. 8 and 9.
As an ablation study, we run our algorithm under the same conditions as Semantify-NN's on the CPU and with a batch size of 1. As seen in Table 9, our runtime is still 100-200× faster than Semantify-NN's. These results show that our speedup is not only due to the ability to leverage GPU hardware, but also due to fundamental algorithmic improvements that allow the computation of interpolated transformations to be efficiently parallelized.
Table 10 shows the training statistics of runtime per epoch and GPU memory usage for all of our networks. When calculating the time and memory statistics, we only consider the epochs after warm-up (i.e., when we start computing the interval robustness loss term).