Title: THE EFFECT OF ADVERSARIAL TRAINING: A THEO-RETICAL CHARACTERIZATION

Abstract: It has widely shown that adversarial training (Madry et al., 2018) is effective in defending adversarial attack empirically. However, the theoretical understanding of the difference between the solution of adversarial training and that of standard training is limited. In this paper, we characterize the solution of adversarial training for linear classification problem for a full range of adversarial radius ε. Specifically, we show that if the data themselves are "ε-strongly linearly separable", adversarial training with radius smaller than ε converges to the hard margin solution of SVM with a faster rate than standard training. If the data themselves are not "ε-strongly linearly separable", we show that adversarial training with radius ε is stable to outliers while standard training is not. Moreover, we prove that the classifier returned by adversarial training with a large radius ε has low confidence in each data point. Experiments corroborate our theoretical finding well.

1. INTRODUCTION:

Despite the impressive performance of deep neural networks on various learning tasks, the widely existing adversarial examples (Goodfellow et al., 2014; Szegedy et al., 2017) has thwarted its application in the safety-sensitive scenarios (Kurakin et al., 2016; Chen et al., 2015) . A well trained neural network can be vulnerable to certain small adversarial perturbation added to the original data, despite the perturbations is almost imperceptible to human.

Adversarial training (Madry et al., 2018) is an effective method to train a robust deep neural network that can resist adversarial samples to some extent. However, the theoretical understanding of adversarial training is quite limited. In this paper, we try to unveil the mystery of adversarial training. Specifically, in this paper for adversarial training, we consider the attack in l 2 norm, i.e. the following objective

min θ 1 N N i=1 max x-x i 2 ≤ε (x, θ).

(1)

This is in contrast with the standard training objective min θ 1 N N i=1 (x, θ). To obtain a clear theoretical characterization, we focus on the linear classifier.

In fact, for linearly separable data, Soudry et al. (2017) ; Ji & Telgarsky (2018) have proven that the linear classifier trained by gradient descent (GD) with logistic loss converges to the hard margin solution of SVM with a rate of O((log t) -1 ). However, we find things become much different for adversarial training. We first prove that for "ε-strongly linearly separable" data (Definition 1), GD can find the hard margin classifier with a faster rate of O((log t) -(1+ε * ) ), with the same exponential tail loss used in Soudry et al. (2017) . Here ε * = (|S|ε(ε 1 -ε))/N , where ε 1 is the distance between the support vectors and the hard margin solution of SVM, and |S| is the number of support vectors corresponding to hard margin classifier. This result shows that we can find a robust solution much faster by adversarial training if the data themselves are more separable than the adversarial radius.

When the data are not ε-strongly linearly separable, adversarial training gives significantly different solutions from the standard training. To further illustration, we consider the following case, most of the data are ε-strongly linearly separable while there several outliers are not or even not linearly separable. Then the classifier returned by standard training is heavily affected by these outliers, since the classifier returned by standard training converges to the hard margin classifier while it can be sensitive to outliers. However, we can show the stability of adversarial training to outliers, i.e. the classifier returned by adversarial training is slightly affected by outliers. Next, we also show that adversarial training leads to a classifier with relatively lower confidence in each data point than that of standard training. We then give a formal characterization for this phenomenon under the case of a large ε. The low confidence in each training data naturally induces a high training loss. A simple generalization error bound informs the high loss on test set, which interprets the widely observed poor test performance of adversarial training.

1.1. RELATED WORK:

Plenty of work trying to obtain a large margin solution to promote model robustness. Cisse et al. (2017) ; Hein & Andriushchenko (2017) regularize the training with the Lipschitz constant of the model to enhance robustness. Another line of work (Elsayed et al., 2018; Lee et al., 2019a; Serra et al., 2018; Croce et al., 2019) uses a first order approximation to compute the margin of deep neural network, and then find a large margin solution by setting the approximation to be the optimization objective. However, none of these works come up with a theoretical guarantee.

Our paper is also related with Soudry et al. (2017) ; Ji & Telgarsky (2018) who prove that gradient descent with logistic loss converge to the hard margin classifier for linearly separable data but with a rate of O((log t) -1 ) or on non-linearly separable data with rate of O(log log t/ log t). Nacson et al. (2018) extend this result to stochastic gradient descent. Gunasekar et al. (2018) study the convergence under other optimization methods. Lyu & Li (2019) provides a similar result for the homogeneous neural networks. However, they all target the standard optimization problem rather than the adversarial training. Ilyas et al. (2019) studies adversarial training via the lens of robust/non-robust features. They claim that adversarial attacks are attributed to the presence of non-robust features and adversarial training can be viewed as explicitly preventing the classifier from learning useful but non-robust features. Their theory is presented under the parameter estimation framework, which is different from the conventional adversarial training. Moreover, they do not discuss the convergence direction of adversarial training.

2. NOTATIONS AND ASSUMPTIONS:

In this section, we introduce the notations and assumptions we used in this paper. We consider a binary classification problem.

Notations. Dataset is represented as {x i , y i } N i=1 , where x i ∈ R d and y i ∈ {-1, 1}. The loss function is represented by (•). • means l 2 norm in this paper. The objective of standard training can be represented as

EQUATION

where w ∈ R d is a linear classifier. Adversarial training has the objective of

EQUATION

)

where ε is the adversarial radius. An intuitive explanation of adversarial training is that it requires the classifier perform well in the ε-ball centered at each data x i . In this paper, w t is the iterate at step t of gradient descent (GD) under adversarial training. We use ŵ to represent the solution of SVM (8). Now, we give the definition of ε-strongly linearly separable data. Definition 1 (ε-strongly linearly separable). 1 The dataset is ε-strongly linearly separable, if there exists w * such that ∀x i , w * T y i x i > 0 and w * T y i x i > ε w * .

The ε-strongly linearly separable means there exists a linear classifier that does not only give a right prediction to each data point but also ensures all data are away from the linear classifier larger than ε. In addition, linearly separable refers to choosing ε = 0 in Definition 1. We now define confidence of classifier. Definition 2 (Confidence). For a given linear classifier w of binary classification problem, the logits is 1/(1 + e -w T xi ) and e -w T xi /(1 + e -w T xi ) for category 1 and -1. Then max{1/(1 + e -w T xi ), e -w T xi /(1 + e -w T xi )} is the confidence of w on data x i .

