Title: ADVERSARIAL TRAINING GENERALIZES DATA-DEPENDENT SPECTRAL NORM REGULARIZATION

Abstract: We establish a theoretical link between adversarial training and operator norm regularization for deep neural networks. Specifically, we present a data-dependent variant of spectral norm regularization and prove that it is equivalent to adversarial training based on a specific 2 -norm constrained projected gradient ascent attack. This fundamental connection confirms the long-standing argument that a network's sensitivity to adversarial examples is tied to its spectral properties and hints at novel ways to robustify and defend against adversarial attacks. We provide extensive empirical evidence to support our theoretical results.

1. INTRODUCTION:

Deep neural networks have been used with great success for perceptual tasks such as image classification (Simonyan & Zisserman, 2014; LeCun et al., 2015) or speech recognition (Hinton et al., 2012) . While they are known to be robust to random noise, it has been shown that the accuracy of deep nets dramatically deteriorates in the face of so-called adversarial examples (Biggio et al., 2013; Szegedy et al., 2013; Goodfellow et al., 2014) , i.e. small perturbations of the input signal, often imperceptible to humans, that are sufficient to induce large changes in the model output. This apparent vulnerability is worrisome as deep nets start to proliferate in the real-world, including in safety-critical deployments. Consequently, there has been a surge in methods that find adversarial perturbations (Sabour et al., 2015; Papernot et al., 2016; Kurakin et al., 2016; Moosavi Dezfooli et al., 2016; Moosavi-Dezfooli et al., 2017; Madry et al., 2017; Athalye et al., 2018) .

The most direct strategy of robustification, called adversarial training, aims to harden a machine learning model by immunizing it against an adversary that maliciously corrupts training examples before passing them to the model (Goodfellow et al., 2014; Kurakin et al., 2016; Miyato et al., 2015; 2017; Madry et al., 2017) . A different strategy of defense is to detect whether the input has been perturbed by detecting characteristic regularities either in the adversarial perturbations themselves or in the network activations they induce (Grosse et al., 2017; Feinman et al., 2017; Xu et al., 2017; Metzen et al., 2017; Carlini & Wagner, 2017; Roth et al., 2019) .

Despite practical advances in finding adversarial examples and defending against them, it is still an open question whether (i) adversarial examples are unavoidable, i.e. no robust model exists, cf. (Fawzi et al., 2018; Gilmer et al., 2018) , (ii) learning a robust model requires too much training data, cf. (Schmidt et al., 2018) , (iii) learning a robust model from limited training data is possible but computationally intractable (Bubeck et al., 2018) , or (iv) we just have not found the right training algorithm yet, i.e. adversarial examples exist because of intrinsic flaws of the model or learning objective that can ultimately be overcome.

In this work, we investigate the origin of adversarial vulnerability in neural networks by focusing on the attack algorithms used to find adversarial examples. In particular, we make the following contributions:

• We present a data-dependent variant of spectral norm regularization that directly regularizes large singular values of a neural network in regions that are supported by the data, as opposed to existing methods that regularize a global, data-independent upper bound.

• We establish a theoretical link between adversarial training and operator norm regularization for deep neural networks. Specifically, we prove that data-dependent spectral norm regularization is equivalent to adversarial training based on a specific 2 -norm constrained projected gradient ascent attack. • We conduct extensive empirical evaluations showing that (i) adversarial perturbations align with dominant singular vectors, (ii) adversarial training and data-dependent spectral norm regularization dampen the singular values, and (iii) both training methods give rise to models that are significantly more linear around data points than normally trained ones.

2. RELATED WORK:

The idea that a conservative measure of the sensitivity of a network against adversarial examples can be obtained by computing the spectral norm of the individual weight layers appeared already in the seminal work of Szegedy et al. (2013) . A number of works have since suggested to regularize the spectral norm (Yoshida & Miyato, 2017; Miyato et al., 2018; Bartlett et al., 2017; Farnia et al., 2018) and Lipschitz constant (Cisse et al., 2017; Hein & Andriushchenko, 2017; Tsuzuku et al., 2018; Raghunathan et al., 2018) as a means to improve model robustness against adversarial attacks. In the same vein, training methods based on input gradient regularization have been proposed (Gu & Rigazio, 2014; Lyu et al., 2015; Cisse et al., 2017) .

