Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 l2 norm, i.e. the following objective
min θ
1
N N∑ i=1 max ‖x−xi‖2≤ε `(x,θ). (1)
This is in contrast with the standard training objective minθ 1N ∑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.

heading: 1.1 RELATED WORK
text: 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.

heading: 2 NOTATIONS AND ASSUMPTIONS
text: 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 {xi, yi}Ni=1, where xi ∈ Rd and yi ∈ {−1, 1}. The loss function is represented by `(·). ‖ · ‖ means l2 norm in this paper. The objective of standard training can be represented as
L0(w) = 1
N N∑ i=1 `(wT yixi), (2)
where w ∈ Rd is a linear classifier. Adversarial training has the objective of
L(w) = 1 N N∑ i=1 max ‖x−xi‖≤ε `(wT yix), (3)
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 xi. In this paper, wt is the iterate at step t of gradient descent (GD) under adversarial training. We use ŵ 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 ∀xi,w∗T yixi > 0 and w∗T yixi > ε‖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
1Please 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∗‖.
ε. 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 Txi) and e−w Txi/(1 + e−w
Txi) for category 1 and −1. Then max{1/(1 + e−w Txi), e−w Txi/(1 + e−w Txi)} is the confidence of w on data xi.
The confidence measures how confident the classifier is about the prediction. In the sequel, we use xi to represent yixi 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, limu→∞ `(u) = limu→∞ ` ′(u) = 0, and the `(u) has Lipschitz gradient.3 Assumption 2. The l(·) and l′(·) have exponential tail, which means there exists some constant u0 and C1, C2 satisfies that ∀u > u0, C1e−u ≤ l(u) ≤ C2e−u as well as l′(u).4
Assumption 3. ThewTxi−ε‖w‖ has the range of [c1,∞) for eachxi, where c1 > −∞. ‖w‖ ≥ c2 for some constant c2.5.
Due to the properties of loss function, the adversarial training objective (3) with radius ε has an explicit formula
L(w) = 1 N N∑ i=1 ` ( wTxi − ε‖w‖ ) . (4)
The adversarial training objective equation 4 is optimized by the gradient descent, i.e.,
wt+1 = wt − η∇L(wt) = wt − η N∑ i=1 `′ ( wTt xi − ε‖wt‖ )( xi − ε wt ‖wt‖ ) , (5)
where η is the learning rate.

heading: 3 ADVERSARIAL TRAINING CONVERGES FASTER TO HARD MARGIN FOR
text: ε-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 {wt} returned by GD under adversarial training satisfy 1): limt→∞ L(wt) = 0, 2): limt→∞ ‖wt‖ = ∞. and 3): limt→∞w T t xi − ε‖wt‖ =∞
The distance of xi away from linear classifier wt is |wTt xi|/‖wt‖. 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) ,
dw(t)
dt = −∇L(w(t)) (6)
satisfies w(t) = ŵ ·O (log t) + h(t), (7)
2The 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.
3It means that |`′(u)− `′(v)| ≤ L|u− v| for some positive constant L. 4Lots of loss functions we used such as log (1 + e−u), e−u are satisfied with this assumption. 5This assumption can be attained by re-scale the norm of w if necessary.
for a large t. Here ŵ is the hard margin solution of SVM:
ŵ = arg min w∈Rd
‖w‖ s.t.wTxi ≥ 1. (8)
‖h(t)‖ is in the order of o(log t). Then
lim t→∞ ∥∥∥∥ w(t)‖w(t)‖ − ŵ‖ŵ‖ ∥∥∥∥ ≤ O((log t)−(1+ε∗)), (9)
where ε∗ = |S|ε(ε1−ε)N , {εi} is the sorted distance of data away from the hard margin solution of SVM, and S = {i : ŵTxi = ε1‖ŵ‖}; |S| is the number of elements in set S. Finally, iterates {wt} of adversarial training updated by GD with step size η satisfies
‖wk −w(kη)‖ ≤ O(η), (10) for k ∈ N+. Then we can conclude
lim t→∞ ∥∥∥∥ wt‖wt‖ − ŵ‖ŵ‖ ∥∥∥∥ ≤ limt→∞ ∥∥∥∥ w(tη)‖w(tη)‖ − ŵ‖ŵ‖ ∥∥∥∥+O(η). (11)
We give a brief discussion to hard margin solution of SVM. Since the dataset is ε-strongly linearly separable, by KKT condition, we have ε < 1/‖ŵ‖ which informs us all the distance between xi and ŵ are larger than ε. Then, we present that perturbations smaller than ε can be defended by ŵ. Hence, the linear classifier wt becomes robust for a large t, since it has the same direction with ŵ. We then conclude adversarial training on ε-strongly linearly separable data helps iterates {wt} 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.

heading: 4.1 THE INFLUENCE OF OUTLIERS
text: 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.

heading: 4.1.1 STANDARD TRAINING IS UNSTABLE TO OUTLIERS
text: 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 {x1i } N1 i=1 and {x2i } N2 i=1, let ŵ1 and ŵ2 be their hard margin classifier respectively. Then, the hard margin classifier ŵ of union dataset {x1i } N1 i=1 ⋃ {x2i } N2 i=1 satisfies ‖ŵ‖ ≥ max{‖ŵ1‖, ‖ŵ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 ‖ŵ‖ ≥ max{‖ŵ1‖, ‖ŵ2‖} and one of wi 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 {( x1i , 0 )}N1 i=1
is well linearly separable with large margin, which means the hard margin classifier ŵ1 has a small norm. We insert some outliers which have the form{(
0,x2i , )}N2 i=1
and N1 N2. If the outlier is linearly separable with relatively small margin, the corresponding hard margin solution is ŵ2, then we have ‖ŵ1‖ ‖ŵ2‖.
We can show that hard margin classifier on the union dataset {( x1i , 0 )}N1 i=1 ⋃{( 0,x2i )}N2 i=1
is (ŵ1, ŵ2). Then for each ( x1i , 0 ) , we have∣∣∣(ŵ1, ŵ2)T (x1i , 0)∣∣∣
‖ (ŵ1, ŵ2) ‖ = ∣∣ŵT1 x1i ∣∣√ ‖ŵ1‖2 + ‖ŵ2‖2 ≤ ∣∣ŵT1 x1i ∣∣ ‖ŵ2‖
∣∣ŵT1 x1i ∣∣ ‖ŵ1‖ . (12)
This shows the distance between each {( x1i , 0 )}N1 i=1 and new hard margin classifier (ŵ1, ŵ2) be-
come extremely small due to a few outliers {( 0,x2i )}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 {x1i } N1 i=1 and {x2i } N2 i=1 with N1, N2 data respectively, where N1 N2. {x1i } N1 i=1 themselves are ε-strongly linearly separable , but {x2i } N2 i=1 are not. Then, dataset {x2i } 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 {(x11i ,x12i )} N1 i=1 ∈ Rd1+d2 is ε-strongly linearly separable but {(0,x22i )} N2 i=1 ∈ Rd1+d2 is not linearly separable. Let S = span{x121 , · · · ,x12N1} = span{x221 , · · · ,x22N2}. Without loss of generality, we assume {x 11 i } N1 i=1 themselves are linearly separable but the hard margin classifier of them ŵ11 has relatively small margin compared to the {x12i } N1 i=1, i.e., ‖ŵ11‖ ‖ŵ12‖, where ŵ12 is the hard margin classifier on {x12i } N1 i=1 6.
The union datasets {(x11i ,x12i )} N1 i=1 ⋃ {(0,x22i )} N2 i=1 is not linearly separable because of the outliers set {(0,x22i )} 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 {x11i } N1 i=1 (Ilyas et al., 2019).
The reason is as follows. The outliers {(0,x22i )} N2 i=1 happens to be the ”Strongly Convex Part” as in Theorem 4.1 of Ji & Telgarsky (2018), then the iterates {wt} updated by gradient descent of standard training converge to a direction of the hard margin classifier ŵ11 of dataset {ΠS⊥(x11i ,x12i )} N1 i=1 = {(x11i , 0)} N1 i=1, where ΠS⊥(·) is the projection operator of space S⊥. Then, the presence of outliers {(0,x22i )} N2 i=1 renders the classifier returned by standard training on union datasets with poor robustness while the true hard margin classifier on dataset {(x11i ,x12i )} 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,x22i )} N2 i=1 into correct category renders the classifier (ŵ1, ŵ2) to be non-robust. The second describes that the outliers mute the information from {(0,x12i )} N1 i=1 for dataset {(x11i ,x12i )} N1 i=1. Then, the classifier turns into a non-robust but useful classifiers.
6The hard margin classifier of {(x11i ,x12i )}N1i=1 ŵ1 satisfies ‖ŵ1‖ ≤ min{‖ŵ11‖, ‖ŵ12‖} which leads to a even more robust solution.

heading: 4.1.2 ADVERSARIAL TRAINING IS STABLE TO OUTLIERS
text: Now, we turn to the behavior of adversarial training on the above two examples. Lemma 1 shows that the iterates {wt} of adversarial training on ε-strongly linearly separable data updated by GD can satisfy limt→∞ ‖wt‖ = ∞. But the non-ε-strongly linearly separability of data ensures there exists some xki such that w T t x k i − ε‖wt‖ ≤ 0 for each specific t. Hence, ‖wt‖ 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∗Txki − ε‖w∗‖ ) = pki , we have
∇L(w∗) = 1 N1 +N2 2∑ k=1 Nk∑ i=1 pki ( xki − ε w∗ ‖w∗‖ ) = 0. (13)
It gives
ε w∗
‖w∗‖ 2∑ k=1 Nk∑ i=1 pki = 2∑ k=1 Nk∑ i=1 pki x k i = 2∑ k=1 Xkpk, (14)
where Xk = (xk1 , · · · ,xkNk) and pk = (p k 1 , · · · pkNk). This implies that the direction of vector w
∗
is decided by a linear combination of data points. Xkpk represents the contribution brought by {xki } Nk i=1.
When data are ε-strongly linearly separable, by Assumption 2, we see pki /p k′
j = o(1) (‖wt‖ goes to infinity) for any support vector xki 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 ŵ satisfies (KKT condition) ŵ = ∑2 k=1 ∑Nk 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 ‖wt‖ can not go to infinity, we have the relation pki /p k′ j = O(1). Then the following inequality
λ 1 2 min ( XT2 X2 ) ‖p2‖ λ 1 2 max (X T 1 X1) ‖p1‖ ≤ ‖X2p2‖‖X1p1‖ ≤ λ 1 2 max ( XT2 X2 ) ‖p2‖ λ 1 2 min (X T 1 X1) ‖p1‖ , (15)
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 {x1i } N1 i=1 and {x2i } N2 i=1. Since p 1 i has the same scale with p 2 j for every i, j and N1 N2, we see ‖p1‖ ‖p2‖, then ‖X1p1‖ ‖X2p2‖. Hence, equation 15 implies that X2p2 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 {x1i } 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 ŵ1, ŵ2 for {x1i } N1 i=1 and {x2i } 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 thatw∗ 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 N1 N2. If N1 ≈ N2, we see adversarial training can preserve a part of information from robust features. Moreover, N2 N1 means that most features are non-robust, and then adversarial training is also helpless.

heading: 4.2 CONFIDENCE OF ADVERSARIAL TRAINING
text: 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, ‖wt‖ converges to some constant when data is not ε-strongly linearly separable. According to Definition 2, the confidence of classifier is decided by |wTt xi| on each xi. Then, a bounded ‖wt‖ corresponds to a relatively low confidence in each xi.
To give a formal description to the confidence of wt, we discuss an extremely large ε ≥ 1 2 maxi,j ‖xi − xj‖, which means each ε-ball centered at xi has overlap with each other. For a xi, larger |w∗Txi| corresponds with higher prediction confidence. For a given dataset {xi}Ni=1, let N1, N2 respectively be the number of data in each category and xk,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∗Txk,i| is either smaller than ε‖w∗‖ or satisfies
e(|w ∗Txk,i|−ε‖w∗‖) ≤ 1
Nk′ Nk′∑ j=1 max x:‖x−xk′,j‖≤ε e(−w ∗Tx+ε‖w∗‖), if w∗Txk,i ≥ ε‖w∗‖,
e(|w ∗Txk,i|) ≤ 1
Nk′ Nk′∑ j=1 e(−w ∗Txk′,j−ε‖w ∗‖), if w∗Txk,i ≤ −ε‖w∗‖,w∗Txk′,j ≥ 0,
(16)
for k′ 6= k.
Our results also applies to l(·) discussed in this paper. A more explicit upper bound for those w∗Txk,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∗Txi| on each xi can not be extremely large. Hence, a relatively low confidence in each xi. A detailed proof of this Theorem is delegated to Appendix D. Here we use ε ≥ 12 maxi,j ‖xi − xj‖ 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).

heading: 5 EMPIRICALLY STUDY
text: 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 {xi}Ni=1 ∼ N (yi · 2 · 12, 0.3 · I2) and support vectors on the 1T2 xi = yi · 2. If there exists at least one support vector in each category, the hard margin solution of SVM ŵ is 12. 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 ε.
We conduct adversarial training with different ε and standard training on three datasets: number of support vectors and non-support vectors in each category are respectively (5000, 0); (2500, 2500) and (1, 4999) (see Figure 1). The results can be referred to Figure 2. Some extra experiments are delegated to Appendix E. We should highlight the direction of {wt} here can converge with rate of O((log 0.01 · t)−1) and O((log 0.01 · t)−(1+ε∗)), respectively for standard training and adversarial training due to equation 11.
The ”margin gap” in Figure 2 means distance between the direction of iterates wt/‖wt‖ and hard margin solution of SVM 12/ √ 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 wt/‖wt‖. 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 {(x1i , 02)}10000i=1 ∼ (N (yi · 2 · 12, 0.3 · I2), 02) and {(02,x2i )}100i=1 ∼ (02,N (yi · 0.5 · 12, 0.1 · I2)). The number of the two datasets in each category are 5000 and 50. The dataset {(02,x2i )}100i=1 is linearly separable while non-ε-strongly linearly separable for ε = 1.5. {(x1i , 02)}10000i=1 is ε-strongly linearly separable for ε = 1.5. {(02,x2i )}100i=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.
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 (‖w1‖/‖w‖, where w ∈ R4 = (w1,w2) ∈ R2+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 {(x1i , 02)}10000i=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 {(02,x2i )}100i=1. Then, we present the results on non-linearly separable data with respect to Example 2, we generate 5000 {(x11i ,x12i )}10000i=1 ∼ (N (yi · 0.5 · 12, 0.1 · I2),N (yi · 2 · 12, 0.3 · I2)) and 50 {(02,x2i )}100i=1 ∼ (02,N (−yi · 0.5 · 12, 0.5 · I2)) in each category. Here {(02,x2i )}100i=1 is the source of non-linearly separability. {x12i }10000i=1 corresponds with a robust hard margin classifier while {x11i }10000i=1 is not. {(02,x2i )}100i=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 {(02,x2i )}100i=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 (‖w1‖/‖w‖ and ‖w2‖/‖w‖, where w ∈ R4 = (w1,w2) ∈ R2+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 {(02,x2i )}100i=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 maxi,j ‖xi − xj‖. We generate 5000 samples {xi} 10000 i=1 ∼ N (±0.5 · 12, 0.1 · I2) in each category. The data are linearly separable but non-ε-strongly linearly separable for ε = 1, besides that, 1 ≥ 12 maxi,j ‖xi − xj‖. 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.

heading: 6 CONCLUSION
text: 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 ε ≥ 12 maxi,j ‖xi − xj‖, 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.

heading: A PROOF OF LEMMA 1
text: Proof. We first give convexity to the adversarial training objective. For any two w1,w2, and 0 ≤ λ ≤ 1, by the convexity and monotone decreasing property of `(·), we have
1
N N∑ i=1 ` ( λwT1 xi + (1− λ)wT2 xi − ε‖λw1 + (1− λ)w2‖ ) ≤ 1 N N∑ i=1 ` ( λwT1 xi + (1− λ)wT2 xi − ελ‖w1‖ − (1− λ)‖w2‖
) ≤ 1 N N∑ i=1 λ` ( wT1 xi − ε‖w1‖ ) + (1− λ)` ( wT2 xi − ε‖w2‖ ) ,
(17)
which implies the convexity of adversarial training objective. On the other hand, if uT∇2L(w)u can be bounded by L‖u‖2 for some L, then L(w) is L-smooth. We see that
∇2L(w) = 1 N N∑ i=1 `′′(wTxi − ε‖w‖) ( xi − ε w ‖w‖ )( xi − ε w ‖w‖ )T − ε‖w‖3 ` ′(wTxi − ε‖w‖)(‖w‖2I−wwT ). (18)
Then, uT∇2L(w)u can be divided into two parts, we respectively compute them∣∣∣∣∣ 1N N∑ i=1 l′′(wTxi − ε‖w‖) ( (uTxi) 2 − 2 ε‖w‖u Txiw Tu+ ε2 ‖w‖2 (u Tw)2 )∣∣∣∣∣ ≤ L0 N ‖u‖2 ( λmax ( XTX ) + 2ε N∑ i=1 ‖xi‖+ 2ε2 ) .
(19)
Here X is matrix (xT1 , · · · ,xTN )T and λmax ( XTX ) is the largest eigenvalue of XTX. On the other hand, according to Assumption 3,
uT ε ‖w‖3 ` ′(wTxi − ε‖w‖)(‖w‖2I−wwT )u ≤ 2ε C1 c2 ‖u‖2. (20)
Combining the two above equations, we conclude that largest eigenvalue of∇2L(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 η = 1L will ensure the iterates {xt} satisfies f(xt)− f(x∗) ≤ O ( 1 t ) . Since the adversarial training loss goes to zero only if wTt xi − ε‖wt‖ goes to infinity for each xi. It reveals our two conclusions limt→∞ ‖wt‖ =∞ and limt→∞wTt xi − ε‖wt‖ =∞.

heading: B ORDER OF NORM
text: 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)‖ − ŵ‖ŵ‖∥∥∥. Our proof is based on the gradient flow, we first bound the difference between flow iterates w(t) and wt.
Lemma 2. Let wt be the iterates updated by GD equation 5, then for dw(t)dt = −∇L(w(t)), we have
‖w(kη)−wk‖ ≤ O(η). (21)
Proof. Let w̄(kη) = w((k − 1)η)− η∇L(w((k − 1)η)). (22)
Then by Lipschitz gradient of L(·), we see
‖w(kη)− w̄(kη)‖ = ∥∥∥∥∥ ∫ kη (k−1)η ∇L(w(u))−∇L(w((k − 1)η))du ∥∥∥∥∥ ≤ ∫ kη (k−1)η L ‖w(u)−w((k − 1)η)‖ du
= ∫ kη (k−1)η L ∥∥∥∥∥ ∫ u (k−1)η ∇L(w(s))ds ∥∥∥∥∥ du = O(η2).
(23)
Then we have
‖w(kη)−wk‖ ≤ ‖wk − w̄(kη)‖+ ‖w(kη)− w̄(kη)‖ ≤ ‖w((k − 1)η)−wk−1‖+ η ‖∇L(w((k − 1)η))−∇L(wk−1)‖+O(η2) ≤ (1 + ηL) ‖w((k − 1)η)−wk−1‖+O(η2)
≤ · · · ≤ (1 + ηL)k ‖w(0)−w0‖+O(η) = O(η),
(24)
for w(0) = w0, which results in the conclusion.
Before proving the Theorem 1, we give a lemma to illustrate thatw(t) will converge to the direction of ŵ.
Lemma 3. There exists a t0, for t > t0, we have
w(t) = ρ(t)ŵ + h(t), (25)
for some ρ(t) and h(t). Here ρ(t) goes to infinity and ‖h(t)‖ is in the order of o(ρ(t)).
Proof. Let
r(t) = w(t)− ‖w(t)‖‖ŵ‖ ŵ, (26)
‖r(t)‖ = o (‖w(t)‖) will implies the conclusion. Since `′(·) has exponential tail Assumption 2, there exists a t0, for t > t0, we have
d dt ‖r(t)‖ = ṙ
T (t)r(t)
‖r(t)‖ = − 1 ‖r(t)‖
( 1− w(t) T ŵ
‖w(t)‖‖ŵ‖
) ∇L(w(t))Tr(t)
≤ C N‖r(t)‖ (1− cos(w(t), ŵ)) N∑ i=1 exp ( −w(t)Txi + ε‖w(t)‖ )( xi − ε w(t) ‖w(t)‖ )T r(t).
(27) Then, we see N∑ i=1 exp ( −w(t)Txi + ε‖w(t)‖ )( xi − ε w(t) ‖w(t)‖ )T r(t)
= N∑ i=1 exp ( −r(t)Txi − ‖w(t)‖ŵTxi ‖ŵ‖ + ε‖w(t)‖ )( xi − ε w(t) ‖w(t)‖ )T r(t) ≤ N∑ i=1 exp ( −‖w(t)‖ŵ Txi ‖ŵ‖ + ε‖w(t)‖ ) − ε exp ( −r(t)Txi − ‖w(t)‖ŵTxi ‖ŵ‖ + ε‖w(t)‖ ) w(t)T ‖w(t)‖r(t)
≤ N exp (−(ε1 − ε)‖w(t)‖) , (28)
where ŵ is the hard margin classifier and ε is the distance between support vectors and ŵ. Here we use the relationship that ze−z ≤ 1 for any z and w(t)Tr(t) ≥ 0. Since
(1− cos(w(t), ŵ)) = − r(t) T ŵ
‖w(t)‖‖ŵ‖ , (29)
and r(t)T ŵ ≤ 0, we have
d dt ‖r(t)‖ ≤ −CN r(t)
T ŵ
‖r(t)‖‖w(t)‖‖ŵ‖ 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
C1 exp ( −w(t)Txi + ε‖w(t)‖ ) ≤ ` ( w(t)Txi − ε‖w(t)‖ ) ≤ N‖ŵ −w0‖
2t , (31)
for some constant C1 and any xi. Then we see
log 2C1
N‖ŵ −w0‖ + log t ≤ w(t)Txi − ε‖w(t)‖. (32)
On the other hand, by the definition of hard margin classifier and Lemma 1, there exists xi such that w(t)Txi ≤ ε1‖w(t)‖. Combining this and equation 32, we have
1
ε1 − ε
( log
C1 N‖ŵ −w0‖ + log t
) ≤ ‖w(t)‖. (33)
Plugging this into equation 30, and we see that there exists a t1 such that 12 log t ≥ log N‖ŵ−w0‖ C1 , then
‖r(t)‖ ≤ ‖r(t0 ∧ t1)‖+ (ε1 − ε)N2‖ŵ −w0‖
CC1
∫ t t0∧t1 1 t log t dt = O(log log t), (34)
for t ≥ t0 ∧ t1. 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 {xi} N i=1 to hard margin solution of SVM ŵ.
Proof. From Lemma 3 and 3, we have
w(t) = ρ(t) ŵ
‖ŵ‖ + h(t), (35)
where ρ(t)→∞ and ‖h(t)‖ = o(ρ(t)). Specifically, the h(t) can be chosen to be orthogonal with ŵ, otherwise we can use a decomposition in a direct sum. For ‖w(t)‖, we have
‖w(t)‖ = √ ρ(t)2 + ‖h(t)‖2
= √ ρ(t)2 + ‖h(t)‖2 − ρ(t) + ρ(t)
=
(√ ρ(t)2 + ‖h(t)‖2 + ρ(t) )(√ ρ(t)2 + ‖h(t)‖2 − ρ(t) ) √ ρ(t)2 + ‖h(t)‖2 + ρ(t) + ρ(t)
= ‖h(t)‖2 ρ(t) + √ ρ(t)2 + ‖h(t)‖2 + ρ(t).
(36)
On the other hand, for t large enough,
d dt ‖w(t)‖ = −∇L(w(t))T w(t)‖w(t)‖
≤ C1 N N∑ i=1 exp ( −w(t)Txi + ε‖w(t)‖ )( xi − ε w(t) ‖w(t)‖ )T w(t) ‖w(t)‖
= C1 N N∑ i=1 exp
( −ρ(t) ŵ
Txi ‖ŵ‖ + h(t) Txi + ερ(t) + ε ‖h(t)‖2 ρ(t) + √ ρ(t)2 + ‖h(t)‖2
)( ŵTxi − ε‖ŵ‖
‖ŵ‖
)
≤ C2 N N∑ i=1 exp (−(εi − ε)ρ(t)) (εi − ε).
(37)
for some constant C1, C2. 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 ddt‖w(t)‖. In summary, we have
C3 N exp (−(ε1 − ε)ρ(t)) (ε1 − ε) ≤ ρ′(t) ≤ C2 exp (−(ε1 − ε)ρ(t)) (εN − ε) (38)
for constant some C3. Hence we can conclude that
log t
ε1 − ε + C5 ≤ ρ(t) ≤
log t
ε1 − ε + C4, (39)
for some constant C4, C5. It results in ρ(t) = O(log t).
We have proven that w(t) will converge to the direction of ŵ. Now, we will show w(t) will have the same support vector with ŵ when t is large. It’s a key fact of proving Theorem 1. Lemma 5. There exists t0 such that w(t) will have the same support vectors with ŵ for t > t0.
Proof. Let S = {i : ŵTxi = ε1‖ŵ‖}, for i ∈ S, j /∈ S, we have
w(t)T ‖w(t)‖ (xi − xj) =
( ρ(t) ŵ‖ŵ‖ + h(t) )T ‖w(t)‖ (xi − xj)
≤ 1‖w(t)‖
( ρ(t) ŵT ‖ŵ‖ (xi − xj) + ‖h(t)‖‖xi − xj‖ ) (40)
Since xi is the support vector of ŵ, ŵ T
‖ŵ‖ (xi − xj) > 0. Then, ‖h(t)‖ = o(ρ(t)) shows that w(t)T ‖w(t)‖ (xi − xj) ≤ 0 for a large t. Then we get the conclusion.

heading: C PROOF OF THEOREM 1
text: 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) ,
dw(t)
dt = −∇L(w(t)) (41)
satisfies w(t) = ŵ ·O (log t) + h(t), (42)
for a large t. Here ŵ is the hard margin solution of SVM:
ŵ = arg min w∈Rd
‖w‖ s.t.wTxi ≥ 1. (43)
‖h(t)‖ is in the order of o(log t). Then
lim t→∞ ∥∥∥∥ w(t)‖w(t)‖ − ŵ‖ŵ‖ ∥∥∥∥ ≤ O((log t)−(1+ε∗)), (44)
where ε∗ = |S|ε(ε1−ε)N , {εi} is the sorted distance of data away from the hard margin solution of SVM, and S = {i : ŵTxi = ε1‖ŵ‖}; |S| is the number of elements in set S. Finally, iterates {wt} of adversarial training updated by GD with step size η will satisfy
‖wk −w(kη)‖ ≤ O(η), (45)
for k ∈ N+. Then we can conclude
lim t→∞ ∥∥∥∥ wt‖wt‖ − ŵ‖ŵ‖ ∥∥∥∥ ≤ limt→∞ ∥∥∥∥ w(tη)‖w(tη)‖ − ŵ‖ŵ‖ ∥∥∥∥+O(η). (46)
Proof. Let w(t) = ρ(t) ŵ‖ŵ‖ + h(t). Denoting the support vectors set by S, S = {i : ŵ Txi = ε1‖ŵ‖}. By the exponential tail of `′(u) (Assumption 2), there exists a t0, for t > t0, we have
1
2
d dt ‖h(t)‖2
= − ( ∇L(w(t)) + ρ′(t) ŵ‖ŵ‖ )T h(t) = −∇L(w(t))Th(t)
≤ C N (∑ i∈S + ∑ i/∈S ) exp (−w(t)xi + ε‖w(t)‖) ( xi − ε w(t) ‖w(t)‖ )T h(t)
= C
N (∑ i∈S + ∑ i/∈S ) exp ( −ρ(t) ŵ Txi ‖ŵ‖ − h(t) Txi + ερ(t) + ‖h(t)‖2 ρ(t) + √ ρ(t)2 + ‖h(t)‖2 )( xi − ε w(t) ‖w(t)‖ )T h(t)
≤ C N ∑ i∈S exp ( −ρ(t) ŵ Txi ‖ŵ‖ − h(t) Txi + ερ(t) )( xi − ε w(t) ‖w(t)‖ )T h(t)
≤ − ε N ∑ i∈S exp (−‖h(t)‖‖xi‖ − (εi − ε)ρ(t)) ‖h(t)‖2 ρ(t) ,
(47) 7Here we use a fact that xTi h(t) ≤ 0 for i ∈ S, due to ŵ is the hard margin classifier. In addition,
1 + ‖h(t)‖2 ρ(t) + √ ρ(t)2 + ‖h(t)‖2 ≤ exp
( ‖h(t)‖2
ρ(t) + √ ρ(t)2 + ‖h(t)‖2
) . (48)
With this, we can choose a t0 such that
∑ i∈S exp ( −ρ(t) ŵ Txi ‖ŵ‖ − h(t) Txi + ερ(t) )( xi − ε w(t) ‖w(t)‖ )T h(t)
‖h(t)‖2 ρ(t) + √ ρ(t)2 + ‖h(t)‖2
+ ∑ i/∈S exp (−w(t)xi + ε‖w(t)‖) ( xi − ε w(t) ‖w(t)‖ )T h(t) ≤ 0,
(49)
for t > t0. This concludes the equation equation 47. Let ‖h(t)‖‖xi‖ 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
‖h(t)‖2 ≤ ‖h(t0)‖2 exp (∫ t t0 −εe −C(u) Nρ(u) ∑ i∈S exp (−(εi − ε)ρ(u)) du ) , (50)
C(t) can be arbitrary small when t > t0. Plugging this into equation 50, and combining Lemma 4, we have
‖h(t)‖2 ≤ ‖h(t0)‖2 exp (∫ t t0 −ε(ε1 − ε) N log u ∑ i∈S u − ( εi−ε ε1−ε ) du )
= ‖h(t0)‖2 exp ( − ∑ i∈S ε(ε1 − ε) N ∫ t t0 1 u log u du )
= ‖h(t0)‖2 exp ( −|S|ε(ε1 − ε)
N log log t ) = O(log t)−ε ∗ ,
(51)
where ε∗ = |S|ε(ε1−ε)N . Since we have
w(t) ‖w(t)‖ = ρ(t)
ρ(t) + ‖h(t)‖ 2
ρ(t)
ŵ ‖ŵ‖ + h(t)
ρ(t) + ‖h(t)‖ 2
ρ(t)
, (52)
7Here we hide the constant C in the last inequality, which is decided by loss function l(·). C will usually smaller than 1 in fact.
then we see ∥∥∥∥ w(t)‖w(t)‖ − ŵ‖ŵ‖ ∥∥∥∥ ≤ 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.

