We augment adversarial training (AT) with worst case adversarial training
(WCAT) which improves adversarial robustness by 11% over the current state-
of-the-art result in the `2-norm on CIFAR-10. We interpret adversarial training as
Total Variation Regularization, which is a fundamental tool in mathematical im-
age processing, and WCAT as Lipschitz regularization, which appears in Image
Inpainting. We obtain verifiable worst and average case robustness guarantees,
based on the expected and maximum values of the norm of the gradient of the
loss. We augment adversarial training (AT) with worst case adversarial training (WCAT) which improves adversarial robustness by 11% over the current state-of-the-art result BID27 in the 2 norm. The method also achieves results comparable to the state-of-the-art results of BID22 in the ∞ norm. Moreover, our adversarial training step uses only one gradient evaluation compared to seven steps in the BID22 work. The worst case adversarial training method is described as follows. During adversarial training, the gradient of the loss is computed for each perturbed image. WCAT records the largest of the gradients norms, and adds a penalty to the loss proportional to this term. In many cases we observe that models trained with AT and WCAT have improved test/validation error over the unregularized model. In §2 we show that the norm of the gradient of the loss of the model is a measure of the robustness of a model to adversarial examples. We obtain verifiable worst and average case robustness guarantees, based on the expected and maximum values of the norm of the gradient of the loss. We then compute these quantities empirically on trained models, and demonstrate that improving these quantities leads to proportional improvements in adversarial robustness. In §3 we interpret adversarial training as Total Variation (TV) Regularization, which is a fundamental tool in mathematical image processing. TV regularization was introduced for image denoising BID29 . It is a measure of the variation of a function, allowing for discontinuities. We also show that WCAT corresponds to Lipschitz regularization, which appears in Image Inpainting BID2 and function approximation BID7 BID25 . Lipschitz regularization was used in a recent proof of generalization of deep neural networks BID26 . Write (x) = • f (x) for the loss of the model. We show that training with AT and WCAT is equivalent to minimizing DISPLAYFORM0 where is the size of the adversarial training perturbation, and λ is the WCAT multiplier. The dual norm · * corresponds to · 1 for attacks measured in ∞ and to · 2 for attacks measured in 2 , 1 see §3.1. The earliest and most successful defense is adversarial training BID31 ; BID11 ; BID32 ; BID22 ). Top entries in a recent adversarial defence competition BID21 ) used Ensemble Adversarial Training BID32 ), where a model is adversarially trained with inputs generated by an ensemble of other models. For more background, refer to the recent review which discusses defences against adversarial attacks and their limitations. Adversarial attacks seek to find the minimum norm vector which leads to a misclassification by the model. Finding the optimal attack is intractable BID0 ). An alternative which permits loss gradients to be used is to consider the attack vector measured in a given norm which most increases the loss, max a ≤ε (x + a).Adversarial training improves robustness to adversarial attacks by solving the minimax problem DISPLAYFORM0 In practice, a tractable attack vector, a(x), is used, in place of the optimal δ, leading to DISPLAYFORM1 Weng et al. FORMULA1 and BID15 showed that the Lipschitz constant of the model can be used to establish rigorous worst-case bounds on adversarial robustness. In particular Weng et al. (2018) show that the Lipschitz constant of the model gives a certifiable minimum adversarial distance: a successful attack on image x will have adversarial distance at least DISPLAYFORM0 where L f is the Lipschitz constant of the model, f , and i * is the correct label of x. Thus training models to have small Lipschitz constant should improve adversarial robustness BID15 ; BID33 ). Remark 2.1 (Application of empirical Lipschitz constants). In theory, it is possible to extend the data with a function whose Lipschitz constant matches that of the data see §C for more details. We argue that a model whose Lipschitz constant better approximates the Lipschitz constant of the data brings us closer to the ground truth. Lipschitz regularization brings the (estimated) Lipschitz constant of a model close to the Lipschitz constant of the data on which it was trained. For example on CIFAR-10, the Lipschitz constant for the dataset is 0.36. For a regularized model (ResNeXt-34, see §5) the estimated Lipschitz constant was 1.32, but was 13.70 for an undefended model (the latter two measured on the test/validation set). Here we obtain adversarial robustness bounds based on the gradient of the loss of the model. The second and third terms in (1) estimate the average and worst case robustness. The first part of the following result is the analogue of (2), with the model loss instead of the model (which is a scalar instead of a vector). The second part of the result gives an average case robustness bound. Lemma 2.2 (Worst-case and expected stability). Write (x) = • f (x) for the loss of the model. Let a be any adversarial perturbation of norm a( DISPLAYFORM0 The proof is in §B.1 Remark 2.3 (Application of robustness guarantees). One possible use of the result is that we can estimate adversarial robustness on unseen data drawn from the same distribution using the values of the terms corresponding to AT and WCAT in (1) The next result interprets adversarial training using either the one-step Signed Gradient attack vector or the gradient attack vector as Total Variation regularization. Lemma 3.1. Adversarial training using the ε-scaled one step attack vector is equivalent up to terms of order ε 2 to augmenting the loss with Total Variation regularization, DISPLAYFORM1 where the · * is the dual norm to the norm measuring adversarial perturbations. The proof is in §B.2. The basis for this result is Rademacher's Theorem (Evans, 2018, §3.1) , which states that if a function g(x) is Lipschitz continuous then it is differentiable almost everywhere and DISPLAYFORM0 We obtain an underestimate of Lip(g) by sampling the norm of the gradient on a subset of points. During training, we apply (5) to (x) and set D to be a mini-batch to obtain the WCAT term in (1). When we estimate the Lipschitz constant of a trained model, we use the full test/validation dataset. Remark 3.3. Regularization of the loss corresponds to partially regularizing the model, but at a much lower cost. Since the loss is a scalar, regularizing by the Lipschitz constant of the loss is equivalent to regularization of the model f in one direction. By the chain rule, DISPLAYFORM1 For example, when is the KL divergence, and when f = softmax(z(x)) then DISPLAYFORM2 Thus, in this case, regularizing (x) corresponds to regularization of z(x) in the direction f (x) − y. Data independent upper bounds on the Lipschitz constant of the model go back to BID1 . These bounds are based on the product of the norm of the weight matrices, and neglect the effects of the activation function. We summarize this upper bound as follows. Let W k be the weight matrix of the k-th layer of a network f comprised of N layers, and suppose all non linearities of a network are at most 1-Lipschitz. Then DISPLAYFORM0 with p 0 = p and p n = q. Certain conditions on the p k 's must be met. For a proof with p, q = 2 see BID33 .Recent works based on this estimate include: BID6 , using the distance to the nearest orthonormal matrix; BID23 , using the 2-norm; BID12 , using either the 1-norm or ∞-norm; and BID27 , using the ∞-norm. In these works, the estimate is used to penalize the Lipschitz constant of the model during training, and so the the logarithm of the estimate is used. Of these four papers, only the implementation of Gouk et al. accounts for batch normalization. Since batch normalization multiplies each weight matrix by a diagonal scaling matrix, the other works are missing important terms in their implementations. A different method for estimating the Lipschitz constant of a pre-trained model was presented in Weng et al. FORMULA1 , using statistical techniques from extreme value theory. This estimate accurately captures the minimum adversarial distance needed to successfully misclassify an image. However it requires at a minimum many tens of model evaluations for each image, and so is not tractable as a Lipschitz penalty during training. Interpreting FORMULA8 as Lipschitz regularization leads to a more accurate and efficient method for estimating the Lipschitz constant in a deep neural network, compared to other recent methods based on the product of weight matrix norms, whose error grows exponentially in the number of layers. For deep models, (6) has a large gap: on the models we considered, this estimate was no smaller than 10 12 and as large as 10 23 . In contrast, our empirical results, which are a lower bound (see §D), give values less than 10. The fact that the robustness guarantees of §2 using FORMULA8 give meaningful results suggests that FORMULA8 is an accurate estimate for our purposes. We studied image classification on the CIFAR-10 and CIFAR-100 datasets BID19 ). We tested our methods on three networks, chosen to represent a broad range of architectures: AllCNN-C (Springenberg et al. FORMULA1 ), having nine layers; a 34 layer ResNet BID14 ); and a 34 layer ResNeXt (Xie et al. (2017) ). Training and model details are provided in Appendix A.In §5.1 we define error curves, an error metric which allows for easy comparisons of model robustness and attack strength across a full range of attack norms. Then in §5.2 we use these curves to rank common attack methods. The curves illustrate a clear ranking of attack methods across models. The change in attack ranking is based on the norm used: Iterative FGSM ( ∞ PGD) is the most effective attack when distance is measured in the ∞ norm; 2 PGD is the most effective attack when distance is measured in the 2 norm. The attack ranking makes defence robustness easier to assess, since we only need to check one attack per norm for each model. In §5.3 we compare the different choices of adversarial defences discussed in this paper, which amounts to a combination of adversarial training and Lipschitz regularization in the corresponding norm. Finally, in §5.4 we compare our results to other works. The error curve of a model for a given attack measures the robustness of the model as a function of the norm of the attack. Definition 5.1. The error curve C err (ε) of the model f for the attack a is the probability over the test data D that an attack of size ε leads to a misclassification DISPLAYFORM0 where c(x) is the model's label at x and c * (x) is the true label. See Figure 1 for error curves for an undefended model over a variety of attacks. We can compare how models or attacks perform using the model error curve. We report common adversarial statistics, which can be read off the curve, in sification at adversarial distance ε = 0 and 0.1 (in the 2-norm) are easily read off the error curve. These values of ε correspond to the test error, and noise which is slightly smaller than a human perceptible perturbation. We also report the median 2 distance which corresponds to the x-intercept of 50% error on the curve. We attacked models on the test/validation set using seven untargeted attack methods: gradient attack; projected gradient descent (constrained in 2 ); the Fast Gradient Sign Method (FGSM) BID11 ); Iterative FGSM (I-FGSM) BID20 ), or projected gradient descent in ∞ ; DeepFool (Moosavi-Dezfooli et al. FORMULA1 ); the Carlini-Wagner attack BID5 ; and the Boundary attack BID4 . The first six methods are first order gradient based white-box attacks, while the last is a black-box attack. I-FGSM and the 2 projected gradient attack are iterative gradient methods, whereas FGSM and the gradient attack are single step. All attacks were implemented with Foolbox BID28 ). Hyperparameters were set to Foolbox defaults, except for the Boundary attack 2 . For each image and attack method, we calculated the adversarial distance in 2 and ∞ .On each model, dataset, and regularization method, we tested all seven attack methods on the entire test/validation set. We compared attack methods using the attack error curve. For example see Figure 1 , where we plot attack error curves for each attack method on an undefended model. We plot the attack error curves in both Euclidean and ∞ distances. When attack norms are measured in ∞ , the most effective attack is Iterative FGSM (PGD in ∞ ). Similarly, when attack norms are measured in 2 , 2 projected gradient descent is the strongest attack. See Figure 1 for an illustration. We observed the same ranking of attacks on all models and defences studied. For this reason in what follows, we only report model statistics using projected gradient descent corresponding to the distance metric used (either 2 or ∞ ). We tested many combinations of defence methods. We use the superscipts 0, 1, 2 to indicate the type of adversarial training used: 0 for none, 1 for one step FGSM, and 2 for one step gradient ascent. We used the superscript Lip for Lipschitz regularization, which measured the gradient in the same norm as was used for adversarial training. For example J 2−Lip indicates adversarial training and Lipschitz regularization in the 2 norm. DISPLAYFORM0 Figure 2: Adversarial robustness results against 2 PGD attacks using ResNeXt networks on CIFAR 10 and 100. The curves are for the undefended (baseline) model, and different regularizations, showing the error rates at different attack vectors norms. The 2 PGD attack was the most effective in the 2 norm. We also considered adding a final sigmoid layer to the network, prior to the softmax. The choice of sigmoid we choose is tanh, and is inspired by (but not equivalent to) tanh-estimators used in classical statistics as a robust estimator (Hampel et al., 2011, Chapter 2) . The intuition behind this choice is to normalize the logit scores of the model, which we believe should improve robustness to outliers. Outside of deep learning, tanh-estimators have been successfully used to normalize scores and improve robustness, for example in machine learning biometrics BID17 ). See Appendix A.1 for layer details. Model robustness is evaluated on the entire test/validation set using the median adversarial distance in both 2 and ∞ , and the percent misclassified at adversarial 2 distance ε = 0.1. We chose ε = 0.1 because at this magnitude attacks are still imperceptible to the human eye. For ease of comparison with other works, we also report percent misclassified at 2 distance ε = 1.5, and (on CIFAR-10) ∞ distance ε = 8 255 . In addition we plot the attack error curve for each model. TAB1 and Figure 2 Here we summarize our results for ResNeXt-34, the model studied with the greatest capacity using the most effect attack in the 2 norm, 2 PGD. Refer also to TAB1 for a summary. Without adversarial perturbations, all ResNeXt-34 models achieve roughly 4% test error on CIFAR-10. However, the undefended (baseline, J 0 ) model achieves 54% test error at adversarial 2 distance ε = 0.1. Adversarial training via FGSM (J 1 ) reduces test error to 24.6%, whereas 2 adversarial training (J 2 ) reduces test error to 13.5%. A combination of all defences (J 2−Lip with tanh) further reduces test error to 12.1%. The models are ranked in the same order when instead measured with median 2 adversarial distance. The model with all defences has median adversarial distance six times that of the undefended model. FGSM (J 1 ) only doubles the median adversarial distance relative to the baseline undefended model. Figure 2a illustrates that this ranking of defences holds over all distances of adversarial perturbations. We observe a similar ranking on CIFAR-100. See for Figure 2b . Unperturbed, all models achieve between 21% and 22% test error. Without adversarial defences, ResNeXt-34 (4x32d) has a test error of 74% at adversarial 2 distance ε = 0.1. Adversarial training alone brings the test error down to 56.3% and 53.7%, with respectively FGSM (J 1 ) and 2 (J 2 ) adversarial training. A combination of all defences further reduces test error to 42.6%. Median 2 adversarial distance increased from 0.05 on the undefended model to 0.14 on the model with all defences. The test/validation error of the regularized models is in many cases better than the baseline undefended model. On CIFAR-10 AT and WCAT can improve test/validation error by nearly one percent TAB6 ). On CIFAR-100 some regularized models perform slightly worse, but typically the difference is no more than one or two percent. In TAB1 we also report statistics measuring the model's Lipschitz constant. For vector valued functions, f , in order to measure the Lipschitz constant the induced matrix norm 3 is used, coming from the norms in the source and target spaces. Further statistics for all adversarial defences and models are deferred to Appendix D. The columns ∇l 2 and ∇f 2,∞ give the maximum of these norms over the test/validation set. Employing all defences significantly decreases the norm of the model Jacobian on the test data, and hence improves model robustness. On CIFAR-10 the model with all defences has Jacobian norm 10 times smaller than the undefended model, whereas adversarial training only improves the Jacobian norm by a factor of three at most. Similarly on CIFAR-100, adversarial training alone improves the norm of the Jacobian by a factor of no more than three. However a combination of all defences decreases the norm of the model Jacobian by a factor of six. These statistics indicate that 2-Lipschitz regularization of the loss, combined with 2 adversarial training, dramatically reduce the Lipschitz constant of a network measured in the 2, ∞ norm. Interestingly, 2-Lipschitz regularization of the loss also decreases the 1, 1 Jacobian norm of the model (see TAB7 ). Thus 2-Lipschitz regularization improves robustness to ∞ attacks as well. In Appendix D we report results for all models and combinations of defence methods. Of the individual defences by themselves, adversarial training (J 1 or J 2 ) improves model robustness the most. We find 2 adversarial training (J 2 ) to be more effective than FGSM (J 1 ) when attacks are measured in 2 . We observe the same ranking of defence methods for AllCNN and ResNet-34. Adversarial training improves model robustness. However model robustness is further improved by adding Lipschitz regularization of the loss, which empirically decreases the Jacobian norm of the model on the test data. In terms of training time, both adversarial training and Lipschitz regularization increase training time by a factor of no more than four. In contrast, adding a final tanh layer to normalize the logits is nearly free, and consistently improves model robustness by itself. On the CIFAR-10 dataset (as of revision) the current state-of-the-art 2 robustness is BID27 . Without adversarial training, their method achieves 89.9% error at ε = 1.5. In contrast, without adversarial training, Lipschitz regularization as implemented here achieves 78.42% error at ε = 1.5, an improvement of over 11%. With adversarial training, our results are comparable to BID27 : they achieved 79.6% error at adversarial perturbation ε = 1.5, whereas our method achieves 78.59%, an improvement of 1%. A direct comparison is difficult, since Qian & Wegman used the Carlini-Wagner attack, which (with Foolbox defaults) is a weaker 2 attack 3 The induced norm of a matrix A is defined as A p,q = max x =0Ax q x p (Horn et al., 1990, Chapter 5.6.4) than the attack used here ( 2 PGD), so our results should be adjusted accordingly. (We applied the Carlini-Wagner attack but we only recorded the results for the strongest attack).After revision we ran comparisons for attacks measured in ∞ . We only used one step adversarial training. The current state-of-the-art on CIFAR-10 is BID22 which used seven steps of ∞ PGD. The strongest attack achieves 54.2% error at ε = 8 255 . Our best model, trained with J 2−Lip regularization, is slightly worse, with 62.4% error at ε = 8 255 . We expect that multi-step adversarial training would improve our results in this setting. We used standard data augmentation for the CIFAR dataset, comprising of horizontal flips, and random crops of padded images, four pixels per side. Images are scaled to have pixel values in [0, 1]. We used square cutout BID8 ) of width 16 on CIFAR-10, and width 8 on CIFAR-100, but no dropout. Batch normalization was used after every convolution layer. We used SGD with an initial learning rate of 0.1, momentum set to 0.9, and a batch size of 128. CIFAR-10 was trained for 200 epochs, dropping the learning rate by a factor of five after epochs 60, 120, and 180. On CIFAR-100, networks were trained for 300 epochs, and the learning rate was dropped by a factor of 10 after epochs 150 and 225. For CIFAR-10 weight decay (Tikhonov/ 2 regularization) was set to 5e−4; on CIFAR-100 it was 1e−4.For networks with Lipschitz regularization in the 2-norm, the Lagrange multiplier λ of the excess Lipschitz term was set to λ = 0.1. With 1-norm Lipschitz regularization, the Lagrange multiplier was scaled down by a factor of √ n from the 2-Lipschitz Lagrange multiplier, where n is the input dimension. Adversarially trained models were trained with images perturbed to an 2 distance of ε = 0.01. We did not tune either of these hyperparameters. For CIFAR-10, the ResNeXt architecture we used had a depth of 34 layers, cardinality 2 and width 32, with a basic residual block rather than a bottleneck. The branches (convolution groups) of the blocks were aggregated via a mean, rather than using a fully connected layer. For CIFAR-100 the architecture was the same, but had cardinality 4. Prior to the final softmax layer, we found inserting a sigmoid activation function improved model robustness. In this case, the sigmoid layer comprised of first batch normalization (without learnable parameters), followed by the activation function t tanh( Other possible defences discussed in include input validation and preprocessing, which would potentially allow adversarial samples to be recognized before being input to the model, and architecture modifications designed to improve robustness to adversarial samples. For more information we refer to the review ) and the discussion of attack methods in BID4 Proof. By Lipschitz continuity of | (x + a) − (x)| ≤ L a = Lε There are two cases for the left-hand side, depending on the sign. In both cases we obtain (3). DISPLAYFORM0 Taking expectations, we obtain (4). The following result shows that Signed Gradient BID11 attack, and the normalized gradient attack are nearly optimal in the following sense. Lemma B.1. Write (x) = (f (x), y). The attack vector directions DISPLAYFORM1 are nearly optimal the ∞ and 2 norm, respectively, in the sense that (x + εa) = max DISPLAYFORM2 and moreover, DISPLAYFORM3 First observe that the proof of Lemma 3.1 follows by taking expectations in (7). Next we prove Lemma B.1.The optimal attack solves max DISPLAYFORM4 Proof. Use the Taylor expansion DISPLAYFORM5 Thus, the optimal attack vector defined by (8) in a generic norm · can be approximated to order ε 2 by solving the problem max DISPLAYFORM6 According to (Boyd & Vandenberghe, 2004, A.1.6) , the equation DISPLAYFORM7 where the norm on the right hand size is the dual norm. Thus DISPLAYFORM8 Define the Lipschitz constant of the data (in the 2, ∞ norm) to be TAB5 lists the Lipschitz constant of the training data for common datasets, which are all small: all but one are below 1 in the 2, ∞ norm. DISPLAYFORM0 The Lipschitz extension theorem BID34 says that given function values {f (x)} x∈D , there exists an extension f ext which perfectly fits the data, and has the same Lipschitz constant, provided the appropriate norm are used on the X and Y spaces. This can be done using, for example, the 2-norm for X and the ∞ norm on the label space. In other norms, we can also make an extension, but the Lipschitz constant may increase BID18 . Of course, such a function may not be consistent with a given architecture. See TAB5 , where we present the Lipschitz constant of common datasets. Here we present complete results for all regularization types studied, on all models and datasets considered. Adversarial distances reported in 2 were generated using 2 PGD; distances in ∞ were generated using ∞ PGD (Iterative FGSM). Model defense method % Err at median % Err at median % Err at ε = 0 distance ε = 0.1 distance ε =
Improvements to adversarial robustness, as well as provable robustness guarantees, are obtained by augmenting adversarial training with a tractable Lipschitz regularization Explores augmenting the training loss with an additional gradient regularization term to improve robustness of models against adversarial examples Uses a trick to simplify the adversarial loss by one in which the adversarial perturbation appears in closed form.