The most direct and popular strategy of robustification, however, is to use adversarial examples as data augmentation during training (Goodfellow et al., 2014; Shaham et al., 2015; Kurakin et al., 2016; Miyato et al., 2017; Madry et al., 2017) . Adversarial training can be viewed as a variant of (distributionally) robust optimization (El Ghaoui & Lebret, 1997; Xu et al., 2009; Bertsimas & Copenhaver, 2018; Namkoong & Duchi, 2017; Sinha et al., 2017; Gao & Kleywegt, 2016) where a machine learning model is trained to minimize the worst-case loss against an adversary that can shift the entire training data within an uncertainty set. Interestingly, for certain problems and uncertainty sets, such as for linear regression and induced matrix norm balls, robust optimization has been shown to be equivalent to regularization (El Ghaoui & Lebret, 1997; Xu et al., 2009; Bertsimas & Copenhaver, 2018; Bietti et al., 2018) . Similar results on the equivalence of robustness and regularization have been obtained also for (kernelized) SVMs (Xu et al., 2009) .

More recently, related works have started to develop a learning theory for robust optimization, including Lipschitz-sensitive generalization bounds (Neyshabur et al., 2015) and spectrally-normalized margin bounds for neural networks (Bartlett et al., 2017) , particularly as bounds on the spectral norm or Lipschitz constant can easily be translated to bounds on the minimal perturbation required to fool a machine learning model.

We extend these lines of work by establishing a theoretical link between adversarial training and data-dependent spectral norm regularization. This fundamental connection confirms the long-standing argument that a network's sensitivity to adversarial examples is tied to its spectral properties and opens the door for adversarially robust generalization bounds via spectral norm based ones.

3. BACKGROUND:



3.1. GLOBAL SPECTRAL NORM REGULARIZATION:

In this section we rederive spectral norm regularization à la Yoshida & Miyato (2017) , while also setting up the notation for later. Let x and y denote input-label pairs generated from a data distribution P . Let f :

X ⊂ R n → R d denote the logits of a θ-parameterized piecewise linear classifier, i.e. f (•) = W L φ L-1 (W L-1 φ L-2 (. . . ) + b L-1 ) + b L

, where φ is the activation function, and W , b denote the layer-wise weight matrix1 and bias vector, collectively denoted by θ. Let us furthermore assume that each activation function is a ReLU (the argument can easily be generalized to other piecewise linear activations). In this case, the activations φ act as input-dependent diagonal matrices Φ x := diag(φ x ), where an element in the diagonal φ x := 1(x ≥ 0) is one if the corresponding pre-activation x := W φ -1 (•) + b is positive and equal to zero otherwise.

Following Raghu et al. (2017) , we call φ x := (φ 1 x , . . . , φ L-1

x ) ∈ {0, 1} m the "activation pattern", where m is the number of neurons in the network. For any activation pattern φ ∈ {0, 1} m we can define the preimage X(φ) := {x ∈ R n : φ x = φ}, inducing a partitioning of the input space via R n = φ X(φ). Note that some X(φ) = ∅, as not all combinations of activiations may be feasible. See Figure 1 in (Raghu et al., 2017) or Figure 3 in (Novak et al., 2018) for an illustration of ReLU tesselations of the input space.

We can linearize f within a neighborhood around x as follows

EQUATION

where J f (x) denotes the Jacobian of f at x

J f (x) = W L • Φ L-1 x • W L-1 • Φ L-2 x • • • Φ 1 x • W 1 .

(2)

We have the following bound for ||∆x|| 2 = 0

EQUATION

where σ(J f (x) ) is the spectral norm (largest singular value) of the linear operator J f (x) . From a robustness perspective we want σ(J f (x) ) to be small in regions that are supported by the data.

Based on the decomposition in Equation 2 and the non-expansiveness of the activations, σ(Φ x ) ≤ 1 for every ∈ {1, ..., L-1}, Yoshida & Miyato (2017) suggest to upper-bound the spectral norm of the Jacobian by the product of the spectral norms of the individual weight matrices