The confidence measures how confident the classifier is about the prediction. In the sequel, we use x i to represent y i x i for simplify the notations. We introduce the assumptions used in this paper. Assumption 1. The loss function (•)2 satisfies that ∀u, (u) > 0, (u) < 0, l (u) ≥ 0, lim u→∞ (u) = lim u→∞ (u) = 0, and the (u) has Lipschitz gradient.3 Assumption 2. The l(•) and l (•) have exponential tail, which means there exists some constant u 0 and

C 1 , C 2 satisfies that ∀u > u 0 , C 1 e -u ≤ l(u) ≤ C 2 e -u as well as l (u). 4 Assumption 3. The w T x i -ε w has the range of [c 1 , ∞) for each x i , where c 1 > -∞. w ≥ c 2 for some constant c 2 . 5 .

Due to the properties of loss function, the adversarial training objective (3) with radius ε has an explicit formula

EQUATION

The adversarial training objective equation 4 is optimized by the gradient descent, i.e.,

EQUATION

)

where η is the learning rate.

3. ADVERSARIAL TRAINING CONVERGES FASTER TO HARD MARGIN FOR ε-STRONGLY LINEARLY SEPARABLE DATA:

In this section, we theoretically characterize where adversarial training converges when the data themselves are ε-strongly linearly separable. We first have the following key lemma which ensures the loss of adversarial training with radius ε can converge to zero on ε-strongly linearly separable data. The proof of this lemma is delegated to Appendix A. Lemma 1. The adversarial training objective equation 4 is convex and L-smooth for some positive constant L. Then if the data are ε-strongly linearly separable (1), the iterates {w t } returned by GD under adversarial training satisfy 1): lim t→∞ L(w t ) = 0, 2): lim t→∞ w t = ∞. and 3):

lim t→∞ w T t x i -ε w t = ∞

The distance of x i away from linear classifier w t is |w T t x i |/ w t . Then, the convergence result in the Lemma 1 does not inform us the robustness of trained classifier. Fortunately, the results in Soudry et al. (2017) ; Ji & Telgarsky (2018) claim that the iterates of standard training updated by GD can converge to hard margin classifier with the rate of O((log t) -1 ). Now, we give the main result of this section. The conclusion is similar to Theorem 3 in Soudry et al. (2017) while the convergence is much sharper. Theorem 1. For any ε-strongly linearly separable data (Definition 1), and loss function (•) satisfies Assumption 1 and 2. If the Assumption 3 holds, then the gradient flow iterates w(t) ,

EQUATION

satisfies

EQUATION

for a large t. Here ŵ is the hard margin solution of SVM:

ŵ = arg min w∈R d w s.t. w T xi ≥ 1. (8)

h(t) is in the order of o(log t). Then

EQUATION

where ε * = |S|ε(ε1-ε)

N:

, {ε i } is the sorted distance of data away from the hard margin solution of SVM, and S = {i : ŵT x i = ε 1 ŵ }; |S| is the number of elements in set S. Finally, iterates {w t } of adversarial training updated by GD with step size η satisfies

EQUATION

for k ∈ N + . Then we can conclude

EQUATION

We give a brief discussion to hard margin solution of SVM. Since the dataset is ε-strongly linearly separable, by KKT condition, we have ε < 1/ ŵ which informs us all the distance between x i and ŵ are larger than ε. Then, we present that perturbations smaller than ε can be defended by ŵ. Hence, the linear classifier w t becomes robust for a large t, since it has the same direction with ŵ. We then conclude adversarial training on ε-strongly linearly separable data helps iterates {w t } converge to a robust solution with a fast rate. A detailed proof of this Theorem is delegated to Appendix C.

For the theorem, we have several remarks about the adversarial training on ε-strongly linearly separable data.

• Adversarial training converges to a robust solution, the same as standard training, with a faster rate. The acceleration is determined by the constant ε * = (|S|ε(ε 1 -ε))/N which related with the true margin ε 1 and the number of support vectors |S|. • Large proportion of support vectors |S|/N , and an appropriate choice of ε (ε 1 /2 is the best) increase the convergence rate.

We next study where adversarial training converges when the data are not ε-strongly linearly separable.

4. ADVERSARIAL TRAINING WHEN DATA ARE NOT ε-STRONGLY LINEARLY SEPARABLE:

It's hard to obtain the exact separability of data without verifying the hard margin solution of SVM before adversarial training. Hence, understanding adversarial training on non-ε-strongly linearly separable data is also crucial.

4.1. THE INFLUENCE OF OUTLIERS:

We consider the case that clean data are ε-strongly linearly separable but the whole data set is not ε-strongly linearly separable because of outliers. We investigate how the outliers affect standard training and adversarial training.

4.1.1. STANDARD TRAINING IS UNSTABLE TO OUTLIERS:

We now illustrate how standard training can be easily altered by outliers for both linearly and nonlinearly separable data.

As shown in Soudry et al. (2017) ; Ji & Telgarsky (2018) , gradient descent converges to the hard margin solution for the exponential loss and linear separable data. Although the hard margin solution is believed to be a reasonably good classifier, it has potential to be non-robust, if one can intentionally insert outliers to be support vectors. The following proposition presents that hard margin classifier somehow can be non-robust.

Proposition 1. For two linearly separable datasets {x 1 i } N1 i=1 and {x 2 i } N2 i=1 , let ŵ1 and ŵ2 be their hard margin classifier respectively. Then, the hard margin classifier ŵ of union dataset

{x 1 i } N1 i=1 {x 2 i } N2 i=1 satisfies ŵ ≥ max{ ŵ1 , ŵ2 }.

This proposition can be derived from the definition of hard margin classifier, which suggests that adding some extra outliers to dataset can easily effect the robustness of hard margin classifier, since ŵ ≥ max{ ŵ1 , ŵ2 } and one of w i can be extremely large. Hence, the non-robustness of hard margin classifier can be attributed to some outliers. We use the next example to illustrate it.

