Title: TOWARDS UNDERSTANDING THE REGULARIZATION OF ADVERSARIAL ROBUSTNESS ON NEURAL NET-WORKS

Abstract: The problem of adversarial examples has shown that modern Neural Network (NN) models could be rather fragile. Among the most promising techniques to solve the problem, one is to require the model to be -adversarially robust (AR); that is, to require the model not to change predicted labels when any given input examples are perturbed within a certain range. However, it is observed that such methods would lead to standard performance degradation, i.e., the degradation on natural examples. In this work, we study the degradation through the regularization perspective. We identify quantities from generalization analysis of NNs; with the identified quantities we empirically find that AR is achieved by regularizing/biasing NNs towards less confident solutions by making the changes in the feature space (induced by changes in the instance space) of most layers smoother uniformly in all directions; so to a certain extent, it prevents sudden change in prediction w.r.t. perturbations. However, the end result of such smoothing concentrates samples around decision boundaries, resulting in less confident solutions, and leads to worse standard performance. Our studies suggest that one might consider ways that build AR into NNs in a gentler way to avoid the problematic regularization.

1. INTRODUCTION:

Despite the remarkable performance (Krizhevsky et al., 2012) of Deep Neural Networks (NNs), they are found to be rather fragile and easily fooled by adversarial examples (Szegedy et al., 2014) . More intriguingly, these adversarial examples are generated by adding imperceptible noise to normal examples, and thus are indistinguishable for humans. NNs that are more robust to adversarial examples tend to have lower standard accuracy (Su et al., 2018) , i.e., the accuracy measured on natural examples. The trade-off between robustness and accuracy has been observed (Kurakin et al., 2017; Madry et al., 2018; Tsipras et al., 2019) . To understand such a phenomenon, Tsipras et al. (2019) show that for linear models, if examples are closed to decision boundaries, robustness provably conflicts with accuracy, though the proof seems unlikely to generalize to NNs. Zhang et al. (2019) show that a gap exists between surrogate risk gap and 0-1 risk gap if many examples are close to decision boundaries, and better robustness can be achieved by pushing examples away from decision boundaries. But pushing examples away again degrades NN performance in their experiments. A more established remedy is developed to require NNs to be -adversarially robust (AR), e.g., via Adversarial Training (Madry et al., 2018) , Lipschitz-Margin Training (Tsuzuku et al., 2018) ; that is, they require the model not to change predicted labels when any given input examples are perturbed within a certain range. Note that such hard requirement is different from penalties on the risk function employed by Lyu et al. (2015) and Miyato et al. (2018) , which is not our subject of investigation (more discussion in appendix A). In practice, hard-requirement methods are found to lead to worse performance measured in standard classification accuracy. We aim to study this branch of methods.

We investigate how adversarial robustness influence the behaviors of NNs to make them more robust but have lower performance. In an earlier time (Szegedy et al., 2014) but an improved performance is only one of the possible outcomes of improved generalization. Technically, improved generalization implies the reduction in gap between training errors and test errors. Regularization achieves the gap reduction by reducing the size of the hypothesis space, which reduces the variance, but meanwhile increases the bias of prediction made -a constant classifier can have zero generalization errors, but also have low test performance. Thus, when a hypothesis space is improperly reduced, another possible outcome is biased poorly performing models with reduced generalization gaps.

Key results. Through a series of theoretically motivated experiments, we find that AR is achieved by regularizing/biasing NNs towards less confident solutions by making the changes in the feature space of most layers (which are induced by changes in the instance space) smoother uniformly in all directions; so to a certain extent, it prevents sudden change in prediction w.r.t. perturbations. However, the end result of such smoothing concentrates examples around decision boundaries and leads to worse standard performance. We elaborate the above statement in details shortly in section 1.1.

Overall, the investigation of generalization behaviors of NNs points out possible directions where we might go if we are to resolve the issue of the test performance degradation done by AR. The main result shows that the hypothesis space of NNs is improperly reduced, thus we might investigate how to avoid it when enforcing AR. Though beyond the scope of this work, we conjecture that the improper reduction comes from the indistinguishability of the change induced in the intermediate layers of NNs by adversarial noise and that by inter-class difference. To guarantee AR, NNs are asked to smoothe out difference uniformly in all directions in a high dimensional space, and thus are biased towards diffident solutions that make similar/concentrated predictions. We leave the investigation of the conjecture as future works.

1.1. AR LEADS TO DIFFIDENT NNS WITH MORE INDECISIVE MISCLASSIFICATIONS:

This section elaborates the key results we briefly present previously.