EQUATION

The layer-wise spectral norms σ := σ(W ) can be computed iteratively using the power method 3 . Starting with a random vector v 0 , the power method iteratively computes

EQUATION

The (final) singular value can be obtained via

σ k = (u k ) W v k .

Yoshida & Miyato (2017) suggest to turn this upper-bound into a global (data-independent) regularizer by learning the parameters θ via the following penalized empirical risk minimization

EQUATION

where (•, •) denotes an arbitrary classification loss. Note, since the parameter gradient of σ(W ) 2 /2 is σ u (v ) , with σ , u and v being the dominant singular value and singular vectors of W (approximated via the power method), Yoshida & Miyato (2017) global spectral norm regularizer effectively adds a term λσ u (v ) for each layer ∈ {1, ..., L} to the parameter gradient of the loss function. In terms of computational complexity, because the global regularizer decouples from the empirical loss, the power-method iterations can be amortized across data-points and a single power method iteration per parameter update step usually suffices in practice (Yoshida & Miyato, 2017) .

3.2. GLOBAL VS. LOCAL REGULARIZATION:

The advantage of global bounds is that they trivially generalize from the training to the test set. The problem however is that they can be arbitrarily loose, e.g. penalizing the spectral norm over irrelevant regions of the ambient space. To illustrate this, consider the ideal robust classifier that is essentially piecewise constant on class-conditional regions, with sharp transitions between the classes. The global spectral norm will be heavily influenced by the sharp transition zones, whereas a local data-dependent bound can adapt to regions where the classifier is approximately constant (Hein & Andriushchenko, 2017) . We would therefore expect a global regularizer to have the largest effect in the empty parts of the input space. A local regularizer, on the contrary, has its main effect around the data manifold.

4. ADVERSARIAL TRAINING GENERALIZES SPECTRAL NORM REGULARIZATION 4.1 DATA-DEPENDENT SPECTRAL NORM REGULARIZATION:

We now show how to directly regularize the data-dependent spectral norm of the Jacobian J f (x) .

Under the assumption that the dominant singular value is non-degenerate2 , the problem of computing the largest singular value and the corresponding left and right singular vectors can efficiently be solved via the power method. Let v 0 be a random vector or an approximation to the dominant right singular vector of J f (x) . The power method iteratively computes

u k ← ũk /||ũ k || 2 , ũk ← J f (x) v k-1 = W L • Φ L-1 x • • • Φ 1 x • W 1 v k-1 (forward pass) v k ← ṽk /||ṽ k || 2 , ṽk ← J f (x) u k = ∇ x (f (x) u k ) (backward pass) (7)

The (final) singular value can be computed via

σ k = u k J f (x) v k .

Note that the right singular vector v k gives the direction in input space that corresponds to the steepest ascent of f (x) along u k .

We can turn this into a regularizer by learning the parameters θ via the following Jacobian-based spectral norm penalized empirical risk minimization

EQUATION

)

where u and v are the data-dependent singular vectors of J f (x) , computed via Equation 7.

By optimality / stationarity3 (u

J f (x) v) 2 = v J f (x) J f (x) v = ||J f (x) v|| 2 2 and linearization J f (x) v f (x + v) -f (x) (which holds with equality if x + v ∈ X(φ x ))

, we can regularize learning also via the following sum-of-squares based spectral norm regularizer

EQUATION

where the data-dependent singular vector v of J f (x) is computed via Equation 7, and λ = λ 2 . Both variants can readily be implemented in modern deep learning frameworks. We found the sum-of-squares based spectral norm regularizer to be more numerically stable than the Jacobian based one, which is why we used this variant in our experiments.

In terms of computational complexity, the data-dependent regularizer is equally expensive as PGAbased adversarial training, and both are a constant (number of power method iterations) times more expensive than the data-independent variant, plus an overhead that depends on the batch size, which is usually mitigated in modern frameworks by parallelizing computations across a batch of data.

4.2. POWER METHOD FORMULATION OF ADVERSARIAL TRAINING:

Adversarial training (Goodfellow et al., 2014; Kurakin et al., 2016; Madry et al., 2017) aims to improve the robustness of a machine learning model by training it against an adversary that independently perturbs each training example subject to a proximity constraint, e.g. in p -norm,

EQUATION

)

where adv (•, •) denotes the loss function used to find adversarial perturbations (does not need to be the same as the classification loss (•, •)).

The adversarial example x * is typically computed iteratively, e.g. via 2 -norm constrained projected gradient ascent (Madry et al., 2017; Kurakin et al., 2016) (the general p -norm constrained case is similar)

EQUATION

where Π B 2 (x) is the projection operator into the norm ball B 2 (x) := {x * : ||x * -x|| 2 ≤ }, α is a step-size or weighting factor, trading off the previous iterate x k-1 with the current gradient direction ∇ x adv (y, f (x k-1 ))/||∇ x adv (y, f (x k-1 ))|| 2 =: v k , and y is the true or predicted label.

For targeted attacks the sign in front of α is flipped, so as to descend the loss function into the direction of the target label.

By the chain-rule, the computation of the gradient-step v k can be decomposed into a logit-gradient and a Jacobian vector product, while the projection into the 2 -norm ball Π B 2 (x) can be expressed as a normalization (see Section A.2 in the Appendix). The 2 -norm constrained projected gradient ascent attack can thus equivalently be written in the following power method like form (the normalization of ũk is optional and can be absorbed into the normalization of ṽk )

u k ← ũk /||ũ k || 2 , ũk ← ∇ z adv (y, z)| z=f (x k-1 ) (forward pass) v k ← ṽk /||ṽ k || 2 , ṽk ← J f (x k-1 ) u k = ∇ x (f (x k-1 ) u k ) (backward pass) (12) x k ← Π B 2 (x) (x k-1 + αv k ) (projection)

Note that the logit-gradient ∇ z adv (y, z)| z=f (x k-1 ) can be computed in a single forward pass, by directly expressing it in terms of the arguments of the adversarial loss.

Comparing the update equations for projected gradient ascent based adversarial training with those of data-dependent spectral norm regularization, we can see that adversarial training generalizes spectral norm regularization in two ways: (i) via the choice of the adversarial loss function and (ii) by iterating x k within the norm ball (which also introduces an additional parameter α).

The adversarial loss function determines the direction u k of the directional derivative ∇ x (f (x k-1 ) u k ), cf. Section A.3 in the Appendix for an example using the softmax cross-entropy loss. The following theorem shows that adversarial training based on a specific 2 -norm constrained projected gradient ascent attack is indeed equivalent to data-dependent spectral norm regularization.

Theorem 1. For small enough such that B 2 (x) ⊂ X(φ x ) and in the limit α → ∞, 2 -norm constrained projected gradient ascent based adversarial training with a sum-of-squares loss on the logits of the clean and perturbed input adv (f (x), f

(x * )) = 1 2 ||f (x) -f (x * )|| 2 2 is equivalent to data-dependent spectral norm regularization.

The proof can be found in Section A.2 in the Appendix.

The conditions on and α can be considered specifics of the iteration method. The condition that be small enough such that B 2 (x) is contained in the ReLU cell around x ensures that the Jacobian J f (x * ) = J f (x) for all x * ∈ B 2 (x), while the condition that α → ∞ means that in the update equation for x k all the weight is placed on the current gradient direction v k whereas no weight is put on the previous iterate x k-1 . Note that the limit α → ∞ is well-defined since it is inside the projection operation (the projection of x k divides by α again).

Note that, in practice, the Theorem is applicable as long as the Jacobian of the network remains approximately constant in the uncertainty ball under consideration, in which case the correspondence between adversarial training and data-dependent spectral norm regularization holds approximately in a region much larger than X(φ x ). In Section 5, we verify this in the experimental setting.

5. EXPERIMENTAL RESULTS:



5.1. DATASET, ARCHITECTURE & TRAINING METHODS:

We trained Convolutional Neural Networks (CNNs) with ReLU activations and batch normalization on the CIFAR10 data set (Krizhevsky & Hinton, 2009) . We use a 7-layer CNN as our default platform, since it has good test set accuracy at acceptable computational requirements (we used an estimated 2.5k GPU hours (Titan X) in total for all our experiments). We train each classifier with a number of different training methods: (i) 'Standard': standard empirical risk minimization with a softmax cross-entropy loss, (ii) 'Adversarial': 2 -norm constrained projected gradient ascent (PGA) based adversarial training with a softmax cross-entropy loss, (iii) 'global SNR': global spectral norm regularization à la Yoshida & Miyato (2017) , and (iv) 'd.-d. SNR': data-dependent spectral norm regularization. As a default attack strategy we use an 2 -norm constrained PGA white-box attack with cross-entropy adversarial loss adv and 10 attack iterations. We verified that all our conclusions also hold for larger numbers of attack iterations, however, due to computational constraints we limit the attack iterations to 10. 

5.2. SPECTRAL PROPERTIES:

Effect of training method on singular value spectrum. We compute the singular value spectrum of the Jacobian J f (x) for networks f trained with different training methods and evaluated at a number of different test set examples (200 except if stated otherwise). Since we are interested in computing the full singular value spectrum, and not just the dominant singular value and singular vectors as during training, the power method would be too impractical to use, as it gives us access to only one (the dominant) singular value-vector pair at a time. Instead, we first extract the Jacobian (which is per se defined as a computational graph in modern deep learning frameworks) as an input-dim×output-dim dimensional matrix and then use available matrix factorization routines to compute the full SVD of the extracted matrix. For each training method, the procedure is repeated for 200 randomly chosen clean and corresponding adversarially perturbed test set examples. Further details regarding the Jacobian extraction can be found in Section A.5 in the Appendix.

The results are shown in Figure 1 (left). We can see that, compared to the spectrum of the normally trained and global spectral norm regularized model, the spectrum of adversarially trained and datadependent spectral norm regularized models is significantly damped after training. In fact, the data-dependent spectral norm regularizer seems to dampen the singular values even slightly more effectively than adversarial training, while global spectral norm regularization has almost no effect compared to standard training.

Alignment of adversarial perturbations with singular vectors. We compute the cosine-similarity of adversarial perturbations with singular vectors v r of the Jacobian J f (x) , extracted at a number of test set examples, as a function of the rank of the singular vectors returned by the SVD decomposition.

For comparison we also show the cosine-similarity with the singular vectors of a random network as well as the cosine-similarity with random perturbations.

The results are shown in Figure 1 (right). We can see that for all training methods (except the random network) adversarial perturbations are strongly aligned with the dominant singular vectors while the alignment decreases towards the bottom-ranked singular vectors. For the random network, the alignment is roughly constant with respect to rank. Interestingly, this strong alignment with dominant singular vectors also explains why input gradient regularization and fast gradient method (FGM) based adversarial training do not sufficiently protect against adversarial attacks, namely because the input gradient, resp. a single power method iteration, do not yield a sufficiently good approximation for the dominant singular vector in general. , as a function of the rank r of the singular vector. For comparison we also show the cosine-similarity with the singular vectors of a random network as well as the alignment with random perturbations. Curves were aggregated over 200 samples from the test set.

5.3. LOCAL LINEARITY:

Validity of linear approximation. In order to determine the size of the area where a locally linear approximation is valid, we measure the deviation from linearity of φ L-1 (x + z) as the distance ||z|| 2 to x is increased in random and adversarial directions, i.e. we measure ||φ L-1 (x + z) -

(φ L-1 (x)+J φ L-1 (x) z)

|| 2 as a function of the distance ||z|| 2 , for random and adversarial perturbations z, aggregated over 200 data points x in the test set, with adversarial perturbations serving as a proxy for the direction in which the linear approximation holds the least. The purpose of this experiment is to investigate how good the linear approximation for different training methods is, as an increasing number of activation boundaries are crossed with increasing perturbation radius. See Figure 1 in (Raghu et al., 2017) or Figure 3 in (Novak et al., 2018) for an illustration of activation boundary tesselations in the input space.

