Year: 2019

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.

heading: 1 INTRODUCTION
text: 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), adversarial training has been suggested as a form of regularization: it augments the training of NNs with adversarial examples, thus might improve the generalization of the end models. How does a possible improvement in generalization end up degrading performance? It prompts us to analyze the regularization effects of AR on NNs. A successful regularization technique is expected to improve test performance,
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.

heading: 1.1 AR LEADS TO DIFFIDENT NNS WITH MORE INDECISIVE MISCLASSIFICATIONS
text: This section elaborates the key results we briefly present previously.

heading: 1. AR reduces the variance of (norms of) the activation/outputs (compared with NNs with different
text: 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 x, singular values of W determine how the norm ||Wx|| is changed 1The 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
when compared with ||x||. 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 ||Wx|| ∈ [σ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 . In more details, note that by SVD decomposition, W δx = ∑ i σiuiv T i δx, thus σi determines how the component vTi δx in the direction of vi 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) 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 relationship discussed between ||W δx|| and ||δx|| equally applies to ||Wx|| and ||x||, where x is an actual example instead of perturbations. Thus, to find out the concentration of perturbations, we can look at the concentration of samples. Technically, we look at margins of examples. In a multi-class setting, suppose a NN computes a score function f : Rd → RL, where L is the number of classes; a way to convert this to a classifier is to select the output coordinate with the largest magnitude, meaning x 7→ argmaxi fi(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 fy(x)−maxi 6=y fi(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 = x− x′ 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.

heading: 1.2 OUTLINE AND CONTRIBUTIONS
text: 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. • 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.

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

heading: 3 PRELIMINARIES
text: 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 Sm = {zi = (xi, yi)}mi=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 7→ Y in a hypothesis space (a class T of functions) that minimizes the expected risk R(l ◦ T ) = EZ∼µ [l (T (X), Y )] , Since µ is unknown, the observable quantity serving as the proxy to the expected risk R is the empirical risk
Rm(l ◦ T ) = 1
m m∑ i=1 l (T (xi), yi) .
Our goal is to study the discrepancy between R and Rm, which is termed as generalization error — it is also sometimes termed as generalization gap in the literature
GE(l ◦ T ) = |R(l ◦ T )−Rm(l ◦ T )|. (1)
Definition 1 (Covering number). Given a metric space (S, ρ), and a subset S̃ ⊂ S, we say that a subset Ŝ of S̃ is a -cover of S̃ , if ∀s̃ ∈ S̃ , ∃ŝ ∈ Ŝ such that ρ(s̃, ŝ) ≤ . The -covering number of S̃ is

heading: N (S̃, ρ) = min{|Ŝ| : Ŝ is an -covering of S̃}.
text: 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 → RL, 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 fŷ(x+ δx)− fi(x+ δx) ≥ 0, where ŷ = argmaxj fj(x) and i 6= ŷ ∈ 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 operatorM : RL × {1, . . . , L} → R is defined as
M(s, y) := sy −max i 6=y si
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
vmin = min x∈{x∈X | ||x−xi||2≤ ,∀xi∈Sm} v(x). (2)
vmin is the smallest instance-space margin of elements in the covering balls that contain training examples.

heading: 4 THEORETICAL INSTRUMENTS FOR EMPIRICAL STUDIES ON AR
text: 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 RL, 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.
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(Tx′′, 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 x′ − x 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 (CX )
k, and assumption 4.1 holds. If T is 0-adversarially robust (defined at definition 2), ≤ 0, and denote vmin the smallest IM margin in the covering balls that contain training examples (defined at definition 6), σimin the smallest singular values of weight matrices Wi, i = 1, . . . , L− 1 of a NN, {wi}i=1,...,|Y| the set of vectors made up with ith rows of WL (the last layer’s weight matrix), then given an i.i.d. training sample Sm = {zi = (xi, yi)}mi=1 drawn from Z , its generalization error GE(l ◦ T ) (defined at eq. (1)) satisfies that, for any η > 0, with probability at least 1− η
GE(lγ ◦ T ) ≤ max{0, 1− umin γ }+
√ 2 log(2)CkX
km +
2 log(1/η)
m (3)
where
umin = min y,ŷ∈Y,y 6=ŷ ||wy −wŷ||2 L−1∏ i=1 σiminvmin (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 umin 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 vmin. 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., umin, σimin. These studies aim to illuminate with empirical evidence on the phenomena that AR regularizes NNs, reduces GE gaps, but degrades test performance.2
Before 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 Il(x) be the activation g(Wlg(Wl−1 . . . g(W1x))) at layer l of x (c.f. definition of NNs at appendix C.2), then there exist n ∈ N sets of matrices {W qji }i=1...l, j = 1 . . . n, that each of the matrix W qj i is obtained by setting some rows of Wi to zero, and {qj}j=1...n are arbitrary distinctive symbols indexed by j that index W qj i , such that
||Il(x)− Il(x′)|| = n∑ j=1 ∫ ej sj ∣∣∣∣∣ ∣∣∣∣∣ l∏ i=1 W qj i dt(x− x ′) ∣∣∣∣∣ ∣∣∣∣∣
where s1 = 0, sj+1 = ej , en = 1, sj , ej ∈ [0, 1] — each [sj , ej ] 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 qji is obtained by setting rows of Wi to zero, the singular values of these induced matrices are intimately related to weight matrices Wi 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 IL−1(x) and the IL−1(x′) of an element x′ on the decision boundary, singular values of {Wi}i=1...L−1 determine the amplification/shrinkage of the IM x− x′.

heading: 5 EMPIRICAL STUDIES ON REGULARIZATION OF ADVERSARIAL ROBUSTNESS
text: 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.

heading: 5.1 ADVERSARIAL ROBUSTNESS EFFECTIVELY REGULARIZES NNS ON VARIOUS DATASETS
text: 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
2 Note that in the previous paragraph, though we identifies quantities umin and σimin 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.
adversarial robustness into NNs. The AR strength is characterized by the maximally allowed l∞ norm of adversarial examples that are used to train the NNs. Details on the technique to build adversarial robustness into NNs is given in appendix B.1.
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.

heading: 5.2 REFINED ANALYSIS THROUGH MARGINS AND SINGULAR VALUES
text: 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.

heading: 5.2.1 MARGINS THAT CONCENTRATE MORE AROUND ZERO LEAD TO REDUCED GE GAP
text: To study how GE gaps are reduced, theorem 4.1 suggests we first look at the margins of examples — a lower bound of margins is umin 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 the margin distributions of samples which are obtained by training ResNet-56 on CIFAR10 and CIFAR100 with increased AR strength (the same setting as for fig. 3). Applying the same network of ResNet-56 respectively on CIFAR-10 and CIFAR-100 of different learning difficulties creates learning settings of larger- and smaller-capacity NNs.
Concentration and reduced accuracy. In fig. 4, we can see that in both CIFAR10/100, the distributions of margins become more concentrated around zero as AR grows. The concentration moves the mode of margin distribution towards zero and more examples slightly across the decision boundaries, where the margins are zero, which explains the reduced accuracy.
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
losses on CIFAR10/100, Tiny-ImageNet, as shown in fig. 3b. The reduced GE gap results from the increased training losses, and decreased or less increased test losses.

heading: 5.2.2 AR MAKES NNS SMOOTHE PREDICTIONS W.R.T. INPUT PERTURABTIONS IN ALL DIRECTIONS
text: 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
∣∣∣∣∣∣∏li=1 W qji δxdt∣∣∣∣∣∣. Note that for each i, W qii is a matrix. By Cauchy interlacing law by row deletion (Chafai), the singular values of Wi, the weight matrix of layer i, determine the singular values of W qji . Thus, suppose l = 1, we have the change (measured in norm) induced by perturbation as ∑n j=1 ∫ ej sj
∣∣∣∣W qj1 δxdt∣∣∣∣. The singular values of W1 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 qj1 δxdt∣∣∣∣ (each of which is the exact form discussed in section 1.1) weighted by 1/(ej − sj). Similarly, for the case where l = 2 . . . L− 1, the singular values of Wl 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.

heading: APPENDICES

heading: A FURTHER RELATED WORKS
text: 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.

heading: B FURTHER EMPIRICAL STUDIES ON ADVERSARIAL ROBUSTNESS

heading: B.1 TECHNIQUE TO BUILD ADVERSARIAL ROBUSTNESS
text: 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.

heading: B.2 QUANTITATIVE ANALYSIS OF VARIANCE REDUCTION IN SINGULAR VALUES
text: 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 σ4i ) of singular values of layer i (of the NN trained) with AR strength 4 that is larger than that (denoted σ16i ) 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 − σ16i ) is 4.7465, and the average is 0.1158. For the second
groups, the summation ( ∑ i σ 16 i − σ4i ) 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.

heading: B.3 DISCREPANCY BETWEEN TRENDS OF LOSS AND ERROR RATE GAPS IN LARGE CAPACITY
text: 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 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.

heading: 1. On CIFAR10, the margin distribution of training sets not only concentrate more around zero, but
text: 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. 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 solutions — since 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.

heading: B.4 FURTHER EVIDENCE OF REGULARIZATION EFFECTS ON NNS WITH VARIED CAPACITY
text: 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 ||Wi||2
where {Wi}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.

heading: B.5 FURTHER EVIDENCE ON THE SMOOTHING EFFECT OF ADVERSARIAL ROBUSTNESS
text: 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.

heading: B.6 FURTHER EMPIRICAL STUDY ON USING FGSM IN ADVERSARIAL TRAINING TO BUILD ADVERSARIAL ROBUSTNESS
text: 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.
The phenomenon has been observed consistently in networks adversarially trained with FGSM on CIFAR10/100, as shown in fig. 9. Phenomenon in fig. 5a 5b is also reproduced consistently in fig. 10a 10b. Please refer to section 5.2.1 for the analysis of the results. Here we mainly present counterparts of the results analyzed there.
Adversarial robustness reduces the standard deviation of singular values of weight matrices in the network. In section 5.2.2, we find that for NNs with stronger adversarial robustness, the standard deviation of singular values of weight matrices is smaller in most layers. The phenomenon has been consistently observed in NNs trained with FGSM on CIFAR10/100, as shown in fig. 10c and 10d. Please refer to section 1.1 and section 5.2.2 for the analysis of the results. Here we mainly present counterparts of the results analyzed there..
In conclusion, all key empirical results have been consistently observed in NNs trained with FGSM.

heading: C PROOF OF THEOREM 4.1

heading: C.1 ALGORITHMIC ROBUSTNESS FRAMEWORK
text: 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 (·) : Zm 7→ R, if Z can be partitioned into K disjoint sets, denoted by C = {Ck}Kk=1, such that the following holds for all si = (xi, yi) ∈ Sm, z = (x, y) ∈ Z, Ck ∈ C:
∀si = (xi, yi) ∈ Ck,∀z = (x, y) ∈ Ck =⇒ |l(f(xi), yi)− l(f(x), y)| ≤ (Sm).
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 ∈ Sm and z ∈ Z are “close” (e.g., in the same partition Ck), 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
GE(fSm) ≤ (Sm) +M √ 2K log(2) + 2 log(1/η)
m . (5)
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 L2(R2), the square integrable function space defined on R2, it has a covering number N (X ; ρ, ) of (CX / )k (Verma, 2013), where CX 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.

heading: C.2 NEURAL NETWORKS
text: A NN is a map that takes an input x from the space X , and builds its output by recursively applying a linear map Wi followed by a pointwise non-linearity g:
xi = g(Wixi−1),
where i indexes the times of recursion, which is denoted as a layer in the community, i = 1, . . . , L, x0 = x, and g denotes the activation function. which is restricted to Rectifier Linear Unit (ReLU) (Glorot et al., 2011) or max pooling operator (Bécigneul, 2017) in this paper. To compactly summarize the operation of T , we denote
Tx = g(WLg(WL−1 . . . g(W1x))). (6)

heading: C.3 PROOF
text: Proof of lemma 4.1. By Theorem 3 in Sokolic et al. (2017), we have ||Il(x)− Il(x′)|| = ∣∣∣∣∣∣∣∣∫ 1
0
J(x− t(x′ − x))dt(x− x′) ∣∣∣∣∣∣∣∣ (7)
where J(x) denotes the Jacobian of Il(x) at x.
By lemma 3.2 in Jia et al. (2019), when we only have max pooling layers and ReLU as nonlinear layer in NNs, J(x) is a linear operator at a local region around x. For terminology concerning regions, we follow the definitions in Jia et al. (2019). More specifically, we have
J(x) = l∏ i=1 W xi
where W xi is the linear mapping (matrix) induced by J(x) at x. It is a matrix obtained by selectively setting certain rows of Wi to zero. For the more concrete form of W xi , refer to lemma 3.2 in Jia et al. (2019). In Jia et al. (2019), it is noted as W qi , where q is a region where x is in.
Suppose that from x to x′, the line segment x− x′ passes through regions {qj}j=1,...,n. The line segment is illustrated in fig. 2b as the boldest black line segment at the upper half of the figure. In the illustration, x− x′ passes through three regions, colored coded as gray, dark yellow, light blue respectively. The line segment is divided into three sub-segments. Suppose l(t) = x+ t(x′ − x). Then the three sub-segments can be represented by l(t) as l(s1) to l(e1), l(s2) to l(e2), and l(s3) to l(e3) respectively, as noted on the line segment in the illustration. Originally, the range of the integration in eq. (7) is from 0 to 1, representing the integration on the line segment l(0) to l(1) in the instance space. Now, since for each of these regions trespassed by the line segment, the Jacobian J(x) is a linear operator, denoted as W qji , the integration in eq. (7) from 0 to 1 can be decomposed as a summation of integration on segments l(s1) to l(e1) etc. In each of these integration, the Jacobian J(x) is the multiplication of linear matrices W qji , i.e., ∏l i=1 W qj i . Thus, eq. (7) can be written as
n∑ j=1 ∫ ej sj ∣∣∣∣∣ ∣∣∣∣∣ l∏ i=1 W qj i dt(x− x ′) ∣∣∣∣∣ ∣∣∣∣∣
where sj , ej denotes the start and end of the segment [sj , ej ] ⊂ [0, 1] of the segment [0, 1] that passes through the region qj .
In the cases that a linear operator is applied on the feature map Il(x) without any activation function, we can also obtain a similar conclusion. Actually, such cases are just degenerated cases of feature maps that have activation functions.
Corollary C.1. Given two elements x,x′, and Il(x) = Wlg(Wl−1 . . . g(W1x)), we have
||Il(x)− Il(x′)|| = n∑ j=1 ∫ ej sj ∣∣∣∣∣ ∣∣∣∣∣Wl l−1∏ i=1 W qj i dt(x− x ′) ∣∣∣∣∣ ∣∣∣∣∣
where symbols are defined similar as in lemma 4.1.
Now, we are ready to prove theorem C.1.
Proof of theorem C.1. Similar with the proof of theorem C.1, we partition space Z into the -cover of Z , which by assumption is a k-dimension manifold. Its covering number is upper bounded by CkX / k, denoting K = CkX / k, and Ĉi the ith covering ball. For how the covering ball is obtained from the -cover, refer to theorem 6 in Xu and Mannor (2012). We study the constraint/regularization that adversarial robustness imposes on the variation of the loss function. Since we only have - adversarial robustness, the radius of the covering balls is at most — this is why we use the same symbol. Beyond , adversarial robustness does not give information on the possible variation anymore. Let T ′ denotes the NN without the last layer.
First, we analyze the risk change in a covering ball Ci. The analysis is divided into two cases: 1 all training samples in Ci are classified correctly; 2) all training samples in Ci are classified wrong. Note that no other cases exist, for that the radius of Ci is restricted to be , and we work on -adversarial robust classifiers. It guarantees that all samples in a ball are classified as the same class. Thus, either all training samples are all classified correctly, or wrongly.
We first study case 1). Given any example z = (x, y) ∈ Ci, let ŷ = argmaxi 6=ywTi T ′x. Its ramp loss is
lγ(x, y) = max{0, 1− 1
γ (wy −wŷ)TT ′x}.
Note that within Ci, (wy −wŷ)TT ′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) := (wy −wŷ)TT ′x, and uimin = min∀x∈Ci u(x). We have
lγ(x, y) ≤ max{0, 1− uimin γ } ≤ max{0, 1− umin γ },
where umin 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) ∈ Ci, and any element z′ := (x′, y′) ∈ Ci, where Ci is the covering ball that covers x, we have
|lγ(x, y)− lγ(x′, y′)|
=|max{0, 1− u(x) γ } −max{0, 1− u(x
′)
γ }|
≤max{0, 1− umin γ }. (8)
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 (wy −wŷ)T L−1∏ i=1 W x−t(x−x′) i dt(x− x ′)
= ∫ 1 0 ∣∣∣∣∣(wy −wŷ)T L−1∏ i=1 W x−t(x−x′) i dt(x− x ′) ∣∣∣∣∣ (11) =
n∑ j=1 ∫ ej sj ∣∣∣∣∣(wy −wŷ)T L−1∏ i=1 W qj i dt(x− x ′) ∣∣∣∣∣ (12) ≥ min y,ŷ∈Y,y 6=ŷ ||wy −wŷ||2 L−1∏ i=1 σimin||x− x′||2 ∫ 1 0 dt (13)
≥ min y,ŷ∈Y,y 6=ŷ ||wy −wŷ||2 L−1∏ i=1 σimin||x− x′||2
where J(x) denotes the Jacobian of Il(x) at x. Equation (10) can be reached by Theorem 3 in Sokolic et al. (2017). Equation (11) can be reached because (wy −wŷ)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 Wl 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 x− x′ ⊥ N ((wy −wŷ)T ′). If the difference x′ − x satisfies x− x′ 6⊥ 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 x − x′ 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 σimin||x||2 (14)
where σimin is the smallest singular value of Wi. 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 (ej − sj) ∣∣∣∣∣(wy −wŷ)T L−1∏ i=1 W qj i (x− x ′) ∣∣∣∣∣ . Now we show that in each operand, x − x′ ⊥ N ((wy − wŷ)T ∏L−1 i=1 W qj i ). Denote Tqj as
N ((wy −wŷ)T ∏L−1 i=1 W qj i ). Suppose that it does not hold. Then we can decompose x− x′ into two components ∆1,∆2, where ∆1 ⊥ Tqj ,∆2 6⊥ Tqj . 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 x− x′ be orthogonal to all N (Tqj ). Thus, by the inequality eq. (14) earlier, we can arrive at eq. (13) — notice that wy − wŷ 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 Ci, let vimin be minx∈Ci v(x). Let vmin be the smallest v i min among all covering balls Ci that contain at least a training example. We have that
umin ≥ min y,ŷ∈Y,y 6=ŷ ||wy −wŷ||2 L−1∏ i=1 σiminvmin
Consequently, we can obtain an upper bound of eq. (8) parameterized on vmin, as follows
max{0, 1− umin γ } ≤ max{0, 1−
miny,ŷ∈Y,y 6=ŷ ||wy −wŷ||2 ∏L−1 i=1 σ i minvmin
γ }.
Notice that only because 0-adversarial robustness, we can guarantee that vmin is non-zero, thus the bound is influenced by AR.
Then, we study case 2), in which all training samples z ∈ Ci are classified wrong. In this case, for all z ∈ Ci, the ŷ given by ŷ = argmaxi 6=ywTi T ′x in the margin operator is the same, for that ŷ is the wrongly classified class. Its ramp loss is
lγ(x, y) = max{0, 1− 1
γ (wy −wŷ)TT ′x}.
Note that in the case 1), it is the y that stays fixed, while ŷ may differ from example to example; while in the case 2), it is the ŷ stays fixed, while y may differ.
Similarly, within Ci as required by adversarial robustness, (wy −wŷ)TT ′x ≤ 0, thus we always have 1− 1γ (wy −wŷ) TT ′x ≥ 1, implying
lγ(x, y) = 1.
Thus, ∀z = (x, y), z′ = (x′, y′) ∈ Ci
|lγ(x, y)− lγ(x′, y′)| = 0. (15)
Since only these two cases are possible, by eq. (8) and eq. (15), we have ∀z, z′ ∈ Ci
|lγ(x, y)− lγ(x′, y′)| ≤ max{0, 1− umin γ }. (16)
The rest follows the standard proof in algorithmic robust framework.
Let Ni be the set of index of points of examples that fall into Ci. Note that (|Ni|)i=1...K is an IDD multimonial random variable with parameters m and (|µ(Ci)|)i=1...K . Then
|R(l ◦ T )−Rm(l ◦ T )|
=| K∑ i=1 EZ∼µ[l(TX, Y )]µ(Ci)− 1 m m∑ i=1 l(Txi, yi)|
≤| K∑ i=1 EZ∼µ[l(TX, Y )] |Ni| m − 1 m m∑ i=1 l(Txi, yi)|
+ | K∑ i=1 EZ∼µ[l(TX, Y )]µ(Ci)− K∑ i=1 EZ∼µ[l(TX, Y )] |Ni| m |
≤| 1 m K∑ i=1 ∑ j∈Ni max z∈Ci |l(Tx, y)− l(Txj , yj)| (17)
+ |max z∈Z |l(Tx, y)| K∑ i=1 | |Ni| m − µ(Ci)||. (18)
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 √
log(2)2k+1CkX γkm + 2 log(1/η)m .
The proof is finished.
D IMPLEMENTATION DETAILS
We summarize the details of the experiments in this section. The experiments are run with PyTorch (Pfeiffer, 2017).