1. AR reduces the variance of (norms of) the activation/outputs (compared with NNs with different AR strength) at most layers that are emitted/induced by feeding perturbations (of any directions) to that layer from the previous layer. Through a series of theoretically motivated experiments, the results prompt us to look at the singular value distributions of the weight matrix of each layer of the NNs. Shown in fig. 1a , we find that overall the standard deviation (STD) of singular values associated with a layer of the NN trained with lower AR strength 4 is larger than that of the NN with higher AR strength 161 -the green dots are mostly below the red dots. Note that given a matrix W and an example In more details, note that by SVD decomposition, W δx = i σ i u i v T i δx, thus σ i determines how the component v T i δx in the direction of v i is amplified. To see an example, suppose that σ min = σ max = σ 0 , then the variance of σ(W ) is zero, and ||W δx|| = σ 0 ||δx||. In this case, the variance of ||W δx|| (given an ensemble of perturbations δx of the same norm c) is zero as well. The conclusion holds as well for ReLU(W δx), where W here is a weight matrix of a layer of a NN, and ReLU denotes Rectifier Linear Unit activation function (proved by applying Cauchy interlacing law by row deletion (Chafai) 

f i (x).

The confidence of such a classifier could be quantified by margins. It measures the gap between the output for the correct label and other labels, meaning f y (x) -max i =y f i (x). Margin piece-wise linearly depends on the scores, thus the variance of margins is also in a piece-wise linear relationship with the variance of the scores, which are computed linearly from the activation of a NN layer. Thus, the consequence of concentration of activation discussed in the previous paragraph can be observed in the distribution of margins. More details of the connection between singular values and margins are discussed in section 5.2.2, after we present lemma 4.1. A zero margin implies that a classifier has equal propensity to classify an example to two classes, and the example is on the decision boundary. We plot the margin distribution of the test set of CIFAR10 in fig. 1b , and find that margins are increasingly concentrated around zero -that is, the decision boundaries -as AR strength grows. 3. The sample concentration around decision boundaries smoothes sudden changes induced perturbations, but also increases indecisive misclassification. The concentration of test set margins implies that the induced change in margins by the perturbation in the instance space is reduced by AR. The statement may not be immediately obvious, so we explain in details as follows. Given two examples x, x from the test set, δx = xx can be taken as a significant perturbation that changes the example x to x . The concentration of overall margins implies the change induced by δx is smaller statistically in NNs with higher AR strength. Thus, for an adversarial perturbation applied on x, statistically the change of margins is smaller as well -experimentally it is reflected in the increased adversarial robustness of the network, as shown in the increasing curve in fig. 1c . That is, the sudden changes of margins originally induced by adversarial perturbations are smoothed (to change slowly). However, the cost of such smoothness is lower confidence in prediction, and more test examples are slightly/indecisively moved to the wrong sides of the decision boundaries -incurring lower accuracy, as shown in the decreasing curve in fig. 1c .

Lastly, we note that experiments in this section are used to illustrate our main arguments in this section. Further consistent quality results are reported in section 5 by conducting experiments on CIFAR10/100 and Tiny-ImageNet with networks of varied capacity.

1.2. OUTLINE AND CONTRIBUTIONS:

As briefly discussed at the beginning, this work carries out generalization analysis on NNs with AR.

The quantities we investigate in the previous section are identified by the generalization errors (GE) upper bound we establish at theorem 4.1, which characterizes the regularization of AR on NNs. The key result is actually obtained at the end of a series of analysis, thus we present the outline of the analysis here.

Outline. After presenting some preliminaries in section 3, we proceed to analyze the regularization of AR on NNs, and establish a GE upper bound in section 4. The bound prompts us to look at the GE gaps in experiments. In section 5.1, we find that for NNs trained with higher AR strength, the surrogate risk gaps (GE gaps) decrease for a range of datasets, i.e., CIFAR10/100 and Tiny-ImageNet (ImageNet, 2018) . It implies AR effectively regularizes NNs. We go further to study the finer behavior change of NNs that might lead to such a gap reduction. Again, we follow the guidance of theorem 4.1. We look at the margins in section 5.2.1, then at the singular value distribution in section 5.2.2, and discover the main results described in section 1.1. More corroborative experiments are run in appendix B.4 to show that such phenomenon exists in a broad range of NNs with varied capacity, and more complementary results are present in appendix B.3 to explain some seemingly abnormal observations. More related works are present in section 2.

Contributions. Overall, the core contribution in this work is to show that adversarial robustness (AR) regularizes NNs in a way that hurts its capacity to learn to perform in test. More specifically:

• We establish a generalization error (GE) bound that characterizes the regularization of AR on NNs.

The bound connects margin with adversarial robustness radius via singular values of weight matrices of NNs, thus suggesting the two quantities that guide us to investigate the regularization effects of AR empirically. 

3. PRELIMINARIES:

Assume an instance space Z = X × Y, where X is the space of input data, and Y is the label space. Z := (X, Y ) are the random variables with an unknown distribution µ, from which we draw samples. We use S m = {z i = (x i , y i )} m i=1 to denote the training set of size m whose examples are drawn independently and identically distributed (i.i.d.) by sampling Z. Given a loss function l, the goal of learning is to identify a function T : X → Y in a hypothesis space (a class T of functions) that minimizes the expected risk

R(l • T ) = E Z∼µ [l (T (X), Y )] ,

Since µ is unknown, the observable quantity serving as the proxy to the expected risk R is the empirical risk

R m (l • T ) = 1 m m i=1 l (T (x i ), y i ) .

Our goal is to study the discrepancy between R and R m , which is termed as generalization errorit is also sometimes termed as generalization gap in the literature

GE(l • T ) = |R(l • T ) -R m (l • T )|. (1)

Definition 1 (Covering number). Given a metric space (S, ρ), and a subset S ⊂ S, we say that a subset Ŝ of S is a -cover of S, if ∀s ∈ S, ∃ŝ ∈ Ŝ such that ρ(s, ŝ) ≤ . The -covering number of S is N ( S, ρ) = min{| Ŝ| : Ŝ is an -covering of S}.

Various notions of adversarial robustness have been studied in existing works (Madry et al., 2018; Tsipras et al., 2019; Zhang et al., 2019) . They are conceptually similar; in this work, we formalize its definition to make clear the object for study.

Definition 2 ((ρ, )-adversarial robustness). Given a multi-class classifier f : X → R L , and a metric ρ on X , where L is the number of classes, f is said to be adversarially robust w.r.t. adversarial perturbation of strength , if there exists an > 0 such that ∀z = (x, y) ∈ Z and δx ∈ {ρ(δx) ≤ }, we have f ŷ (x + δx) -f i (x + δx) ≥ 0, where ŷ = arg max j f j (x) and i = ŷ ∈ Y. is called adversarial robustness radius. When the metric used is clear, we also refer (ρ, )-adversarial robustness as -adversarial robustness.

Note that the definition is an example-wise one; that is, it requires each example to have a guarding area, in which all examples are of the same class. Also note that the robustness is w.r.t. the predicted class, since ground-truth label is unknown for a x in test.

We characterize the GE with ramp risk, which is a typical risk to undertake theoretical analysis (Bartlett et al., 2017; Neyshabur et al., 2018b) . Definition 3 (Margin Operator). A margin operator M : R L × {1, . . . , L} → R is defined as

M(s, y) := s y -max i =y s i

Definition 4 (Ramp Loss). The ramp loss l γ : R → R + is defined as

l γ (r) :=    0 r < -γ 1 + r/γ r ∈ [-γ, 0] 1 r > 0

Definition 5 (Ramp Risk). Given a classifier f , ramp risk is the risk defined as

R γ (f ) := E(l γ (-M(f (X), Y ))),

where X, Y are random variables in the instance space Z previously.

We will use a different notion of margin in theorem 4.1, and formalize its definition as follows. We reserve the unqualified word "margin" specifically for the margin discussed previously -the output of margin operator for classification. We call this margin to-be-introduced instance-space margin (IM). Definition 6 (Smallest Instance-space Margin). Given an element z = (x, y) ∈ Z, let v(x) be the distance from x to its closest point on the decision boundary, i.e., the instance-space margin (IM) of example x. Given an -covering of Z, let

EQUATION

)

v min is the smallest instance-space margin of elements in the covering balls that contain training examples.

4. THEORETICAL INSTRUMENTS FOR EMPIRICAL STUDIES ON AR:

In this section, we rigorously establish the bound mentioned in the introduction. We study the map T defined in section 3 as a NN (though technically, T now is a map from X to R L , instead of to Y, such an abuse of notation should be clear in the context). To begin with, we introduce an assumption, before we state the generalization error bound guaranteed by adversarial robustness.

(a) (b)

Figure 2 : (a) Illustration of the regularization effect of adversarial robustness. If a NN T isadversarially robust, for a given example x (drawn as filled squares or circles) and points x in the yellow ball {x | ρ(x, x ) ≤ } around x, the predicted labels of x, x should be the same, and the loss variation is potentially bigger as x moves from the center to the edge, as shown as intenser yellow color at the edge of a ball. Collectively, the adversarial robustness of each example requires an instance-space margin (IM) to exist for the decision boundary, shown as the shaded cyan margin.

As normally known, margin is related to generalization ability that shrinks the hypothesis space. In this case, the IM required by adversarial robustness would weed out hypotheses that do not have an adequate IM, such as the red dashed line shown in the illustration. (b) Illustration of lemma 4.1. Given a NN with ReLU activation function, the feature map I l at layer l is divided into regions where I l (x) is piecewise linear w.r.t. x. The induced linear map W q 1 is given by diag(τ 1 (q))W 1 , where diag(τ l (q)) is a diagonal matrix whose diagonal entries are given by a vector τ 1 (q) that has 0-1 values. For example, in region p, I 1 = W p 1 x and distance between instances x are vertical elongated, while in region q, I 1 = W q 1 x and distance are horizontally elongated. Thus given x, x , the difference ||I l (x) -I l (x )|| between I l (x) and I l (x ) is the length of the transformed line segment xx drawn, of which each segment is linearly transformed in a different way.

Assumption 4.1 (Monotony). Given a point x ∈ X , let x be the point on the decision boundary of a NN T that is closest to x. Then, for all x on the line segment x + t(x -x), t ∈ [0, 1], the margin M(T x , y) decreases monotonously.

The assumption is a regularity condition on the classifier that rules out undesired oscillation between x and x . To see how, notice that the margin defined in definition 3 reflects how confident the decision is made. Since x is on the decision boundary, it means the classifier is unsure how it should be classified. Thus, when the difference xx is gradually added to x, ideally we want the confidence that we have on classifying x to decrease in a consistent way to reflect the uncertainty. Theorem 4.1. Let T denote a NN with ReLU and MaxPooling nonlinear activation functions (a definition is put at eq. ( 6) for readers' convenience), l γ the ramp loss defined at definition 4, and Z the instance space assumed in section 4. Assume that Z is a k-dimensional regular manifold that accepts an -covering with covering number ( C X ) k , and assumption 4.1 holds. If T is 0 -adversarially robust (defined at definition 2), ≤ 0 , and denote v min the smallest IM margin in the covering balls that contain training examples (defined at definition 6), σ i min the smallest singular values of weight matrices W i , i = 1, . . . , L -1 of a NN, {w i } i=1,...,|Y| the set of vectors made up with ith rows of W L (the last layer's weight matrix), then given an i.i.d. training sample S m = {z i = (x i , y i )} m i=1 drawn from Z, its generalization error GE(l • T ) (defined at eq. (1)) satisfies that, for any η > 0, with probability at least 1 -η

EQUATION

where

u min = min y,ŷ∈Y,y =ŷ ||w y -w ŷ || 2 L-1 i=1 σ i min v min (4)