Example 1. Suppose a dataset x 1 i , 0 N1 i=1 is well linearly separable with large margin, which means the hard margin classifier ŵ1 has a small norm. We insert some outliers which have the form 0,

x 2 i , N2 i=1 and N 1 N 2 .

If the outlier is linearly separable with relatively small margin, the corresponding hard margin solution is ŵ2 , then we have ŵ1 ŵ2 .

We can show that hard margin classifier on the union dataset

EQUATION

)

This shows the distance between each x 1 i , 0 N1 i=1 and new hard margin classifier ( ŵ1 , ŵ2 ) become extremely small due to a few outliers 0,

x 2 i N2 i=1 .

This indicates the solution returned by standard training is somewhat very sensitive to a few outliers because outliers can easily alter the hard margin classifier.

We now give a more general description of outliers based on the understanding of Example 1. Given two datasets

{x 1 i } N1 i=1 and {x 2 i } N2 i=1 with N 1 , N 2 data respectively, where N 1 N 2 . {x 1 i } N1 i=1 them- selves are ε-strongly linearly separable , but {x 2 i } N2 i=1 are not. Then, dataset {x 2 i } N2

i=1 is considered as outliers. Outliers themselves can even be not linearly separable. We use the next example to illustrate another behavior of standard training to non-linearly separable outliers. Example 2. Dataset {(x 11 i ,

x 12 i )} N1 i=1 ∈ R d1+d2 is ε-strongly linearly separable but {(0, x 22 i )} N2 i=1 ∈ R d1+d2 is not linearly separable. Let S = span{x 12 1 , • • • , x 12 N1 } = span{x 22 1 , • • • , x 22 N2 }.

Without loss of generality, we assume {x 11 i } N1 i=1 themselves are linearly separable but the hard margin classifier of them ŵ11 has relatively small margin compared to the {x 12 i } N1 i=1 , i.e., ŵ11 ŵ12 , where ŵ12 is the hard margin classifier on {x 12 i } N1 i=16 .

The union datasets {(x 11 i ,

x 12 i )} N1 i=1 {(0, x 22 i )} N2 i=1 is not linearly separable because of the outliers set {(0, x 22 i )} N2 i=1 .

Even worse, we show in this case, the classifier returned by standard training can make the prediction most based on the useful but non-robust information {x 11 i } N1 i=1 (Ilyas et al., 2019) .

The reason is as follows. The outliers {(0, x 22 i )} N2 i=1 happens to be the "Strongly Convex Part" as in Theorem 4.1 of Ji & Telgarsky (2018) , then the iterates {w t } updated by gradient descent of standard training converge to a direction of the hard margin classifier ŵ11 of dataset

{Π S ⊥ (x 11 i , x 12 i )} N1 i=1 = {(x 11 i , 0)} N1 i=1

, where Π S ⊥ (•) is the projection operator of space S ⊥ . Then, the presence of outliers {(0, x 22 i )} N2 i=1 renders the classifier returned by standard training on union datasets with poor robustness while the true hard margin classifier on dataset {(x 11 i ,

x 12 i )} N1 i=1 is robust.

The two examples that standard training converges to non-robust solution at the presence of outliers also demonstrates that standard training can easily capture the "non-robust but useful information". The first is to classify outliers {(0, x 22 i )} N2 i=1 into correct category renders the classifier ( ŵ1 , ŵ2 ) to be non-robust. The second describes that the outliers mute the information from {(0,

x 12 i )} N1 i=1 for dataset {(x 11 i , x 12 i )} N1 i=1 .

Then, the classifier turns into a non-robust but useful classifiers.

4.1.2. ADVERSARIAL TRAINING IS STABLE TO OUTLIERS:

Now, we turn to the behavior of adversarial training on the above two examples. Lemma 1 shows that the iterates {w t } of adversarial training on ε-strongly linearly separable data updated by GD can satisfy lim t→∞ w t = ∞. But the non-ε-strongly linearly separability of data ensures there exists some x k i such that w T t x k i -ε w t ≤ 0 for each specific t. Hence, w t can not go to infinity, otherwise we end up with an infinite loss. This is the essential distinction caused by non-εstrongly linearly separability. Now, we give a formal analysis to the stability of adversarial training to outliers.

Due to Lemma 1, iterates of adversarial training updated by GD converge to a minimum w * . Then, let l w * T x k i -ε w * = p k i , we have

EQUATION

)

It gives

EQUATION

where

X k = (x k 1 , • • • , x k N k ) and p k = (p k 1 , • • • p k N k ).

This implies that the direction of vector w * is decided by a linear combination of data points. X k p k represents the contribution brought by

{x k i } N k i=1 .

When data are ε-strongly linearly separable, by Assumption 2, we see p k i /p k j = o(1) ( w t goes to infinity) for any support vector x k i and non-support vector x k j of w * / w * . Hence, the direction of w * is mostly decided by support vectors. This is consistent with the conclusion that hard margin solution of SVM ŵ satisfies (KKT condition) ŵ =

2 k=1 N k i=1 α k i x k i

, where α k i = 0 for nonsupport vectors. Then, hard margin classifier is only decided by the linear combination of support vectors, which could be potential instability of standard training to outliers, since outliers can easily alter support vectors.

However, things become different for non-ε-strongly linearly separable data. Since w t can not go to infinity, we have the relation p k i /p k j = O(1). Then the following inequality

EQUATION

informs us the stability of adversarial training to outliers, where λ min (A), λ max (A) are respectively the smallest and largest eigenvalue of matrix A. From equation 13, we see the direction of w * can be decided by both dataset {x 1 i } N1 i=1 and {x 2 i } N2 i=1 . Since p 1 i has the same scale with p 2 j for every i, j and N 1 N 2 , we see p 1 p 2 , then X 1 p 1 X 2 p 2 . Hence, equation 15 implies that X 2 p 2 has little contribution to the direction of w * . Thus, w * can not be the hard margin classifier on union dataset. In addition, w * is mostly decided by data {x 1 i } N1 i=1 which tells the stability of adversarial training to outliers.

