Year: 2018

Abstract:
We augment adversarial training (AT) with worst case adversarial training (WCAT) which improves adversarial robustness by 11% over the current stateof-the-art result in the `2 norm on CIFAR-10. We obtain verifiable average case and worst case robustness guarantees, based on the expected and maximum values of the norm of the gradient of the loss. We interpret adversarial training as Total Variation Regularization, which is a fundamental tool in mathematical image processing, and WCAT as Lipschitz regularization.

heading: 1 INTRODUCTION
text: 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 (Qian & Wegman, 2018) in the `2 norm. The method also achieves results comparable to the state-of-the-art results of Madry et al. (2017) in the `∞ norm. Moreover, our adversarial training step uses only one gradient evaluation compared to seven steps in the Madry et al. (2017) 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 (Rudin et al., 1992). 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 (Bertalmio et al., 2000) and function approximation (Crandall et al., 2001; Oberman, 2005). Lipschitz regularization was used in a recent proof of generalization of deep neural networks (Oberman & Calder, 2018). Write `(x) = ` ◦ f(x) for the loss of the model. We show that training with AT and WCAT is equivalent to minimizing
J [`] = E (x,y)∼D [`(x)]︸ ︷︷ ︸ expected loss + E (x,y)∼D [‖∇x`(x)‖∗]︸ ︷︷ ︸ AT = TV regularization +λ max (x,y)∈D ‖∇x`(x)‖∗︸ ︷︷ ︸ WCAT = Lipschitz regularization
(1)
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.

heading: 1.1 ADVERSARIAL ATTACKS AND ADVERSARIAL TRAINING
text: The earliest and most successful defense is adversarial training (Szegedy et al. (2013); Goodfellow et al. (2014); Tramèr et al. (2018); Madry et al. (2017)). Top entries in a recent adversarial defence
1We overload ‘`’ as notation for both the loss and for norms: the meaning should be clear from the context.
competition (Kurakin et al. (2017)) used Ensemble Adversarial Training (Tramèr et al. (2018)), where a model is adversarially trained with inputs generated by an ensemble of other models. For more background, refer to the recent review Goodfellow et al. (2018) 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 (Athalye et al., 2018). 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
min w E (x,y)∼D [ max ‖δ‖≤ε `(f(x+ δ;w), y) ] In practice, a tractable attack vector, a(x), is used, in place of the optimal δ, leading to
E (x,y)∼D [` (x+ a(x))] .

heading: 2 ROBUSTNESS GUARANTEES FROM THE LIPSCHITZ CONSTANT
text: Weng et al. (2018) and Hein & Andriushchenko (2017) 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
δ ≥ min j 6=i∗ fi∗(x)− fj(x) 2Lf
(2)
where Lf 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 (Hein & Andriushchenko (2017); Tsuzuku et al. (2018)). 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).

heading: 2.1 ADVERSARIAL ROBUSTNESS BASED ON GRADIENTS OF MODEL LOSS
text: 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(x)‖ ≤ ε. If `(x) is L-Lipschitz continuous then
`(x+ a) ≤ `(x) + Lε (3)
In addition, if TV (`) = E (x,y)∼D ‖∇`(x)‖∗ ≤ R then
E (x,y)∼D [`(x+ a)] ≤ E (x,y)∼D [`(x)] +Rε+O(ε2) (4)
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)
For example, we estimated the values of the terms corresponding to AT and WCAT in (1) for a regularized model trained with (1) and for an undefended model. We expect the ratio of these values between the models to be an effective predictor of the relative robustness of each model. The regularized model had better values of AT and WCAT by factors of 3.3, and 9, respectively. The median adversarial distance of the regularized model was better by a factor of 5, which lies between those factors. See §5 for more empirical results.

heading: 3 REGULARIZATION INTERPRETATION OF AT AND WCAT

heading: 3.1 ADVERSARIAL TRAINING CORRESPONDS TO TV REGULARIZATION
text: The next result interprets adversarial training using either the one-step Signed Gradient attack vector (Goodfellow et al., 2018) 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,
J [`] = E (x,y)∼D [` (x) + ε‖∇`(x)‖∗]
where the ‖ · ‖∗ is the dual norm to the norm measuring adversarial perturbations.
The proof is in §B.2.