heading: D.1 DATASETS
text: CIFAR10/100. Each CIFAR dataset consists of 50, 000 training data and 10, 000 test data. CIFAR-10 and CIFAR-100 have 10 and 100 classes respectively. Our data augmentation follows the standard manner in Lee et al. (2015): during training, we zero-pad 4 pixels along each image side, and sample a 32 × 32 region cropped from the padded image or its horizontal flip; during testing, we use the original non-padded image.
Tiny-ImageNet. Tiny-ImageNet is a subset of ImageNet dataset, which contains 200 classes rather than 1, 000 classes. Each class has 500 training images and 50 validation images. Images in the Tiny-ImageNet dataset are of 64× 64 pixels, as opposed to 256× 256 in the full ImageNet set. The data augmentation is straightforward: an input image is 56× 56 randomly cropped from a resized image using the scale, aspect ratio augmentation as well as scale jittering. A single 56× 56 cropped image is used for testing.

heading: D.2 EXPERIMENTS IN SECTION 5.1
text: CIFAR10/100 Models and Training. The models for CIFAR10/100 are the same as the ones in appendix B.4, except that we do not use spectral normalization anymore. CIFAR100 has 100 output neurons instead of 10.
Tiny-ImageNet Model. For Tiny ImageNet dataset, we use 50-layered wide residual networks with 4 groups of residual layers and [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.
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.

heading: D.3 EXPERIMENTS IN APPENDIX B.4
text: 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.
Dropout layers are omitted as well. Following Sedghi et al. (2018), we clip the spectral norm every epoch rather than every iteration.
Training. The experiments on CIFAR10 datasets are based on a mini-batch size of 256 for 200 epochs. The learning rate starts at 0.05, and is divided by 10 at 100 and 150 epochs respectively. All experiments are trained on training set with stochastic gradient descent based on the momentum of 0.9.
Results. The data for fig. 6 are given in table 6.

Review summaries:
The paper presents new theory to develop understanding about why adversarially robust neural networks show lower test performance compared to their standard counterparts despite being more robust to perturbations in the data. The main hypothesis is that the degradation in performance in adversarially robust networks is due to many samples being concentrated around the decision boundary, which makes the network less confident about its decisions. The paper studies this hypothesis by deriving a bound on the generalization error based on the margin between the samples in the training set and the decision boundary. The paper then presents empirical demonstrations that aim to illustrate the theoretical findings. 

This paper focuses on analyzing the regularization of adversarial robustness (AR) on neural networks (NNs). They establish a generalization error (GE) bound characterizing the regularization of AR, and identify two quantities: margin distributions and singular values of NNs' weight matrices. With empirical studies, they show that AR is achieved by regularizing NNs towards less confident solutions and making feature space changes smoother uniformly in all directions, which prevents sudden change wrt perturbations but leads to performance degradation.