We now provide a discussion to the stability of adversarial training via the lens of robust/non-robust but useful features proposed by Ilyas et al. (2019) . First, we quote the definition of non-robust but useful feature here. Definition 3 (non-robust but useful feature (Ilyas et al., 2019) ). For a given distribution (x, y), if

E (x,y) [y •f (x)] ≥ ρ for some ρ > 0, but E (x,y) inf δ ≤ε y • f (x + δ) ≤ 0, then f (•) is non-robust but useful feature.

The definition of robust feature can be generalized for f (•) with E (x,y) inf δ ≤ε y • f (x + δ) ≥ 0. We see the feature is defined by classifier f (•) which is w for linear case. Then, the hard margin solution of SVM ŵ1 , ŵ2 for {x 1 i } N1 i=1 and {x 2 i } N2 i=1 in Example 1 and 2 are respectively robust feature and non-robust feature. Further more, let w * be the classifier (feature) captured by adversarial training. We note that w * being stable to outliers means adversarial training can prevent the classifier capture information from non-robust but useful features in sharp contrast with standard training. This interprets the conclusion in Ilyas et al. (2019) while they only empirically verify it.

We can also understand other scenarios from equation 15 that are not limited to N 1 N 2 . If N 1 ≈ N 2 , we see adversarial training can preserve a part of information from robust features. Moreover, N 2 N 1 means that most features are non-robust, and then adversarial training is also helpless.

4.2. CONFIDENCE OF ADVERSARIAL TRAINING:

In this subsection, we give a characterization to the confidence of classifier returned by adversarial training where data is not ε-strongly linearly separable. As shown in Section 4.1.2, w t converges to some constant when data is not ε-strongly linearly separable. According to Definition 2, the confidence of classifier is decided by |w T t x i | on each x i . Then, a bounded w t corresponds to a relatively low confidence in each x i .

To give a formal description to the confidence of w t , we discuss an extremely large ε ≥ 1 2 max i,j x i -x j , which means each ε-ball centered at x i has overlap with each other. For a x i , larger |w * T x i | corresponds with higher prediction confidence. For a given dataset {x i } N i=1 , let N 1 , N 2 respectively be the number of data in each category and x k,i represents the data from the k-th category. Then we have following theorem descriping the confidence of classifier.

Theorem 2. Let l(u) = e -u , for classifier w * returned by adversarial training on non-linearly separable data, |w * T x k,i | is either smaller than ε w * or satisfies

EQUATION

for k = k.

Our results also applies to l(•) discussed in this paper. A more explicit upper bound for those w * T x k,i ≥ ε w * is referred to equation 56. We notice that w * is bounded on non-ε-strongly linearly separable data. Then, this theorem implies that |w * T x i | on each x i can not be extremely large. Hence, a relatively low confidence in each x i . A detailed proof of this Theorem is delegated to Appendix D. Here we use ε ≥ 1 2 max i,j x i -x j is out of simplicity, a large ε for adversarial training can also correspond to a similar result.

Theorem 2 informs the training loss of classifier w * is at a relatively high level. Then, a simple generalization error bound (Vapnik, 1995) can tell that w * can also end up with a high error on test data. This is an interpretation to the model trained by adversarial training always face a poor test accuracy (Madry et al., 2018) .

5. EMPIRICALLY STUDY:

In this section, we compare adversarial training with standard training via linear classifier for two scenarios, i.e., ε-strongly linearly separable data and non-ε-strongly linearly separable data. All experiments are conducted with loss function (u) = log (1 + e -u ), and the update rule is GD with learning rate 0.01.

5.1. EXPERIMENTS ON ε-STRONGLY LINEARLY SEPARABLE DATA:

We first conduct a series of simulations to verify our conclusion on ε-strongly linearly separable data. The dataset includes support and non-support vectors. We generate non-support vectors

{x i } N i=1 ∼ N (y i • 2 • 1 2 , 0.3 • I 2 ) and support vectors on the 1 T 2 x i = y i • 2.

If there exists at least one support vector in each category, the hard margin solution of SVM ŵ is 1 2 . See Figure 1 for an example. The distance of support vectors away from the hard margin classifier is √ 2. Hence, the data are at most √ 2-linearly separable. We respectively verify our conclusions in Theorem 1 of the convergence rate, support vector number |S| and adversarial radius ε. The "margin gap" in Figure 2 means distance between the direction of iterates w t / w t and hard margin solution of SVM 1 2 / √ 2. In Figure 2 , the label, for example "Adv: 2500 support 2500 non support: 0.1 varepsilon" means adversarial training with ε = 0.1 on dataset with 2500 support vectors and 2500 non-support vectors in each category. From the results, we see that adversarial training indeed accelerates convergence rate of w t / w t . On the other hand, both adversarial training and standard training can benefit from the number of support vectors. Finally, as we claimed in Theorem 1, the best adversarial radius ε is ε 1 /2 which is √ 2/2 here.

5.2. EXPERIMENTS ON NON-ε-STRONGLY LINEARLY SEPARABLE DATA:

In this subsection, we conduct experiments on linearly separable (but non-ε-strongly linearly separable) and non-linearly separable data. More extra experiments can be referred to Appendix E.

We first discuss the stability of adversarial training to outliers on linearly separable data corresponding to Example 1. We generate {(x

1 i , 0 2 )} 10000 i=1 ∼ (N (y i • 2 • 1 2 , 0.3 • I 2 ), 0 2 ) and {(0 2 , x 2 i )} 100 i=1 ∼ (0 2 , N (y i • 0.5 • 1 2 , 0.1 • I 2 )).

The number of the two datasets in each category are 5000 and 50. The dataset {(0 2 , x 2 i )} 100 i=1 is linearly separable while non-ε-strongly linearly separable for ε = 1.5. {(x 1 i , 0 2 )} 10000 i=1 is ε-strongly linearly separable for ε = 1.5. {(0 2 , x 2 i )} 100 i=1 can be viewed as outliers. Then, we compare the stability of adversarial training and standard training conducted on the union dataset to outliers. The adversarial radius ε is 1.5. Detailed results can be referred to Figure 3a . 2 max i,j x i -x j . The y-axis is number of data.