is a lower bound of margins of examples in covering balls that contain training samples.

The proof of theorem 4.1 is in appendix C. The bound identifies quantities that would be studied experimentally in section 5 to understand the regularization of AR on NNs. The first term in eq. ( 3) in theorem 4.1 suggests that quantities related to the lower bound of margin u min might be useful to study how -adversarial robustness ( -AR) regularizes NNs. However, -AR is guaranteed in the instance space that determines the smallest instance-space margin v min . To relate GE bound with -AR, we characterize in eq. ( 4) the relationship between margin with IM, via smallest singular values of NNs' weight matrices, suggesting that quantities related to singular values of NNs' weight matrices might be useful to study how AR regularizes NNs as well. An illustration on how AR could influence generalization of NNs through IM is also given in fig. 2a . The rightmost term in eq. ( 3) is a standard term in robust framework (Xu and Mannor, 2012) in learning theory, and is not very relevant to the discussion. The remaining of this paper are empirical studies that are based on the quantities, e.g., margin distributions and singular values of NNs' weight matrices, that are related to the identified quantities, i.e., u min , σ i min . These studies aim to illuminate with empirical evidence on the phenomena that AR regularizes NNs, reduces GE gaps, but degrades test performance. 2Before turning into empirical study, we further present a lemma to illustrate the relation characterized in eq. ( 4) without the need to jump into proof of theorem 4.1. It would motivate our experiments later in section 5.2.2. We state the following lemma that relates distances between elements in the instance space with those in the feature space of any intermediate network layers. Lemma 4.1. Given two instances x, x ∈ X , let I l (x) be the activation g(W l g(W l-1 . . . g(W 1 x))) at layer l of x (c.f. definition of NNs at appendix C.2), then there exist n ∈ N sets of matrices {W qj i } i=1...l , j = 1 . . . n, that each of the matrix W qj i is obtained by setting some rows of W i to zero, and {q j } j=1...n are arbitrary distinctive symbols indexed by j that index

W qj i , such that ||I l (x) -I l (x )|| = n j=1 ej sj l i=1 W qj i dt(x -x )

where s 1 = 0, s j+1 = e j , e n = 1, s j , e j ∈ [0, 1] -each [s j , e j ] is a segment in the line segment parameterized by t that connects x and x .

Its proof is in appendix C, and an illustration is given in fig. 2b . Essentially, it states that difference in the feature space of a NN, induced by the difference between elements in the instance space, is a summation of the norms of the linear transformation ( l i=1 W qj i ) applied on segments of the line segment that connects x, x in the instance space. Since W qj i is obtained by setting rows of W i to zero, the singular values of these induced matrices are intimately related to weight matrices W i of NN by Cauchy interlacing law by row deletion (Chafai) . Since the margin of an example x is a linear transform of the difference between I L-1 (x) and the I L-1 (x ) of an element x on the decision boundary, singular values of {W i } i=1...L-1 determine the amplification/shrinkage of the IM xx .

5. EMPIRICAL STUDIES ON REGULARIZATION OF ADVERSARIAL ROBUSTNESS:

In this section, guided by theorem 4.1, we undertake empirical studies to explore AR's regularization effects on NNs. We first investigate the behaviors of off-the-shelf architectures of fixed capacity on various datasets in section 5.1 and 5.2. More corroborative controlled studies that explore the regularization effects of AR on NNs with varied capacity are present in appendix B.4.

5.1. ADVERSARIAL ROBUSTNESS EFFECTIVELY REGULARIZES NNS ON VARIOUS DATASETS:

This section aims to explore whether AR can effectively reduce generalization errors -more specifically, the surrogate risk gaps. We use adversarial training (Madry et al., 2018) to build Our experiments are conducted on CIFAR10, CIFAR100, and Tiny-ImageNet (ImageNet, 2018) that represent learning tasks of increased difficulties. We use ResNet-56 and ResNet-110 (He et al., 2016) for CIFAR10/100, and Wide ResNet (WRN-50-2-bottleneck) (Zagoruyko and Komodakis, 2016) for Tiny-ImageNet (ImageNet, 2018). These networks are trained with increasing AR strength. Results are plotted in fig. 3 , where Net A stands for ResNet56, and Net B for ResNet-110.

Regularization of AR on NNs. We observe in fig. 3a (shown as blue lines marked by circles) that GE gaps (the gaps between training and test losses) decrease as strength of AR increase; we also observe in fig. 3a that training losses increase as AR strength increase; these results (and more results in subsequent fig. 6 ) imply that AR does regularize training of NNs by reducing their capacities to fit training samples. Interestingly, in the CIFAR10/100 results in fig. 3b , the test losses show a decreasing trend even when test error rates increase. It suggests that the network actually performs better measured in test loss as contrast to the performance measured in test error rates. This phenomenon results from that more diffident wrong predictions are made by NNs thanks to adversarial training, which will be explained in details in section 5.2, when we carry on finer analysis. We note that on Tiny-ImageNet, the test loss does not decrease as those on CIFAR10/100. It is likely because the task is considerably harder, and regularization hurts NNs even measured in test loss.

Trade-off between regularization of AR and test error rates. The error rate curves in fig. 3b also tell that the end result of AR regularization leads to biased-performing NNs that achieve degraded test performance. These results are consistent across datasets and networks.

Seemingly abnormal phenomenon. An seemingly abnormal phenomenon in CIFAR10 observed in fig. 3a is that the error rate gap actually increases. It results from the same underlying behaviors of NNs, which we would introduce in section 5.2, and an overfitting phenomenon that AR cannot control. Since it would be a digress to explain, it is put in appendix B.3.

We finally note that the adversarial robustness training reproduced is relevant, of which the defense effect is comparable with existing works. One may refer to fig. 11 in appendix D.2 for the details.

We can see from it that similar adversarial robustness to Madry et al. (2018) and Li et al. (2018) is achieved for CIFAR10/100, Tiny-ImageNet in the NNs we reproduce.

5.2. REFINED ANALYSIS THROUGH MARGINS AND SINGULAR VALUES:

The experiments in the previous sections confirm that AR reduces GE, but decreases accuracy. We study the underlying behaviors of NNs to analyze what have led to it here. More specifically, we show that adversarial training implements -adversarial robustness by making NNs biased towards less confident solutions; that is, the key finding we present in section 1.1 that explains both the prevented sudden change in prediction w.r.t. sample perturbation (i.e., the achieved AR), and the reduced test accuracy.

5.2.1. MARGINS THAT CONCENTRATE MORE AROUND ZERO LEAD TO REDUCED GE GAP:

To study how GE gaps are reduced, theorem 4.1 suggests we first look at the margins of examplesa lower bound of margins is u min in eq. ( 4). The analysis on margins has been a widely used tool in learning theory (Bartlett et al., 2017) . It reflects the confidence that a classifier has on an example, which after being transformed by a loss function, is the surrogate loss. Thus, the loss difference between examples are intuitively reflected in the difference in confidence characterized by margins.

To study how AR influences generalization of NNs, we plot in fig. 4 Concentration and reduced loss/GE gap. The concentration has different consequences on training and test losses. Before describing the consequences, to directly relate the concentration to loss gap, we further introduce estimated probabilities of examples. This is because though we use ramp loss in theoretical analysis, in the experiments, we explore the behaviors of more practically used cross entropy loss. The loss maps one-to-one to estimated probability, but not to margin, though they both serve as a measure of confidence. Suppose p(x) is the output of the softmax function of dimension L (L is the number of target classes), and y is the target label. The estimated probability of x would be the y-th dimension of (p(x)), i.e., (p(x)) y . On the training sets, since the NNs are optimized to perform well on the sets, only a tiny fraction of them are classified wrongly. To concentrate the margin distribution more around zero, is to make almost all of predictions that are correct more diffident. Thus, a higher expected training loss ensues. On the test sets, the estimated probabilities of the target class concentrate more around middle values, resulting from lower confidence/margins in predictions made by NNs, as shown in fig. 5a (but the majority of values are still at the ends). Note that wrong predictions away from decision boundaries (with large negative margins) map to large loss values in the surrogate loss function. Thus, though NNs with larger AR strength have lower accuracy, they give more predictions whose estimated probabilities are at the middle (compared with NNs with smaller AR strength). These predictions, even if relatively more of them are wrong, maps to smaller loss values, as shown in fig. 5b , where we plot the histogram of loss values of test samples.