The results are shown in Figure 2 (left). We can see that adversarial training and data-dependent spectral norm regularization give rise to models that are considerably more linear than the clean trained one, both in random as well as adversarial directions. Compared to the normally trained model, the adversarially trained and spectral norm regularized ones remain flat in random directions for pertubations of considerable magnitude and even remain flat in the adversarial direction for perturbation magnitudes up to the order of the used during adversarial training, while the deviation from linearity seems to increase roughly linearly with ||z|| 2 thereafter. The global spectral norm regularized model behaves similar to the normally trained one.

Largest singular value over distance. Alignment of adversarial perturbations with dominant singular vector. Figure 3 (right) shows the cosine-similarity of adversarial perturbations of mangitude with the dominant singular vector of J f (x) , as a function of perturbation magnitude . For comparison, we also include the alignment with random perturbations. For all training methods, the larger the perturbation magnitude , the lesser the adversarial perturbation aligns with the dominant singular vector of J f (x) , which is to be expected for a simultaneously increasing deviation from linearity. The alignment is similar for adversarially trained and data-dependent spectral norm regularized models and for both larger than that of global spectral norm regularized and naturally trained models.

6. CONCLUSION:

We established a theoretical link between adversarial training and operator norm regularization for deep neural networks. Specifically, we presented a data-dependent variant of spectral norm regularization that directly regularizes large singular values of a neural network in regions that are supported by the data and proved that it is equivalent to adversarial training based on a specific 2 -norm constrained projected gradient ascent attack. This fundamental connection confirms the long-standing argument that a network's sensitivity to adversarial examples is tied to its spectral properties and opens the door for adversarially robust generalization bounds via data-dependent spectral norm based ones. We also conducted extensive empirical evaluations showing that (i) adversarial perturbations align with dominant singular vectors, (ii) adversarial training and datadependent spectral norm regularization dampen the singular values, and (iii) both training methods give rise to models that are significantly more linear around data points than normally trained ones.

A APPENDIX:

A.1 ROBUST OPTIMIZATION AND REGULARIZATION FOR LINEAR REGRESSION

In this section, we recapitulate the basic ideas on the relation between robust optimization and regularization presented in Bertsimas & Copenhaver (2018) . Note that the notation deviates slightly from the main text: most importantly, the perturbations refer to perturbations of the entire training data X, as is common in robust optimization. Consider linear regression with additive perturbations of the data matrix X min w max ∈U g (y -(X + )w) , with loss g : R n → R ,

where U denotes the uncertainty set. A general way to construct U is as a ball of bounded matrix norm perturbations U = { : ≤ λ}. Of particular interest are induced matrix norms

EQUATION

)

where g is a semi-norm and h is a norm. It is obvious that if g fulfills the triangle inequality then one can upper bound

EQUATION

by using (a) the triangle inequality and (b) the definition of the matrix norm.

The question then is, under which circumstances both inequalities become equalities at the maximizing * . It is straightforward to check (Bertsimas & Copenhaver, 2018 , Theorem 1) that specifically we may choose the rank 1 matrix * = λ g(r)

rv , where r = y -Xw , v = arg max

v:h * (v)=1

v w , (h * is the dual norm) .

(16)

If g(r) = 0 then one can pick any u for which g(u) = 1 to form = λuv (such a u has to exist if g is not identically zero). This shows that, for robust linear regression with induced matrix norm uncertainty sets, robust optimization is equivalent to regularization.

A.2 PROOF OF MAIN THEOREM:

Theorem 1 For small enough such that B 2 (x) ⊂ X(φ x ) and in the limit α → ∞, 2 -norm constrained projected gradient ascent based adversarial training with a sum-of-squares loss on the logits of the clean and perturbed input adv (f (x), f

(x * )) = 1 2 ||f (x) -f (x * )|| 2

2 is equivalent to data-dependent spectral norm regularization.

To proof the theorem we need show that the update equations in (12) for 2 -norm constrained projected gradient ascent based adversarial training with the sum-of-squares loss function and the above conditions on and α reduce to the corresponding update equations for data-dependent spectral norm regularization in equation ( 7).

We start with the following lemma. Lemma 1. In the limit α → ∞, the projection