For linearly separable data, the solid lines in Figure 3a are the norm of iterates returned by adversarial training and standard training. The dash lines in Figure 3a , for example, "Adv-sep/whole" means the ratio between the norm of classifier decided by the ε-strongly linearly separable part that is the first two dimensions of iterates and whole norm of iterates ( w 1 / w , where w ∈ R 4 = (w 1 , w 2 ) ∈ R 2+2 ). The first and the last two dimensions of iterates are with respect to robust and non-robust features. We have two observations for adversarial training, first, the norm of iterates can converge to some constant rather than infinity. Second, The direction of iterates is mostly decided by {(x 1 i , 0 2 )} 10000 i=1 , since the "Adv-sep/whole" can converge to 1 as the iterate steps growing up. However, we have an opposite observation for standard training, which means the direction of classifier obtained by standard training is easily effected by some outliers {(0 2 , x 2 i )} 100 i=1 . Then, we present the results on non-linearly separable data with respect to Example 2, we generate 5000 {(x 11 i ,

x 12 i )} 10000 i=1 ∼ (N (y i • 0.5 • 1 2 , 0.1 • I 2 ), N (y i • 2 • 1 2 , 0.3 • I 2 )) and 50 {(0 2 , x 2 i )} 100 i=1 ∼ (0 2 , N (-y i • 0.5 • 1 2 , 0.5 • I 2 )) in each category.

Here {(0 2 , x 2 i )} 100 i=1 is the source of non-linearly separability. {x 12 i } 10000 i=1 corresponds with a robust hard margin classifier while {x 11 i } 10000 i=1 is not. {(0 2 , x 2 i )} 100 i=1 can be viewed as outliers. We conduct adversarial training with ε = 0.7. The results can be referred to Figure 3 .

Figure 3b refers to non-linearly separable data, where the solid lines in it are also the norm of iterates. The first and the last two dimensions of iterates are respectively decided by the "useful but non-robust" part and "robust" part. The non-linearly separability is from the last two dimensions of data brought by outliers {(0 2 , x 2 i )} 100 i=1 . The dash lines in Figure 3b , for example, "Adv:sep-nrob" and "Adv-non sep-rob" are respectively the proportion in norm for the norm of the first and the last two dimensions of iterates ( w 1 / w and w 2 / w , where w ∈ R 4 = (w 1 , w 2 ) ∈ R 2+2 ).

We see standard training can easily capture the information from "useful but non-robust" (first two dimensions) part while the information from the "robust" part (last two dimensions) is muted attributes to outliers {(0 2 , x2 i )} 100 i=1 . But adversarial training can oppositely capture the information from "mostly robust" part.

Finally, we see the confidence of the classifier obtained by adversarial training with ε ≥ 1 2 max i,j x i -x j . We generate 5000 samples {x i } 10000 i=1 ∼ N (±0.5 • 1 2 , 0.1 • I 2 ) in each category. The data are linearly separable but non-ε-strongly linearly separable for ε = 1, besides that, 1 ≥ 1 2 max i,j x i -x j . We compare the confidence in each data point for classifiers returned by adversarial training with ε = 1 and standard training. The distributions of confidence via classifiers in data can be referred to Figure 4 . We see the classifier obtained by adversarial training corresponds with nearly 50% confidence in all data. However, the confidence of classifier returned by standard training is almost 100% in all data. Hence, a large ε for adversarial training can hurt the prediction confidence of classifier.

6. CONCLUSION:

In this paper, we give a theoretical characterization to adversarial training for linear classifiers under various settings. We conclude that on ε-strongly linearly separable data, adversarial training helps iterates converge to the hard margin classifier with a rapid rate compared with standard training. It means iterates of adversarial training can be robust with less update steps. Furthermore, we characterize the adversarial training on non-ε-strongly linearly separable data. We show both theoretically and empirically that adversarial training can be more stable to the outliers of the dataset but standard training is not. Finally, we discuss the confidence of the classifier obtained by adversarial training. We prove that under the condition of ε ≥ 1

A PROOF OF LEMMA 1:

Proof. We first give convexity to the adversarial training objective. For any two w 1 , w 2 , and 0 ≤ λ ≤ 1, by the convexity and monotone decreasing property of (•), we have

EQUATION

which implies the convexity of adversarial training objective. On the other hand, if u T ∇ 2 L(w)u can be bounded by L u 2 for some L, then L(w) is L-smooth. We see that

EQUATION

Then, u T ∇ 2 L(w)u can be divided into two parts, we respectively compute them

EQUATION

)

Here X is matrix

(x T 1 , • • • , x T N )

T and λ max X T X is the largest eigenvalue of X T X. On the other hand, according to Assumption 3,

EQUATION

)

Combining the two above equations, we conclude that largest eigenvalue of ∇ 2 L(w) is bounded for some constant, which result in the L-smoothness of adversarial training objective. It's a well known (Boyd & Vandenberghe, 2004 ) that for a convex and L-smooth function f (•), GD with step size η = 1 L will ensure the iterates {x t } satisfies f (x t ) -f (x * ) ≤ O 1 t . Since the adversarial training loss goes to zero only if w T t x i -ε w t goes to infinity for each x i . It reveals our two conclusions lim t→∞ w t = ∞ and lim t→∞ w T t x i -ε w t = ∞.

B ORDER OF NORM:

In this section we give the order of w(t) on ε-strongly linearly separable data, which is highly related to the convergence rate of w(t) w(t) -ŵ ŵ . Our proof is based on the gradient flow, we first bound the difference between flow iterates w(t) and w t .

Lemma 2. Let w t be the iterates updated by GD equation 5, then for dw(t) dt = -∇L(w(t)), we have

EQUATION

)

Proof. Let

EQUATION

)

Then by Lipschitz gradient of L(•), we see

EQUATION

)

Then we have

EQUATION

for w(0) = w 0 , which results in the conclusion.