In the end, it results in expected test losses that are lower, or increase in a lower rate than the training The observation in section 5.2.1 shows that AR make NNs just less confident by reducing the variance of predictions made and concentrate margins more around zero. In this section, we study the underlying factors of AR that make NNs become less confident.

To begin with, we show that the singular values of the weight matrix of each layer determine the perturbation in margins of samples induced by perturbations in the instance space. Such a connection between singular values and the perturbation of outputs of a single layer, i.e., ReLU(W δx), has been discussed in section 1.1. In the following, with lemma 4.1, we describe how the relatively more complex connection between margins and singular values of each weight matrix of layers of NNs holds. Observe that margins are obtained by applying a piece-wise linear mapping (c.f. the margin operator in definition 3) to the activation of the last layer of a NN. It implies the perturbations in activation of the last layer induce changes in margins in a piece-wise linear way. Meanwhile, the perturbation in the activation of the last layer (induced by perturbation in the instance space) is determined by the weight matrix's singular values of each layer of NNs. More specifically, this is explained as follows. Lemma 4.1 shows that the perturbation δI induced by δx, is given by n j=1 ej sj l i=1 W qj i δxdt . Note that for each i, W qi i is a matrix. By Cauchy interlacing law by row deletion (Chafai) , the singular values of W i , the weight matrix of layer i, determine the singular values of W qj i . Thus, suppose l = 1, we have the change (measured in norm) induced by perturbation as n j=1 ej sj W qj 1 δxdt . The singular values of W 1 would determine the variance (of norms) of activation change induced by perturbations δx, similarly as explained in section 1.1 except that the norm change now is obtained by a summation of n terms W qj 1 δxdt (each of which is the exact form discussed in section 1.1) weighted by 1/(e j -s j ). Similarly, for the case where l = 2 . . . L -1, the singular values of W l determine the variance of changes induced by the perturbation of the previous layer (induced by perturbation from further previous layer recursively) of layer l. Consequently, we choose to study these singular values.

We plot the standard deviation of singular values of each layer of ResNet56 trained on CIFAR10/100 earlier, shown in fig. 5c 5d . Overall, we can see that the standard deviation of singular values associated with a layer of the NN trained with AR strength 4 is mostly larger than that of the NN with AR strength 16. The STD reduction in CIFAR100 is relatively smaller than CIFAR10, since as observed in fig. 4b , the AR induced concentration effect of margin distributions is also relatively less obvious than that in fig. 4a . More quantitative analysis is given in appendix B.2. This leads us to our key results described in section 1.1.

APPENDICES A FURTHER RELATED WORKS:

Hard and soft adversarial robust regularization. We study the behaviors of NNs that are trained in the way that adversarial examples are required to be classified correctly. We note that the adversarial robustness required can also be built in NNs in a soft way by adding a penalty term in the risk function. Relevant works includes Lyu et al. (2015) and Miyato et al. (2018) . This line of works is not our subject of investigation. They focus on increasing test performance instead of defense performance. The focus of our works is to study the behaviors that lead to standard performance degradation when a network is trained to has a reasonable defense ability to adversarial examples. For example, a 50% accuracy on adversarial examples generated by PGD methods (Madry et al., 2018) in fig. 11 is a defense ability that can serve as a baseline for a reasonable defense performance. It is natural that in the setting where the requirement to defend against adversarial examples is dropped, the regularization can be weakened (added as a penalty term) to only aim to improve the test performance of the network. In this case, no performance degradation would occur, but the defense performance is also poor.

B FURTHER EMPIRICAL STUDIES ON ADVERSARIAL ROBUSTNESS B.1 TECHNIQUE TO BUILD ADVERSARIAL ROBUSTNESS:

To begin with, we describe the technique that we use to build AR into NNs. As mentioned in the caption of fig. 1 , we choose arguably the most well received technique, i.e., the adversarial training method (Madry et al., 2018) . Specifically, we use l ∞ -PGD (Madry et al., 2018) untargeted attack adversary, which creates an adversarial example by performing projected gradient descent starting from a random perturbation around a natural example. Then, NNs are trained with adversarial examples. NNs with different AR strength are obtained by training them with increasingly stronger adversarial examples. The adversarial strength of adversarial examples is measured in the l ∞ norm of the perturbation applied to examples. l ∞ -norm is rescaled to the range of 0 -255 to present perturbations applied to different datasets in a comparable way; that means in fig. 1 3 4 5 6 11, AR is measured in this scale. We use 10 steps of size 2/255 and maximum of = [4/255, 8/255, 16/255] respectively for different defensive strength in experiments. For example, a NN with AR strength 8 is a NN trained with adversarial examples generated by perturbations whose l ∞ norm are at most 8. Lastly, we note that although adversarial training could not precisely guarantee an adversarial robustness radius of , a larger l ∞ norm used in training would make NNs adversarially robust in a larger ball around examples. Thus, though the precise adversarial robustness radius is not known, we know that we are making NNs adversarially robust w.r.t. a larger . Consequently, it enables us to study the influence of -AR on NNs by studying NNs trained with increasing l ∞ norm.

B.2 QUANTITATIVE ANALYSIS OF VARIANCE REDUCTION IN SINGULAR VALUES:

Here, we provide more quantitative analysis on fig. 5c and fig. 5d , as noted previously in section 5.2.2. Quantitatively, we can look at the accumulated standard deviation (STD) difference in all layers. We separate the layers into two group: the group that the STD (denoted σ 4 i ) of singular values of layer i (of the NN trained) with AR strength 4 that is larger than that (denoted σ 16 i ) of AR strength 16; and the group that is smaller. In CIFAR10, for the first group, the summation of the difference/increments of STD of the two networks ( i σ 4 i -σ 16 i ) is 4.7465, and the average is 0.1158. For the second groups, the summation ( i σ 16

i -σ 4 i ) is 0.4372, and the average is 0.0312. In CIFAR100, the summation of the first group is 3.7511, and the average is 0.09618; the summation of the second group is 0.4372, and the average is 0.1103. The quantitative comparison shows that the accumulated STD decrease in layers that have their singular value STDs decreased (comparing STD of the NN with AR strength 16 with STD of the NN with AR strength 4) is a magnitude larger the accumulated STD increase in the layers that have their singular value STDs increased. The magnitude difference is significant since the STDs of singular values of most layers are around 1. review as a conference paper at ICLR 2020

B.3 DISCREPANCY BETWEEN TRENDS OF LOSS AND ERROR RATE GAPS IN LARGE CAPACITY NNS:

In section 5.1, we have noted an inconsistent behaviors of CIFAR10, compared with that of CIFAR100 and Tiny-ImageNet: the error gap reduces for CIFAR100 and Tiny-ImageNet, but increases for CIFAR10. It might suggest that AR does not effectively regularize NNs in the case of CIFAR10. However, we show in this section that the abnormal behaviors of CIFAR10 are derived from the same margin concentration phenomenon observed in section 5.2.1 due to capacity difference, and compared with the error gaps, the GE/loss gaps are more faithfully representatives of the generalization ability of the NNs. Thus, the seemingly abnormal phenomenon corroborate, not contradict, the key results present in section 1.

Using 4c , the high training accuracy is made up of correct predictions with relatively lower confidence (compared with NNs with lower AR), which is bad and not characterized by the error rate; and the low test accuracy are made up of wrong predictions with relatively lower confidence as well (as explain in section 5.2.1), which is good, and not characterized by error rate as well. Thus, the error gap in this case does not characterize the generalization ability (measured in term of prediction confidence) of NNs well, while the GE gap more faithfully characterizes the generalization ability, and show that AR effectively regularizes NNs. In the end, AR still leads to biased poorly performing solutionssince the overfitting in training set does not prevent the test margin distribution concentrating more around zero, which leads to higher test errors of CIFAR10 as shown in 3b. It further suggests that the damage AR done to the hypothesis space is not recovered by increasing capacity, however the ability of NNs to fit arbitrary labels is not hampered by AR.