x k = Π B 2 (x) (x k-1 + αv k ) reduces to x k = x + v k .

Proof. The projection x k = Π B 2 (x) (x k-1 + αv k ) can be expressed as follows,

EQUATION

where the max( ,

||x k -x|| 2 ) ensures that if ||x k -x|| 2 < then x k = xk . Thus, x k = lim α→∞ Π B 2 (x) (x k-1 + αv k ) (18) = lim α→∞ x + xk -x max( , ||x k -x|| 2 ) (19) = x + lim α→∞ x k-1 + αv k -x max( , ||x k-1 + αv k -x|| 2 ) (20) = x + lim α→∞ α(v k + 1 α (x k-1 -x)) max( , α||v k + 1 α (x k-1 -x)|| 2 ) (21) = x + lim α→∞ α(v k + 1 α (x k-1 -x)) α||v k + 1 α (x k-1 -x)|| 2 (22) = x + v k /||v k || 2 (23) = x + v k (24)

where in the third-to-last line we used that the max will be attained at its second argument in the limit α → ∞ since ||v k + 1 α (x k-1 -x)|| 2 > 0 for v k = 0, and in the last line we used that v k is normalized by construction, i.e. by how it is defined in the update equations in (12).

Proof of Theorem 1. With the lemma in place, it is now easy to show that for small enough, such that B 2 (x) ⊂ X(φ x ), and in the limit α → ∞, adversarial training reduces to data-dependent spectral norm regularization. Let us show this step by step.

In the limit α → ∞, we have for the forward pass

EQUATION

EQUATION

where the last equality holds by the lemma.

For the backward pass, we have

EQUATION

) since J f (x k ) = J f (x) for all x k ∈ B 2 (x).

Together, this gives

u k ← ũk /||ũ k || 2 , ũk ← J f (x) v k-1 v k ← ṽk /||ṽ k || 2 , ṽk ← J f (x) u k (30) x k ← x + v k .

Observing that the first two update equations don't depend on x k , and absorbing the into the normalization of ũk , we precisely end up with the data-dependent spectral norm regularization in Equation ( 7):

EQUATION

We have thus proved that the update equations for the adversarial attack in Theorem 1 correspond exactly to those of data-dependent spectral norm regularization.

It is also easy to see that the adversarial training objective in Equation ( 10) corresponds to that of data-dependent spectral norm regularization for the specific choice of adversarial loss function

EQUATION

)

The attack strength used for PGA was chosen to be the smallest value such that almost all adversarially perturbed inputs to the standard model are successfully misclassified, which is = 1.75.

The regularization constants of the other training methods were then chosen in such a way that they roughly achieve the same test set accuracy on clean examples as the adversarially trained model does, i.e. we allow a comparable drop in clean accuracy for regularized and adversarially trained models.

When training the derived regularized models, we started from a pre-trained checkpoint and ran a hyper-parameter search over number of epochs, learning rate and regularization constants. Table 1 summarizes the test set accuracies and hyper-parameters for all the training methods we considered.

A.5 EXTRACTING JACOBIAN AS A MATRIX:

Since we know that any neural network with its nonlinear activation function set to fixed values represents a linear operator, which, locally, is a good approximation to the neural network itself, we develop a method to fully extract and specify this linear operator in the neighborhood of any input datapoint x. We have found the naive way of determining each entry of the linear operator by consecutively computing changes to individual basis vectors to be numerically unstable and therefore have settled for a more robust alternative:

In a first step, we run a set of randomly perturbed versions of x through the network (with fixed activation functions) and record their outputs at the particular layer that is of interest to us (usually the logit layer). In a second step, we compute a linear regression on these input-output pairs to obtain a weight matrix W as well as a bias vector b, thereby fully specifying the linear operator. The singular vectors and values of W can be obtained by performing an SVD. 

:

Note that convolutional layers can be constructed as matrix multiplications by converting the convolution operator into a Toeplitz matrix.

Due to numerical errors, we can safely assume that the dominant singular value is non-degenerate.

u = J f (x) v/||J f (x) v||2

Figures and Tables:

Figure1: (Left) Singular value spectrum of the Jacobian J f (x) for networks f trained with different training methods. (Right) Cosine-similarity of adversarial perturbations with singular vectors v r of the Jacobian J f (x) , as a function of the rank r of the singular vector. For comparison we also show the cosine-similarity with the singular vectors of a random network as well as the alignment with random perturbations. Curves were aggregated over 200 samples from the test set.

Figure 2: (Left) Deviation from linearity ||φ L-1(x + z) -(φ L-1 (x) + J φ L-1 (x) z)||2 as a function of the distance ||z|| 2 from x for random and adversarial perturbations z. (Right) Largest singular value of the linear operator J f (x+z) as a function of the magnitude ||z|| 2 of random and adversarial perturbations z. The dashed vertical line indicates the used during adversarial training. Curves were aggregated over 200 samples from the test set.

Figure 4: (Left) Deviation from linearity ||φ L-1 (x + z) -(φ L-1 (x) + J φ L-1 (x) z)|| 2 as a function of the distance ||z|| 2 from x for random and ∞ -PGA adversarial perturbations z. (Right) Largest singular value of the linear operator J f (x+z) as a function of the magnitude ||z|| 2 of random and ∞ -PGA adversarial perturbations z. The dashed vertical line indicates the used during adversarial training. Curves were aggregated over 200 samples from the test set.

CIFAR10 test set accuracies and hyper-parameters for the CNN7 and training methods we considered. The regularization constants were chosen such that the models achieve roughly the same test set accuracy on clean examples as the adversarially trained model does.

Table content: <table><tr><td>TRAINING METHOD</td><td>ACCURACY</td><td>HYPER-PARAMETERS</td></tr><tr><td>STANDARD TRAINING</td><td>93.5%</td><td>-</td></tr><tr><td>ADVERSARIAL TRAINING</td><td>83.6%</td><td>= 1.75, α = 2 /ITERS, ITERS = 10</td></tr><tr><td>GLOBAL SPECTRAL NORM REG.</td><td>80.4%</td><td>λ = 3 • 10 -4 , ITERS=1</td></tr><tr><td>DATA-DEP. SPECTRAL NORM REG.</td><td>84.6%</td><td>λ = 3 • 10 -2 , = 1.75, ITERS = 10</td></tr></table>

The attack strength used for training was chosen to be the smallest value such that almost all adversarially perturbed inputs to the standard model are successfully misclassified, which is = 1.75 (indicated by a vertical dashed line in the Figures below). The regularization constants of the other training methods were then chosen in such a way that they roughly achieve the same test set accuracy on clean examples as the adversarially trained model does. Further details regarding the experimental setup can be found in Section A.4 in the Appendix. Table1summarizes the test set accuracies and hyper-parameters for the training methods we considered. Shaded areas in the plots below denote standard errors with respect to the number of test set samples over which the experiment was repeated.

Table content: <table/>

Peer review (iclr2020):
This paper studies the link between adversarial training and the proposed data-dependent operator norm regularization for ReLU network. Under specific conditions, in theory, the authors show the equivalence between the l2 PGD training and the regularization method. Empirical experiments are conducted to support the theory. While this paper gives interesting observation on both theory and empirical study, I think this paper is not qualified for publishing in ICLR due to the following reasons: (1) limited theoretical results; (2) No significant improvement for practical algorithm; Main argument: The main theorem 1 seems to be weak as it is only valid for small perturbation region epsilon and it is unclear how this assumption is consistent to the practice. It is also unclear how the assumption that alpha 	o infty influences the practical algorithm. It would be better to generalize the theorem to other ell_p attack, instead of just ell_2. Discussion of computational complexity of the proposed regularization method compared with PGD is missed. The adversarial robustness is related to the (local) Lipschitz continuity and many other types of regularization decreases the (local) Lipschitz constant. Could you further give result that distinguishes the proposed norm? It would be better to give improved algorithm for adversarial training based on the current result. The current contribution for further theoretical is too weak as the main theorem requires strong assumption. And I don’t see significant contribution to empirical algorithm. Minor Equ (10) seems not the typical one used and seems not the one studied later.