Before proving the Theorem 1, we give a lemma to illustrate that w(t) will converge to the direction of ŵ. Lemma 3. There exists a t 0 , for t > t 0 , we have

EQUATION

for some ρ(t) and h(t). Here ρ(t) goes to infinity and h(t) is in the order of o(ρ(t)).

Proof. Let

EQUATION

r(t) = o ( w(t) ) will implies the conclusion. Since (•) has exponential tail Assumption 2, there exists a t 0 , for t > t 0 , we have

EQUATION

Then, we see

EQUATION

where ŵ is the hard margin classifier and ε is the distance between support vectors and ŵ. Here we use the relationship that ze -z ≤ 1 for any z and w(t) T r(t) ≥ 0. Since

EQUATION

and r(t) T ŵ ≤ 0, we have

d dt r(t) ≤ -CN r(t) T ŵ r(t) w(t) ŵ exp (-(ε1 -ε) w(t) ) ≤ CN w(t) exp (-(ε1 -ε) w(t) ) . (30)

Similar to Theorem 3 in Su et al. (2015) , by exponential tail of l(•) Assumption 2, we have

EQUATION

for some constant C 1 and any x i . Then we see

EQUATION

On the other hand, by the definition of hard margin classifier and Lemma 1, there exists x i such that w(t) T x i ≤ ε 1 w(t) . Combining this and equation 32, we have

EQUATION

Plugging this into equation 30, and we see that there exists a t 1 such that 1 2 log t ≥ log N ŵ-w0

C1:

, then

EQUATION

for t ≥ t 0 ∧ t 1 . Combining these, we conclude that r(t) is in the order of o( w(t) ).

Next, we use a lemma to illustrate the explicit order of ρ(t)

Lemma 4. ρ(t) in Lemma 3 is on the scale of log t ε1-ε , where {ε i } is the sorted distance of {x i } N i=1 to hard margin solution of SVM ŵ.

Proof. From Lemma 3 and 3, we have

EQUATION

where ρ(t) → ∞ and h(t) = o(ρ(t)). Specifically, the h(t) can be chosen to be orthogonal with ŵ, otherwise we can use a decomposition in a direct sum. For w(t) , we have

EQUATION

On the other hand, for t large enough,

EQUATION

for some constant C 1 , C 2 . Since ρ(t) goes to infinity and h(t) = o(ρ(t)), the derivation of

h(t) 2 ρ(t)+ √ ρ(t) 2 + h(t) 2 will o(ρ (t))

. Similar to equation 37, we can get the lower bound of d dt w(t) . In summary, we have

EQUATION

for constant some C 3 . Hence we can conclude that

EQUATION

for some constant C 4 , C 5 . It results in ρ(t) = O(log t).

We have proven that w(t) will converge to the direction of ŵ. Now, we will show w(t) will have the same support vector with ŵ when t is large. It's a key fact of proving Theorem 1. Lemma 5. There exists t 0 such that w(t) will have the same support vectors with ŵ for t > t 0 .

Proof. Let S = {i : ŵT

EQUATION

Since x i is the support vector of ŵ,

ŵT ŵ (x i -x j ) > 0. Then, h(t) = o(ρ(t)) shows that w(t) T w(t) (x i -x j ) ≤ 0 for a large t.

Then we get the conclusion.

C PROOF OF THEOREM 1:

In this section, we give a fully characterization to the proof of Theorem 1.

Restate of Theorem 1. For any ε-strongly linearly separable data (Definition 1), and loss function (•) satisfies Assumption 1 and 2. If the Assumption 3 holds, then the gradient flow iterates w(t) ,

EQUATION

satisfies

EQUATION

for a large t. Here ŵ is the hard margin solution of SVM:

EQUATION

h(t) is in the order of o(log t). Then

EQUATION

where ε * = |S|ε(ε1-ε)

, {ε i } is the sorted distance of data away from the hard margin solution of SVM, and S = {i : ŵT x i = ε 1 ŵ }; |S| is the number of elements in set S. Finally, iterates {w t } of adversarial training updated by GD with step size η will satisfy

EQUATION

for k ∈ N + . Then we can conclude

EQUATION

Proof. Let w(t) = ρ(t) ŵ ŵ + h(t). Denoting the support vectors set by S, S = {i : ŵT x i = ε 1 ŵ }. By the exponential tail of (u) (Assumption 2), there exists a t 0 , for t > t 0 , we have

EQUATION

7 Here we use a fact that x T i h(t) ≤ 0 for i ∈ S, due to ŵ is the hard margin classifier. In addition,

EQUATION

)

With this, we can choose a t 0 such that

EQUATION

for t > t 0 . This concludes the equation equation 47. Let h(t) x i be C(t), we can first derive that h(t) will converge to zero, then C(t) can be close to zero. By Gronwall's inequality, we have

EQUATION

C(t) can be arbitrary small when t > t 0 . Plugging this into equation 50, and combining Lemma 4, we have

EQUATION

where ε * = |S|ε(ε1-ε)

. Since we have then we see

EQUATION

w(t) w(t) - ŵ ŵ ≤   1 - ρ(t) ρ(t) + h(t) 2 ρ(t)   + h(t) ρ(t) + h(t) 2 ρ(t) = h(t) 2 ρ(t) 2 + h(t) 2 + h(t) ρ(t) + h(t) 2 ρ(t) = O (log) -(1+ε * ) (53) when t goes to infinity. Since h(t) ≤ O(log t) -ε * , for ε * = |S|ε(ε1-ε) N .

Combining Lemma 2, we can get the conclusion.

D PROOF OF THEOREM 2:

Proof. The x k,i will either satisfies |w * T x k,i | ≤ ε w * nor |w * T x k,i | ≥ ε w * . We know the first inequality represents the distance between x k,i and w * is smaller than ε. Then for w * T x k,i ≥ ε w * , due to ε ≥ 1 2 max i,j x k,i -x k ,j for any i, j, there exists x k ,j ∈ B 2 (x k ,j , ε) B 2 (x k,i , ε) with k , k = 1, 2 and k = k. By triangle inequality, the distance between x k ,j and w * is smaller than

w * T x k,i