B.4 FURTHER EVIDENCE OF REGULARIZATION EFFECTS ON NNS WITH VARIED CAPACITY:

In previous sections, we observe AR consistently effectively regularizes NNs; meanwhile, we also observe that in the case where a NN has a large capacity, it can spuriously overfit training samples and lead to an increased error gap. In this section, we present additional results by applying AR to networks of controlled capacities. This is to ensure that our observations and analysis in previous sections exist not just at some singular points, but also in a continuous area in the hypothesis space. To control capacities of NNs quantitatively, we choose the measure based on spectral norm (Bartlett et al., 2017; Neyshabur et al., 2018a) . In spectral norm based capacity measure bound (Bartlett et al., 2017; Neyshabur et al., 2018a) , the NN capacity is normally proportional to a quantity called spectral complexity (SC), which is defined as follows.

Definition 7 (Spectral Complexity). Spectral complexity SC(T ) of a NN T is the multiplication of spectral norms of weight matrices of layers in a NN.

SC(T ) = L i=1 ||W i || 2

where {W i } i=1...L denotes weight matrices of layers of the NN.

To control SC, we apply the spectral normalization (SN) (Sedghi et al., 2018) on NNs. The technique renormalizes the spectral norms of the weight matrices of a NN to a designated value after certain iterations. We carry out the normalization at the end of each epoch. We train ResNet56 with increasingly strong AR and with increasingly strong spectral normalization. The results are shown in fig. 6 .

As can be seen, as the capacity of NNs decreases (from upper left to bottom right in each subfigure), the error gap between training and test gradually changes from an increasing trend to a decreasing trend, while the loss gap keeps a consistent decreasing trend. It suggests that the overfitting phenomenon is gradually prevented by another regularization techniques, i.e., the spectral normalization. As a result, the regularization effect of AR starts to emerge even in the error gap, which previously manifests only in the loss gap. The other curves corroborate our previous observations and analysis as well.

B.5 FURTHER EVIDENCE ON THE SMOOTHING EFFECT OF ADVERSARIAL ROBUSTNESS:

We quantitatively measure the smoothing effect around examples here by measuring the average maximal loss change/variation induced by the perturbation (of a fixed infinity norm) applied on examples. We found that the loss variation decreases as networks become increasingly adversarially robust. Note that the loss of an example is a proxy to the confidence of the example -it is the logarithm of the estimated probability (a characterization of confidence) of the NN classifier.

For a given maximal perturbation range characterized by the infinity norm, we generate adversarial examples within that norm for all test samples. For each example, the maximal loss variation/change of the adversarial example w.r.t. the natural example is computed for networks with different adversarial strength. To obtain statistical behaviors, we compute the average and standard deviation of such maxima of all test samples. The results are shown in fig. 7 . The exact data can be found in table 1 . We can see that the average loss variation decreases with adversarial robustness. The standard deviation decreases with network adversarial robustness as well. The phenomenon that the standard deviation is comparably large with the mean might need some explanation. This is because different examples have different losses, thus the loss varies in relatively different regimens -the more wrongly classified examples vary in a larger magnitude, and vice versa for more correctly classified examples. This phenomenon leads to the large standard deviation of the loss variation. We also use FGSM (Goodfellow et al., 2015) in the adversarial training to build adversarial robustness into NNs. The results are consistent with the results obtained using PGD. The experiments are carried on CIFAR10/100. We present key plots that support the results obtained in the main content here. All the setting are same with that described in appendix B.1 of PGD, except that we replace PGD with FGSM.

Adversarial robustness reduces generalization gap and standard test performance. In section 5.1, we find that NNs with stronger adversarial robustness tend to have smaller loss/generalization gap between training and test sets. Consistent phenomenon has been observed in networks adversarially trained with FGSM on CIFAR10/100, as shown in fig. 8a . Consistent standard test performance degradation has been observed in adversarially trained with FGSM on CIFAR10/100 as well, as shown in fig. 8b . The exact data can be found in table 2.

Adversarial robustness concentrates examples around decision boundaries. In section 5.2.1, we find that the distributions of margins become more concentrated around zero as AR grows. In order to characterize the bound to the GE, we build on the algorithmic robustness framework (Xu and Mannor, 2012) . We introduce the framework below. Definition 8 ((K, (•))-robust). An algorithm is (K, (•)) robust, for K ∈ N and (•) : Z m → R, if Z can be partitioned into K disjoint sets, denoted by C = {C k } K k=1 , such that the following holds for all s i = (x i , y i ) ∈ S m , z = (x, y) ∈ Z, C k ∈ C:

∀s i = (x i , y i ) ∈ C k , ∀z = (x, y) ∈ C k =⇒ |l(f (x i ), y i ) -l(f (x), y)| ≤ (S m ).

The gist of the definition is to constrain the variation of loss values on test examples w.r.t. those of training ones through local property of the algorithmically learned function f . Intuitively, if s ∈ S m and z ∈ Z are "close" (e.g., in the same partition C k ), their loss should also be close, due to the intrinsic constraint imposed by f . For any algorithm that is robust, Xu & Mannor (Xu and Mannor, 2012) proves Theorem C.1 (Xu & Mannor (Xu and Mannor, 2012) ). If a learning algorithm is (K, (•))-robust and L is bounded, a.k.a. L(f (x), y) ≤ M ∀z ∈ Z, for any η > 0, with probability at least 1 -η we have

EQUATION

To control the first term, an approach is to constrain the variation of the loss function. Covering number (Shalev-Shwartz & Ben-David, (Shalev-Shwartz and Ben-David, 2014) , Chapter 27) provides a way to characterize the variation of the loss function, and conceptually realizes the actual number K of disjoint partitions.

For any regular k-dimensional manifold embedded in space equipped with a metric ρ, e.g., the image data embedded in L 2 (R 2 ), the square integrable function space defined on R 2 , it has a covering number N (X ; ρ, ) of (C X / ) k (Verma, 2013) , where C X is a constant that captures its "intrinsic" properties, and is the radius of the covering ball. When we calculate the GE bound of NNs, we would assume the data space is a k-dimensional regular manifold that accepts a covering.

Adversarial robustness makes NNs a (K, (•))-robust algorithm, and is able to control the variation of loss values on test examples. Building on covering number and theorem C.1, we are able to prove theorem 4.1.

C.2 NEURAL NETWORKS:

A NN is a map that takes an input x from the space X , and builds its output by recursively applying a linear map W i followed by a pointwise non-linearity g:

x i = g(W i x i-1 ),

where i indexes the times of recursion, which is denoted as a layer in the community, i = 1, . . . , L, x 0 = x, and g denotes the activation function. which is restricted to Rectifier Linear Unit (ReLU) (Glorot et al., 2011) or max pooling operator (Bécigneul, 2017) in this paper. To compactly summarize the operation of T , we denote

EQUATION

C.3 PROOF Proof of lemma 4.1. By Theorem 3 in Sokolic et al. (2017) , we have

EQUATION

where J (x) denotes the Jacobian of I l (x) at x.

We first study case 1). Given any example z = (x, y) ∈ C i , let ŷ = arg max i =y w T i T x. Its ramp loss is l γ (x, y) = max{0, 1 -1 γ (w y -w ŷ ) T T x}.

Note that within C i , (w y -w ŷ ) T T x ≥ 0, thus l γ (x, y) is mostly 1, and we would not reach the region where r > 0 in definition 4. Let u(x) := (w y -w ŷ ) T T x, and u i min = min ∀x∈Ci u(x). We have

l γ (x, y) ≤ max{0, 1 - u i min γ } ≤ max{0, 1 - u min γ },

where u min denotes the smallest margin among all partitions.

The inequality above shows adversarial robustness requires that T x should vary slowly enough, so that in the worst case, the loss variation within the adversarial radius should satisfy the above inequality. The observation leads to the constraint on the loss difference (•) defined earlier in definition 8 in the following.

Given any training example z := (x, y) ∈ C i , and any element z := (x , y ) ∈ C i , where C i is the covering ball that covers x, we have