heading: 3.2 WORST CASE AT CORRESPONDS TO LIPSCHITZ REGULARIZATION
text: 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
Lip(g) = max x ‖∇g(x)‖
We obtain an underestimate of Lip(g) by sampling the norm of the gradient on a subset of points. Definition 3.2 (Method for estimating the Lipschitz constant). Let ` be a Lipschitz continuous function. Then
max x∈D ‖∇`(x)‖ ≤ Lip(`) (5)
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,
∇x `(f(x), y) = ∇f `(f(x), y)∇x f(x)
For example, when ` is the KL divergence, and when f = softmax(z(x)) then
∇x `(f(x), y) = (f(x)− y))∇x z(x)
Thus, in this case, regularizing `(x) corresponds to regularization of z(x) in the direction f(x)− y.

heading: 4 IMPLEMENTATION OF THE LIPSCHITZ CONSTANT OF A NETWORK
text: Data independent upper bounds on the Lipschitz constant of the model go back to Bartlett (1996). 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
Lipp,q(f) ≤ N∏ k=1 ‖W k‖pk,pk−1 (6)
with p0 = p and pn = q. Certain conditions on the pk’s must be met. For a proof with p, q = 2 see Tsuzuku et al. (2018).
Recent works based on this estimate include: Cissé et al. (2017), using the distance to the nearest orthonormal matrix; Miyato et al. (2018), using the 2-norm; Gouk et al. (2018), using either the 1-norm or∞-norm; and Qian & Wegman (2018), 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. (2018), 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.

heading: 4.1 COMPARING METHODS
text: Interpreting (5) 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 1012 and as large as 1023. 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 (5) give meaningful results suggests that (5) is an accurate estimate for our purposes.

heading: 5 EMPIRICAL RESULTS
text: We studied image classification on the CIFAR-10 and CIFAR-100 datasets (Krizhevsky & Hinton (2009)). We tested our methods on three networks, chosen to represent a broad range of architectures: AllCNN-C (Springenberg et al. (2014)), having nine layers; a 34 layer ResNet (He et al. (2016)); 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.

heading: 5.1 ERROR CURVES FOR MODELS AND ROBUSTNESS METRICS
text: 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 Cerr(ε) 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
Cerr(ε) = PD{c(x+ a(x)) 6= c∗(x) | for an attack ‖a(x)‖X ≤ ε} 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 Table 1. For example the percent misclas-
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.

heading: 5.2 ATTACK EVALUATION
text: 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) (Goodfellow et al. (2014)); Iterative FGSM (I-FGSM) (Kurakin et al. (2016)), or projected gradient descent in `∞; DeepFool (Moosavi-Dezfooli et al. (2016)); the Carlini-Wagner attack (Carlini & Wagner, 2017); and the Boundary attack (Brendel et al., 2018). 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 (Rauber et al. (2017)). Hyperparameters were set to Foolbox defaults, except for the Boundary attack2. 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 `∞).