w * -ε. Since x k ,j locates in different category with x k,i , by the monotone decreasing property of (•), we have Hence we have

EQUATION

EQUATION

Then, we have

EQUATION

if w * can correctly predict a point far from margin larger than ε in each category, for those w * T x k,i ≥ ε w * due to w * is minimum, then L(w * ) ≤ L(0). On the other hand, for w * T x k,i ≤ -ε w * , we can immediately derive

EQUATION

by triangle inequality where w * T x k ,j ≥ 0. Then we get the conclusion.

E EXTRA EXPERIMENTS:

E.1 ADVERSARIAL TRAINING IN l p SPACE

Our conclusions are obtained for adversarial training in l 2 space while it can be conducted in a more general l p space (Goodfellow et al., 2014; Madry et al., 2018) . It is meaningful to verify whether these conclusions are still hold in l p space. Hence, we extend our experiments to l p space.

The adversarial training objective within linear classifier can be formulated as

EQUATION

in l p space, where • p is l p norm. It has an explicit formulation

EQUATION

where 1 p + 1 q = 1. We conduct experiments for p = 4 and p = ∞. We empirically verify that adversarial training in l p space helps accelerating the convergence to hard margin solution of SVM on ε-strongly linearly separable data. Besides that, adversarial training can benefit from more support vectors and an appropriate adversarial radius ε. For non-ε-strongly linearly separable data, we try to validate that adversarial training in l p space is stable to outliers while it will obtain a classifier with low confidence on each data. All the experiments we conducted here are following the settings in Section 5, expect for the p are respectively chosen as 4 and ∞.

In addition, we should notice that the distance between support vectors locate in 1 T d x = ±d and hard margin classifier 1 d in l p space is d 1 d q . Hence we should adjust the adversarial radius ε for different p.

We first verify the conclusion for ε-strongly linearly separable data. The results for p = 4 and p = ∞ can be respectively referred to Figure 5 and 6 . Noticing that the distance between support vectors and hard margin solution of SVM is d 1 d q = d 1 p . Then for p = 4, p = ∞ and d = 2, we have 2 1 4 ≈ 1.18, 2 0 = 1. From the results, we see that an appropriate adversarial radius (ε = ε 1 /2) and more support vectors are helpful for adversarial training even in l p space. Now, we pay our attention to non-ε-strongly linearly separable data. We respectively verify our conclusions about stability and confidence of adversarial training. The experimental settings are again same with Section 5. The results can be referred to Figure 7 and 8 . We see that our conclusions are still hold in l p space, i.e. classifier obtained by adversarial training is stable to outliers and the confidence of it will consist keep in a low level for a large ε.

As a matter of fact, we can generalize our theoretical results to l p space by following the methods in this paper. The inner product •, • of linear classifier is derived from • 2 while l 2 is a Hilbert space, but l p space is not. The inner product we used does not math the l p space. Hence, we need adding some extra bounded conditions to extend our conclusions to l p space. 2019) suggest that over-parameterized neural networks of sufficient width (or infinite width) evolve as linear models with Neural Tangent Kernel (NTK). Hence our conclusions can somehow represent the performance of adversarial training for neural network models. In this subsection, we try to empirically verify our conclusions about adversarial training within neural network model. We use CIFAR10 (Krizhevsky et al., 2012) to conduct our experiments. CIFAR10 is a dataset with 10 categories. To simplify the experiments, we only keep the first two categories, which turns the experiments into binary classification problem. The model we used for adversarial training is ResNet20 (He et al., 2015) , which is a CNN with 20 layers. The experiments are conducted in l 2 and l ∞ space.

Since we can not compute the exact distance between data and classifier, we use the loss on training data8 with perturbation to represent the robustness of trained model. The perturbations are founded by running 10 steps projected gradient descent (PGD). We handle adversarial training by following the settings in Madry et al. (2018) . We use PGD to find the arg max x: x-xi ≤ε (x, θ) for each x i . The steps of PGD is 10 for each x i . All the models are trained by stochastic gradient descent with 0.1 learning rate and 0.9 momentum parameter for 100 epochs. The loss function is set to be cross entropy.

We first validate our conclusions for ε-strongly linearly separable data. Since neural network is not a linear model, it is hard to construct extra support vectors like in Section 5. Hence, we can only verify our conclusion that iterates of adversarial training converge faster to a robust solution, and it will benefit from an appropriate choice of adversarial radius ε. To compare the influence of ε, we choose ε = 0.25, 1.0, 2.0 in l 2 space and ε = 2/255, 8/255, 16/255 in l ∞ space. The size of perturbations are from Madry et al. (2018) . Besides that, the perturbations on training set9 to verify the robustness of trained model are 1.0 and 8/255 respectively in l 2 space and l ∞ space. The experimental results in l 2 and l ∞ space can be referred to Figure 9a 10 and 10a. The label of curves, for example, "Adv: 0.25 varepsilon" means adversarial training with ε = 0.25. From the figures, we see that the models returned by adversarial training with ε = 1 and ε = 8/255 are respectively the most robust in l 2 and l ∞ space. Hence, the conclusion that adversarial training can benefit from an appropriate choice of ε also holds for neural network.

Then, for non-ε-strongly linearly separable data, we respectively discuss the influence of outliers and a large ε. First, we construct 50 outliers {x i } 100 i=1 ∼ N (±0.078125 • 1 32×32×3 , 0.045 • I 32×32×3 ) in each category in both l 2 and l ∞ space. The influence of outliers for adversarial training in l 2 and l ∞ space can be respectively referred to Figure 9a and 10a . "Adv with outliers: 0.25 varepsilon" means adversarial training with outliers added into dataset and ε = 0.25. From the results, we see that outliers will barely effect the performance of adversarial training. Hence, we can conclude that adversarial training is still stable to outliers, even the model is neural network. On the other hand, we respectively choose ε equal to 4 and 32/255 in l 2 and l ∞ space to verify the confidence of classifier returned by adversarial training. The distributions of confidence via adversarial training in l 2 and l ∞ space can be respectively referred to Figure 9b and 10b . The results reveal that the confidence of neural network trained by adversarial training with large ε is at a fairly low level in each data.