heading: D PROOF OF THEOREM 2
text: Proof. The xk,i will either satisfies |w∗Txk,i| ≤ ε‖w∗‖ nor |w∗Txk,i| ≥ ε‖w∗‖. We know the first inequality represents the distance between xk,i and w∗ is smaller than ε. Then for w∗Txk,i ≥ ε‖w∗‖, due to ε ≥ 12 maxi,j ‖xk,i − xk′,j‖ for any i, j, there exists x ′ k′,j ∈
B2(xk′,j , ε) ⋂ B2(xk,i, ε) with k′, k = 1, 2 and k′ 6= k. By triangle inequality, the distance between x′k′,j andw ∗ is smaller than w ∗Txk,i ‖w∗‖ − ε. Since xk′,j locates in different category with xk,i, by the monotone decreasing property of `(·), we have
`(−w∗Txk,i + ε‖w∗‖) ≤ `(x′k′j) ≤ max ‖x−xk′,j‖≤ε `(w∗Tx). (54)
Hence we have
`(−w∗Txk,i + ε‖w∗‖) ≤ 1
Nk′ Nk′∑ j=1 max ‖x−xk′,j‖≤ε `(w∗Tx− ε‖w∗‖). (55)
Then, we have N2` ( −|w∗Tx1,i|+ ε‖w∗‖ ) +N1` ( −|w∗Tx2,i|+ ε‖w∗‖ ) ≤ (N1 +N2)`(0), (56)
if w∗ can correctly predict a point far from margin larger than ε in each category, for those w∗Txk,i ≥ ε‖w∗‖ due to w∗ is minimum, then L(w∗) ≤ L(0). On the other hand, for w∗Txk,i ≤ −ε‖w∗‖, we can immediately derive
`(w∗Txk,i) ≤ `(−w∗Txk′,j − ε‖w∗‖), (57)
by triangle inequality where w∗Txk′,j ≥ 0. Then we get the conclusion.

heading: E EXTRA EXPERIMENTS
text: E.1 ADVERSARIAL TRAINING IN lp SPACE
Our conclusions are obtained for adversarial training in l2 space while it can be conducted in a more general lp space (Goodfellow et al., 2014; Madry et al., 2018). It is meaningful to verify whether these conclusions are still hold in lp space. Hence, we extend our experiments to lp space.
The adversarial training objective within linear classifier can be formulated as
L(w) = 1 N N∑ i=1 max ‖x−xi‖p≤ε `(wTx), (58)
in lp space, where ‖ · ‖p is lp norm. It has an explicit formulation
L(w) = 1 N N∑ i=1 ` ( wTxi − ε‖w‖q ) , (59)
where 1p + 1 q = 1. We conduct experiments for p = 4 and p =∞.
We empirically verify that adversarial training in lp 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 lp 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 1Td x = ±d and hard margin classifier 1d in lp space is d‖1d‖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‖1d‖q = d 1 p . Then for p = 4, p = ∞ and d = 2, we have 2 1 4 ≈ 1.18, 20 = 1. From the results, we see that an appropriate adversarial radius (ε = ε1/2) and more support vectors are helpful for adversarial training even in lp 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 lp 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 lp space by following the methods in this paper. The inner product 〈·, ·〉 of linear classifier is derived from ‖ · ‖2 while l2 is a Hilbert space, but lp space is not. The inner product we used does not math the lp space. Hence, we need adding some extra bounded conditions to extend our conclusions to lp space.
E.2 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. (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 l2 and l∞ space.
Since we can not compute the exact distance between data and classifier, we use the loss on training data 8 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 maxx:‖x−xi‖≤ε `(x,θ) for each xi.
8Here we only focus on training data because we do not discuss the generalization of model obtained by adversarial training.
The steps of PGD is 10 for each xi. 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 l2 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 set 9 to verify the robustness of trained model are 1.0 and 8/255 respectively in l2 space and l∞ space. The experimental results in l2 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 l2 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 {xi}100i=1 ∼ N (±0.078125 · 132×32×3, 0.045 · I32×32×3) in each category in both l2 and l∞ space. The influence of outliers for adversarial training in l2 and l∞ space can be respectively referred to Figure 9a and 10a. ”Adv with outliers: 0.25 varepsilon”
9We should highlight that the perturbations are recalculated after each epoch of training. 10We 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).
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 l2 and l∞ space to verify the confidence of classifier returned by adversarial training. The distributions of confidence via adversarial training in l2 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.

Review summaries:
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).

This paper provides some analyses of the difference between adversarial training and standard training for linear classification problem. In particular, it proves that when the data is \eps linearly separable, adversarial training converges faster than standard trading. It also argues that when the data is not \eps linearly separable, adversarial training is more robust to outlier. Simulations are constructed to verify the arguments in the paper but there is no experiments on real dataset.