heading: 5.3 EVALUATION OF DEFENCE METHODS
text: 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 J2−Lip indicates adversarial training and Lipschitz regularization in the `2 norm.
2 The Boundary attack is a computationally demanding attack. Instead of attacking all test images, we only attacked the first 1000 images, for 5000 iterations.
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 (Jain et al. (2005)). 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 ε = 8255 . In addition we plot the attack error curve for each model. Table 1 and Figure 2 present a summary of results for ResNeXt-34. The best statistics are in bold. Complete results, for all models, datasets, and adversarial defences, are presented in Appendix D.
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 Table 1 for a summary. Without adversarial perturbations, all ResNeXt-34 models achieve roughly 4% test error on CIFAR-10. However, the undefended (baseline, J0) model achieves 54% test error at adversarial `2 distance ε = 0.1. Adversarial training via FGSM (J1) reduces test error to 24.6%, whereas `2 adversarial training (J2) reduces test error to 13.5%. A combination of all defences (J2−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 (J1) 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 (J1) and `2 (J2) 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
(see AllCNN results in Table 3). On CIFAR-100 some regularized models perform slightly worse, but typically the difference is no more than one or two percent.
In Table 1 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 norm3 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 Tables 4 and 6). 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 (J1 or J2) improves model robustness the most. We find `2 adversarial training (J2) to be more effective than FGSM (J1) 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.

heading: 5.4 COMPARISON WITH OTHER WORK
text: On the CIFAR-10 dataset (as of revision) the current state-of-the-art `2 robustness is Qian & Wegman (2018). 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 Qian & Wegman (2018): 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
3The induced norm of a matrix A is defined as ‖A‖p,q = maxx 6=0 ‖Ax‖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 Madry et al. (2017) which used seven steps of `∞ PGD. The strongest attack achieves 54.2% error at ε = 8255 . Our best model, trained with J2−Lip regularization, is slightly worse, with 62.4% error at ε = 8255 . We expect that multi-step adversarial training would improve our results in this setting.

heading: A MODEL AND TRAINING DETAILS
text: 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 (Devries & Taylor (2017)) 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.
A.1 PRE-softmax SIGMOID LAYER
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(xt ), where t is a single learnable parameter, common across all layer inputs.
Other possible defences discussed in Goodfellow et al. (2018) 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 (Goodfellow et al. (2018)) and the discussion of attack methods in (Brendel et al. (2018)).

heading: B PROOFS
text: B.1 PROOF OF LEMMA 2.2
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).
Using Taylor’s theorem `(x+ a(x)) = `(x) +∇`(x) · a(x) +O(ε2)
≤ `(x) + ‖∇`(x)‖∗‖a(x)‖+O(ε2) by dual norm §3.1 ≤ `(x) + ε‖∇`(x)‖∗ +O(ε2)
Taking expectations, we obtain (4).
B.2 PROOF OF LEMMA 3.1
The following result shows that Signed Gradient (Goodfellow et al., 2014) 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
(a)i = ∇`(x)i |∇`(x)i| , and a = ∇`(x) ‖∇`(x)‖2 ,
are nearly optimal the `∞ and `2 norm, respectively, in the sense that
`(x+ εa) = max ‖b‖p≤ε
`(x+ b) +O(ε2), p =∞, 2, respectively
and moreover,
`(x+ εa) = `(x) + ε‖∇`(x)‖p +O(ε2), p = 1, 2, respectively (7)
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 ‖a‖≤ε `(x+ a) (8)
Proof. Use the Taylor expansion
`(x+ εa) = `(x) + εa · ∇x`(x) +O(ε2) Thus, the optimal attack vector defined by (8) in a generic norm ‖ · ‖ can be approximated to order ε2 by solving the problem
max ‖a‖≤1
∇x`(f(x), y) · a
According to (Boyd & Vandenberghe, 2004, A.1.6), the equation
max ‖a‖≤1
b · a = ‖b‖∗
where the norm on the right hand size is the dual norm. Thus
max ‖a‖≤ε
∇x`(f(x), y) · a = ε‖∇x`(f(x), y)‖p, p = 1, 2 respectively.

heading: C LIPSCHITZ CONSTANT OF DATA AND OPTIMAL EXTENSIONS
text: Define the Lipschitz constant of the data (in the 2,∞ norm) to be
Lip2,∞(D) = max x1,x2∈D { ‖c∗(x1)− c∗(x2)‖∞ ‖x1 − x2‖2 ∣∣∣∣ c∗(x1) 6= c∗(x2)} Table 2 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. The Lipschitz extension theorem (Valentine, 1945) says that given function values {f(x)}x∈D, there exists an extension fext 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 (Johnson & Lindenstrauss, 1984). Of course, such a function may not be consistent with a given architecture.
See Table 2, where we present the Lipschitz constant of common datasets.

heading: D FURTHER EXPERIMENTAL RESULTS
text: 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).

Review summaries:
This paper explores augmenting the training loss with an additional gradient regularization term to improve the robustness of models against adversarial examples. The authors show that this training loss can be interpreted as a form of adversarial training against optimal L2 and L_infinity adversarial perturbations. This augmented training effectively reduces the Lipschitz constant of the network, leading to improved robustness against a wide variety of attack algorithms.