EQUATION

Now we relate the margin to the margin in the instance space.

Given z := (x, y) ∈ Z, and z , of which x is the closest points to x (measured in Euclidean norm) on the decision boundary, we can derive the inequality below.

u(x) = u(x) -u(x ) (9) = 1 0 J (x -t(x -x ))dt(x -x ) (10) = 1 0 (w y -w ŷ ) T L-1 i=1 W x-t(x-x ) i dt(x -x ) = 1 0 (w y -w ŷ ) T L-1 i=1 W x-t(x-x ) i dt(x -x ) (11) = n j=1 ej sj (w y -w ŷ ) T L-1 i=1 W qj i dt(x -x ) (12) ≥ min y,ŷ∈Y,y =ŷ ||w y -w ŷ || 2 L-1 i=1 σ i min ||x -x || 2 1 0 dt (13) ≥ min y,ŷ∈Y,y =ŷ ||w y -w ŷ || 2 L-1 i=1 σ i min ||x -x || 2

where J (x) denotes the Jacobian of I l (x) at x. Equation (10) can be reached by Theorem 3 in Sokolic et al. (2017) . Equation ( 11) can be reached because (w y -w ŷ )W

x-t(x-x ) i (x -x ) is the actually classification score u(x), u(x ) difference between x, x , and by assumptions 4.1, they are positive throughout. Equation ( 12) is reached due to corollary C.1 -in this case, the matrix W l in corollary C.1 is of rank one.

To arrive from eq. ( 12) to eq. ( 13), we observe that x is the closest point to x on the decision boundary. Being the closest means xx ⊥ N ((w y -w ŷ )T ). If the difference xx satisfies xx ⊥ N (T ), we can always remove the part in the N (T ), which would identify a point that is closer to x, but still on the decision boundary, which would be a contradiction. Then if xx is orthogonal to the null space, we can bound the norm using the least singular values. We develop the informal reasoning above formally in the following.

Similarly in Lemma 3.4 in Jia et al. (2019) , by Cauchy interlacing law by row deletion, assuming x ⊥ N ( L-1 i=1 W qj i ) (N denotes the null space; the math statement means x is orthogonal to the null space of J (x)), we have

|| L-1 i=1 W qj i x|| 2 ≥ L-1 i=1 σ i min ||x|| 2 (14)

where σ i min is the smallest singular value of W i . Then conclusion holds as well for multiplication of matrices L-1 i=1 W qj i , since the multiplication of matrices are also a matrix. Notice that in each integral in eq. ( 12), we are integrating over constant. Thus, we have it equates to

n j=1 (e j -s j ) (w y -w ŷ ) T L-1 i=1 W qj i (x -x ) . Now we show that in each operand, x -x ⊥ N ((w y -w ŷ ) T L-1 i=1 W qj i ). Denote T qj as N ((w y -w ŷ ) T L-1 i=1 W qj i

). Suppose that it does not hold. Then we can decompose xx into two components ∆ 1 , ∆ 2 , where ∆ 1 ⊥ T qj , ∆ 2 ⊥ T qj . We can find a new point x = x + ∆ 1 that is on the boundary. However, in this case

||x -x || 2 = ||∆ 1 || 2 ≤ ||∆ 1 || 2 + ||∆ 2 || 2 = ||x -x || 2

Recall that x is the closest point to x on the decision boundary. This leads to a contradiction. Repeat this argument for all j = 1, . . . , n, then we have xx be orthogonal to all N (T qj ). Thus, by the inequality eq. ( 14) earlier, we can arrive at eq. ( 13) -notice that w y -w ŷ is a matrix with one column, thus also satisfies the above reasoning.

Through the above inequality, we can transfer the margin to margin in the instance space. Let v(x) be the shortest distance in || • || 2 norm from an element x ∈ X to the decision boundary. For a covering ball C i , let v i min be min x∈Ci v(x). Let v min be the smallest v i min among all covering balls C i that contain at least a training example. We have that

u min ≥ min y,ŷ∈Y,y =ŷ ||w y -w ŷ || 2 L-1 i=1 σ i min v min

Consequently, we can obtain an upper bound of eq. ( 8) parameterized on v min , as follows

max{0, 1 - u min γ } ≤ max{0, 1 - min y,ŷ∈Y,y =ŷ ||w y -w ŷ || 2 L-1 i=1 σ i min v min γ }.

Notice that only because 0 -adversarial robustness, we can guarantee that v min is non-zero, thus the bound is influenced by AR.

Then, we study case 2), in which all training samples z ∈ C i are classified wrong. In this case, for all z ∈ C i , the ŷ given by ŷ = arg max i =y w T i T x in the margin operator is the same, for that ŷ is the wrongly classified class. Its ramp loss is

l γ (x, y) = max{0, 1 - 1 γ (w y -w ŷ ) T T x}.

Note that in the case 1), it is the y that stays fixed, while ŷ may differ from example to example; while in the case 2), it is the ŷ stays fixed, while y may differ.

Similarly, within C i as required by adversarial robustness, (w y -w ŷ ) T T x ≤ 0, thus we always have

EQUATION

Since only these two cases are possible, by eq. ( 8) and eq. ( 15), we have ∀z,

EQUATION

The rest follows the standard proof in algorithmic robust framework.

Let N i be the set of index of points of examples that fall into C i . Note that (|N i |) i=1...K is an IDD multimonial random variable with parameters m and (|µ 

(C i )|) i=1...K . Then |R(l • T ) -R m (l • T )| =| K i=1 E Z∼µ [l(T X, Y )]µ(C i ) -

Remember that z = (x, y).

By eq. ( 16) we have eq. ( 17) is equal or less than max{0, 2(1 -umin γ )}. By Breteganolle-Huber-Carol inequality, eq. ( 18) is less or equal to [3, 4, 6, 3] bottleneck residual units for each group respectively. The 3 × 3 filter of the bottleneck residual units have [64 × k, 128 × k, 256 × k, 512 × k] feature maps with the widen factor k = 2 as mentioned in Zagoruyko and Komodakis (2016) . We replace the first 7 × 7 convolution layer with 3 × 3 filters with stride 1 and padding 1. The max pooling layer after the first convolutional layer is also removed to fit the 56 × 56 input size. Batch normalization layers are retained for this dataset. The weights of convolution layers for Tiny ImageNet are initialized with Xavier uniform (Glorot and Bengio, 2010) . Again, all dropout layers are omitted.

Tiny-ImageNet Training. The experiments on the Tiny-ImageNet dataset are based on a mini-batch size of 256 for 90 epochs. The initial learning rate is set to be 0.1 and decayed at 10 at 30 and 60 epochs respectively. All experiments are trained on the training set with stochastic gradient descent with the momentum of 0.9. Models. We use ResNet-type networks (Zhang et al., 2018) . Given that we need to isolate factors that influence spectral complexity, we use ResNet without additional batch normalization (BN) layers.

To train ResNet without BN, we rely on the fixup initialization proposed in Zhang et al. (2018) . The scalar layers in Zhang et al. (2018) are also omitted, since it changes spectral norms of layers.

:

The AR strength is characterized by the maximally allowed l∞ norm of adversarial examples that are used to train the NNs -we use adversarial training(Madry et al.,

2018) to build adversarial robustness into NNs. Details can be found in appendix B.1

Note that in the previous paragraph, though we identifies quantities umin and σ i min related to the upper bound of GE, the quantities we actually would study empirically are margin distribution and all singular values that characterize the GE of all samples, not just the extreme case (upper bound). The analytic characterization of the GE of all samples is not possible since we do not have enough information (at least we do not know the true distribution of samples). That's why to arrive at close-form analytic characterization of GE, we resort to the extreme non-asymptotic large-sample behaviors. The analytic form is a neat way to present how relevant quantities influence GE. In the rest of the paper, we would carry on empirical study on the distributions of margins and singular values mostly to investigate AR's influence on GE of all samples.

Figures and Tables:

Figure 1: Experiment results on ResNet56 (He et al., 2016) trained on the CIFAR10 dataset. For the details of the experiments, refer to section 5. (a) The standard deviation of singular values of each layer of NNs with adversarial robustness (AR) strength 4, 16 (AR strength 8 is dropped for clarity of the plot). To emphasize, the x-axis is the layer index -overall 56 layers are involved. (b) The probability distribution of margins of NNs with AR strength 4, 8, 16. (c) The standard and adversarial accuracy of NNs with AR 4, 8, 16.

Figure 3: Experiment results on CIFAR10/100, and Tiny-ImageNet. Net A, B are ResNet-56 and ResNet-110 (He et al., 2016) respectively. The unit of x-axis is the adversarial robustness (AR) strength of NNs, c.f. the beginning of section 5. (a) Plots of loss gap (and error rate gap) between training and test datasets v.s. AR strength. (b) Plots of losses (and error rates) on training and test datasets v.s. AR strength.

Figure 4: Margin distributions of NNs with AR strength 4, 8, 16 on Training and Test sets of CIFAR10/100.

Figure 5: (a)(b) are histograms of estimated probabilities and losses respectively of the test set sample of NNs trained AR strength 4, 8, 16. We plot a subplot of a narrower range inside the plot of the full range to show the histograms of examples that are around the middle values to show the change induced by AR that induces more middle valued confidence predictions. (c)(d) are standard deviations of singular values of weight matrices of NNs at each layer trained on CIFAR10/100 with AR strength 4, 16. The AR strength 8 is dropped for clarity.

Figure 6: The four plots from upper left to lower bottom (in each subfigure) are NNs with increasingly smaller spectral complexity, where "Spectral Norm 1" means for each weight matrix of the NN, its spectral norm is at most 1. (a) Plots of training/test loss gap (and error gap) against adversarial robustness strength. (b) Training/test losses and error rates against increased strength of adversarial robustness.

Figure 7: Average maximal loss variation induced by adversarial examples in networks with increasing adversarial robustness. The experiments are carried on CIFAR10/100. represents the maximal perturbation can be applied on natural test examples to generate adversarial examples. It is measured in the infinity norm. The larger the , the stronger the perturbation is. The error bars represent standard deviation.

Figure 8: Experiment results on CIFAR10/100. The network is ResNet-56 (He et al., 2016). The unit of x-axis is the adversarial robustness (AR) strength of NNs, c.f. the beginning of section 5. (a) Plots of loss gap between training and test datasets v.s. AR strength. (b) Plots of error rates on training and test datasets v.s. AR strength.

Z∼µ [l(T X, Y )]µ(C i )x, y) -l(T x j , y j )|

Figure 11: The plot of accuracy on adversarial examples v.s. adversarial defense strength built in NNs. The dotted line of which the intersections are marked by stars are adversarial accuracy in Madry et al. (2018) (CIFAR10), in Li et al. (2018) (Tiny ImageNet) under similar adversarial attack strength.

More specifically, let σ min , σ max be the maximal and minimal singular values, if x is not in the null space of W , then we have ||W x|| ∈ [σ min ||x||, σ max ||x||], where || • || denotes 2-norm. This applies to norm ||δx|| of a perturbation as well; that is, given possible changes δx of x of the same norm ||δx|| = c, where c is a constant, the variance of σ(W ) roughly determines the variance of ||W δx||, where σ(W ) denotes all singular values {σ i } of W .

Table content: <table/>

to lemma 4.1). Consequently, by reducing the variance of singular values of weight matrix of a layer of the NN, AR reduces the norm variance of layer activations induced by input perturbations. 2. The reduced norm variance induced by example perturbations concentrates examples, and it empirically concentrates them around decision boundaries; that is, predictions are more diffident.The reduced variance implies that the outputs of each layer of the NN are more concentrated, but it does not tell where they are concentrated. Note that in the previous paragraph, the variance

Table content: <table/>

Our empirical analysis tells that AR effectively regularizes NNs to reduce the GE gaps. To understand how reduced GE gaps turns out to degrade test performance, we study variance of singular values of layer-wise weight matrices of NNs and distributions of margins of samples, when different strength of AR are applied on NNs.• The study shows that AR is achieved by regularizing/biasing NNs towards less confident solutions by making the changes in the feature space of most layers (which are induced by changes in the instance space) smoother uniformly in all directions; so to a certain extent, it prevents sudden change in prediction w.r.t. perturbations. However, the end result of such smoothing concentrates samples around decision boundaries and leads to worse standard performance.

Table content: <table><tr><td>2 RELATED WORKS</td></tr><tr><td>Robustness in machine learning models is a large field. We review some more works that analyze</td></tr><tr><td>robustness from the statistical perspective. The majority of works that study adversarial robustness</td></tr><tr><td>from the generalization perspective study the generalization behaviors of machine learning models</td></tr><tr><td>under adversarial risk. The works that study adversarial risk include Attias et al. (2018); Schmidt</td></tr><tr><td>et al. (2018); Cullina et al. (2018); Yin and Bartlett (2018); Khim and Loh (2018); Sinha et al. (2018).</td></tr><tr><td>The bounds obtained under the setting of adversarial risk characterize the risk gap introduced by</td></tr><tr><td>adversarial examples, thus, it is intuitive that a larger risk gap would be obtained for a larger allowed</td></tr><tr><td>perturbation limit , which is roughly among the conclusions obtained in those bounds. That is to</td></tr><tr><td>say, the conclusion normally leads to a larger generalization error as an algorithm is asked to handle</td></tr><tr><td>more adversarial examples, for that it focuses on characterizing the error of adversarial examples, not</td></tr><tr><td>that of natural examples. However, adversarial risk is not our focus. In this paper, we study when a</td></tr><tr><td>classifier needs to accommodate adversarial examples, what is the influence that the accommodation</td></tr><tr><td>has on generalization behaviors of empirical risk of natural data.</td></tr></table>

CIFAR10 and CIFAR100 as examples and evidence in the previous sections, we explain how the discrepancy emerges from AR's influence on margin distributions of the same network trained on tasks with different difficulties. Further evidence that the discrepancy arises from capacity difference would be shown at appendix B.4, where we run experiments to investigate GE gap of NNs with varied capacities on the same task/dataset. 1. On CIFAR10, the margin distribution of training sets not only concentrate more around zero, but also skews towards zero. As shown in the margin distribution on training sets of CIFAR10 in fig. 4c, we find that the large error gap is caused by the high training accuracy that is achieved with a high concentration of training samples just slightly beyond the decision boundary. This phenomenon does not happen in CIFAR100. Comparing margin distribution on the test set in fig. 4a, the margin distribution on the training set in fig. 4c is highly skewed, i.e., asymmetrically distributed w.r.t. mean. While the margin distributions of CIFAR100 training set in fig. 4d is clearly less skewed, and looks much more like a normal distribution, as that of the margin distribution on the test set. 2. The high skewness results from the fact that the NN trained on CIFAR10 is of large enough capacity to overfit the training set. As known, CIFAR100 is a more difficult task w.r.t. CIFAR10 with more classes and less training examples in each class. Thus, relatively, even the same ResNet56 network is used, the capacity of the network trained on CIFAR10 is larger than the one trained on CIFAR100. Recall that NNs have a remarkable ability to overfit training samples (Zhang et al., 2016). And note that though AR requires in a ball around an example, the examples in the ball should be of the same class, since the ball is supposed only to include imperceptible perturbation to the example, few of the training samples are likely in the same ball. Thus, the ability to overfit the training set is not regularized by AR: if NNs can overfit all training samples, it can still overfit some more examples that are almost imperceptibly different. For CIFAR10, since NNs have enough capacity, the NN simply overfits the training set. 3. However, as shown in the observed overfitting phenomenon in fig.

Table content: <table/>

Data of the smoothing effect of PGD adversarial training in fig. 7.