To summary, although our conclusion about adversarial training are derived from linear classifier, the empirically results suggest it can be somehow extended to the case of neural networks. Thus, a theoretical exploration for neural network is crucial in the future work.

:

Please notice that ε-strongly linearly separable is a stronger condition compared with linearly separable. It distinguishes with the separability under soft margin which allows some w * T yixi < 0 but w * T yixi > ε w * .

The loss is set to be positive, differentiable, monotonically decreasing convex function. Lots of general used loss functions are satisfied, such as e -u , log (1 + e -u ) etc.

It means that | (u) -(v)| ≤ L|u -v| for some positive constant L.

Lots of loss functions we used such as log (1 + e -u ), e -u are satisfied with this assumption.

This assumption can be attained by re-scale the norm of w if necessary.

The hard margin classifier of {(x 11 i , x 12 i )} N 1 i=1 ŵ1 satisfies ŵ1 ≤ min{ ŵ11 , ŵ12 } which leads to a even more robust solution.

max i,j x i -x j , the confidence of classifier obtained by adversarial training keeps in a low level. This reveals that a large ε for adversarial training is not a wise choice.

Here we hide the constant C in the last inequality, which is decided by loss function l(•). C will usually smaller than 1 in fact.

Here we only focus on training data because we do not discuss the generalization of model obtained by adversarial training.

We should highlight that the perturbations are recalculated after each epoch of training.

We only list the results of adversarial leaning, because the loss on data with perturbation of standard training will not converge (always larger than 2.0).

Figures and Tables:

(a) Dataset with 5000 support vectors in each category. (b) Dataset with 2500 support vectors and 2500 non-support vectors in each category. (c) Dataset with 1 support vector and 4999 non-support vectors in each category.

Figure 1: Three types of datasets.

(a) Adversarial training with different ε. (b) Adversarial training with different number of support vectors. (c) Standard training with different number of support vectors

Figure 2: Gap between the direction of iterates and direction of hard margin classifier.

(a) Non-ε-strongly linearly separable but linearly separable data.(b) Non-linearly separable data.

Figure 3: Adversarial and standard training on non-ε-strongly linearly separable but linearly separable data and non-linearly separable data.

Figure 4: The confidence distributions of adversarial training and standard training when data are linearly separable but ε ≥ 12 max i,j x i -x j . The y-axis is number of data.

(a) Adversarial training with different ε. (b) Adversarial training with different number of support vectors.

Figure 5: Gap between the direction of iterates and direction of hard margin classifier in l 4 space.

Figure 6: Gap between the direction of iterates and direction of hard margin classifier in l ∞ space.

Figure 7: Adversarial training in l 4 space. Outliers are added into dataset of the first two subfigure. The third subfigure is confidence distribution for adversarial training when data are linearly separable but ε ≥ 12 max i,j x i -x j . The y-axis in the third pictures is number of data.

ADVERSARIAL TRAINING FOR NEURAL NETWORK Our conclusions are derived from linear classifier, but Du et al. (2019); Jacot et al. (2018); Lee et al. (2019b); Arora et al. (

(a) Adversarial training with different ε for outliers exist or not. (b) Frequency of confidence for data point under adversarial training with an extremely large ε.

Figure 9: Performance of adversarial training in l 2 space

Figure 10: Performance of adversarial training in l ∞ space

Peer review (iclr2020):
The aim of this paper is to provide a theoretical analysis of adversarial training under the linear classification setting. The main result states that, under many technical assumptions, adversarial training using gradient descent may converge to the hard margin SVM classifier with a fast rate. Here *fast* is not the standard 1/T fast rates but, rather, a rate of o(1/log T) (in comparison to recent results that looked into the convergence of gradient descent with logistic loss to the hard-margin SVM solution). Overall, the paper is not recommended for publication for many reasons. First, the notation used is sometimes imprecise and in some cases it is entirely wrong. For example, the authors decided to use x_i to replace the product y _i x_i in order to *simplify* notation. This makes things really hard to follow. The authors need to use a different symbol, such as z to stand for the product yx. Second, some equations do not appear to be correctly typed (e.g. in Page 1, standard learning should have xi not x). Third, the authors use epsilon to denote two different things (one for the definition of linearly separable data and one for the robustness radius), and so on. Second, the paper needs to be proof-read. It has a lot of typos and grammatical errors that make sentences difficult to understand. Examples include: - *while there several outliers are not or even not linearly separable*, - *a simple generalization error bound informs the high loss on test set* Third, some of the mathematical results do not make sense. For example, Definition 1 has two conditions, the first one is immediately satisfied once the second condition is satisfied, so why both? Also, in Proposition 1, the authors should mention that both sets are subsets of a linearly separable superset. In that case, the conclusion of Proposition 1 is obvious. Definitely, if data are linearly separable, then the hard margin will shrink as more examples are added (it cannot increase by definition of *maximum* margin). Moreover, in Example 1, the authors conclude with an inequality of norms and I don*t see how this follows from the description of the example. The example is generic and there is nothing that indicates one norm would be larger than the other. Forth, the authors make many assumptions about the loss without mentioning one example that satisfies them. In fact, the loss function they used later in the experiments violates Assumption 2. Some additional comments: - How did the authors arrive at Eq 4? I don*t see how this follows from the assumptions. Can you please elaborate? - I am not aware of any book written by Vapnik in 1995 called *Convex Optimization*. I think the authors meant the SVM paper. Given all of these issues and the fact that the main result is incremental and holds under a very limited setting (homogenous linear classifiers under a strong separability assumption) and relies on very strong assumptions about the loss function that may not be achievable to begin with, I do not recommend acceptance. =========== #Post Rebuttal Remarks Regarding the rate of convergence, just to be clear, I was only clarifying what the term *fast* meant in the paper, not complaining. So, this did not affect my score. The notation issues need to be fixed and the authors need to ensure that mathematical equations are written precisely, as stated in my review. Thanks for clarifying the issue about the loss functions. I agree that the example they mentioned satisfy it but it is not a common loss used in practice.