Table content: <table><tr><td>Dataset</td><td>Attack Strength</td><td>4</td><td>Defensive Strength 8</td><td>16</td></tr><tr><td/><td>= 1</td><td colspan="3">0.0273 ± 0.0989 0.0236 ± 0.0778 0.0215 ± 0.0588</td></tr><tr><td>CIFAR10</td><td>= 2</td><td colspan="3">0.0590 ± 0.1637 0.0477 ± 0.1337 0.0443 ± 0.1102</td></tr><tr><td/><td>= 4</td><td colspan="3">0.1337 ± 0.2494 0.1006 ± 0.2137 0.0888 ± 0.1816</td></tr><tr><td/><td>= 1</td><td colspan="3">0.0550 ± 0.1276 0.0430 ± 0.1043 0.0379 ± 0.0886</td></tr><tr><td>CIFAR100</td><td>= 2</td><td colspan="3">0.1072 ± 0.2138 0.0839 ± 0.1802 0.0732 ± 0.1568</td></tr><tr><td/><td>= 4</td><td colspan="3">0.1868 ± 0.2946 0.1563 ± 0.2712 0.1355 ± 0.2494</td></tr><tr><td colspan="5">B.6 FURTHER EMPIRICAL STUDY ON USING FGSM IN ADVERSARIAL TRAINING TO BUILD</td></tr><tr><td colspan="2">ADVERSARIAL ROBUSTNESS</td><td/><td/><td/></tr></table>

Data of fig. 8

Table content: <table><tr><td>Dataset</td><td/><td>Defensive Strength 4 8 16</td></tr><tr><td/><td colspan="2">Test Acc. 89.32 86.67 82.83</td></tr><tr><td/><td colspan="2">Trn Loss 0.038 0.086 0.252</td></tr><tr><td>CIFAR10</td><td colspan="2">Test Loss 0.467 0.495 0.637</td></tr><tr><td/><td>∆ Loss</td><td>0.429 0.409 0.385</td></tr><tr><td/><td colspan="2">Test Acc. 62.01 59.78 56.30</td></tr><tr><td/><td colspan="2">Trn Loss 0.469 0.656 0.822</td></tr><tr><td>CIFAR100</td><td colspan="2">Test Loss 1.776 1.723 1.797</td></tr><tr><td/><td>∆ Loss</td><td>1.307 1.067 0.975</td></tr></table>

Raw data of CIFAR10 dataset for plots in fig. 3 and fig. 11.

Table content: <table><tr><td>Method</td><td/><td>Defensive Strength 4 8 16</td></tr><tr><td/><td colspan="2">Trn Acc. 99.51 98.45 95.97</td></tr><tr><td/><td colspan="2">Test Acc. 88.86 87.51 84.89</td></tr><tr><td>ResNet-56 + Adv Trn</td><td colspan="2">∆Acc. Trn Loss 0.014 0.043 0.105 10.65 10.94 11.08 Test Loss 0.683 0.649 0.650</td></tr><tr><td/><td>∆Loss</td><td>0.669 0.606 0.545</td></tr><tr><td/><td>PGD</td><td>65.92 65.24 72.16</td></tr><tr><td/><td colspan="2">Trn Acc. 99.95 99.62 98.42</td></tr><tr><td/><td colspan="2">Test Acc. 89.20 87.09 85.02</td></tr><tr><td>ResNet-110 + Adv Trn</td><td colspan="2">∆Acc. Trn Loss 0.002 0.010 0.044 10.75 12.53 13.40 Test Loss 0.825 0.813 0.729</td></tr><tr><td/><td>∆Loss</td><td>0.823 0.803 0.685</td></tr><tr><td/><td>PGD</td><td>58.02 66.94 72.40</td></tr></table>

Raw data of CIFAR100 dataset for the plot in fig.3and fig. 11. Results. The data for fig. 3 are given in table 3, 4 and 5. More specifically, the data on CIFAR10 are given in table 3. The result on CIFAR100 are given in table 4. The result on Tiny-ImageNet are given in table 5.Adversarial Robustness Attack Method. The adversarial accuracy is evaluated against l ∞ -PGD(Madry et al., 2018) untargeted attack adversary, which is one of the strongest white-box attack methods. When considering adversarial attack, they usually train and evaluate against the same perturbation. And for our tasks, we only use the moderate adversaries that generated by 10 iterations with steps of size 2 and maximum of 8. When evaluating adversarial robustness, we only consider clean examples classified correctly originally, and calculate the accuracy of the adversarial examples generated from them that are still correctly classified. The adversarial accuracy is given in table 3 4 5, the row named "PGD", and plotted in fig.11.

Table content: <table><tr><td>Method</td><td/><td>Defensive Strength 4 8 16</td></tr><tr><td/><td colspan="2">Trn Acc. 88.73 86.97 82.17</td></tr><tr><td/><td colspan="2">Test Acc. 61.31 60.87 59.43</td></tr><tr><td>ResNet-56 + Adv Trn</td><td colspan="2">∆Acc. Trn Loss 0.357 0.413 0.570 27.42 26.10 22.74 Test Loss 2.063 2.106 1.978</td></tr><tr><td/><td>∆Loss</td><td>1.706 1.693 1.408</td></tr><tr><td/><td>PGD</td><td>30.52 40.99 48.81</td></tr><tr><td/><td colspan="2">Trn Acc. 96.91 94.55 90.90</td></tr><tr><td/><td colspan="2">Test Acc. 61.48 61.26 59.56</td></tr><tr><td>ResNet-110 + Adv Trn</td><td colspan="2">∆Acc. Trn Loss 0.098 0.171 0.278 35.43 33.29 31.34 Test Loss 2.645 2.413 2.323</td></tr><tr><td/><td>∆Loss</td><td>2.547 2.241 2.045</td></tr><tr><td/><td>PGD</td><td>33.33 42.08 50.99</td></tr></table>

Peer review (iclr2020):
The paper proposes to explain a phenomenon that the increasing robustness for adversarial examples might lead to performance degradation on natural examples. The authors analyzed it from the following aspects: 1) Adversarial robustness reduces the variance of output at most layers in terms of reducing the standard deviation (STD) of singular values associated with a layer of NN. The authors provide the experiment to show that the stronger robustness for adversarial examples leads to smaller STD of singular values of parameter of layers. 2) The reduced norm variance can cause the margins concentrated around zeros. Specifically? the authors provide the relevant lemma to show the relationship between margin and singular vectors. Moreover?the authors also conducted the experiment to show that stronger robustness over adversarial examples can lead to zero concentration of margin. The authors think a small margin might cause shrinking the hypothesis space which might cause low generalization. 3) The authors have derived a bound of generalization which is related to Instance-space Margin?and minimum singular values. This proved that strong robustness on adversarial examples might reduce the generalization. In general, this paper seems technically sound. It is good that to some theoretic analysis can be derived in particular a bound of generalization can be given. Moreover, some experiments were made trying to verify the theory. Despite interesting, there are still some major concerns regarding the paper? 1. The authors mentioned that “it is widely observed that such methods would lead to standard performance degradation, i.e., the degradation on natural examples.” I am afraid that this may not be always the case. In some other related work (see C1), adversarial training can perhaps achieve the performance lift on both the adversarial examples and natural examples (if a trade-off parameter can be well specified). Some clarification or further discussion may be necessary regarding this point. 2. Only PGD was used as the adversarial perturbations in the experimental part of this paper. It would be more convincing if the authors could perform analysis on different adversarial training methods, e.g. FGSM and even the unified gradient perturbations developed in C2. There are also more adversarial attacks in the literature. 3. The authors stated that the sample concentration around decision boundaries smoothness sudden changes, which was verified by the accuracy degradation. This is ok but it would be better to visualize or quantifying directly whether this can indeed make the boundary smoother. One possible way is to plot the confidence when moving the points near the decision boundary to check whether the confidence changes smoothly. 4. Finally, this paper seems to be written in a hurry. The paper may need substantial improvement on the English writing. There are still quite a few typos and grammar errors in the paper; this makes the paper less attractive though it contains some theoretic merits. In summary, it is good that a theoretical bound can be derived from the paper, but this paper*s quality may need more enhancement particularly on its writing and experimental parts. C1: Virtual Adversarial Training: a Regularization Method for Supervised and Semi-Supervised, Learning* http://arxiv.org/abs/1704.03976 C2: A Unified Gradient Regularization Family for Adversarial Examples C. Lyu, K. Huang, and H. Liang, ICDM 2015. ============ I have carefully read the response as well as the revised paper. To me, the response has addressed those of my major concerns. I an inclined to increase my rating and would suggest to weak accept this paper.